Full Compile-Time Processor Feature Detection

[Sewer56]

Currently memchr does run-time feature detection for x86, storing 'preferred' functions inside a field that is later referenced in subsequent calls

// Inside `unsafe_ifunc!`

// store
FN.store(fun as Fn, Ordering::Relaxed);

// use
let fun = FN.load(Ordering::Relaxed);

This manifests itself as a mov and call in x86; and one or two other misc instructions along the way.

In order to avoid unnecessary code bloat and improve performance, it should be possible to bypass this mechanism if we know what is available at build time.
This would allow for inlining, and slightly lesser call overhead.

That is of course, when the Rust compiler is invoked with the correct flags to ship a binary targeting a specific processor.

Note

This isn't a formal feature request, it's more so a reminder for myself.
I want to reference this issue in my own codebase, and possibly PR this sometime in the future.

[BurntSushi]

I think if would be better to try and do this without feature flags. We can detect at compile time whether, for example, the avx2 target feature is enabled.

[Sewer56]

I think if would be better to try and do this without feature flags.

I wrote this when I was tired (still am).
Seems you're right, even easier to adjust, in this case.

[ambyjkl]

I haven't examined the code here yet, but it seems just setting rustflags to -Ctarget-feature=+avx2 might be enough to skip the check, not sure b4a4c6a

[Sewer56]

I haven't examined the code here yet, but it seems just setting rustflags to -Ctarget-feature=+aes2 might be enough to skip the check, not sure b4a4c6a

https://godbolt.org/z/h7av5rx3n

extern crate memchr;
use memchr::memchr;

#[no_mangle]
fn memchr_1(data: &[u8]) -> usize {
    memchr(0, &data).unwrap()
}

I believe these mov operation correspond to

let fun = FN.load(Ordering::Relaxed);

The commit you linked does add compile-time checks, but it still stores a function pointer.
The goal here is to call the target directly, since it can be determined at compile time in this case.

[ambyjkl]

I see, seems the compiler doesn't automatically inline the call, sad

[ambyjkl]

so I have an issue that ties into this one, and solving this issue can help solve that. The SearcherKind enum is a bit too fat, especially on an avx2 supported cpu, it has two copies of the sse2 Finder along with an avx2 Finder, making the whole thing 288 bytes on x86_64, and I would benefit from having that go down to reduce memory usage. The fix would be to expose specialized sse2/avx2/neon Finders that statically only have the fields they actually need, and that would also do away with the function pointer. @BurntSushi @Sewer56 lmk if this solution would work for you guys too

[Sewer56]

Would need to dig a bit more into it, but it sounds interesting at the very least.
I'm always down to reduce stack usage.

[ambyjkl]

Also @BurntSushi I love your work and just started sponsoring you through my company so I hope you read this :)

[BurntSushi]

so I have an issue that ties into this one, and solving this issue can help solve that. The SearcherKind enum is a bit too fat, especially on an avx2 supported cpu, it has two copies of the sse2 Finder along with an avx2 Finder, making the whole thing 288 bytes on x86_64, and I would benefit from having that go down to reduce memory usage.

I really do think this is an entirely separate issue. I addressed it as a Discussion question here: #164

I love your work and just started sponsoring you through my company

Thank you! :-)

[BurntSushi]

@Sewer56 Since it seems like you are trying to micro-optimize here, I think there are two important questions to answer:

1. Have you come up with a benchmark where this matters?
2. Have you tried any of the lower level APIs in crate::arch that give you more direct access to the operations defined in memchr? For example, memchr::arch::x86_64::avx2::memchr::One. There's no function pointers there.

[ambyjkl]

I really do think this is an entirely separate issue. I addressed it as a Discussion question here: #164

Ok that's just what i was looking for, thank you, and OP can also just do this directly as well

[Sewer56]

Have you come up with a benchmark where this matters?

I'm porting an open source archive format I wrote during work hours to Rust in my own time, while giving it a small upgrade:

https://sewer56.dev/sewer56-archives-nx/Specification/Table-Of-Contents/#string-pool

Reading names from the pool usually involves reading strings, usually average 40-ish characters, before hitting null terminator.
If you have 40 strings, repeat that NumFiles times.

I did recently write a benchmark around this; and while it is true that in my use case the actual memchr operation takes very little time compared to decompression of the pool itself; I nonetheless strive to make the code as good as possible. In my specific case, I have inlining to gain from this; as it would be the only use case of memchr when compiled into a standalone dynamic library.

How much the improvement actually amounts to, I'm not concerned. I'd guess something in the range of 0.1-0.5% and a hundred or two bytes of assembly code less. To me any improvement is an improvement.

Have you tried any of the lower level APIs in crate::arch that give you more direct access to the operations defined in memchr? For example, memchr::arch::x86_64::avx2::memchr::One. There's no function pointers there.

I could use those directly, but it's more about improving the whole ecosystem.

Why just use a workaround for myself when I could instead eventually contribute and make an improvement for everyone?

It'd also avoid a death by 1000 cuts situations. Code depends on other code; if you make the lowest level code more efficient, you make the system as a whole more efficient. That means there's a chance for others' stuff to run faster too, and everyone, myself included gets to benefit in tandem.

[ambyjkl]

So, I can see two improvements here:

• memchr exports stuff like NativeFinder and similar which at compile time branches on the cpu feature flags to reexport memchr::arch::x86_64::(avx2|sse2)::*, etc, that would give you theoretically max performance at the cost of portability: basically something like -march=native
• we replace the function pointer with an enum, and we branch on the enum at the call site to call the correct version. I believe switching on enum is generally faster than dereferencing function pointers. This solution would still be dynamic dispatch, but just better