[WIP] SIMD support for x86/x86_64 #38

kamyuentse · 2018-03-21T19:07:58Z

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

This is super impressive!

seanmonstar · 2018-03-21T21:19:23Z

src/lib.rs

+// ASCII codes to accept URI string.
+// i.e. A-Z a-z 0-9 !#$%&'*+-._();:@=,/?[]~
+// TODO: Make a stricter checking for URI string?
+static URI_MAP: [bool; 256] = byte_map![


Just cause I'm curious, why is this different from just parsing as a token?

From RFC7230 Section 3.2.6, we can get the formalize description of token:

token = 1*tchar tchar = "!" / "#" / "$" / "%" / "&" / "'" / "*" / "+" / "-" / "." / "^" / "_" / "`" / "|" / "~" / DIGIT / ALPHA ; any VCHAR, except delimiters

Current is_token(b: u8) -> bool; is not satisfy this def, I think that should be changed.

For URI matching, depends on the safeguard requirement, the accepted charset may differ, IMO, we should be careful here, maybe we can provide a strict mode, which is an optional feature here? That's why I extract a URI_MAP here.

seanmonstar · 2018-03-21T21:19:54Z

src/lib.rs

+// TODO: Make a stricter checking for URI string?
+static URI_MAP: [bool; 256] = byte_map![
+    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,


Is this indentation difference intentional?

My fault, I should check my editor config.

seanmonstar · 2018-03-21T21:21:54Z

src/lib.rs


 static HEADER_VALUE_MAP: [bool; 256] = byte_map![
-    0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,
+    0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,


Yikes! Just checked, this was previously allowing Backspace instead of Horizontal Tab 😢

Thanks for the fix!

seanmonstar · 2018-03-21T21:24:49Z

src/lib.rs

+}
+
+#[cfg(feature = "nightly")]
+#[cfg(all(any(target_arch = "x86", target_arch = "x86_64"), target_feature = "avx2"))]


What happens if a user has enabled the nightly feature, but their compile target doesn't support these? We'd need match_url_char_32 versions for those too, I think.

I thought about this previous, we need to add an SSE4.2 version here? Is it reasonable?

I think the completed constaints should be:

nightly AND (x86 OR x86_64) AND AVX2 => enable AVX2 support;

nightly AND (x86 OR x86_64) AND SSE4.2 => enable SSE4.2 support;

otherwise, use the fallback implementation.

But this will cause a rather lengthy #[cfg(...)], I don't know how to simply it.

Yea, its probably reasonable. Not too worried about complicated cfg attributes.

seanmonstar · 2018-03-21T21:25:52Z

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

seanmonstar · 2018-04-10T18:54:53Z

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 · 2018-04-11T03:11:43Z

@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.

nvzqz · 2018-05-15T12:43:02Z

src/lib.rs

+    let ptr = buf.as_ptr();
+
+    #[allow(non_snake_case, overflowing_literals)]
+        unsafe {


In case you didn't catch it, there's an accidental indentation here

seanmonstar · 2018-06-22T01:34:35Z

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

Initial SIMD support for x86/x86_64 with AVX2.

27404ef

seanmonstar reviewed Mar 21, 2018

View reviewed changes

Added basic SSE4.2 support.

37b77af

kamyuentse changed the title ~~Initial SIMD support for x86/x86_64 with AVX2.~~ [WIP] SIMD support for x86/x86_64 Apr 11, 2018

nvzqz reviewed May 15, 2018

View reviewed changes

seanmonstar mentioned this pull request Jun 21, 2018

use SSE4.2 and AVX2 instructions when available #40

Merged

seanmonstar closed this Jun 22, 2018

Uh oh!

[WIP] SIMD support for x86/x86_64 #38

[WIP] SIMD support for x86/x86_64 #38

Uh oh!

Conversation

kamyuentse commented Mar 21, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Simple bench result

With AVX2

With SSE4.2

Without SIMD

Uh oh!

seanmonstar left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

kamyuentse Mar 22, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

seanmonstar commented Mar 21, 2018

Uh oh!

seanmonstar commented Apr 10, 2018

Uh oh!

kamyuentse commented Apr 11, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

seanmonstar commented Jun 22, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

3 participants

kamyuentse commented Mar 21, 2018 •

edited

Loading

kamyuentse Mar 22, 2018 •

edited

Loading