Mmmm... close.

Three weeks to graduation (well, two plus finals). Still looking for a job. Seems like no one's hiring right now, not a great time to be graduating. Oh well; I'll find something I'm sure, even if it's repair work for a while.

Time is money... if I had time, I'd have money.

Three months since my last post... school's been busy. 5 weeks of classes left (plus one on break), exams, then graduation. Hopefully I'll have found a job by then, but the trail's gone cold. Haven't lost hope, reserving that for December 8th-ish.

Been working on creating my own linux distribution off and on, it's a hassle but a good learning experience. Once I finish I might make a guide. Ever tried to compile gcc in full? Takes f-o-r-e-v-e-r. Thank FSM for package managers.

Looking for a secure way to sync all my bookmarks between machines. Yeah, random thought. Anyway. Not sure if I want to trust del.icio.us, foxmarks, etc. with all of my bookmarks, I'd rather have something less public. I'll figure something out... that, or I'll forget about it for a while. Not that important.

Met Kanwal Rekhi the other day. He's had an eventful life, and during the conversations I came to full realization of who integral he was in the development of technology. Wikipedia doesn't do him justice. Was a pretty amazing experience.

Class in the morning. Bedtime. I'll try to update more often (not that anyone'll notice, I'm sure!)

Algorithm Wiki

Been pretty distracted lately with job searching, but the other day I had the random desire to start up an algorithm wiki. I'd like to have it be a compilation of actual implementations, as opposed to just pseudocode as is on Wikipedia.

http://algowiki.net/

If anyone would like to contribute, please do so.

Java Code Optimization

Update: I now have a greater understanding of this topic, and I may make another post on it sometime to make up for this poorly-informed post. The general point is that knowing how adaptive JIT compilation works can be beneficial. Put code that you know will run many times in its own method and it will be optimized better (depending, of course, on your JIT compiler).

Just another quick word today, this one about writing efficient Java code. I'm sure this is somewhat well-known to some, but I've never actually seen it written anywhere (much less explained in a programming course). However, before I say anything, know that you should always test to make sure it actually yields you better results. Depending on your compiler and JVM, you may or may not see improvement. It also largely depends on your code.

Note that this doesn't just affect Java, it has an effect on many/all JIT (Just In Time) compilers.

Take this bit of code:

    public void func1(){               
        int sum1 = 0;                  // cold
        double sqrtsum1 = 0;           // cold
        for(int i=0; i<10000; i++){    // hot
            sum += i;                  // hot
            sqrtsum += Math.sqrt(i);   // hot
            for(int j=0; j<10000; j++){// very hot
                int sumplusj = j+i;    // very hot
            }                          // very hot
        }                              // hot
    }                                  // cold

Cold means the code is executed very infrequently, while hot code is executed often. Assuming this "func1()" is called very few times, the method as a whole is cold.

The thing to notice is the hot/very hot section in the cold method. Most modern JIT compilers compile/optimize on the method level: if a method is determined to be hot (after it is executed numerous times), it is compiled and optimized. Before that, it's just interpreted, which is much slower.

The issue is having hot code in cold methods. Since the method is cold, it isn't compiled to native and optimized very quickly (if at all). Note that, depending on your specific application and setup, the hot code may not be either - in which case this won't help you.

So what can one do to remedy the situation? Extract hot code into separate methods.

    int sum1 = 0;                      // cold
    double sqrtsum1 = 0;               // cold

    public void func1(){               // cold
        for(int i=0; i<10000; i++){    // cold
            func2(i);                  // hot
        }                              // cold
    }                                  // cold

    public void func2(int i){          // hot
            sum += i;                  // hot
            sqrtsum += Math.sqrt(i);   // hot
            for(int j=0; j<10000; j++){// very hot
                int sumplusj = j+i;    // very hot
            }                          // very hot
    }

