random memes }

Trie in Java - revisited

An earlier attempt at writing a fast general purpose Trie in Java gave huge memory use, and disappointing results. Seems a Trie implementation that is both fast and general purpose is not possible. (Translation: For most use a Trie cannot replace a hash table.)

After the prior results, I wanted to see if a less general-purpose implementation would perform better. Given enough advantages, could a Trie out-perform a hash table? (Again, this visits to some extent the question asked in a prior discussion.)

For the current exercise I built two Trie implementations. The LinkedTrie is cheap to build, minimal in use of memory, but not especially fast to access. The FixedTrie implementation should be pretty close to optimal in access time (for a Trie), but expensive to build (in fact the FixedTrieBuilder transforms a LinkedTrie into an optimized FixedTrie).

As before, the sources are in (as an Eclipse project): http://svn.bannister.us/public/Trie/.

The performance numbers make sense. The older TallTrie and WideTrie implementations (that traded increased memory use for speed) are indeed faster, though the LinkedTrie uses much(!) less memory. The new FixedTrie is fastest (hurrah!) and uses the least memory (a shade less than LinkedTrie).

But even the FixedTrie is slower than a generic hash table, with read-only access about 3 times as expensive.

Sample measurements...

=== words 21 ms - 98569 words loaded

=== hash 3935/second - hash map loaded {4007 ms, 15771040 operations = 254 ns/op} 8554/second - hash map re-loaded {4010 ms, 34302012 operations = 116 ns/op} 10768/second - access each item in hash map {4000 ms, 43074653 operations = 92 ns/op}

=== trie (linked) 870/second - loaded trie (linked) {4078 ms, 3548484 operations = 1149 ns/op} 1204/second - re-loaded trie (linked) {4010 ms, 4829881 operations = 830 ns/op} 1431/second - access each item in trie (linked) {4063 ms, 5815571 operations = 698 ns/op} 98569 slots of trie (linked) 225791 nodes of trie (linked)

=== build fixed trie

=== trie (fixed) 85779/second - loaded trie (fixed) {4000 ms, 343118689 operations = 11 ns/op} 87652/second - re-loaded trie (fixed) {4000 ms, 350609933 operations = 11 ns/op} 3438/second - access each item in trie (fixed) {4013 ms, 13799660 operations = 290 ns/op} 98569 slots of trie (fixed) 225791 nodes of trie (fixed)

=== trie (wide) 65/second - loaded trie (wide) {4502 ms, 295707 operations = 15224 ns/op} 1659/second - re-loaded trie (wide) {4040 ms, 6702692 operations = 602 ns/op} 1672/second - access each item in trie (wide) {4007 ms, 6702692 operations = 597 ns/op} 41533124 slots of trie (wide) 225890 nodes of trie (wide)

=== trie (tall) 682/second - loaded trie (tall) {4043 ms, 2759932 operations = 1464 ns/op} 1733/second - re-loaded trie (tall) {4036 ms, 6998399 operations = 576 ns/op} 1913/second - access each item in trie (tall) {4019 ms, 7688382 operations = 522 ns/op} 6982694 slots of trie (tall) 446075 nodes of trie (tall)

=== string to UTF8 conversion 1393/second - word to UTF8 (stock) {4033 ms, 5618433 operations = 717 ns/op} 9585/second - word to UTF8 (fast) {4000 ms, 38343341 operations = 104 ns/op}

(Note that the FixedTrie ignores re-load, so the times for load and re-load are bogus.)

I suspect a C++ Trie implementation could do a bit better ... but not necessarily outperform ... compared to hash tables.

Looks very much like even a specialized read-only Trie cannot match the performance of a generic hash table (at least in Java).