3 ms·

15+ years ago, I was working on indexing gigabytes of text on a mobile CPU (before smart phones caused massive investment in such CPUs). Word normalization logi

15+ years ago, I was working on indexing gigabytes of text on a mobile CPU (before smart phones caused massive investment in such CPUs). Word normalization logic (e.g., sky/skies/sky's -> sky) was very slow, so I used a cache, which sped it up immensely. Conceptually the cache looked like {"sky": "sky", "skies": "sky", "sky's": "sky", "cats": "cat", ...}. I needed cache eviction logic as there was only 1 MB of RAM available to the indexer, and most of that was used by the library that parsed the input format. The initial version of that logic cleared the entire cache when it hit a certain number of entries, just as a placeholder. When I got around to adding some LRU eviction logic, it became faster on our desktop simulator, but far slower on the embedded device (slower than with no word cache at all). I tried several different "smart" eviction strategies. All of them were faster on the desktop and slower on the device. The disconnect came down to CPU cache (not word cache) size / strategy differences between the desktop and mobile CPUs - that was fun to diagnose! We ended up shipping the "dumb" eviction logic because it was so much faster in practice. The eviction function was only two lines of code plus a large comment explaining all the above and saying something to the effect of "yes, this looks dumb, but test speed on the target device when making it smarter."

fritzo 3y ago
Those are my favorite functions! Two lines of code with a page of text explaining why it works.
dharmab 3y ago
Similarly, a modder recently found that unrolling loops _hurt_ performance on the N64 because of RAM bus contention: https://www.youtube.com/watch?v=t_rzYnXEQlE https://www.youtube.com/watch?v=t_rzYnXEQlE
- pclmulqdq 3y ago
  Unrolled loops can also often hurt for the same reason on big server chips. It's not always clearly good to unroll your loops.
o11c 3y ago
... how does doing a full string dict lookup take less time than just checking a few trailing characters in a trie? For indexing it's okay to be aggressive since you can check again for the actual matches.
- Exoristos 3y ago
  > since you can check again for the actual matches. Can you explain this?
  - o11c 3y ago
    An aggressive stemmer might stem both "generic" and "general" to "gener". Then if your query is "what documents contain 'generic'?", you look in the index for "gener" and then open each of those documents and check if it actually has "generic" using a stricter stemmer (that accepts generic{,s}, genericness{,es}, genericit{y,ies}, generically ... this is a bit of a bad example since they all have the prefix directly). The cost is acceptable as long as both words have about the same frequency so it doesn't affect the big O. Of course if you have any decent kind of compute, you can hard-code exceptions before building the index (which does mean you have to rebuild the index if your exception list changes ... or at least, the part of the index for the specific part of the trie whose exception lists changed - you don't do a global lookup!) to do less work at query time. But regardless, you still have to do some of this at query time to handle nasty cases like lie/lay/laid (searching for "lie" should not return "laid" or vice versa, but "lay" should match both of the others) or do/does/doe (a more obviously unrelated example).
    - rented_mule 3y ago
      > and then open each of those documents That alone ruled out doing anything like this on the device I'm talking about. The goal, which we reached, was to be able to search 1,000 documents in 5 seconds. Opening a document took nearly a second given the speed of our storage (a few KB/s). The search itself took about a second, and then we'd open up just enough of the documents to construct search result snippets as you paged through them.
Agentlien 3y ago
This reminds me of something I encountered when working on surgical training simulators about ten years ago. There was a function which needed to traverse a large (a few million vertices) mesh and, for each vertex, adjust its position to minimise some measurement. The original code, written by a colleague, just calculated in which direction to move it and then, in a loop, made changes of decreasing magnitude until it got close enough. This function was part of a performance bottleneck we had to solve, so I asked my colleague why he hadn't solved it analytically. He shrugged and said he hadn't bothered because this worked. So, I rewrote it, calculating the exact change needed and removing the loop. My code took twice as long. After analysing why, I realised with his heuristic most triangles required only 1 iteration and only a handful required at most 3. This was less work than the analytical solution which required a bunch of math including a square root.

fritzo 3y ago

Those are my favorite functions! Two lines of code with a page of text explaining why it works.

dharmab 3y ago

Similarly, a modder recently found that unrolling loops _hurt_ performance on the N64 because of RAM bus contention: https://www.youtube.com/watch?v=t_rzYnXEQlE https://www.youtube.com/watch?v=t_rzYnXEQlE

pclmulqdq 3y ago
Unrolled loops can also often hurt for the same reason on big server chips. It's not always clearly good to unroll your loops.

o11c 3y ago

... how does doing a full string dict lookup take less time than just checking a few trailing characters in a trie? For indexing it's okay to be aggressive since you can check again for the actual matches.

Exoristos 3y ago
> since you can check again for the actual matches. Can you explain this?
- o11c 3y ago
  An aggressive stemmer might stem both "generic" and "general" to "gener". Then if your query is "what documents contain 'generic'?", you look in the index for "gener" and then open each of those documents and check if it actually has "generic" using a stricter stemmer (that accepts generic{,s}, genericness{,es}, genericit{y,ies}, generically ... this is a bit of a bad example since they all have the prefix directly). The cost is acceptable as long as both words have about the same frequency so it doesn't affect the big O. Of course if you have any decent kind of compute, you can hard-code exceptions before building the index (which does mean you have to rebuild the index if your exception list changes ... or at least, the part of the index for the specific part of the trie whose exception lists changed - you don't do a global lookup!) to do less work at query time. But regardless, you still have to do some of this at query time to handle nasty cases like lie/lay/laid (searching for "lie" should not return "laid" or vice versa, but "lay" should match both of the others) or do/does/doe (a more obviously unrelated example).
  - rented_mule 3y ago
    > and then open each of those documents That alone ruled out doing anything like this on the device I'm talking about. The goal, which we reached, was to be able to search 1,000 documents in 5 seconds. Opening a document took nearly a second given the speed of our storage (a few KB/s). The search itself took about a second, and then we'd open up just enough of the documents to construct search result snippets as you paged through them.

Agentlien 3y ago

This reminds me of something I encountered when working on surgical training simulators about ten years ago. There was a function which needed to traverse a large (a few million vertices) mesh and, for each vertex, adjust its position to minimise some measurement. The original code, written by a colleague, just calculated in which direction to move it and then, in a loop, made changes of decreasing magnitude until it got close enough. This function was part of a performance bottleneck we had to solve, so I asked my colleague why he hadn't solved it analytically. He shrugged and said he hadn't bothered because this worked. So, I rewrote it, calculating the exact change needed and removing the loop. My code took twice as long. After analysing why, I realised with his heuristic most triangles required only 1 iteration and only a handful required at most 3. This was less work than the analytical solution which required a bunch of math including a square root.