7 ms·

JavaScript Trie Performance Analysis

119 points by sant0sk1 16y ago

deleted 16y ago
[deleted]
- adamesque 16y ago
  …because although lookup performance is maximized and the amount of data sent over the wire is minimized, the processor time required to parse the data structure and the memory required to store it were both well out-of-bounds for the target device.
ot 16y ago
The reason why the Trie doesn't improve (and actually it does worse) is probably that the strings are too short. At an average of 5-6 characters per string, each one has size comparable to a single pointer. A way to make the plain string search faster would be to use binary search. It is possible to do it on a space separated string by jumping at a generic position of the string (which could be in the middle of a word) and going back to the rightmost space preceding the position. It is easy to see that the algorithm is correct and if the words have bounded length the runtime is still O(log n). BTW, by using a fair amount of succinct data structures and bit tricks it is possible to do way better than this: a succinct (binary) representation of the trie can use around 3 bits per node, and the labels can be compressed to 5-6 bits per label. However I would not implement that in JS :)
- jeresig 16y ago
  "A way to make the plain string search faster would be to use binary search." Isn't that premature optimization, though? As I noted in my post - lookups, even in the worst case, take less than a millisecond. Presumably someone could do that if they wanted even faster lookup performance, although I don't need it in this case. I definitely agree that a binary representation would probably get us pretty close to an ideal form - although I'm (as you are) skeptical that it could be done in a performant way in JavaScript.
  - ot 16y ago
    > Isn't that premature optimization, though? Yes of course it is, I should have started the sentence with "if performance becomes a concern". Since in the post you say "if you were building a game that required multitudes of dictionary lookups you might want to go with a faster hash or Trie technique" I just wanted to point out that binary search would probably work fine as well, without the huge memory increase.
    - jeresig 16y ago
      Ah yes - you're very right! I'm tempted to try fiddling around with a simple binary search across the string just to see what sort of performance characteristics it generates. I imagine that the result would be comparable to doing a Trie lookup (if a bit slower). Although, as mentioned before, we'll still have the file size overhead of the uncompressed string.
  - dunham 16y ago
    Are you just testing if words are members of a dictionary? If so, have you considered using a bloom filter? There is a slight chance of false positives, depending on how you choose your parameters, but it's a very compact way to store a set of strings. To make the initial parsing fast, but retain easy lookup I would store the bit vector in an ascii string, 6 bits per character, adding 32 to the raw value to get the character. The wikipedia article can guide you on the parameters needed to get an acceptable error rate and size.
    - jeresig 16y ago
      I looked into bloom filters after someone commented as such on my last post. I guess the possibility of false positives makes me a bit jumpy. I realize that it can be reduced with larger data structures but that prospect doesn't make me terribly excited (and having an as-close-to-zero-as-possible error rate would seem to create a significantly large data structure in the end - at least one that doesn't seem to provide much benefit over gzip compression). Although, please feel free to correct me if I'm wrong - if this does provide a tangible benefit with virtually no errors then I'd be very open to using this technique.
