Has anyone seen this video?

https://www.youtube.com/watch?v=DMQ_HcNSOAI

additional reddit discussion:

https://www.reddit.com/r/rust/comments/11r26x1/faster_than_rust_and_c_the_perfect_hash_table/

Custom hash aside, I had no idea about gperf or that it was so blazing fast.

I wonder how easy it would be to slap it into D to test. Do you just override the toHash function in your objects or is there more to it?

On Monday, 11 December 2023 at 03:25:15 UTC, Christopher Katko wrote:

The "faster than Rust" achievement doesn't mean much in reality, because the hash function in Rust is DoS-resistant by default. There's an old bug about a related issue in D: https://issues.dlang.org/show_bug.cgi?id=7179

D language lacks flexibility in this area and replacing the built-in associative arrays hash function doesn't seem like an easy task. Moreover, there's now the https://dlang.org/changelog/2.106.0.html#dmd.static-assoc-array feature and CTFE makes everything even more tricky. Reminds me of the old prelink vs. ASLR dilemma: https://lwn.net/Articles/190139/

One the other hand, it's possible to leave the built-in associative arrays alone and design a custom container class with a custom hash function. Tailored either for maximum performance or for DoS-resistance.

On Monday, 11 December 2023 at 03:25:15 UTC, Christopher Katko wrote:

To fork on that subject... I was very "gperf-like-perfecthash-friendly" for years but nowadays I use lookuptables. Very fast too. You have Trie or suffix arrays that are very fast too but they tend not to be memory friendly.

On Monday, 11 December 2023 at 11:36:10 UTC, Basile.B wrote:

If the whole set of the string identifiers to be parsed is known at compile time, then another approach for mapping them to numbers or whatever else is to use something like https://re2c.org

On Monday, 11 December 2023 at 12:37:56 UTC, Siarhei Siamashka wrote:

Sorry but that sound a bit like "let's rely on a library, let's not know how that works" ;)

Holy crap! I was thinking about this kind of thing a few months ago. My situation is this:

• I have textures (filename = string texturename) listed in a manfiest.json file.
• all textures are loaded and placed into an texture[string] associative array
• they're used in code that ends up being like drawBitmap(bitmaps["grass"], ...)

It lets me immediately add a new texture, add one line to the manifest, and I can call it from my code. (I could do filename = stringname automatically but that doesn't let me do things like pack textures into atlases to reduce texture swaps so that kind of automatic filename scanning isn't applicable.)

Noting that:

• technically, a finite list of all potentially used texture names in code should be knowable to the compiler.
• the list does not change at run time.

I had thought about trying some sort of D-based compile-time, or, manual tool-based lexing to build say, an enum, and replacing all those names from "grass01" to GRASS01=17.

But I was also wondering if simply getting a faster container would improve things. Because one flaw there is if I ever support mods, then I do not at compile time know the total maximum set of texture name entries.

Still, once all my texture entries are received they don't change after loading (even if I load-in assets based on scene requirements, the names will never swap/reorder. Even if grass01 texture isn't loaded, it can still have the name grass01 reserved. There are no key deletions or changes once set. So grass01 could simply be a null pointer until loaded.)

Awhile back, during some profiling, D Associative Arrays were way higher up in total CPU usage in my game than they should have been compared to the act of drawing entire textures. Like in the top 7. BUT, as I'm thinking right now, I'm wondering if now the profiling measuring code itself was inflating those AA accesses (a tiny real code compared to overhead of logging code).

Hmm, so it looks like a part of what I'm thinking of, is called a "perfect hash function".

https://en.wikipedia.org/wiki/Perfect_hash_function

And I probably could still generate one, based on known a load-time constant such as all the names/set of all textures in game+[loaded mods].

I wonder if using const strings keys (e.g. "grass01") in my code is a significant slowdown compared to an int key. I should probably do some benchmarks. Because if they are, maybe I could do some tokenization pass converting all strings into ints. But if I'm adding an entire parsing copy-paste step to my makefile, it better be for a significant improvement to justify the complexity, maintainability, etc.

And of course, what to do about modding adding stuff without recompiling.

I'm just looking into what all my options are given various constraints.

On Monday, 11 December 2023 at 12:37:56 UTC, Siarhei Siamashka wrote:

Sorry for the inaccuracy. This is part of what a compiler uses to generate the code to switch over a string. This is not used at run-time.

Generated code is more like: https://godbolt.org/z/Y54bKeWYe

What is used at run-time is: https://gitlab.com/styx-lang/styx/-/blob/master/library/rtl.sx?ref_type=heads#L426

In fine you have decimated a string into a unique number and you just take the path of a normal switch. The decimation is not very different of hashing. Just it's guaranteed to give unique indexes for a set of unique strings.

I believe D uses a different strategy for that. Binary search IIRC. not quite sure.

Anyway just to clarify.