Some pointers for which variants to use

[jonhoo]

Following a discussion over at gimli-rs/addr2line#61 (comment), I'm thinking of implementing the Eytzinger array-based search in Rust. But, looking through https://github.com/patmorin/arraylayout/blob/master/src/eytzinger_array.h, it's not immediately clear to me which of the variants would be the appropriate one to implement.

If I'm reading the paper correctly:

arraylayout/src/eytzinger_array.h

Line 128 in 3f20174

I __attribute__ ((noinline)) eytzinger_array_deeppf<T,I,C,aligned>::search(T x) const {

should be used when the size of T is small (roughly < 8 bytes), and

arraylayout/src/eytzinger_array.h

Line 253 in 3f20174

I __attribute__ ((noinline)) eytzinger_array_bfpm<T,I,aligned>::search(T x) const {

should be used as the general implementation for all T.

Are those conclusions mostly correct? Which would suggest that I should implement the latter of the two first, and then possibly add a variant for small T using the former.

I also noticed there's an "unrolled" version of the algorithm:

arraylayout/src/eytzinger_array.h

Line 266 in 3f20174

I __attribute__ ((noinline)) eytzinger_array_unrolled<T, I, aligned>::search(T x) const {

which is not evaluated in the paper? Is that something worth paying attention to?

[patmorin]

Yes. Start with branch-free eytzinger with explicit prefetching and a mask. That's this code in the repo: // branch-free code with masked prefetching template<typename T, typename I, bool aligned> I __attribute__ ((noinline)) eytzinger_array_bfpm<T,I,aligned>::search(T x) const { I i = 0; while (i < n) { __builtin_prefetch(a + ((multiplier * i + offset) & mask)); i = (x <= a[i]) ? (2 * i + 1) : (2 * i + 2); } I j = (i + 1) >> __builtin_ffs(~(i + 1)); return (j == 0) ? n : j - 1; } Deep prefetching might help with larger data types. Unrolling gave some tiny improvement for small arrays, but didn't seem worth the trouble. Good luck! I'll follow this to see how it turns out. (Though I guess just the change from Btree to a single array is already going to give you a big speed up.) Best, Pat On Oct 22, 2017 00:18, "Jon Gjengset" <notifications@github.com> wrote: Following a discussion over at gimli-rs/addr2line#61 (comment) <gimli-rs/addr2line#61 (comment)>, I'm thinking of implementing the Eytzinger array-based search in Rust. But, looking through https://github.com/patmorin/arraylayout/blob/master/src/ eytzinger_array.h, it's not immediately clear to me which of the variants would be the appropriate one to implement. If I'm reading the paper correctly: - https://github.com/patmorin/arraylayout/blob/3f20174a2a0ab52c6f37f2ea87d087 307f19b5ee/src/eytzinger_array.h#L128 ("Branch-free code with deep prefetching") should be used when the size of T is small (roughly < 8 bytes) - https://github.com/patmorin/arraylayout/blob/ 3f20174/src/eytzinger_array.h#L253 <https://github.com/patmorin/arraylayout/blob/3f20174a2a0ab52c6f37f2ea87d087307f19b5ee/src/eytzinger_array.h#L253> ("branch-free code with masked prefetching") should be used as the general implementation for all T. Are those conclusions mostly correct? Which would suggest that I should implement the latter of the two first, and then possibly add a variant for small T using the former. I also noticed there's an "unrolled" version of the algorithm (https://github.com/patmorin/arraylayout/blob/ 3f20174/src/eytzinger_array.h#L266) which is not evaluated in the paper? Is that something worth paying attention to? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#3>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AAGXT_rXFtL2a1Vdd8rygJ7J3GuMu5ARks5susILgaJpZM4QBz2r> .

[jonhoo]

First implementation here: https://github.com/jonhoo/ordsearch

[jonhoo]

Some observations: it seems like the implemented algorithm is only faster when n is small and when the data type is relatively large. A straightforward binary search is faster once you go to L3, and sooner if you're operating on smaller data types (e.g., u8). I tried implementing deep prefetching, and if anything it seems to have made things slower (C=0 gives no improvement, C=1 gives a 10% slowdown, and C=2 gives a 20% slowdown).

The implementation of search (called find_gte) is here: https://github.com/jonhoo/ordsearch/blob/master/src/lib.rs#L282-L325

It'd be awesome if you could take a look if you have some spare time and see if I'm doing something clearly silly? If I'm interpreting the relationship between the trends I see and the results in the paper correctly, it seems like the prefetching isn't working properly?

[jonhoo]

@patmorin after doing some more experiments, my code is actually faster if I comment out the pre-fetching, which suggests that it's prefetching the wrong value. However, as far as I can tell, it does exactly the same prefetching as the C++ code. The one thing I can't quite wrap my head around is how offset is computed to be multiplier + multiplier / 2. For the 16 great-great-grandchildren, shouldn't the leftmost child (and thus the start of the prefetch) be at 16i + 8 + 4 + 2 + 1? Which would make offset = multiplier - 1?

[jonhoo]

Sorry for the spam, but I walked through the calculation carefully, and I think I get it now. Left a somewhat long-winded comment here: https://github.com/jonhoo/ordsearch/blob/b17cb0b3f5089112145af25dfad6bbc8376c408a/src/lib.rs#L292

However, given that this all seems correct, I do not understand why the prefetching does not speed anything up? The search is still faster without any prefetching.