Re: HASH_CHUNK_SIZE vs malloc rounding

On Tue, Nov 29, 2016 at 6:27 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> Thomas Munro <thomas(dot)munro(at)enterprisedb(dot)com> writes:
>> I bet other allocators also do badly with "32KB plus a smidgen". To
>> minimise overhead we'd probably need to try to arrange for exactly
>> 32KB (or some other power of 2 or at least factor of common page/chunk
>> size?) to arrive into malloc, which means accounting for both
>> nodeHash.c's header and aset.c's headers in nodeHash.c, which seems a
>> bit horrible. It may not be worth doing anything about.
>
> Yeah, the other problem is that without a lot more knowledge of the
> specific allocator, we shouldn't really assume that it's good or bad with
> an exact-power-of-2 request --- it might well have its own overhead.
> It is an issue though, and not only in nodeHash.c. I'm pretty sure that
> StringInfo also makes exact-power-of-2 requests for no essential reason,
> and there are probably many other places.

Right, enlargeStringInfo doubles the size whenever it runs out, a
common technique. Aside from the "plus a smidgen" thing mentioned
above, there is something else interesting about that: Andrew Koenig
wrote a widely referenced comp.lang.c++.moderated post[1] about why
you should probably use a growth factor of 1.5, and the topic comes up
from time to time in standard library implementation discussions[2].
I have no idea whether it really matters in reality and how the space
vs time trade off works with whatever actual string growth patterns
someone might be optimising for, but it's fun to think about...

[1] https://groups.google.com/forum/#!msg/comp.lang.c++.moderated/asH_VojWKJw/Lo51JEmLVboJ
[2] https://gcc.gnu.org/ml/libstdc++/2013-03/msg00058.html

--
Thomas Munro
http://www.enterprisedb.com