cl-skip-list

[utterances-bot]

cl-skip-list

https://40ants.com/lisp-project-of-the-day/2020/07/0121-cl-skip-list.html

[spacebat]

Freedom from deadlocks

[tychoish]

I'd look at:

• what do mixed read/write workloads look like? The mutex is single-exclusion, and I would imagine it'd be rough in that case (and I'm not aware of a multi-reader single-writer mutex in bt/etc.)
• is performance consistent across numbers of threads in both cases?

Also:

• I'm curious about the reason for adding the "foo" symbol?
• Why do you divide the hash example by 100 and the skip list example by 1000?

My guess is that there's some optimization in the implementation of the hash table that isn't avalible (or implemented) in the skip list.

[svetlyak40wt]

I'm curious about the reason for adding the "foo" symbol?

I just wanted to have in the map the value which I'll be quering.

Why do you divide the hash example by 100 and the skip list example by 1000?

I'm dividing to internal-time-units-per-second in both cases. For SBCL it is 1000. But Lisp is smart enough to simlify RATIO presentation:

POFTHEDAY> (/ 1 1000)
1/1000

POFTHEDAY> (/ 10 1000)
1/100

POFTHEDAY> (/ 100 1000)
1/10

POFTHEDAY> (type-of *)
RATIO

[Harleqin]

Ah, but if you always fetch only a single predetermined object, then it can be luck that one data structure happens to have it at a more shallow place than the other. I believe that you need to fetch random objects in order to get statistical results.