Shrinking Ruby Hashes
8 points by raymii
8 points by raymii
Some nice intricate work here.
I was left wondering what rebuilds_num is for, i.e., what is the purpose of keeping track of rebuilds? It’s a relatively big field (compared to, say, entries_start which is discussed in detail) so I expected it would be a good target for shrinking.
Good question.
Since Ruby is a very dynamic language, when looking up a key in a Hash, it has to invoke #hash and #eql? methods on objects.
And these methods can be arbitrary code, which means they can add or remove entries from the hash-table being looked up, which in turn could cause a "rebuild" of the table, meaning the entries list may be reallocated and gaps between entries removed.
Hence Ruby has to be able to detect such case to avoid use-after free and similar errors.
You can see an example of that here: https://github.com/ruby/ruby/blob/fb7a2465c458167c82b426f8e2b5bfa48dccc213/st.c#L1637
And yes indeed, a full 32-bit integer for that is pushing it. I didn't mention it in the post, but I did consider making rebuilds_num 8-bit and entries_start 32-bit. I probably should, but I'm not sure it matters that much to be honest, aside from the very rarely used Hash#shift, it's hard to imagine entries_start reaching 255.