Normally one may say "but isn't there a method call overhead that makes it slower?" - if this were C or C++, perhaps. Yes, there is an overhead, but extracting the hot code out of the cold method overcomes that by a large margin.

As for the "very hot" code in the second method, it is debatable as to when to extract that as well. It is my own heuristic that the more operations in the hot section, the more the benefit. With just that one statement, there may not be much benefit (testing would be required to know for sure).

In general though, keep cold code in cold methods and hot code in hot methods. Cursory tests similar to (though more intensive) the above show a performance increase of 200%, but it's largely going to depend on your JIT compiler.

As JIT compilation evolves, this will most likely become less of an issue - I expect that it will rely less on method boundaries in the future. For now though, keep those methods hot.

Changing Things Up

Too much lately I've been working on semi-useless native code, so I think I'll play around with Android for a while.

http://code.google.com/android/
http://code.google.com/android/reference/packages.html

I can't wait to get a phone that runs Android, though I'm sure it'll be a while. Just gives me time to play around with its SDK, right? Right.

XGetWindowAttributes and You

Right at the end of a project I've been working on, I run into a very weird issue. As per the title of this post, it's with XGetWindowAttributes and the XWindowAttributes struct.

Reference page:
XGetWindowAttributes

The main reason I'm looking to use this function is for XWindowAttributes.class, which will tell me if the window I have is InputOutput (visible) or InputOnly (not visible). If there's a simpler way to detect a window's visibility, I couldn't find it.

Anyway, in my coding I have this:

    XWindowAttributes attr;
    XGetWindowAttributes(display, hwnd, &attr);
    if(attr.class == InputOutput){
        [...]
    }else{
        [...]
    }

Looks fine, yes? Well, it won't compile.

