c: vectorize table lookups

indutny commented 5 years ago

Use SSE4.2 vector instructions to speed up matching. When node has a lot characters to match and loops to itself, the table lookups could be replaced with a call to _mm_cmpestri, skipping all matching characters in the input stream.

cc @nodejs/http maybe?

The benchmark results (from llhttp) are:

No SSE:

url loose (C)
32768.00 mb | 1389.49 mb/s | 28018961.78 ops/sec | 23.58 s
url strict (C)
32768.00 mb | 1319.83 mb/s | 26614195.26 ops/sec | 24.83 s
http loose: "seanmonstar/httparse" (C)
32768.00 mb | 1236.92 mb/s | 1844958.53 ops/sec | 26.49 s
http strict: "seanmonstar/httparse" (C)
32768.00 mb | 989.90 mb/s | 1476514.44 ops/sec | 33.10 s
http loose: "nodejs/http-parser" (C)
32768.00 mb | 1181.67 mb/s | 2382818.56 ops/sec | 27.73 s
http strict: "nodejs/http-parser" (C)
32768.00 mb | 956.21 mb/s | 1928191.66 ops/sec | 34.27 s

SSE

url loose (C)
32768.00 mb | 1396.29 mb/s | 28156047.11 ops/sec | 23.47 s
url strict (C)
32768.00 mb | 1324.29 mb/s | 26704105.59 ops/sec | 24.74 s
http loose: "seanmonstar/httparse" (C)
32768.00 mb | 2043.78 mb/s | 3048452.47 ops/sec | 16.03 s
http strict: "seanmonstar/httparse" (C)
32768.00 mb | 1924.88 mb/s | 2871105.55 ops/sec | 17.02 s
http loose: "nodejs/http-parser" (C)
32768.00 mb | 1636.96 mb/s | 3300913.67 ops/sec | 20.02 s
http strict: "nodejs/http-parser" (C)
32768.00 mb | 1507.33 mb/s | 3039511.00 ops/sec | 21.74 s

indutny commented 5 years ago

Example of generated code: https://gist.github.com/indutny/8047e46247ad58ca0c39bd2a8ac2549a

indutny commented 5 years ago

No way... I just pushed it as a minor...

indutny commented 5 years ago

Had to publish 6.1.1 to resolve this. :facepalm:

indutny commented 5 years ago

I think it should build on Windows and all supported Unixes, but would really appreciate @bnoordhuis sign-off if they have time :wink:

indutny commented 5 years ago

Landed in 25d4378. Thanks!

nodejs / llparse

c: vectorize table lookups #24