replaces the current PCL cache with a (hopefully) thread safe one.
The thread safety hasn't yet been stressed very hard, though.
This should be considered a rough cut: some of the "cleanups"
I've subjected PCL to in while implementing this possibly aren't.
I've been using the microbenchmarks at
to measure the performance of this, and am happy to say that
it seems to compare favorably to the current implmentation both
in terms of speed and space: speed is the same or slightly better,
and space is sometimes less, sometimes more -- but overall it seems
to average out (I've can easily manage less space by upping the
probe limit, but that costs speed...)
...though since it uses only one of the layout-clos-hash slots,
it is probably possible to construct a case where the caches
get absurdly large absurdly fast.
* Overflow mechanism to avoid allocating huge caches. (Maybe)
* Double hashing instead of linear probing to reduce
* Better probe-depth limitations: allow deep individual
probes as long as the average remains good.
* Limit number of keys to something sane.
* Oogle at the disassembly to see if something stands out.
...but basically, it "seems to work pretty nicely". I would
very much appreciate if people could poke holes at this.
is the updated version, against 22.214.171.124.
It was pointed out to me that the back-to-front, front-to-back
contortions weren't a win after all, and doing everything
front-to-back works just as well -- if all wrapper writes use CAS. As
an added benefit there is now no need to spin when writing -- not even
in rare cases.
I experimented with the N hashes from 1 seed scheme outlined in the
Kickzales & Rodriguez paper's notes, but this patch does not include
my implementation thereof exect for one skeletal comment: trying to
find the best hash for each cache when expanding (and trying to avoid
expanding when possible) didn't seem to help very much at all. It is
of course possible that my implementation was at fault.