> But the double-lookup in two data structures is unnecessary slow.
Not necessarily. You'd have 2xlog(n) and because you wouldn't be storing the data in the HAMT it could be denser / wider and thus better fit in cache. At least that's what happened with Raymond Hettinger's (non-persistent) naturally ordered dict: rather than a sparse array of buckets, the hashmap is a sparse array of indices and a dense array of buckets leading to much better memory density (even more so with an adaptive sparse array where the stored indices can be u8, u16 or usize depending on the number of items: most maps will only need a sparse array of u8 leading to even better memory behaviour for the most problematic part).
> But enumerating the list is in reverse, is it not? Going from the newest key to the oldest key. I want it to go from the oldest to the newest key.
Not if you have a doubly linked list, but that increases your costs in storage and update complexity
> In any case it should be better to store pointers to HAMT nodes rather than keys.
If you're implementing the entire datastructure then yes, I was rather assuming you were on the outside with an existing HAMT.
I have not read about them. Might take a while to implement.
I use Pascal. But it is hard to find Pascal libraries for anything. Either they do not exist at all or have not been maintained for over a decade
So, if I want to use a data structure, I usually need to implement it myself
>Not necessarily. You'd have 2xlog(n) and because you wouldn't be storing the data in the HAMT it could be denser / wider and thus better fit in cache.
If I reuse the HAMT as persistent vector, it is not so good. There is no grouping, each node is allocated separately and could be anywhere in memory. One lookup could be five cache misses.
>At least that's what happened with Raymond Hettinger's (non-persistent) naturally ordered dict: rather than a sparse array of buckets, the hashmap is a sparse array of indices and a dense array of buckets leading to much better memory density (even more so with an adaptive sparse array where the stored indices can be u8, u16 or usize depending on the number of items: most maps will only need a sparse array of u8 leading to even better memory behaviour for the most problematic part).
I use such a hashmap, too, for the insertion order. (there are Pascal libraries with hashmaps, but even then I needed some weeks to customize it). But all indices there are 32-bit. Perhaps I will add the adaptiveness to it. 16-bit at least. 8-bit seems hardly worth it, at most it can save 256 bytes
>> But enumerating the list is in reverse, is it not? Going from the newest key to the oldest key. I want it to go from the oldest to the newest key.
>Not if you have a doubly linked list, but that increases your costs in storage and update complexity
But a doubly linked list would not be persistent.
Arbitrary many new nodes could point to one old node, but the old node can only point to one of them
Why not get a persistent vector?
> But the double-lookup in two data structures is unnecessary slow.
Not necessarily. You'd have 2xlog(n) and because you wouldn't be storing the data in the HAMT it could be denser / wider and thus better fit in cache. At least that's what happened with Raymond Hettinger's (non-persistent) naturally ordered dict: rather than a sparse array of buckets, the hashmap is a sparse array of indices and a dense array of buckets leading to much better memory density (even more so with an adaptive sparse array where the stored indices can be u8, u16 or usize depending on the number of items: most maps will only need a sparse array of u8 leading to even better memory behaviour for the most problematic part).
> But enumerating the list is in reverse, is it not? Going from the newest key to the oldest key. I want it to go from the oldest to the newest key.
Not if you have a doubly linked list, but that increases your costs in storage and update complexity
> In any case it should be better to store pointers to HAMT nodes rather than keys.
If you're implementing the entire datastructure then yes, I was rather assuming you were on the outside with an existing HAMT.