"Subkey" concept is undocumented

[sjakobi]

There are two constants named using this term, but I can't find any other use of it in Bagwell's paper or the context of HAMTs.

unordered-containers/Data/HashMap/Internal.hs

Lines 2361 to 2362 in 4da2c20

	bitsPerSubkey :: Int
	bitsPerSubkey = 5

unordered-containers/Data/HashMap/Internal.hs

Lines 2367 to 2368 in 4da2c20

	subkeyMask :: Bitmap
	subkeyMask = 1 `unsafeShiftL` bitsPerSubkey - 1

From this context I suspect that a subkey is a 5-bit part of a hash. I.e. a 64-bit or 32-bit hash can be understood as a sequence of subkeys. For example:

hash32 = 0b10_00101_00100_00011_00010_00001_00000
subkeys(hash32) = [0b00000, 0b00001, 0b00010, 0b00011, 0b00100, 0b00101, 0b10]

Subsequent subkeys of a given hash are used to navigate the tree at subsequent levels:

index(hash, shift) = subkeys(hash) !! (shift / bitsPerSubkey)

[sjakobi]

@treeowl Does my explanation above make sense to you, or do you have a different understanding?

[sjakobi]

I wonder whether "sub-hash" might be a better name, since the term "key" usually refers to a k type thing instead of its hash.

[sjakobi]

Simply 'Index' might be another good name.

It would be good to have a proper explanation of how a HashMap tree can be navigated by following the "index path" represented by a hash. The invariant on correctly located leaf nodes could then reference this explanation.

[treeowl]

I think your explanation is good. I don't know which word to use. index might be simplest in context.

[sjakobi]

type Index = Word

indexPath :: Hash -> [Index]
indexPath = go 0
  where
     go s !h | s >= finiteBitSize @Word 0 = []
             | otherwise = index h s : go (nextShift s) h

[treeowl]

The problem with index is that it might be confused with an array index.

[sjakobi]

The problem with index is that it might be confused with an array index.

That's not entirely wrong though. The existing index function does compute the array index for the array in a Full node:

https://hackage.haskell.org/package/unordered-containers-0.2.19.1/docs/Data-HashMap-Internal.html#v:index

[treeowl]

Right, but the index is not the subkey.

[sjakobi]

Right, but the index is not the subkey.

Yes, it is?! It's just two names for the same concept: A 5-bit chunk of a Hash that can be used to index into a Bitmap or a Full node's array.

[treeowl]

You have to combine the the subkey with the mask to get the array index, don't you?

[sjakobi]

You have to combine the the subkey with the mask to get the array index, don't you?

I think you're referring to BitmapIndexed nodes now, where the array indices are computed with sparseIndex using the Bitmap stored in the node.

For a Full node, all you do is right-shift the hash by the Shift corresponding to the desired level and use the subkeyMask to get the lowest 5 bits. Then you have the index into the array.

I'll try to document all this stuff properly and let you review.

[treeowl]

Yeah, that's what I was talking about for sure. I think the subkey thing makes sense as a unifying principle there. But of course getting rid of Full would be better. I doubt I'll have time to work on that in the next few weeks though.

[sjakobi]

Even if we get rid of Full, this sub-key / index concept will remain essential to understand the HashMap internals.

[treeowl]

Yes. I feel like we're talking past each other somehow? I had the impression you wanted to rename subkey to index. Was that a bogus misinterpretation on my part?