40ants / lisp-project-of-the-day

Here I'll post notes about Quicklisp projects. Also I publish them on Twitter account svetlyak40wt.

http://40ants.com/lisp-project-of-the-day/

BSD 2-Clause "Simplified" License

51 stars 6 forks source link

cl-skip-list #19

Open utterances-bot opened 4 years ago

utterances-bot commented 4 years ago

cl-skip-list

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

spacebat commented 4 years ago

Freedom from deadlocks

tychoish commented 4 years ago

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 commented 4 years ago

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 commented 3 years ago

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.