Perfect hashing with hashify

[xamgore]

So, it turns out there are more than one approach for perfect hashing. Hashify is one of those.

For large tables they promise to be at least 40% more performant, while decreasing the compilation time. I think it worth a try.

---

I am working on this one, as I wanna play with build.rs mechanics. But can't run unescape benchmarks to compare results. There must be some features to be included, which I can't figure out.

[xamgore]

I have tried the crate and considering the noise threshold = 10%, results are good enough:

unescape/unescape_slow/sample_128_normal
                 change:
                        time:   [-5.4879% -5.2733% -5.0280%] (p = 0.00 < 0.01)
                        thrpt:  [+5.2942% +5.5669% +5.8066%]

unescape/unescape_attribute_slow/sample_128_normal
                 change:
                        time:   [-6.6267% -6.4116% -6.2112%] (p = 0.00 < 0.01)
                        thrpt:  [+6.6226% +6.8508% +7.0970%]

unescape/unescape_slow/sample_128_bare
                 change:
                        time:   [-19.504% -19.265% -19.013%] (p = 0.00 < 0.01)
+                       thrpt:  [+23.477% +23.862% +24.230%]

unescape/unescape_attribute_slow/sample_128_bare
                 change:
                        time:   [+8.8047% +9.1306% +9.4847%] (p = 0.00 < 0.01)
-                       thrpt:  [-8.6630% -8.3667% -8.0922%]

unescape/unescape_slow/sample_128_none
                 change:
                        time:   [-0.0003% +0.2743% +0.5688%] (p = 0.01 > 0.01)
                        thrpt:  [-0.5656% -0.2736% +0.0003%]

unescape/unescape_attribute_slow/sample_128_none
                 change:
                        time:   [-0.4180% -0.1345% +0.1508%] (p = 0.23 > 0.01)
                        thrpt:  [-0.1506% +0.1347% +0.4198%]

unescape/unescape_slow/sample_128_invalid
                 change:
                        time:   [-25.087% -24.867% -24.620%] (p = 0.00 < 0.01)
+                       thrpt:  [+32.661% +33.097% +33.488%]

unescape/unescape_attribute_slow/sample_128_invalid
                 change:
                        time:   [+6.0339% +6.3088% +6.5929%] (p = 0.00 < 0.01)
-                       thrpt:  [-6.1851% -5.9344% -5.6905%]

On M3 MAX, matchgen is 2-4x faster. Don't know how and why 😄

[xamgore]

Ok, there is also quickphf.

[danielparks]

Looks like quickphf is abandoned — it hasn’t been updated in almost 2 years, and to use it we would need dtrifuno/quickphf#5 to be merged.

Regarding hashify: the benchmarks are somewhat inconsistent, but I think it probably is faster than phf. In particular, I don’t understand why unescape_attribute() performs the way it does. See the graphs below.

I’m working on this in PR #110, which builds on @xamgore’s commit from #83.

Just getting an entry from the hash

Plus doing an expansion with matchgen.

Using the various strategies in unescape()

Using the various strategies in unescape_attribute()

[xamgore]

In particular, I don’t understand why unescape_attribute() performs the way it does.

It does look weird, but maybe it's all about memory?

matchgen is consistent, as it's probably just a bunch of JMPs fit into one or two L1/L2/L3 cache lines. The match-case tree is hierarchical, so top-level matches could be in the first line, and starting from the level N there can be a cache line per subtree.

I believe, it's not like that with all those phfs. There are two parts: a perfect hashing function and the map itself. The map is presented in the form (value, hash, key?), while the perfect hashing function is constructed as composition of simpler functions. I haven't read the paper yet, but suppose it may be big. The takeaway is, task switches are costly for L1-L2-L3 cache.

Ordinary unescape has a loop around ENTITIES.get, while unescape_attribute fetches the table once. At scale unescape has better utilization of the same memory region, thus the shift to the right on unescape_attribute graph.