# Cache efficient batch search

**URL:** <https://users.rust-lang.org/t/cache-efficient-batch-search/46558>\
**Category:** uncategorized\
**Created:** [July 29, 2020, 12:26pm UTC](https://users.rust-lang.org/t/cache-efficient-batch-search/46558 "2020-07-29T12:26:42Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![raidwas](https://avatars.discourse-cdn.com/v4/letter/r/c67d28/32.png) [@raidwas](https://users.rust-lang.org/u/raidwas)\
**Post date:** [July 29, 2020, 12:26pm UTC](https://users.rust-lang.org/t/cache-efficient-batch-search/46558/1 "2020-07-29T12:26:43Z")

</div>

So I thought about this some time and I implemented a more cache friendly search (in sorted slices).

The code can be found [here](https://github.com/raidwas/rust_batch_search).

The basic idea is that during a binary search in (big) sorted slices the cpu is mainly waiting for the next value to compare to and therefore wasting time.  
This can be improved by asking the cpu to prefetch the data and during that prefetching start searching for the next values.

I implemented this concept in three ways:

- a handcrafted state machien
- using futures
- using generators

I personally prefer the two versions using generators as they stay extremely close to the original (the binary search from the `std`) while greatly improving performance (on big slices). Sadly generators cannot be used yet in stable...

I am not looking for a code review but mainly wanted to share it and ask for your opinions or try to answer questions you have.

---

<div class="post-metadata">

**Author:** ![notriddle](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/notriddle/32/51307_2.png) [@notriddle](https://users.rust-lang.org/u/notriddle)\
**Post date:** [July 30, 2020, 7:32pm UTC](https://users.rust-lang.org/t/cache-efficient-batch-search/46558/2 "2020-07-30T19:32:10Z")

</div>

I'm curious how it compares to [Eytzinger Binary Search](https://algorithmica.org/en/eytzinger), which takes a completely different approach to defining a cache-friendly algorithm.

---

<div class="post-metadata">

**Author:** ![raidwas](https://avatars.discourse-cdn.com/v4/letter/r/c67d28/32.png) [@raidwas](https://users.rust-lang.org/u/raidwas)\
**Post date:** [July 30, 2020, 8:06pm UTC](https://users.rust-lang.org/t/cache-efficient-batch-search/46558/3 "2020-07-30T20:06:40Z")

</div>

As far as I understand it, the text you linked does not prefetch the data for the immediatly following comparison, but for a comparison down the line.

Either way, here are my thoughts after flying over the link:

- inserting or removing values might require rebuilding the whole array in a pattern that is far more complicated than a `memcpy` (what a array would use for insertion or deletion), thus making the Eytzinger representation not suitable for many situations
- The text is only trying to speed up a single search, so the setting is a bit different. If I tried to speed up a single search I would have to prefetch multiple locations in the array beforhand without knowing which of them will be required, which would waste a lot of memory bandwith.

---

<div class="post-metadata">

**Author:** ![system](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/system/32/51372_2.png) [@system](https://users.rust-lang.org/u/system)\
**Post date:** [October 28, 2020, 8:06pm UTC](https://users.rust-lang.org/t/cache-efficient-batch-search/46558/4 "2020-10-28T20:06:47Z")

</div>

Closed on October 28, 2020, 8:06pm UTC

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.