Date: Sun, 7 Aug 2016 14:15:29 +0200 From: Ed Schouten <ed@nuxi.nl> To: Piotr Stefaniak <email@piotr-stefaniak.me> Cc: Pedro Giffuni <pfg@freebsd.org>, src-committers <src-committers@freebsd.org>, "svn-src-all@freebsd.org" <svn-src-all@freebsd.org>, "svn-src-head@freebsd.org" <svn-src-head@freebsd.org> Subject: Re: svn commit: r303746 - head/usr.bin/indent Message-ID: <CABh_MKkZaCcSJHQtYCfXxLsUtTQxp3j_1sBScWMfnkoceVcyBQ@mail.gmail.com> In-Reply-To: <VI1PR0901MB150127A162620B7A73B1C3EB851A0@VI1PR0901MB1501.eurprd09.prod.outlook.com> References: <201608041527.u74FR9xo083057@repo.freebsd.org> <CABh_MKkD2N4YXEJGHA14zavYuF_PmwDei6tjKTm4kC4mr1MY=Q@mail.gmail.com> <54ec1a67-177b-9fb7-ad2a-b3f371926cc5@FreeBSD.org> <VI1PR0901MB150127A162620B7A73B1C3EB851A0@VI1PR0901MB1501.eurprd09.prod.outlook.com>
next in thread | previous in thread | raw e-mail | index | archive | help
Hi Piotr, 2016-08-07 10:19 GMT+02:00 Piotr Stefaniak <email@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@nuxi.nl> Nuxi, 's-Hertogenbosch, the Netherlands KvK-nr.: 62051717
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CABh_MKkZaCcSJHQtYCfXxLsUtTQxp3j_1sBScWMfnkoceVcyBQ>