2 ms·
Ah ok I found it there, I see what you mean now. My only guess would be cache effects? With that large AVL tree (1 M entries, so likely dozens of MiB), you are
by colanderman 3y ago
Ah ok I found it there, I see what you mean now. My only guess would be cache effects? With that large AVL tree (1 M entries, so likely dozens of MiB), you are escaping L2 cache and hitting shared L3 or main memory for a large portion of lookups, and are bandwidth-constrained at the die level, thus adding that knee (which I think is visible with some of the other algorithms as well).
- telez 3y agobut TL2 shouldn't be using more memory than say TinySTM, i don't think. If the implementations are object based and nodes are cache aligned, adding an extra 8 bytes for the versioned-lock shouldn't bump the node size to greater than a cache line. however, i do think the tl2 implementation as described in the paper is memory based, as is TinySTM so every read needs to do a hash to locate the corresponding lock / meta data. the read-only transactions for tl2 and TinySTM seem identical to me which is why i am so confused. looking at other figures from the 2PLSF paper, the TL2 for 100% lookup on hash set and skip list it looks like such a dog compared to the other algos.