Fork me on GitHub
#clj-kondo
<
2023-10-05
>
Ngoc Khuat04:10:50

could anyone help me understand why {:a 1} creates an array-map instead of a hash-map? IMO hash-map has O(1) lookup time which is pretty nice. On the other hand, array-map has the benefit of maintaining insertion order, but I don’t think we really need that property.

seancorfield04:10:12

This doesn't seem to be a clj-kondo question but I'll answer it here anyway: small hash maps (up to 8 entries) use an array map, then it switches to a hash map. This is an implementation detail and you shouldn't rely on it. Array map has a much simpler implementation than a regular hash map so it's better for overall performance/memory usage for small maps, as I understand it.

Ngoc Khuat05:10:56

ah nice! that actually makes sense! Thank you Sean. And sorry I meant to ask in #C03S1KBA2

1
👍 1
lispyclouds07:10:49

@U023C0QKU4W purely as a fun exercise you can try measuring the perf of looking for something (membership check) in a small fixed sized array vs a map, say upto 10-15 elements. the results might surprise you 😉 the C times O(n) vs C times O(1) starts to matter when n is small

seancorfield14:10:06

I should also have mentioned that hash maps use a chunked hash trie, with a chunk size of 32, which is really efficient for large maps but still involves a number of sequential comparisons.

hifumi12300:10:23

lookups in a hash map are not O(1), they are average O(1), which can be quite different from O(1) worst case

1
hifumi12300:10:08

for small hash maps, it is actually faster to use a flat array that fits in a CPU cache line, you can benchmark this yourself in any language, not just Clojure

hifumi12300:10:14

at least my theory as to why array-map stops at 8 kv pairs is due to the fact that 16 pointers in a modern JVM (assuming pointer compression) is exactly the size of a cache line in modern x86 and ARM processors (64 bytes)

1