ekmett / ekmett/structures

Perform multiple searches in parallel

Open
#6 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Haskell
Stars
65
Forks
10
PR merge metrics
No merged PRs in 30d

Description

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.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.