error: expected unqualified-id before class
error: expected `)' before class

Some research on the error turns up next to nothing; just a bunch of people saying that switching header include orders fixes it. Didn't fix it for me.

So then I figure, perhaps the documentation is old, and "class" has been removed. Changing "class" to a random string returns a different error, so that's not it. So I looked at the newest documentation I could find - the source. Turns out that it WAS changed, and here it is (abbridged):

typedef struct {
    int x, y;                   /* location of window */
    [...]
    Window root;                /* root of screen containing window */
#if defined(__cplusplus) || defined(c_plusplus)
    int c_class;                /* C++ InputOutput, InputOnly*/
#else
    int class;                  /* InputOutput, InputOnly*/
#endif
    int bit_gravity;            /* one of bit gravity values */
    [...]
    Screen *screen;             /* back pointer to correct screen */
} XWindowAttributes;

As it turns out, my code is C++, and apparently there's a different member for C and C++ (whoever heard of doing that? I fail to see the reasoning - though I'm sure there is some).

Anyway, a simple change of variable name to c_class fixed the errors, and it compiles successfully. Mark another one up for non-deterministic error messages.

Wider Posts!

I've edited the template a little, and now it seems a little less cramped. Of course, I'm on a widescreen so it still looks like text crunched into the middle of the screen, but I tried to keep it at a width of 800px for easy viewing on older machines (sometimes I wish they'd all just burn up and get replaced). Anyway, I checked it on a couple browsers, and it looks fine, but let me know if there's an issue.

Using Xlib with JNI

Quick tutorial today on using Xlib with JNI (obviously).

Check my previous posts tagged with Xlib and X11 for reference material. If you've never used JNI before, you're probably going to need to do some basic tutorials first - again, previous posts here may help.

Let's get started! The first thing you're going to need is the X11 development headers. On my machine:

apt-cache search libx11-dev
  libx11-dev - X11 client-side library (development headers)

apt-get install libx11-dev

Your java source is your own to deal with, seeing as all that's relevant here is the method and class name. We'll use String JXTest.doSomething();

JXTest.cpp:

#include "/usr/include/X11/Xlib.h"
#include "JXTest.h"

// open the current display. NULL means check the DISPLAY shell variable
Display *display = XOpenDisplay(NULL);
Window hwnd;
int revert_to;
char title[80];

JNIEXPORT jstring JNICALL Java_JXTest_doSomething(JNIEnv *env, jobject obj){

    // make sure we're connected to an X display
    if(display == NULL){
        printf("Could not open display\n");
        return NULL;
    }

    // now we get to do stuff!
    // let's keep with previous posts, and go with getting the focused window's title
    // check the reference pages on these functions for more information

    XGetInputFocus(display, &hwnd, &revert_to);

    char* retval;
    if(XFetchName(display, hwnd, &retval)) != 0){
        // we have to free the string, so let's copy it into our own
        // note that title is global so that we're not allocating new memory each time
        strcpy(title, retval);
        XFree(retval);
        printf("Our window title is %s\n", title);

        // as per a previous post, NewStringUTF does not preserve the pointer, so we can reuse title later
        return env->NewStringUTF(title);
    }
    printf("Could not get window title!\n");
    return null;

}

g++ -lX11 -shared -o libtestlibrary.so -I/usr/lib/jvm/java-6-sun-1.6.0.00/include/ -I/usr/lib/jvm/java-6-sun-1.6.0.00/include/linux -I/usr/includes/X11/ nimbusLinux.cpp

-lX11 links the library to X11 and includes the X11 headers
-o is the output file name - remember that System.loadLbrary translates "testlibrary" to "libtestlibrary.so" automatically
-I are include paths - you'll probably hae to modify these to suit your own system

If all goes well, you should now have a program that interacts with X to get the currently-focused window's title!

Note that under some window managers the currently-focused window has an invisible "FocusProxy" over it - see my post here for information on that and a couple other issues.

One last note: on Linux, I've had issues with library loading with System.loadLibrary. This should help, and it's cross-platform:

static {
                try{
                        File pwd = new File(".");
                        System.load(pwd.getCanonicalPath() + "/"  + System.mapLibraryName("libraryname"));
                }catch(Exception e){
                        e.printStackTrace();
                        System.exit(1);
                }
        }

Intro to JNI on Linux

Today (as the title says) I'm going to go over a few things dealing with JNI compilation for Linux. I recommend you read my previous post for JNI on Windows if you've never used it before, this just deals with the quick and dirty details.

Let's get to some simple code:

myNativeMethod.cpp:

#include "myClass.h"

JNIEXPORT void JNICALL Java_myClass_myNativeMethod(JNIEnv *env, jobject obj){
    printf("well hello there!\n");
}

Easy stuff. As always, myClass.h is generated after the java code is compiled and run through javah. Our native method is defined in the java source as:

...
    private native void myNativeMethod();
    static {
        System.loadLibrary("myNativeLibrary");
    }
...

NOTE: System.loadLibrary expects a certain filename. On Linux, it prepends "lib" and appends ".so" - so the above call looks for "libmyNativeLibrary.so" on Linux, just as it would look for "myNativeLibrary.dll" on Windows.

Let's compile! Of course, your include paths will probably be different, but that shouldn't be hard to fix.

 g++ -shared -o libmyNativeLibrary.so -I/usr/lib/jvm/java-6-sun-1.6.0.00/include/ -I/usr/lib/jvm/java-6-sun-1.6.0.00/include/linux myNativeMethod.cpp

Viola! We have compiled our library.

Now, when you try to use it, sometimes you'll get am UnsatisfiedLinkError if everything's not exactly right. This is caused from a couple things:

1) You didn't name it lib[name].so!
2) You didn't use the right method signature - the header signature and your own signature should be EXACTLY the same.
3) It's simply not in Java's library search path. The quick and dirty way to force it in is to run:

java -Djava.library.path=./ myClass

Unfortunately, the library path that overwrites usually has stuff in it that is needed - which results in more Unsatisfied Link Errors. The next quick and dirty way is to just move libmyNativeLibrary.so to /lib or somewhere else in the library path.

Gatta run, I may add more later.

JNI's NewStringUTF and Memory Use

After a few crashes and debugging returning the error location being a malloc call, I did some research on NewStringUTF usage.

It was difficult to find, but it appears that a returned jstring (made by NewStringUTF) is copied by Java into its own heap space. This contradicts my previous assumption that it just kept the memory pointer. In my previous code I had similar to:

JNIEXPORT jstring JNICALL Java_myClass_myMethod(JNIEnv *env, jobject obj){
...
 LPTSTR buffer = (LPTSTR)malloc(200*sizeof(TCHAR));
...
 return env->NewStringUTF(buffer);
}

Obviously this doesn't free the memory allocated and pointed to by "buffer" - which I'd previously thought was correct, assuming the Java garbage collector would clean it up. It appears that was incorrect, though - so (in my situation) the best solution was to make a global buffer and use it over and over.

LPTSTR buffer = (LPTSTR)malloc(200*sizeof(TCHAR));
JNIEXPORT jstring JNICALL Java_nimbus_getForegroundWindow(JNIEnv *env, jobject obj){
...
  return env->NewStringUTF(buffer);
}

This ensures that memory isn't constantly allocated and not deleted. Hopefully in the future the Sun JNI examples will note this better.

Messing with X11

My latest foray into X windowing got me stuck in a couple places. I'll give a brief overview today of my issues and resolutions, and perhaps if I find some time I'll go through in more detail later.

Issue: Finding a call to locate the focused window.
Resolution: XGetInputFocus

Issue: Finding a call to get the window title.
Resolution1: XGetWindowProperty
Resolution2: XFetchName (much much easier)

Issue: Window title is null?
Reason: There appears to be an invisible window overlayed on it. Often "FocusProxy".
Resolution: XQueryTree to find the parent. This resolution is iffy.

Issue: Finding a call to get a process ID from a window.
Resolution: XGetWindowProperty -> _NET_WM_PID (though it's not always set)

X System Calls

Lately I've been searching for a couple calls under X that have been evading me. The one in particular that I need is a call to determine the process ID of the foreground window.

I've found some very interesting info, lots of stuff that would be useful if I were implementing a complete window manager:

Inter-client Communication Conventions Manual
Window ID -> Process ID
Wikipedia's Xlib Article

I have a feeling that what I need is in Xlib, but I haven't had time to go through it completely yet.

What worries me, though, is that I've read a couple places that going from window ID to process ID is (almost?) nondeterministic in X. There HAS to be a way though... right? I just don't know enough about window managers and X I guess.

Edit/Update:

This:

Xlib Programming Manual: Input Focus Events

has some potential for helping.

XGetInputFocus

Promising!

"A C++ program to generate every possible X11 request"

Very useful.

Batch File Issue

If anyone has an answer to why it's doing this, please let me know. I'm not too concerned about it, so I haven't gone digging, but figured I'd put it out there for all to see.

So I've got this batch file I've been using to build these simple JNI projects. Nothing fancy:

[make.bat]

call clean.bat
javac javaclass.java
javah -jni javaclass
call "C:\Program Files (x86)\Microsoft Visual Studio 9.0\VC\vcvarsall.bat" amd64
cl -I"c:\program files\java\jdk1.6.0_06\include" -I"c:\program files\java\jdk1.6.0_06\include\win32" -I"." -MD -LD javanative.cpp -Fejavanative.dll user32.lib
mt -manifest javanative.dll.manifest -outputresource:javanative.dll;2

Every, say, 12 builds in the same console window, and I get this error message:

The input line is too long.
The syntax of the command is incorrect.

The message comes from the Visual Studio batch file or the compiler, not sure which - the batch file prints out a message saying it's configured as normal, and that's when it dies.

Anyway, from then on it fails to build, and the only way to fix it is to open a new console window. Nothing big, just annoying sometimes.

user32.dll Functions in JNI

UPDATE NOTE:
Please read this post explaining a small issue with the code used in this article.

If you've never used JNI before, please read my previous post first.

In this post I'm going to go over how to use some windows functions with JNI. Specifically, two which have caused me frustration recently: GetForegroundWindow and GetWindowText.

Reference Pages:
GetForegroundWindow
GetWindowText
GetWindowTextLength
GetLastError
C++ JNI Types/Functions

To the code! This is similar to my initial code - there is a problem with it. Hopefully you don't see it, so as to keep my programming ego intact. Again, this code DOES NOT WORK - if you're just here for the code look down further.

[javanative.cpp]

#include "windows.h"
#include "winuser.h"
#include "jni.h"
#include "javaclass.h" // generated header file

JNIEXPORT jstring JNICALL Java_javaclass_getForegroundWindow(JNIEnv *env, jobject obj){
  HWND hwnd = GetForegroundWindow();
  if(hwnd == 0){
    return NULL;
  }
  int length = GetWindowLength(hwnd);
  LPTSTR buffer = "xxxxxxxxxxxxxxxxxxxx"; // this is how I found a few examples online
  int textLength = GetWindowText(hwnd, buffer, 20);
  return env->NewStringUTF(buffer); // this too - memory leak. see code below
}

Note that the functions (GetWindowText, etc.) are in user32.dll; in order to use them, you must include the user32.lib library during compilation. The method to do this depends on your compiler; with the Visual Studio command-line compiler, you just append the libraries to the end (as you'll see below).

Compilation:

javac javaclass.java
javah -jni javaclass
call "C:\Program Files (x86)\Microsoft Visual Studio 9.0\VC\vcvarsall.bat" amd64
cl -I"c:\program files\java\jdk1.6.0_06\include" -I"c:\program files\java\jdk1.6.0_06\include\win32" -I"." -MT -LD javanative.cpp -Fejavanative.dll user32.lib

Now then, it compiles - but it doesn't work. It returns the "xxxx..." string as the name every time. After some debugging, I found that GetWindowText was returning an error code of 1400 - and that code means that the window does not exist. Some more testing confirmed that the window DID exist - IsWindow returned true, etc. So, what's the problem?

As you probably guessed (the only commented line in the code):

  LPTSTR buffer = "xxxxxxxxxxxxxxxxxxxx"; // this is how I found a few examples online

Apparently, having the buffer on the stack makes the call return 1400 - a completely wrong error code. The correct way to do it is to put the buffer on the heap.

  int length = GetWindowTextLength(hwnd);
  // make some heap space - lots of ways to do this.
  LPTSTR buffer = (LPTSTR)malloc(length * sizeof(TCHAR));

It works!

Here's the full, working code:

#include "windows.h"
#include "winuser.h"
#include "jni.h"
#include "javaclass.h"

JNIEXPORT jstring JNICALL Java_nimbus_getForegroundWindow(JNIEnv *env, jobject obj){

  HWND hwnd = GetForegroundWindow();
  if(hwnd == 0){
    return NULL;
  }
  int length = GetWindowTextLength(hwnd);
  LPTSTR buffer = (LPTSTR)malloc(length * sizeof(TCHAR));
  int textLength = GetWindowText(hwnd, buf, length);
  DWORD lasterror = GetLastError();
  jstring jstr = env->NewStringUTF(buffer);
  free(buffer);
  return jstr;
}

Note that even though we allocate heap space, we don't want to free it ourselves. This is not a memory leak, Java's GC will deallocate it when it's no longer in use.

And there you have it. Calling getForegroundWindow() in your java source now returns the caption of the foreground window.

Introduction to JNI

As my first technical post, I'm going to overview how to use JNI with C++.

My platform:
Windows Vista Ultimate
AMD Athlon64 X2 6000+
5GB DDR2
Java 1.6.0_06 64-bit
Microsoft Visual Studio 2008

Straight to the code:

[HelloWorld.java]

class HelloWorld {
  public static native void HelloNative(String s);
    static {
      System.loadLibrary("HelloDLL");
    }
  public static void main(String[] Args){
    HelloNative("Hello, world!");
  }
}

Things to note:
- The method we're going to create in the DLL is declared as "native" but not defined.
- To load the methods from the DLL, we call System.loadLibrary("library");
- Do not put the extension in the call - our DLL will be HelloDLL.dll, so we call with "HelloDLL"
- After that, we can use the function just as normal.

[HelloWorld.cpp (here's where it gets messy)]

#include "HelloWorld.h"
JNIEXPORT void JNICALL Java_HelloWorld_HelloNative(JNIEnv *env, jobject obj, jstring javaString){
  const char *input = env->GetStringUTFChars(javaString, 0);
  printf("%s\n", input);
  env->ReleaseStringUTFChars(javaString, input);
}

Things to note:
-The header "HelloWorld.h" will be generated by javah as we'll see in a bit.
-The function name must be Java_ClassName_MethodName
-The function parameters must start with a JNIEnv* and a jobject, after that come your own.
-To use the jstring you passed in as a character array, you have to call GetStringUTFChars
-You MUST call ReleaseStringUTFChars after calling GetStringUTFChars once you're done

Putting it all together:

javac HelloWorld.java
javah -jni HelloWorld

[Here you can use a C++ compiler of your choice, as long as you know how to use it to create a DLL. This example is with Visual Studio 2008]

call "C:\Program Files (x86)\Microsoft Visual Studio 9.0\VC\vcvarsall.bat" amd64

cl -I"c:\program files\java\jdk1.6.0_06\include" -I"c:\program files\java\jdk1.6.0_06\include\win32" -I"." -MT -LD HelloWorld.cpp -FeHelloDLL.dll

All done!
Let's go over the compilation.

You'd better know what javac does already; javah creates the header file for the class, which we already included in our cpp file (HelloWorld.h).

The first Visual Studio command is a batch file, with an architecture parameter. I'm compiling to amd64. The batch file sets the paths and settings necessary for compilation, makes things easy. I don't believe the standard install of Visual Studio comes with the different architectures - you have to enable it during install (you can go to reinstall and add it without reinstalling the whole thing). Visual Studio Express may not have it - you'll have to install the Windows SDK to get them. There's a help page on the MSDN somewhere about that.

cl is the command-line compiler for Visual Studio. I'm adding include paths to Java's includes directories, as well as the current directory. Some extra switches for good measure, the source file, and the output file.

Viola! You now have your DLL.


Important Note:

With Visual Studio, you can either compile with -MT or -MD. I believe default is MD. the difference is that MT adds the library code directly (statically) to your DLL, while MD links it dynamically. If you use MD, your program is now dependent on msvcr90.dll (or whatever version of Visual Studio you're using). If it fails to run, you need to grab this DLL. I chose to just put it in with my own DLL, as not everyone is going to have it. If you don't, you can find it easily online, or if you have Visual Studio it should be at:

C:\Program Files (x86)\Microsoft Visual Studio 9.0\VC\redist\somewheredownthere

I prefer to use MT, so that I don't have to worry about distributing extra static libraries. There are up and downsides to using both. Static will make your DLL a little larger, will MD will make your DLL rely on other libraries. You also may have to embed the manifest file into your DLL if you use MD.

Also note that there are different versions of msvcr90.dll for different architectures, if you choose to use dynamic linking. You can't use the wrong one. Don't worry, it should tell you if you have the wrong one.

Anyway...
That's the end of my first post. Hope you enjoyed.

So last night...

... while I couldn't sleep after an afternoon of frustrations, I thought it might be beneficial to both myself and others if I had somewhere to keep notes on the general "quirks and quandaries" I run into while programming. Of course, I'll also try to post examples of things I found difficult to find, for the betterment of the learning community.

Anyway, I hope at least some of what I do is useful to someone.