wingo 16y ago
It sounds like you need to build on the strengths of the JS implementations you care about, and encode your data structure in a string or something. Have a jump table in the beginning with the first characters, and then likewise for other characters, with some other convention to denote leafs. You won't be able to add to the trie, lookup won't be as fast, but it would still be O(log N) and parsing would be dead simple.
jrockway 16y ago
I love the idea of sharing the common suffixes.
pkeane 16y ago
http://www.w3.org/TR/IndexedDB/ http://www.w3.org/TR/IndexedDB/
- jeresig 16y ago
  (Saw that you also replied on my blog post, dumping my reply to you here, as well.) IndexedDB may help a bit in this case. It'll cut down on memory usage (at the cost of additional reads on the disk - which will likely increase battery usage on mobile devices) and <em>may</em> decrease search time. Although easily the biggest benefit of my current technique is that it's capable of easily using <code>localStorage</code> - and that has fantastic cross-browsers support (in contrast with IndexedDB, which doesn't).
eapen 16y ago
Great follow-up and appreciate the deep analysis with graphs. I am curious how you measure the Mobi Safari load times. Is there a tool (xcode?) to do this?
- jeresig 16y ago
  It was rather unglamorous - just loading the JavaScript string via Ajax and evaluating. I ran it on my iPhone 4 running iOS 4.3. Simple test is here: https://github.com/jeresig/trie-js/blob/master/load.html https://github.com/jeresig/trie-js/blob/master/load.html
  - eapen 16y ago
    Thanks, I assumed you would have some sophisticated tool that you use for benchmarks against jQuery mobile etc.
theycallmemorty 16y ago
This gave me fond memories of my second year university project where we had to implement a rudimentary spell checker and I wrote a Trie in C.
timtadh 16y ago
I wrote a implementation of Ternary Search Trie[1] in Python and found that for insert/update/delete I could get my performance to be on the same order to one order of magnitude slower than python built in dict. Considering that Tries offer a great base to build a flexible string matching algorithm off of I consider the prototype a success. The author's approach to optimizing the JavaScript trie is pretty good but there are still improvements that could be made. I would be curious to see if the Ternary approach could yield with interior node collapsing (like a Patricia Trie) would yield the performance the author is looking for. Also as @ot noted using 5-6 characters per string is too short for a Trie's strengths to really shine. They work better as the average length of string increases. [1] https://github.com/timtadh/tst https://github.com/timtadh/tst
euroclydon 16y ago
Any recommended articles on Javascript benchmarking, client and/or server?
davidst 16y ago
Here's an example of decoding and searching a DAWG in real-time in javascript. It encodes a dictionary of 106,495 words (an old Scrabble dictionary) into 427,982 base64 characters. http://www.davidst.com/jsanagram/ http://www.davidst.com/jsanagram/
- davidst 16y ago
  Note: This was an experiment to see if javascript could be fast enough to do this sort of thing. It was never finished. The count of anagrams should be updated and the crossword finder should be hooked up. Feel free to take it and hack on it if you like.

119 points by sant0sk1 16y ago

deleted 16y ago

[deleted]

adamesque 16y ago
…because although lookup performance is maximized and the amount of data sent over the wire is minimized, the processor time required to parse the data structure and the memory required to store it were both well out-of-bounds for the target device.

ot 16y ago

The reason why the Trie doesn't improve (and actually it does worse) is probably that the strings are too short. At an average of 5-6 characters per string, each one has size comparable to a single pointer. A way to make the plain string search faster would be to use binary search. It is possible to do it on a space separated string by jumping at a generic position of the string (which could be in the middle of a word) and going back to the rightmost space preceding the position. It is easy to see that the algorithm is correct and if the words have bounded length the runtime is still O(log n). BTW, by using a fair amount of succinct data structures and bit tricks it is possible to do way better than this: a succinct (binary) representation of the trie can use around 3 bits per node, and the labels can be compressed to 5-6 bits per label. However I would not implement that in JS :)

jeresig 16y ago
"A way to make the plain string search faster would be to use binary search." Isn't that premature optimization, though? As I noted in my post - lookups, even in the worst case, take less than a millisecond. Presumably someone could do that if they wanted even faster lookup performance, although I don't need it in this case. I definitely agree that a binary representation would probably get us pretty close to an ideal form - although I'm (as you are) skeptical that it could be done in a performant way in JavaScript.
- ot 16y ago
  > Isn't that premature optimization, though? Yes of course it is, I should have started the sentence with "if performance becomes a concern". Since in the post you say "if you were building a game that required multitudes of dictionary lookups you might want to go with a faster hash or Trie technique" I just wanted to point out that binary search would probably work fine as well, without the huge memory increase.
  - jeresig 16y ago
    Ah yes - you're very right! I'm tempted to try fiddling around with a simple binary search across the string just to see what sort of performance characteristics it generates. I imagine that the result would be comparable to doing a Trie lookup (if a bit slower). Although, as mentioned before, we'll still have the file size overhead of the uncompressed string.
- dunham 16y ago
  Are you just testing if words are members of a dictionary? If so, have you considered using a bloom filter? There is a slight chance of false positives, depending on how you choose your parameters, but it's a very compact way to store a set of strings. To make the initial parsing fast, but retain easy lookup I would store the bit vector in an ascii string, 6 bits per character, adding 32 to the raw value to get the character. The wikipedia article can guide you on the parameters needed to get an acceptable error rate and size.
  - jeresig 16y ago
    I looked into bloom filters after someone commented as such on my last post. I guess the possibility of false positives makes me a bit jumpy. I realize that it can be reduced with larger data structures but that prospect doesn't make me terribly excited (and having an as-close-to-zero-as-possible error rate would seem to create a significantly large data structure in the end - at least one that doesn't seem to provide much benefit over gzip compression). Although, please feel free to correct me if I'm wrong - if this does provide a tangible benefit with virtually no errors then I'd be very open to using this technique.

