[WIP] SIMD support for x86/x86_64

kamyuentse commented 6 years ago

Use vectorized compare based matching for header values. (More chars, fewer ranges?)
Use vectorized shuffle based matching for URI. (Fewer chars, more ranges?)

Simple bench result

With AVX2

Bench with RUSTFLAGS="-C target-feature=+avx2,+bmi" cargo bench --features=nightly

test bench_httparse       ... bench:         259 ns/iter (+/- 3) = 2714 MB/s
test bench_httparse_short ... bench:          56 ns/iter (+/- 1) = 1214 MB/s
test bench_pico           ... bench:         402 ns/iter (+/- 6) = 1748 MB/s
test bench_pico_short     ... bench:          53 ns/iter (+/- 1) = 1283 MB/s

With SSE4.2

Bench with RUSTFLAGS="-C target-feature=+sse42,+bmi" cargo bench --features=nightly

test bench_httparse       ... bench:         358 ns/iter (+/- 3) = 1963 MB/s
test bench_httparse_short ... bench:          52 ns/iter (+/- 1) = 1307 MB/s
test bench_pico           ... bench:         426 ns/iter (+/- 5) = 1650 MB/s
test bench_pico_short     ... bench:          55 ns/iter (+/- 1) = 1236 MB/s

Without SIMD

Bench with cargo bench

test bench_httparse       ... bench:         468 ns/iter (+/- 6) = 1502 MB/s
test bench_httparse_short ... bench:          54 ns/iter (+/- 0) = 1259 MB/s
test bench_pico           ... bench:         405 ns/iter (+/- 7) = 1735 MB/s
test bench_pico_short     ... bench:          53 ns/iter (+/- 0) = 1283 MB/s

You may get a different mileage, depends on the specified platform.

seanmonstar commented 6 years ago

Oh, not required, but it'd be neat to see also what the bench results are without nightly :D

seanmonstar commented 6 years ago

I'm so sorry I forgot about this!

Just a few quick questions:

I don't know the answer, so asking: do we need to check target_arch along with target_feature? Does target_feature not imply an arch has it?
I think the only thing left is probably some way to test the changes. Specifically, if we can test in CI the avx2, the sse42, and the fallback. I haven't investigated, does the Travis linux environment support these target features? If they are supported, that's simple! In order to test them each, then, we'd probably need cargo features for each case, and adjust the Travis matrix to test with each enabled individually...

kamyuentse commented 6 years ago

@seanmonstar The target_feature seems will be reform? I do not check the RFC yet, but I think target_feature is enough. For the CI, I will modify the script once this PR ready. I plan to continue working on this as soon as SIMD stable for x86/x86_64.

seanmonstar commented 6 years ago

I've taken what was started here and got it working and running tests in #40. Thanks so much!

seanmonstar / httparse