Re: [TCLCORE] Unifying list and dict types

[Andy G. <unu...@ai...>]

"Donal K. Fellows" <don...@ma...> wrote:
> Have you evaluated the memory cost of these changes to code that only
> needs basic lists or basic dicts and isn't transforming one to the other?

>From the way the data structures are defined, it appears to me that this new
approach would use less memory.  Let me try to put some numbers to this,
with 32-bit/64-bit byte counts.  The old and new numbers should compare
directly because I don't plan to change the preallocation characteristics.
I don't know the overhead each ckalloc() incurs.

If you like, I could make a table comparing the expected memory utilization
for dicts of various sizes.

New code:

Each hash entry, both actively used and preallocated, requires...
1. One Tcl_Obj * inside List.elements (4/8 bytes).
2. One DictEntry inside Dict.entries (12/16 bytes).
3. One int inside Dict.allocation (4/4 bytes).
4. Total (20/28 bytes).

Each list+dict intrep requires...
1. One List (24/32 bytes).
2. One Dict (36/56 bytes, not counting the static* arrays).
3. Total (60/88 bytes).
4. Two ckallocs() for List and List.dict.

Each list+dict over the STATIC size wastes...
1. An unused Dict.staticBuckets array (16/16 bytes).
2. An unused Dict.staticEntries array (240/336 bytes).
3. An unused Dict.staticAllocation array (48/48 bytes).
4. Total (304/400 bytes).

Each list+dict over the STATIC size has an extra...
1. Three ckalloc()s for Dict.buckets, Dict.entries, and Dict.allocation.

Each non-dict intrep wastes...
1. An unused List.dict pointer (4/8 bytes).

Old code:

Each actively used hash entry requires...
1. One ChainEntry (28/56 bytes).
2. One ckalloc() for the ChainEntry.

Each dict intrep requires...
1. One Dict (60/88 bytes, not counting staticBuckets).
2. One ckalloc() for the Dict.

Each dict intrep over the SMALL_HASH_TABLE size wastes...
1. An unused Dict.table.staticBuckets array (16/32 bytes).

Each dict intrep over the SMALL_HASH_TABLE size has an extra...
1. One ckalloc() for Dict.table.buckets.

Some cuts are possible.  A 32-bit hash could be used on a 64-bit machine,
which is the current Tcl behavior, saving four bytes per entry on a 64-bit
machine.  Maybe when the Dict struct exceeds the STATIC size (12 entries),
it could be shrunk with ckrealloc() to no longer contain the static* arrays,
possibly saving 304/400 bytes for large dicts.  The allocation array could
be interleaved into the entries array, since they always have the same
length (just add an allocation field to the DictEntry struct), saving 4/8
bytes for all dicts and one ckalloc() for large dicts.

-- 
Andy Goth | http://andy.junkdrome.org./
unununium@{aircanopy.net,openverse.com}