Re: [New module] Persistent Hash Array Mapped Tries (HAMTs)

[Marc Nieper-Wißkirchen]

Hi Bruno,

Am Sa., 10. Okt. 2020 um 16:35 Uhr schrieb Bruno Haible <bruno@clisp.org>:

> It is exciting to see such a datastructure with various application domains 
> [1]
> in Gnulib!

I'm glad that you like the idea.

>
> I haven't read through it line by line; nevertheless a couple of comments:

A few more lines will follow before the final draft is done because I
have been adding some destructive update procedures in the meantime.

>   - +/* The public interface is documented in the file hamt.c.
>
>     This is not good. As a user of the module, I would want to read *only*
>     hamt.h and know how to use the public interface. In other words, hamt.h
>     should have the functions' comments.

I followed the example of the already existing "hash" module. But I
can easily move the public comments into the header file.

>   - "Each
>     updating operation returns a new hamt, which shares structure with
>     the original one."
>     So, after calling hamt_insert or hamt_delete, which function should I call
>     to delete the original Hamt without affecting the new one? (In order to
>     avoid accumulating pieces of old Hamts in memory.)

When you do, say,

new_hamt = hamt_insert (hamt, ...)

and new_hamt != hamt afterwards, you have to delete both hamt and
new_hamt with hamt_free to free all the memory. After you have freed
the first hamt, the second won't be affected.

>   - "The GL_HAMT_THREAD_SAFE flag is set if the implementation of hamts
>     is thread-safe as long as two threads do not simultaneously access
>     the same hamt."
>     I don't understand this sentence. Isn't the guarantee that
>     "is thread-safe as long as two threads do not simultaneously access
>     the same hamt" trivial? And what you want to achieve through the use
>     of _Atomic is that it is thread-safe *also* when two threads access
>     the same hamt?

The guarantee is not trivial because two different hamts may share
some structure.

So... assume you have a hamt. You do some operations on it (or you do
hamt_copy) to get a new_hamt that shares structure. Now if thread 1
works on hamt and thread 2 on new_hamt, it is safe when
GL_HAMT_THREAD_SAFE is set.

If two threads access the same hamt, it is not guaranteed to be safe.
If you need this, get an (extremely shallow) copy through hamt_copy
first.

Marc