Over the years some of my favorite programming tasks required the judicious application of algorithms. 15 years ago when memory was scarce, I was packing encrypted data into memory blocks that were constrained by the old Intel architecture and the frightful Win16 environment. Lempel-Ziv-Welch compression and Huffman coding were two of the algorithms I used back then. We had to compress - otherwise thing just wouldn't fit! (BTW, remember those "RAM Doubler" products?)
I also had to develop some quicksort implementations that did fast sorting in a static heap. Chapter 8 of Introduction to Algorithms (1st edition) was essential for this work.
So why is Better Living through Algorithms on my mind today?
My recent work at FMG revolves around a technology we call "HyperMemory", which is a building block for some of our new products. (Yes, I know ATI is already using the name!)
I am absolutely loving being involved in this effort, because it is taking me back to the old days... except now, no 16-bit pointer nightmares making me miserable.
So I started hacking away on an engine that can load data from our Business Objects into memory, index it, query it, and so on. After some review of the excellent Java Performance Tuning, Second Edition, I implemented a modified Digital Trie that links to a Ternary Tree. This was a "modified" tree because instead of functioning as a Set I needed this index to support multiple hits on any given node in the tree. So each node in my tree has a bucket as opposed to one value.
Before adding the indexing, benchmarking of HyperMemory searches was measured in "milliseconds" (1/1000 of a second = 1 millisecond). After I added the indexing layer, I had to start using the the cool new Java 5
That's right. NANO TIME. Better living indeed!
I ended up rounding up to microseconds (1/1,000,000 of a second) to make more sense of the numbers - not to mention that depending on the underlying OS, this call may give you nanosecond resolution but the accuracy is actually to the microsecond. I hope to expand on this in another post some day.
OK, so having "been there/done that" back in the 90's, using unmanaged code in the pathetic Win16 environment I gotta tell ya... being here 15 years later, doing it all over again - sans Win16/DOS, sans 16-bit headaches... It's great to be alive in 2005!