We used a JIT-less subset of Java 1.4 on that device. Hashing of word-length strings in the underlying optimized C code was extremely fast and CPU cache friendl

We used a JIT-less subset of Java 1.4 on that device. Hashing of word-length strings in the underlying optimized C code was extremely fast and CPU cache friendly (and came with the JVM). With the simple cache in place, indexing time was dominated by the libraries that extracted the text from the supported formats. So, in line with this Ask HN's topic, it was good enough. And less code to maintain. And easier for engineers after me to understand. A good tradeoff overall. More technical details for the curious... Earlier I had done a quick trie implementation for other purposes in that code, but abandoned it. The problem is that we had to index (and search) large amounts of content in many different languages, including Chinese and Japanese with full Unicode support. This means that there is such large potential fan-out / sparsity within the trie that you need faster lookups / denser storage at each node in the trie (a hash map or binary search or ...). In that situation, a trie can be much slower than a single hash map with short strings as keys. Especially in a JIT-less JVM (the same code had to run server-side, where native extensions weren't allowed). If we were only dealing with ASCII, then maybe. And there would also be more complexity to maintain for decades (you can still buy newer versions of the device today that are running the same indexing and search code). All those languages were also the reason that normalization needed caching. In v1, we were English only. I hand rolled a "good enough" normalizer that was simple / fast enough to not need caching. In v2 we went international as described above. I wasn't capable of hand rolling anything beyond English. So we brought in Lucene's tokenizers/stemmers (including for English, which was much more accurate than mine). Many of the stemmers were written in Snowball and the resulting Java code was very slow on the device.