Evaluate using prefetching on slice's binary_search algorithm

[gnzlbg]

This SO answer shows a 20% speed-up on binary_search with prefetching enabled at the cost of:

• trashing at most 2 cache lines when an element is found (since two other elements will be prefetched),
• increasing code-size with prefetching instructions.

We should consider adding this optimization if it turns out to be worth it.

[hirschenberger]

It seems as there's no support for the llvm.prefetch intrinsic available in librustc_trans/intrinsic.rs. Is this intentional?

[gnzlbg]

One can probably work around that using the link_llvm_intrinsics feature.

[hirschenberger]

Do you know how I can enable the link_llvm_intrinsics feature when building the compiler, or do I have to enable it in every crate explicitly?

I declared an external function like this:

extern {
    #[link_name = "llvm.prefetch"]
    fn prefetch(address: *const i8, rw: i32, locality: i32, cache_type: i32);
}

and used it the the binary_search. But when building other crates the compiler bails out with:

Cannot invoke an intrinsic other than donothing, patchpoint or statepoint
  invoke void @llvm.prefetch(i8* %37, i32 0, i32 1, i32 1)
          to label %bb13 unwind label %cleanup

[gnzlbg]

Do you know how I can enable the link_llvm_intrinsics feature when building the compiler?

I've never enabled/disabled features in the compiler crates (in my crates I just add it to the root of the crates that uses the feature). Maybe @alexcrichton does know or know somebody who knows.

[alexcrichton]

The error there looks unrelated to the link_llvm_intrinsics feature being enabled/disabled, that specifically looks like a codegen error. I'm not particularly sure why that'd show up, though. This may mean that support in intrinsics.rs needs to be added to execute the intrinsic.

[hirschenberger]

Ok, I'll try to add the prefetch intrinsic, was it intentionally left out?

[alexcrichton]

Nah it probably just hasn't gotten around to getting bound yet, very little is intentionally left out!

[hirschenberger]

Hmm, I'm stuck at adding the pretetch intrinsic. I added it in:

• libcore/intrinsics.rs
• librustc_trans/context.rs
• librustc_trans/intrinsic.rs
• librustc_typeck/check/intrinsic.rs

But I still get the error:

error[E0093]: unrecognized intrinsic function: `prefetch`
   --> src/libcore/intrinsics.rs:569:5
    |
569 |     pub fn prefetch<T>(data: *const T, rw: i32, locality: i32, cache: i32);
    |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ unrecognized intrinsic

Is there some bootstrapping necessary?

[hanna-kruppe]

The bootstrap compiler won't recognize the intrinsic, so you need to guard the definition with #[cfg(not(stage1))].

A similar problem will show up when you try to use the intrinsic in. I guess the easiest way to solve that without code duplication will be to define a #[cfg(stage1)] stub that does nothing.

[hirschenberger]

@rkruppe You mean stage0, or?

[hanna-kruppe]

Yes, I confused "which stage is the compiler" with "which stage are we compiling the source code for".

[hirschenberger]

Ok, I added the prefetch intrinsic and benchmarked a small stand-alone binsearch.

https://gist.github.com/hirschenberger/dcf3fc6f2b7ddad08c889adfa8f5f1cf

With this setup, I got the following results:

• Valilla: test bench_binsearch ... bench: 105 ns/iter (+/- 0)
• With prefetch: test bench_binsearch ... bench: 95 ns/iter (+/- 0)

That's approx. 10%, don't know if it's worth it and if this microbenchmark is significant. I think the compiler is already doing good work. Here's the output of perf for both versions:

• Vanilla:

           320.577 L1-dcache-load-misses     #    0,46% of all L1-dcache hits   [66,26%]
        69.887.806 L1-dcache-loads                                              [67,23%]
            35.613 L1-dcache-prefetches                                         [66,60%]

• With prefetching:

           190.783 L1-dcache-load-misses     #    0,14% of all L1-dcache hits   [67,13%]
       133.433.668 L1-dcache-loads                                              [67,00%]
            51.848 L1-dcache-prefetches                                         [65,94%]

---

Update:

I did some more tests and got the runtime down to: test bench_binsearch ... bench: 81 ns/iter (+/- 0)

The change prefetches the destination slice after every iteration.