svn commit: r303746 - head/usr.bin/indent

[Ed Schouten]

Hi Piotr,

2016-08-07 10:19 GMT+02:00 Piotr Stefaniak <email at piotr-stefaniak.me>:
> The most important conclusion, though, is that at least the glibc
> implementation imposes an arbitrary limit on how many items you can add
> to the data structure:
>         The argument nel specifies the maximum number of entries in the table.
> (This  maximum  cannot be changed later, so choose it wisely.)
> Adding new items to the data structure (or searching them - I didn't
> investigate) actually _stopped working_ when approximately /nel/ number
> of elements was reached (I accidentally set it to 2000 while PostgreSQL
> has nearly 3000 typedef names). I don't know if FreeBSD's implementation
> does the same, but it's a show-stopper to me anyway, so personally I
> won't be pursuing this idea of replacing bsearch() with hsearch().

Yeah, that's quite annoying. Both the hsearch() implementation of
FreeBSD <11.0 and glibc seem to have a strong disregard of data
structure theory. FreeBSD <11.0 uses a fixed size hash table with
chaining. glibc also uses a fixed size, but doesn't even do chaining,
meaning that there is a hard limit on the number of elements that can
be stored. It also becomes incredibly slow by the time it gets close
to full.

In FreeBSD 11.0 I replaced our implementation by one that runs in
constant time per operation (expected and amortised) and also has no
fixed limit on the number of elements it can store. In fact, it even
ignores the size hint that you provide. Source code:

https://svnweb.freebsd.org/base/head/lib/libc/stdlib/hcreate_r.c?view=markup
https://svnweb.freebsd.org/base/head/lib/libc/stdlib/hdestroy_r.c?view=markup
https://svnweb.freebsd.org/base/head/lib/libc/stdlib/hsearch_r.c?view=markup

My guess is that it's faster than bsearch() in this specific case, but
if Linux compatibility is important, then I'd say we'd better stick to
bsearch().

Thanks for sharing your thoughts!

-- 
Ed Schouten <ed at nuxi.nl>
Nuxi, 's-Hertogenbosch, the Netherlands
KvK-nr.: 62051717