[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
- Re: HAMT iterators, (continued)
- Re: HAMT iterators, Bruno Haible, 2020/10/11
- Re: out-of-memory handling, Bruno Haible, 2020/10/11
- Re: out-of-memory handling, Marc Nieper-Wißkirchen, 2020/10/11
- Re: out-of-memory handling, Bruno Haible, 2020/10/11
- Re: out-of-memory handling, Marc Nieper-Wißkirchen, 2020/10/11
- Re: HAMT for gl_set and gl_map, Bruno Haible, 2020/10/11
- Re: [New module] Persistent Hash Array Mapped Tries (HAMTs), Marc Nieper-Wißkirchen, 2020/10/11
- Re: Draft #3 (with iterators), Marc Nieper-Wißkirchen, 2020/10/11
- Re: Draft #3 (with iterators), Bruno Haible, 2020/10/11
- Re: Non-opaque hamt type?, Marc Nieper-Wißkirchen, 2020/10/12
- Re: Non-opaque hamt type?,
Bruno Haible <=
- Re: Non-opaque hamt type?, Marc Nieper-Wißkirchen, 2020/10/18
- Re: Non-opaque hamt type?, Bruno Haible, 2020/10/18
- Re: Non-opaque hamt type?, Marc Nieper-Wißkirchen, 2020/10/18
- Re: terminology, Bruno Haible, 2020/10/11
- Re: terminology, Marc Nieper-Wißkirchen, 2020/10/11
- Re: _Atomic, Bruno Haible, 2020/10/10
- Re: _Atomic, Paul Eggert, 2020/10/11
- Re: _Atomic, Bruno Haible, 2020/10/11