bug-gnulib
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Non-opaque hamt type?


From: Bruno Haible
Subject: Re: Non-opaque hamt type?
Date: Sun, 18 Oct 2020 16:39:28 +0200
User-agent: KMail/5.1.3 (Linux/4.4.0-189-generic; KDE/5.18.0; x86_64; ; )

Hi Marc,

> At the moment, the header file exposes an opaque struct Hamt and
> communication with the code happens through (stack-allocated) pointers
> to a Hamt. In the implementation, however, each Hamt just consists of
> two pointers (a pointer to a function table and a pointer to the
> root), so stack-allocating Hamts instead and passing them around by
> values makes as much sense.
> 
> This would have the advantage of reducing heap allocation.

By how much does it reduce the heap allocation? Say, someone allocates
a HAMT and adds 100 entries. There will be heap allocations of ca. 5-10
buckets and internal nodes. Adding one more heap allocation for the
root object is not a tragedy.

So, in the end the question is whether to optimize the case of small HAMTs.

> The disadvantage would be that adding further fields to a Hamt in future
> extensions might be more problematic

True. But when this happens we can mitigate this through a warning in the
NEWS file.

> and that identity of Hamts cannot
> be decided through pointer identity anymore (so the protocol how to
> decide whether an element has been inserted or not has to be changed).

Does this protocol change introduce a significant slowdown?

Bruno




reply via email to

[Prev in Thread] Current Thread [Next in Thread]