|Keep It Simple, Stupid
Re: Hash Search is VERY slowby dd-b (Monk)
|on Oct 02, 2021 at 03:00 UTC
Ooh, excellent timing, this thread is one thing I needed today. I'm just implementing something using several of the same tools and techniques, and while mine is enough smaller that writing it badly wouldn't be as severely punished--still, it's better to write it right, just for drill!
(The back of the envelope says my case might grow to 500K bytes, which on a system with 16GB of ram is just not something I'm going to worry about, even if the back of the envelope is off by an order of magnitude in growth. But still.)
In particular the fact that hash entries auto-vivify when referenced, and using that to make the pushing onto an array held in a hash entry vastly more efficient, is stuff I've seen the bits of repeatedly but mostly don't quite think of clearly enough to put them together in that order myself just by default. (The auto-vivification feels mysterious and I tend to avoid mysterious code when possible; but this case has big benefits.)