4 ms·

Great explanation and practical sample of javascript features + HTML5's local storage. The only thing missing was converting the dictionary data into a trie. ;

by eapen 16y ago

Great explanation and practical sample of javascript features + HTML5's local storage. The only thing missing was converting the dictionary data into a trie. ;-)

pmjordan 16y ago
The only thing missing was converting the dictionary data into a trie. ;-) That's what I was thinking. I wonder what the memory and download footprint for that would be in practice. Considering characters are represented by string objects in JavaScript, it could get expensive, unless the runtime interns short strings. If not, you could represent single letters with integers, which are almost certainly interned or even use a non-pointer representation. All those objects at each tree level might be a bit much though.
- rudiger 16y ago
  Less than a naive dictionary; it's a very compact and natural representation of ordered lists of unique words.
  - pmjordan 16y ago
    I realise that, I'm interested in the per-object overhead. This approaches zero for the single giant string.
    - rudiger 16y ago
      Take a look at Saurabh Odhyan's JavaScript prefix trie implementation; https://github.com/odhyan/trie https://github.com/odhyan/trie
- jerf 16y ago
  In this situation, I'd seriously consider throwing down a binary blob as a string that directly represents this data as whatever fancy structure you want and writing the small handful of functions it would take to traverse that "string" to do the lookup. Then you can do whatever optimal thing you want and memory usage is very predictable. Technically this is what his final solution converged on, it's just the least fancy "fancy structure" there is. It's a last resort, certainly, but in certain cases it's the simplest answer. Be aware of encoding issues, though; UTF-8 technically can't carry arbitrary binaries and you may have to work around some things a bit.
  - jacobolus 16y ago
    I'd recommend sending base64'd data down. Use this to encode/decode from javascript strings of 1-byte-per-character data: https://github.com/mcarter/js.io/blob/master/packages/std/base64.js https://github.com/mcarter/js.io/blob/master/packages/std/ba...
    - gojomo 16y ago
      FYI, many browsers offer (native) 'atob()' and 'btoa()' functions for Base64 encode/decode that will outperform that JS code.
      - deleted 16y ago
        [deleted]
      - tjarratt 16y ago
        For what it's worth, the linked code on github appears to be specific to node.js. Last I checked, there was no native function to convert strings to and from base64, only buffers. If you're writing this for client side, it would indeed be preferable to use the native functions.
jeresig 16y ago
Thanks for the Trie suggestion! I’ll do a follow-up post and talk about that specifically. Note that this post was mostly written to get people thinking about practical forms of optimization (that hopefully transcend dictionaries themselves – which only have limited applications in JavaScript applications). I’ll definitely do another post digging deeper into dictionary lookups themselves. Thanks!
- eapen 16y ago
  I didn't expect you to do that and was joking (hence the wink) but it would be amazing to see it AT work. If you had added the Trie in this post, it would have probably been over the average human threshold of patience and understanding.
shazow 16y ago
While a Trie is the "correct" datastructure with appropriate storage techniques, you have to be careful when your hands are tied regarding what datastructure you build it on top of. When I benchmarked a Trie implementation using dicts of dicts in Python, and I found that the memory usage was an order of magnitude higher than just having a set or list of strings (2mb vs ~100kb), while the performance difference was negligible. I ended up going with a set. The issue is that each layer per node has 26+ instances of your core object struct (whether it's a list or a dict), so any overhead gets ballooned really fast.
- wisty 16y ago
  You can get around that by using an array, and having functions to get and set parts of the array. That stops the object overhead in python from killing memory. But it's not the prettiest way to do things.

by eapen 16y ago

Great explanation and practical sample of javascript features + HTML5's local storage. The only thing missing was converting the dictionary data into a trie. ;-)

pmjordan 16y ago

The only thing missing was converting the dictionary data into a trie. ;-) That's what I was thinking. I wonder what the memory and download footprint for that would be in practice. Considering characters are represented by string objects in JavaScript, it could get expensive, unless the runtime interns short strings. If not, you could represent single letters with integers, which are almost certainly interned or even use a non-pointer representation. All those objects at each tree level might be a bit much though.

rudiger 16y ago
Less than a naive dictionary; it's a very compact and natural representation of ordered lists of unique words.
- pmjordan 16y ago
  I realise that, I'm interested in the per-object overhead. This approaches zero for the single giant string.
  - rudiger 16y ago
    Take a look at Saurabh Odhyan's JavaScript prefix trie implementation; https://github.com/odhyan/trie https://github.com/odhyan/trie
jerf 16y ago
In this situation, I'd seriously consider throwing down a binary blob as a string that directly represents this data as whatever fancy structure you want and writing the small handful of functions it would take to traverse that "string" to do the lookup. Then you can do whatever optimal thing you want and memory usage is very predictable. Technically this is what his final solution converged on, it's just the least fancy "fancy structure" there is. It's a last resort, certainly, but in certain cases it's the simplest answer. Be aware of encoding issues, though; UTF-8 technically can't carry arbitrary binaries and you may have to work around some things a bit.
- jacobolus 16y ago
  I'd recommend sending base64'd data down. Use this to encode/decode from javascript strings of 1-byte-per-character data: https://github.com/mcarter/js.io/blob/master/packages/std/base64.js https://github.com/mcarter/js.io/blob/master/packages/std/ba...
  - gojomo 16y ago
    FYI, many browsers offer (native) 'atob()' and 'btoa()' functions for Base64 encode/decode that will outperform that JS code.
    - deleted 16y ago
      [deleted]
    - tjarratt 16y ago
      For what it's worth, the linked code on github appears to be specific to node.js. Last I checked, there was no native function to convert strings to and from base64, only buffers. If you're writing this for client side, it would indeed be preferable to use the native functions.

jeresig 16y ago

Thanks for the Trie suggestion! I’ll do a follow-up post and talk about that specifically. Note that this post was mostly written to get people thinking about practical forms of optimization (that hopefully transcend dictionaries themselves – which only have limited applications in JavaScript applications). I’ll definitely do another post digging deeper into dictionary lookups themselves. Thanks!

eapen 16y ago
I didn't expect you to do that and was joking (hence the wink) but it would be amazing to see it AT work. If you had added the Trie in this post, it would have probably been over the average human threshold of patience and understanding.

shazow 16y ago

While a Trie is the "correct" datastructure with appropriate storage techniques, you have to be careful when your hands are tied regarding what datastructure you build it on top of. When I benchmarked a Trie implementation using dicts of dicts in Python, and I found that the memory usage was an order of magnitude higher than just having a set or list of strings (2mb vs ~100kb), while the performance difference was negligible. I ended up going with a set. The issue is that each layer per node has 26+ instances of your core object struct (whether it's a list or a dict), so any overhead gets ballooned really fast.

wisty 16y ago
You can get around that by using an array, and having functions to get and set parts of the array. That stops the object overhead in python from killing memory. But it's not the prettiest way to do things.