Expedite Huffman decoder using alternate tree representation

[gwlucastrig]

During recent testing, I observed that the Huffman decoder is significantly slower than the corresponding Deflate operation. In a way, that is not surprising since the Deflate uses a class from the standard Java API and is probably written in a very low-level language while the Huffman decoder is written in Java as part of the Gridfour library. On the other hand, Huffman decoding is conceptually quite simple (just a tree traversal) and the fact that it is so slow is a bit unexpected.

To create test data for investigating this matter, I built two test versions of the ETOPO1 library, one using Huffman coding and one using Deflate. This could be accomplished in the PackageData.java demo application by removing one of the codecs from the GvrsFileSpecification. The example snippet below removes Deflate, but leaves Huffman in place for processing (the opposite would also work)

    GvrsFileSpecification spec = // set up in application code
    spec.setDataCompressionEnabled(compressionEnabled);
    spec.removeCompressionCodec(GvrsCodecType.GvrsDeflate.name());

Compression using Deflate took somewhat longer than the simpler Huffman, but the decompression timing raised some concerns

   Time to read whole file, Deflate:     3.09 seconds
   Time to read whole file, Huffman:     6.26 seconds

I performed some code tweaks and was able to reduce that to 5.93 seconds.

Since I wasn't satisfied with that improvement, I tried something entirely different. The Huffman code is stored in a tree. The tree consists of instances of a class called SymbolNode. The traversal is just a matter of using bits collected from an input source to control how the tree is traversed (a zero bit means traverse left, a one bit means traverse right):

   for (int i = 0; i < nSymbols; i++) {
      SymbolNode node = root;
      while (!node.isLeaf) {
        if (input.getBit() == 0) {
          node = node.left;
        } else {
          node = node.right;
        }
      }
      symbols[i] = (byte) node.symbol;
    }

As an experiment, instead of constructing the tree as a set of objects, I implemented it in an array of integers. That is really old school programming. The last time I did something like that, I was working in Fortran 77 (an older version of Fortran that pre-dated structured data types). Anyway, here's a snippet of code showing the same loop:

    int []nodeIndex = decodeTree(...); // gets the Huffman tree as an array of integers
    for (int i = 0; i < nSymbols; i++) {
      int offset = nodeIndex[1 + input.getBit()]; // start from the root node
      // branch nodes are indicated by values of -1, leaf nodes by values >= 0
      while (nodeIndex[offset] == -1) {
        offset = nodeIndex[offset + 1 + input.getBit()];
      }
      symbols[i] = (byte) nodeIndex[offset];
    }

An detailed explanation of the code is included in HuffmanDecoder.java. But the odd thing is that this reduces the time to process the ETOPO1 data set down to 4.55 seconds. Still not as fast as Deflate, but better than it was.

The thing is, I don't really understand why this implementation is so much faster than the conventional tree traversal. I welcome any insights that people can offer. I have revised Gridfour's HuffmanDecoder.java class to use the approach shown above and have posted the code. The original implementation was renamed HuffmanDecoderReference.java and retained in the code base for documentation and future study.

Finally, I close by urging people to use Gridfour as much as they possibly can... I spent many hours refining the code to save 2 seconds per run. So I want to make sure it is used enough times to save users as much time I put into it [grin].

[gwlucastrig]

When GVRS data files are created using data compression, the API uses the technique that yields the best compression ratios. Sometimes it's Deflate. Sometimes it's Huffman. While Deflate is usually preferred for most of the predictors, Huffman is actually preferred in 60 percent of all cases when using the LSOP predictor.

For more information on Gridfour data compression, please see:

Gridfour Data Compression Algorithms

Lossless Compression for Raster Data using Optimal Predictors

[gwlucastrig]

This issue is now closed.