Replace implementation of hsearch() by one that scales.

[ed]

Summary

Traditionally the hcreate() function creates a hash table that uses
chaining, using a fixed user-provided size. The problem with this
approach is that this often either wastes memory (table too big) or
yields bad performance (table too small). For applications it may not
always be easy to estimate the right hash table size. A fixed number
only increases performance compared to a linked list by a constant
factor.

This problem can be solved easily by dynamically resizing the hash
table. If the size of the hash table is at least doubled, this has no
negative on the running time complexity. If a dynamically sized hash
table is used, we can also switch to using open addressing instead of
chaining, which has the advantage of just using a single allocation for
the entire table, instead of allocating many small objects.

Finally, a problem with the existing implementation is that its
deterministic algorithm for hashing makes it possible to come up with
fixed patterns to trigger an excessive number of collisions. We can
easily solve this by using FNV-1a as a hashing algorithm in combination
with a randomly generated offset basis.

Measurements have shown that this implementation is about 20-25% faster
than the existing implementation (even if the existing implementation is
given an excessive number of buckets). Though it allocates more memory
through malloc() than the old implementation (between 4-8 pointers per
used entry instead of 3), process memory use is similar to the old
implementation as if the estimated size was underestimated by a factor

10. This is due to the fact that malloc() needs to perform less

bookkeeping.

Test Plan

The existing ATF/Kyua tests that we've inherited from NetBSD all seem to
work.

[jilles]

Looks good to me.

The change to struct hsearch_data's size is only possible because this API is not yet in a release. Although hsearch_r is not used very much, I expect struct hsearch_data to be embedded in other structures.

Unfortunately, even hsearch_r is unusable in most applications since it does not allow removing a single entry, only all entries at once.

[pfg]

lib/libc/stdlib/hcreate_r.c

48

I don't like the 16 or any other magic number: I would prefer something depending like nel/2 or nel/3.
Not a showstopper though.

[ed]

In D4644#99619, @jilles wrote:

The change to struct hsearch_data's size is only possible because this API is not yet in a release. Although hsearch_r is not used very much, I expect struct hsearch_data to be embedded in other structures.

Exactly!

Unfortunately, even hsearch_r is unusable in most applications since it does not allow removing a single entry, only all entries at once.

Yes. That's pretty annoying. Fortunately, it also works to our advantage in this case. If it's possible to delete entries from hash tables, it becomes harder to use open addressing schemes. You'd need to mark entires as deleted and likely apply some periodic scrubbing/rebuilding of the hash table.

[ed]

lib/libc/stdlib/hcreate_r.c

48

As I mentioned through private mail: using a value based on nel has the disadvantage that it blows up memory use in case the hint is not fully accurate. My gut feeling is that there are many callers of hcreate_r() that just pass in a hint of what the upper bound may be, without actually knowing what it's going to be. By using a value based on nel, we already allocate a large hash table that may likely not be used at all.

Also, there is no gain in doing this. Say, nel is accurate and we'd use nel / 3 as you'd propose. As the resulting hash table eventually grows to be between twice and four times as large as nel, it means that the hash table needs to be reallocated at least three times. As resizing becomes twice as expensive at every step, that means that we only gain 1/2^3 = 12.5% of the CPU cycles on hash table resizing. My guess is that we spend at most half of the cycles of hsearch_r() on resizing tops, so you'd only see a performance improvement of at most 6%. A 6% gain, while potentially wasting a lot of memory.

Finally, keep in mind that the hash table always has to have a size of 2^k, for the reason that the quadratic probing scheme used by this implementation does not guarantee accessing all of the elements when the hash table for arbitrary sizes.

Ignoring the hint should not be treated as some form of laziness; this implementation actually does it on purpose.

[pfg]

Just for reference (and I hate phabricator doesn't let me reply to your reply);

According to the linux manpage the value of nel is always bigger than expected. The implementation in glibc used to say:
"The hcreate() function shall allocate sufficient space for the table, and the application shall ensure it is called before hsearch() is used. The nel argument is an estimate of the maximum number of entries that the table shall contain. This number may be adjusted upward by the algorithm in order to obtain certain mathematically favorable circumstances."

Now it says
"Hash table implementations are usually more efficient when the table contains enough free space to minimize collisions. Typically, this means that nel should be at least 25% larger than the maximum number of elements that the caller expects to store in the table. "

What I dislike about magic numbers is that 16 will almost always be the wrong value and the main advantage of your implementation is that it is indeed scalable. If we take the 25% hint from the linux page then we could use 3*nel/4, which is probably a better guess. But anything we take is just a guess so I am not insisting on this.

[ed]

In D4644#99648, @pfg wrote:>

What I dislike about magic numbers is that 16 will almost always be the wrong value [...]

Keep in mind that 16 is just an arbitrary small power-of-two that I picked. Any other power-of-two will do, even 1. Zero won't work, as hsearch_r() requires the table to exist to not crash. If you prefer a different constant, just let me know.

[pfg]

In D4644#99649, @ed wrote:

In D4644#99648, @pfg wrote:>

What I dislike about magic numbers is that 16 will almost always be the wrong value [...]

Keep in mind that 16 is just an arbitrary small power-of-two that I picked. Any other power-of-two will do, even 1. Zero won't work, as hsearch_r() requires the table to exist to not crash. If you prefer a different constant, just let me know.

Precisely, if I say 256 still I will be wrong for many cases.
Just an idea ... if we could round down the nearest power of 2 from nel, that would be a good estimate for someone that guessed within 100% accuracy and we can still scale otherwise.

[ed]

In D4644#99653, @pfg wrote:

[...] that would be a good estimate [...]

No. As I already mentioned numerous times, the nel argument of hcreate() is not a good estimate of the number of elements that will be placed in the hash table. Any heuristic that we're going to invent here based on that value is not going to help us in any way.

Leaving the initial hash table size set to 16.

[pfg]

In D4644#99668, @ed wrote:

In D4644#99653, @pfg wrote:

[...] that would be a good estimate [...]

No. As I already mentioned numerous times, the nel argument of hcreate() is not a good estimate of the number of elements that will be placed in the hash table. Any heuristic that we're going to invent here based on that value is not going to help us in any way.

Just to clarify with an example: .. say user specifies nel = 500 but in really the program ends up only needing 300, 16 is bad choice, a heuristic chooses 256 which not perfect, but better.
If the user had specified nel < 300, the code would be broken on other platforms and wouldn't be portable.

The idea is not to get a perfect value, but to hopefully not scale more that once (unless the code is broken/non-portable).

Leaving the initial hash table size set to 16.

Hmm ... that's fine ... I said it was not a show stopper, just that it could be more efficient. OTOH, this API is not very used so spending more time on this is a waste of time.