Storing Strings, Succinctly

Alas, I lack an alliterative algorithm for squashing strings into less space, but hopefully I can make it up to you by sharing an improvement on a simple way of storing strings. To make it easier to follow, I'll build up to the full algorithm, step-by-step. 

Step 1: Reduce Randomness

Compression algorithms in general work better if you can reduce the randomness in your data. That may seem impossible, after all, the information is what the information is, but it is actually possible. The way that we're going to reduce randomness is by sorting our strings (e.g. putting them in alphabetic order). As an example, if we have the strings {cat, carrot, car}, we can store them as [car, carrot, cat]. That may not seem like it helps, but it does.

Step 2: Remove Redundancy

Looking at our list above ([car, carrot, cat]), we see that car is a prefix of carrot and carrot and cat share the prefix "ca". We can use that information to cut down on what we have to store, by recording the length of the shared prefix and then just writing the suffix.  What we end up with is [c,a,r,3,r,o,t,2,t], where 3 and 2 are the shared prefix lengths. Now, you may be asking how we can tell when one word ends and the next begins, and if you are, good, because that's a great question! One approach, that will probably be warmly embraced by C programmers, is to null terminate the strings, i.e. end them with a 0 (that's a zero, not an O). That approach works pretty well and leaves us with [c,a,r,0,3,r,o,t,0,2,t]

Step 3: Look at Lengths

English words, by and large, aren't terribly long. With one byte, like the one that we used to store the length of the shared prefix or the one with which we terminate strings, we can store up to the number 255. Most words aren't nearly that long and, unless you're dealing with protein names, you're not likely to encounter any of the few that are longer than that. To take advantage of that, instead of null-terminating, let's store the length of the prefix and the length of the suffix. Since we're storing lengths, we can also take advantage of words being short by storing the prefix and suffix lengths in one byte, together. If we devote 4 bits to the length of the prefix, we can avoid storing up to 15 bytes of prefix; if the shared prefix is longer than that, we can just duplicate the extra (4 bits isn't a magic number; I arrived at it through trial and error using a list of 99,171 English words, my initial guess at a good number was 3 bits). That leaves us with another 4 bits to store the remainder and a bit of a quandary if the remaining suffix is more than 16 bytes long (it would be 15 but, since the suffix must be at least 1 byte, we trade the ability to store 0 to make the remainder 1 smaller). Thankfully, another compression trick called (among several other things) variable byte encoding, comes to our rescue.

The standard way that variable byte encoding works is to use one bit to encode if there are more bytes in the number. We're going to deviate from that just a bit by instead taking up to the entire 4 bits to store the length. If the length is larger than, or equal to, 15 we store 1's in all 4 bits, subtract 15 from the remainder, and then use standard variable byte encoding to store the rest (even if that's a byte of all zeros). 

Results

So, what has all this bit-twiddling bought us? Encoding 99,171 words, which took a total of 938,848 bytes got it down to 323,370 bytes. Now, that's still not tiny, but it's about a 61% reduction in size. Gzip gets it down to about 256,000 bytes, which is considerably smaller, but this also has the benefit that it should be fairly easy to implement it such that it can encode & decode faster than gzip and permit more nearly random access to elements.

Hey, what do you know, I did manage to describe the algorithm using alliteration! Bonus! I hope this has been at least slightly entertaining, I hope it has been useful, and I hope it has been informative.

Hodge Podge

This is just a hodge podge of short items; the 2nd part of the multithreading post will probably be up in a few days.

What's In a Name?

The methods in the Java standard libraries are generally well-named, but there are a few astonishingly irritating exceptions, and java.lang.Character seems to collect them.

Q: Which of the following returns true for a space, tab, newline and non-breaking whitespace: isWhitespace, isSpace, isSpaceChar.

A: NONE OF THEM!

isSpace and isWhitespace return false for a non-breaking space; isSpaceChar returns false for newlines and tabs. If you want to know if a character is a whitespace, you need isSpaceChar || isWhitespace. As an added kick in the shins, the \s regular expression class also doesn't match non-breaking space.

Keep on Moving (Conditionally)

Branch mispredictions on modern processors hurt. Badly. Because of that, anything that you can do to make branches (e.g. if statements & the conditionals on loops) easier to predict will generally make your code faster. Sometimes, though, you just reach the point where you can't make the branches easier to predict. In those cases, you can sometimes play some tricks to replace them with conditional moves/sets and pick up some performance. For example, here's the body of the main loop for merging two arrays in merge sort:

if(arr1[index1] < arr2[index2]) {  
   mergeInto[index3++] = arr1[index1++];
} else {
   mergeInto[index3++] = arr2[index2++];
}

and here's a version that replaces the branches with conditional moves/sets

int read = arr1[index1] < arr2[index2] ? arr1[index1] : arr2[index2];
mergeInto[index3++] = read;
int addTo1 = arr1[index1] == read ? 1 : 0;
index1 += addTo1;
index2 += addTo1 == 0 ? 1 : 0;

On an Ivy Bridge laptop running Java 1.7, the latter code is about 1.50 nanoseconds (0.0000015 ms) / element faster for the low, low price of making your code's intentions a little less obvious and the code a little harder to read. It should go without saying, but you shouldn't drop to this level of optimization unless your code is too slow, you've profiled it and know that your bottleneck is there and at least strongly suspect that the problem is branch mispredictions.

Singletonish

java.util.concurrent has a lot of neat classes, including the ever-useful ConcurrentHashMap. ConcurrentHashMap has a nifty little method called putIfAbsent that we can use to create singleton-ish objects. For example, if you need to run some expensive initialization once for each user who logs on, but you only want to do it once / user. The downside to putIfAbsent is that it takes an object, which would appear to meant that we have to instantiate the thing anyway. We can, however, take a page from Future's playbook and put an object that will instantiate the object. 

One thing you'll have to keep in mind is that you must check the return value from putIfAbsent, otherwise you'll be defeating the whole purpose and reinstantiating every time. Basically, here's the general pattern you'll want to use:

Instantiator instantiator = new Instantiator();

Instantiator fromMap = theMap.putIfAbsent(theKey, instantiator);

theValue = fromMap != null ? fromMap.getTheValue() : instantiator.getTheValue();

Instantiator's just a run-of-the-mill object that builds the object once and returns it. You'll need to do some synchronization to make sure you only instantiate its object once, but that's fairly cookie-cutter code.