Optimizing hash tables: hiding the hash code
This (and the older blog-post about backing stores[0]) are incredibly relevant to my LZ-string optimisations[1]. LZ-string takes an input string, builds a dictionary of substrings as it scans over the input, and outputs substring-tokens to a bit-stream, then converts that bit-stream into a new string.<p>How that dictionary is built is what is most relevant here: it is the greatest bottleneck in determining the speed of the algorithm. I have tried many variants. The ones that seem to work best match what is described here:<p>- instead of naively using sub-strings and dictionary lookup, build a trie[2] (putting all sub-strings in an object used as a flat dictionary quickly overflows the 1022-elements limit)<p>- instead of character strings, use charCodeAt[0] to use integer keys in the look-up of the trie (index with elements rather than hashcodes, and because JS strings are UTF16, the keys are <i>SMI</i>. It also removes string creation overhead).<p>- for a long time, I used <i>one</i> object for each node, with 0 as the key to look up its value, and charCode+1 to look up next nodes. In recent benchmarks it turned out that <i>{ v: val, d: {} }</i> is faster[4][5][6]. This makes sense because: <i>&quot;we don&#x27;t store information about present indexed properties on the HiddenClass&quot;</i> [0]. In other words: the new options creates a distinct hidden class compared to a plain object, which might be optimised. At the same time adding integer keys to a separate <i>d</i> object will not mess with this hidden class, preventing de-opts.<p>- for <i>really</i> fast performance except in a few degenerate cases, instead of key look-up, use an array with linear search (yes, really! Turns out compact arrays without holes are faster to the point where even linear search makes it worth it - up to a certain length).<p>So this explains a lot of <i>why</i> certain approaches work better than others. Some of the explanations here might let me optimise it even further, but at this point it would become hyper-optimized for V8. Are there some take-aways that I can generalise? And is there a similar blog for the other big javascript engines?<p>I expect that &quot;type stability&quot; - that is, maintaining identical hidden classes - is fairly universal for example.<p>[0] <a href="https:&#x2F;&#x2F;v8project.blogspot.se&#x2F;2017&#x2F;08&#x2F;fast-properties.html" rel="nofollow">https:&#x2F;&#x2F;v8project.blogspot.se&#x2F;2017&#x2F;08&#x2F;fast-properties.html</a><p>[1] <a href="https:&#x2F;&#x2F;github.com&#x2F;pieroxy&#x2F;lz-string&#x2F;pull&#x2F;98" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;pieroxy&#x2F;lz-string&#x2F;pull&#x2F;98</a><p>[2] <a href="https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Trie" rel="nofollow">https:&#x2F;&#x2F;en.wikipedia.org&#x2F;wiki&#x2F;Trie</a><p>[3] <a href="https:&#x2F;&#x2F;developer.mozilla.org&#x2F;en-US&#x2F;docs&#x2F;Web&#x2F;JavaScript&#x2F;Reference&#x2F;Global_Objects&#x2F;String&#x2F;charCodeAt" rel="nofollow">https:&#x2F;&#x2F;developer.mozilla.org&#x2F;en-US&#x2F;docs&#x2F;Web&#x2F;JavaScript&#x2F;Refe...</a><p>[4] <a href="https:&#x2F;&#x2F;run.perf.zone&#x2F;view&#x2F;LZ-String-2018-01-18-v2-1516198507426" rel="nofollow">https:&#x2F;&#x2F;run.perf.zone&#x2F;view&#x2F;LZ-String-2018-01-18-v2-151619850...</a><p>[5] <a href="https:&#x2F;&#x2F;run.perf.zone&#x2F;view&#x2F;LZ-String-2018-01-18-v1-1516197522874" rel="nofollow">https:&#x2F;&#x2F;run.perf.zone&#x2F;view&#x2F;LZ-String-2018-01-18-v1-151619752...</a><p>[6] <a href="https:&#x2F;&#x2F;github.com&#x2F;pieroxy&#x2F;lz-string&#x2F;pull&#x2F;98&#x2F;commits&#x2F;1894f7c3765f5544299727885cbb4d9cbadd5db5" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;pieroxy&#x2F;lz-string&#x2F;pull&#x2F;98&#x2F;commits&#x2F;1894f7c...</a>