Huh? No unsigned values in Java?

I’ve been working on this program with my friends Dmitri and Oleg. The program computes permutations of reversible circuits (i.e. NOT gates, CNOT gates, etc.) for different numbers of inputs. The gates are simulated by performing bit operations on 64-bit unsigned integers. The details aren’t that important, but what’s interesting is that the number of permutations gets massively huge as the number of inputs increases. To store results for 8 inputs, you need an array of size (2^29)*8, where the 8 is for 64-bit unsigned integers.

Oleg developed a C++ version to do the calculations and after some tweaks and bug fixes we managed to get it to calculate up to 6 inputs in about 5 seconds. With 7 inputs, things get a little tricky because you need a table of size (2^26)*8, but we also use three other arrays of similar size. On our 2GB machines, this is too much. However, it’s possible to calculate for 7 inputs if we do something hacky like make one special table that size and leave the other ones smaller at size (2^23)*8.

We want to calculate values for at least 8 inputs. This is beyond our 2GB machines, at least if we keep everything in memory. I originally worked on dumping our hashtables to files and merge sorting the files in the process when the hashtables get too large, but this is pretty slow. After this I decided to try dumping the tables into a database. I converted the program from C++ to Java and hooked in a MySQL database.

This is where I ran into the issue that Java does not support unsigned long values. I hadn’t realized this, but of course, how often do you need a full 64-bit integer? Luckily, I was able to get around the lack of unsigned values by first realizing that bit shift operators in Java do not care about the sign bit except for the right-shift (>>). However, there’s an unsigned version (i.e. >>>). The second problem was that you can’t use less than and greater than operators because if you’re using the sign bit, then a potentially large number will be negative. To get around this, I wrote my own comparison function, which is shown below.

/**
* Bitwise comparison of longs.  This is to handle the fact 
* that Java does not support unsigned longs.
*/
static int compareLongs(long p, long q) {
  if(p == q) return 0;
 
  for(int i = 64; i >= 0; --i) {
     long t1 = (1 << i) & p;
     long t2 = (1 << i) & q;
     if(t1 < t2) return -1;
     else if(t1 > t2) return 1;
  }
  return 0;
}

I had to make some other tweaks as well, like writing a clone function for our hash table as assignment in Java works differently than C++. Once I completed this, and the various bit shift changes, the Java version ran almost as fast as the C++ version.

For the database integration, I ended up doing a lot of MySQL configuration tweaks in order to get my bulk insertion speed faster. I also discovered some new MySQL specific SQL syntax. For example, you can use REPLACE INTO instead of INSERT INTO if you are going to potentially insert a record with a matching primary key. The replace version will delete the old version and insert the new one. I actually ended up using a similar SQL statement, INSERT IGNORE INTO, which does the same thing but does not delete the original record but simply ignores the new one.

I’m not sure how useful this Java version is going to be as I managed to get access to a server with 8GBs of RAM where I can allocate enough memory for the C++ version to work. Also, Oleg was able to calculate inputs of 8 values by dumping multiple files to disk and then using the Unix sort program to merge and sort the files. However, it was still a good learning experience and we can possibly use it for verifying our numbers. I’ll post a bit about the C++ version next time.