5 ms·

gperf enters the chat https://www.gnu.org/software/gperf/ https://www.gnu.org/software/gperf/ For C++ users, frozen is also a possibility: https://github.com/

by rwmj 4y ago

gperf enters the chat https://www.gnu.org/software/gperf/ https://www.gnu.org/software/gperf/ For C++ users, frozen is also a possibility: https://github.com/serge-sans-paille/frozen https://github.com/serge-sans-paille/frozen

anonymoushn 4y ago
But how many ns per query?
- SloopJon 4y ago
  On my system (Windows 10, i7-10700K, Clang 11 with Visual C++ 2017 linker), frozen::unordered_set takes about 10ns. This is faster than std::unordered_set at 14ns, but slower than direct comparison at 6ns.
mananaysiempre 4y ago
While gperf (unlike, say, CMPH[1]) is also intended for small sets of short strings, I expect the difference here is in the definition of “small”: in the article, it’s six, whereas in gperf’s intended application, it’s more like six dozen (and CMPH’s “large” is thousands to millions). [1] https://cmph.sourceforge.net/gperf.html https://cmph.sourceforge.net/gperf.html
- rurban 4y ago
  I've optimized gperf and nbperf to such small sets. I also add the padding, when it helps in the hash and comparison. cmph has an extremely large constant overhead. https://github.com/rurban/nbperf https://github.com/rurban/nbperf https://github.com/rurban/gperf https://github.com/rurban/gperf
malkia 4y ago
I worked on a game port (PS1->PC) and all (game object) strings were hashed using 16-bit hash and code directly checked their 16-bit values against them in the code, but unlike "gperf" there was no perect hash, just some standard routine (forgot what it was). So it made me wonder (initially) when some objects were named differently - like instead of chara, it was chara2 or chara5 (no 1, 3 or 4) - e.g. find a name where when hashed won't result in collision... then again it was super fast and just using 16-bits so win overall... Later in another studio we had some DB with collisions (32-bits) such that you don't introduce some string that would cause collision with existing.
- malkia 4y ago
  Now obviously this won't work with external names, like http, https, etc. - but worked pretty good when all these names are under your control.

by rwmj 4y ago

anonymoushn 4y ago

But how many ns per query?

SloopJon 4y ago
On my system (Windows 10, i7-10700K, Clang 11 with Visual C++ 2017 linker), frozen::unordered_set takes about 10ns. This is faster than std::unordered_set at 14ns, but slower than direct comparison at 6ns.

mananaysiempre 4y ago

While gperf (unlike, say, CMPH[1]) is also intended for small sets of short strings, I expect the difference here is in the definition of “small”: in the article, it’s six, whereas in gperf’s intended application, it’s more like six dozen (and CMPH’s “large” is thousands to millions). [1] https://cmph.sourceforge.net/gperf.html https://cmph.sourceforge.net/gperf.html

rurban 4y ago
I've optimized gperf and nbperf to such small sets. I also add the padding, when it helps in the hash and comparison. cmph has an extremely large constant overhead. https://github.com/rurban/nbperf https://github.com/rurban/nbperf https://github.com/rurban/gperf https://github.com/rurban/gperf

malkia 4y ago

I worked on a game port (PS1->PC) and all (game object) strings were hashed using 16-bit hash and code directly checked their 16-bit values against them in the code, but unlike "gperf" there was no perect hash, just some standard routine (forgot what it was). So it made me wonder (initially) when some objects were named differently - like instead of chara, it was chara2 or chara5 (no 1, 3 or 4) - e.g. find a name where when hashed won't result in collision... then again it was super fast and just using 16-bits so win overall... Later in another studio we had some DB with collisions (32-bits) such that you don't introduce some string that would cause collision with existing.

malkia 4y ago
Now obviously this won't work with external names, like http, https, etc. - but worked pretty good when all these names are under your control.