[tdmackey]

They are very interesting but in practice often preform poorly due to the cpu not being able to figure out what to cache.

[cpeterso]

Yes. I have read that big skip lists have poor data locality because the skips jump at unpredictable (probabilistic) times to memory that is probably on a different page.