Hi there Ed,

been trying to dust off this project and wondering if you knew of implementations or efforts which pick up where you left off with cache oblivious data structures. I know of the haskell-works repo with succinct data structures, but I can't tell at first glance whether it also includes cache oblivious data structure.

Thanks!

Jun

The test suite tries to verify that the code is free of hlint warnings, but it isn't: http://hydra.cryp.to/build/496548/log/raw.

This requires extending Data.Vector.Array with a notion of prefetch and likely upgrading dependencies to GHC 7.10 or hiding it behind an option.

http://cglab.ca/~morin/misc/arraylayout-v2/arraylayouts.pdf

With a binary tree we can a.) switch to a branchless form and b.) do the searches with a baked in prefetch call. We can then batch 4-8 array searches in parallel, and take advantage of the prefetches from #5.

With Eytzinger order #4, however, such extra prefetches would be random main memory reads if we needed to do extra levels. This would bound our parallelism by the number of structures at the same level as us. (2-3x currently.)

If the payout is large enough, the latter may supply motivation for considering a larger radix number system.

Hi there again.

Been wondering about whether these fast range queries you mentioned were implemented somewhere? Or if I'm overlooking something about deriving them from the existing machinery...

Cheers,

Jun