4 ms·

So, how long does it take to identify a verb on a 2.66GHz Core2 MacBook Pro… FOURCC 4.9ns // The parent comment code FOURCC-witho

by jws 17y ago

So, how long does it take to identify a verb on a 2.66GHz Core2 MacBook Pro… FOURCC 4.9ns // The parent comment code FOURCC-without-alignment-bug 6.1ns // ... safely assemble the word NGINX 10.3ns // main ariticle's code STRCMP 17.6ns // most commen verbs first The FOURCC codes as in the parent only work if you can assume you know the character after the verb to be a space or other known character because GET and PUT are too short. They also require disambiguating code for the 5+ letter verbs but these are all relatively rare (probably). My strings are all 4 byte aligned, so the FOURCC case may be getting an unfair boost, it never generates an unaligned read which possibly is slower. Test data is a set of jumbled GET,HEAD,POST,PUT lookups that I made up to meet my idea of a web server. There are some worst cases hiding out there, for instance all PROPPATCH verbs… FOURCC 14.7ns FOURCC-without-alignment-bug 17.7ns NGINX 19.8ns STRCMP 37.4ns Feels like gcc sequentially tests case values. Make sure to put them in the order for common verbs to match first. The FOURCC codes get the most control here. NGINX is most consistent, probably from its two layered lookup nature. So there you have it: nginx's algorithm is significantly better then strcmp, and fairly independent of verb distribution. A FOURCC lookup is faster, even if made safe for all architectures. And finally, strcmp isn't that bad (freebsd anyway, the GNU libc is about half as fast as seen in further testing). (I am left with a nagging desire to check a perfect hashing function though.) Edit: gperf is about 50% slower than the nginx method. No need to go that direction for perfect hashing.

jws 17y ago
So what about other architectures? How about a 1.6GHz Atom 330 processor. This doesn't have out of order execution and should more closely match ARM and MIPS type small machines. (Sorry, I can't get one of those booted from where I am now.) FOURCC 23.3ns FOURCC-without-alignment-bug 27.6ns NGINX 29.8ns STRCMP 70.5ns (glibc) The difference between FOURCC and NGINX is vanishing here. How about a 3GHz core-i7 840 FOURCC 4.8ns FOURCC-without-alignment-bug 5.6ns NGINX 8.3ns STRCMP 13.9ns (freebsd) Not a lot faster than a Core-2, but some. Of course it has twice the cores plus hyperthreading ready to go. How about if you are cheap (like me) and got a 2.93GHz core i3 for your server: FOURCC 5.3ns FOURCC-without-alignment-bug 5.8ns NGINX 9.9ns STRCMP 33.6ns (glibc) Not bad for the little guy. (Saved $100 on the cpu, plus didn't need to add a video card with some goofey driver, and its system wide low power state is almost as good at the Atom's.)
- Dav3xor 17y ago
  Most ARM's will be significantly slower on non-aligned data. Un^H^Hfortunately I'm not at work to test. :)
viraptor 17y ago
I'm not sure if you were just curious, or were you trying to prove that nginx is right in optimising this. But since we have the figures - assuming strcmp takes 37ns, we could estimate that wikipedia spent whole 13 seconds parsing the request verb each day in 2008 (assuming 350M visits). Cutting it down by half would definitely be worth the programming time... not.
- jws 17y ago
  I was mostly just calbrating my opimization decision making. I think only considering wikipedia visits is underestimating. A visit is many http transactions, and a webserver is targetted for many times the traffic of wikipedia. Still, it is likely no one ever felt a better user exprience from this one optimization. But what if all the code is 33% faster than strcmp style code? That would be nice, but also seems unlikely. My biggest two takeaways: — beware your OS. The freebsd (mac) strcmp is about twice as fast as the GNU glibc. — forget about gnu's gperf, it is extra complexity for no benefit. Maybe it would win on very long word lists, but I don't know.

by jws 17y ago

jws 17y ago

So what about other architectures? How about a 1.6GHz Atom 330 processor. This doesn't have out of order execution and should more closely match ARM and MIPS type small machines. (Sorry, I can't get one of those booted from where I am now.) FOURCC 23.3ns FOURCC-without-alignment-bug 27.6ns NGINX 29.8ns STRCMP 70.5ns (glibc) The difference between FOURCC and NGINX is vanishing here. How about a 3GHz core-i7 840 FOURCC 4.8ns FOURCC-without-alignment-bug 5.6ns NGINX 8.3ns STRCMP 13.9ns (freebsd) Not a lot faster than a Core-2, but some. Of course it has twice the cores plus hyperthreading ready to go. How about if you are cheap (like me) and got a 2.93GHz core i3 for your server: FOURCC 5.3ns FOURCC-without-alignment-bug 5.8ns NGINX 9.9ns STRCMP 33.6ns (glibc) Not bad for the little guy. (Saved $100 on the cpu, plus didn't need to add a video card with some goofey driver, and its system wide low power state is almost as good at the Atom's.)

Dav3xor 17y ago
Most ARM's will be significantly slower on non-aligned data. Un^H^Hfortunately I'm not at work to test. :)

viraptor 17y ago

I'm not sure if you were just curious, or were you trying to prove that nginx is right in optimising this. But since we have the figures - assuming strcmp takes 37ns, we could estimate that wikipedia spent whole 13 seconds parsing the request verb each day in 2008 (assuming 350M visits). Cutting it down by half would definitely be worth the programming time... not.

jws 17y ago
I was mostly just calbrating my opimization decision making. I think only considering wikipedia visits is underestimating. A visit is many http transactions, and a webserver is targetted for many times the traffic of wikipedia. Still, it is likely no one ever felt a better user exprience from this one optimization. But what if all the code is 33% faster than strcmp style code? That would be nice, but also seems unlikely. My biggest two takeaways: — beware your OS. The freebsd (mac) strcmp is about twice as fast as the GNU glibc. — forget about gnu's gperf, it is extra complexity for no benefit. Maybe it would win on very long word lists, but I don't know.