wingo 16y ago

It sounds like you need to build on the strengths of the JS implementations you care about, and encode your data structure in a string or something. Have a jump table in the beginning with the first characters, and then likewise for other characters, with some other convention to denote leafs. You won't be able to add to the trie, lookup won't be as fast, but it would still be O(log N) and parsing would be dead simple.

jrockway 16y ago

I love the idea of sharing the common suffixes.

pkeane 16y ago

http://www.w3.org/TR/IndexedDB/ http://www.w3.org/TR/IndexedDB/

jeresig 16y ago
(Saw that you also replied on my blog post, dumping my reply to you here, as well.) IndexedDB may help a bit in this case. It'll cut down on memory usage (at the cost of additional reads on the disk - which will likely increase battery usage on mobile devices) and <em>may</em> decrease search time. Although easily the biggest benefit of my current technique is that it's capable of easily using <code>localStorage</code> - and that has fantastic cross-browsers support (in contrast with IndexedDB, which doesn't).

eapen 16y ago

Great follow-up and appreciate the deep analysis with graphs. I am curious how you measure the Mobi Safari load times. Is there a tool (xcode?) to do this?

jeresig 16y ago
It was rather unglamorous - just loading the JavaScript string via Ajax and evaluating. I ran it on my iPhone 4 running iOS 4.3. Simple test is here: https://github.com/jeresig/trie-js/blob/master/load.html https://github.com/jeresig/trie-js/blob/master/load.html
- eapen 16y ago
  Thanks, I assumed you would have some sophisticated tool that you use for benchmarks against jQuery mobile etc.

theycallmemorty 16y ago

This gave me fond memories of my second year university project where we had to implement a rudimentary spell checker and I wrote a Trie in C.

timtadh 16y ago

I wrote a implementation of Ternary Search Trie[1] in Python and found that for insert/update/delete I could get my performance to be on the same order to one order of magnitude slower than python built in dict. Considering that Tries offer a great base to build a flexible string matching algorithm off of I consider the prototype a success. The author's approach to optimizing the JavaScript trie is pretty good but there are still improvements that could be made. I would be curious to see if the Ternary approach could yield with interior node collapsing (like a Patricia Trie) would yield the performance the author is looking for. Also as @ot noted using 5-6 characters per string is too short for a Trie's strengths to really shine. They work better as the average length of string increases. [1] https://github.com/timtadh/tst https://github.com/timtadh/tst

euroclydon 16y ago

Any recommended articles on Javascript benchmarking, client and/or server?

davidst 16y ago

Here's an example of decoding and searching a DAWG in real-time in javascript. It encodes a dictionary of 106,495 words (an old Scrabble dictionary) into 427,982 base64 characters. http://www.davidst.com/jsanagram/ http://www.davidst.com/jsanagram/

davidst 16y ago
Note: This was an experiment to see if javascript could be fast enough to do this sort of thing. It was never finished. The count of anagrams should be updated and the crossword finder should be hooked up. Feel free to take it and hack on it if you like.