Excessive main memory usage by stdlib_hashmaps routines

Help stdlib
22

If going for a custom hashmap implementation is an option, maybe a swiss table could be useful here.

(Disclaimer: For Go 1.24, its native map implementation went from chaining map to swiss table, so I asked Gemini to generate an equivalent in C, and even though it hallucinated things like uint66_t, it’s quite straightforward.)

If what needs to be stored is only key and value of int32 type, then the memory usage reduces to

type :: slot_t
    integer(INT32) :: key, val
end type

type :: group_t
    integer(INT8) :: ctrl(8)    ! stores only the rightmost 7 bits of the hash
    type(slot_t) :: slots(8)
end type

type :: map_t
    integer :: resident = 0, deleted = 0, ngroups = 2, capacity = 16
    integer :: grow_threshold, shrink_threshold, compact_threshold
    type(group_t), allocatable :: groups(:)
end type

So that’s 9 bytes per slot —plus some compiler-specific overhead?

Since there are no linked lists, recursion is out of the question, along with stack exhaustion. The heart of the swiss table implementation is in its find_slot algorithm, so that’s the only thing in need of careful consideration.

The implementation in Go 1.24’s standard library is more complex than the one in the link above, since it relies on the runtime for AES- and SSE-related instructions.

1 Like
23

I’ve put a simple test here that shows total storage actually used by compilers. Indeed it looks like gfortran is using the least memory, while flang uses the least for the 1D allocatable descriptor:

Compiler Bytes (total) Bytes (key only) Bytes (class(*))
nvfortran 312 152 136
flang 144 48 40
gfortran 112 64 24
ifx 224 72 128
1 Like
24

Thanks! Note the stdlib hashmap currently uses 32 bit hashing, so int_hash and int_index are int32 in the current stdlib. However changing those values didn’t make any changes when I ran it.

2 Likes