5 ms·

Question to the author : Seing the benchmark really made me wonder, how can you be twice as a fast as nginx ? I've always thought writing assembly manually was

by bsaul 11y ago

Question to the author : Seing the benchmark really made me wonder, how can you be twice as a fast as nginx ? I've always thought writing assembly manually was for some very specific edge cases, or to talk to some very specific hardware, but that it was just a waste of time for anything else, especially compared to C (and especially with all the progress in compilers). Is it the death by a thousand cuts scenario, or are there some big chunks of performances gained thanks to some specific tricks (and if so, could you give some example ?). I'm thinking maybe cryptographic functions ?

2ton_jeff 11y ago
Hey thanks! Contrary to popular belief, x86_64 assembler isn't really that bad to deal with. An eagle-eye perspective is simply that regardless of how good optimising compilers get, they can never really know my intent. My zlib implementation for example is consistently 25% faster than the reference version, despite me simply "hand compiling" it straight from the C source. There are lots of contributing factors that all add up to the end result as seen in the benchmarks. The short answer is: there is no single reason, it is the culmination of all of the underlying bits of the library that made it what it is. I added code profiling to rwasa so that you can run load tests against it and watch call graphs and individual function timings, which makes for interesting inspection of the library itself for specific "tricks" that were employed. (the library's page contains rwasa-specific profiling examples: https://2ton.com.au/HeavyThing/ https://2ton.com.au/HeavyThing/ )
- JoshTriplett 11y ago
  > My zlib implementation for example is consistently 25% faster than the reference version, despite me simply "hand compiling" it straight from the C source. Have you compared it to Intel's optimized implementation of zlib, at https://github.com/jtkukunas/zlib/ https://github.com/jtkukunas/zlib/ ? If you can improve on that implementation, please consider submitting a patch.
  - anotherangrydev 11y ago
    Congrats on your work 2ton_jeff! Regarding zlib, is that the fastest implementation that's currently available? I rememeber stumbling into a guy that claimed his implementation was way faster (2x or more) than the original zlib, and it was a drop-in replacement and scaled fairly well. Unfortunately, I can't find it right now (it should be bookmarked on another computer).
    - JoshTriplett 11y ago
      Various people have attempted to speed up zlib; it's not that high a bar, if you're OK with not producing output binary-identical to the original zlib. Deflate compression algorithms keep references to possible LZ backreferences in a hash table, and depending on your choice of hash algorithm, and how much you prune your table versus spending memory and time storing and searching it, you'll end up emitting different backreferences. The implementation at https://github.com/jtkukunas/zlib/ https://github.com/jtkukunas/zlib/ replaces the hash algorithm with something much faster.
    - Jweb_Guru 11y ago
      libslz is really, really fast (and fairly new). It's used in the next version of haproxy. In my own tests it's proved substantially faster than both zlib and miniz.
  - 2ton_jeff 11y ago
    I am aware of Intel's patch re: psubusw usage, and interestingly chose the same solution when hand-compiling it as theirs well before I saw their patch to it (in fill window, which does make a substantial difference). Have you compared my code to [your?] repo yet? I will endeavour to do so, though I am not sure submitting a fasm-based patch to that repo would make sense. Cheers
    - JoshTriplett 11y ago
      I hadn't compared the code yet; I figured it would make sense to compare performance first.
- nickpsecurity 11y ago
  It's the same in the high assurance systems field albeit with different goals. We're concerned with optimization-induced failures, subversion, complexity, and so on. Mainstream languages and their compilers... doesn't exactly help on this. I've been out of it a while, evangelizing & informing mainly these days. Yet, your post brings back memories. My strategy, leveraging the Write Great Code book, was to map language constructs onto assembler via macro-assembler or languages such as LISP with good metaprogramming. Then, I hand compiled the code in other's projects with my macro's. So, we took a similar approach there although my goal was to show a correspondence argument between source & asm. Meta tools turned that into full program for assembling and linking. One wild idea I had for portability was doing optimized routines of a safe HLL in a bytecode like LLVM. That knocks out most of the uncertainty of above layers that limit optimizations the most. Then, the simple optimizations that machines are good at can be performed from there along with generation of assembler. Close to portability of C and efficiency of hand-written assembler with inline available. For instance, code zlib functions in pretty optimal LLVM and let toolchain do the rest on full-optimization. Think yours will be 25% faster, 10%, similar? And I'm talking what you can code quickly rather than spend 30min-1hr optimizing by hand. Just curious to hear your thoughts as you have way more experience in that stuff.
  - Joky 11y ago
    Saying that you're afraid by optimization-induced failures and then saying that you will feed some LLVM bytecode to the optimizer seems contradictory to me...
    - nickpsecurity 11y ago
      They're kind of two different things. The first was hand-compiling (or tracing) things for highly assured work. The other was a tangent where I wonder if a bytecode like LLVM could be used as a cross-platform assembler that's closer to hand-optimized assembler than C due to less knowledge of intent being required. Not to mention simpler structure. They're different things. If it's a worthwhile path, then the formal efforts on LLVM IR and verified optimizations could be combined with hand-made, inline LLVM for a safer, portable alternative to different inline assembler for each platform. Complimentary, not contradictory, when in context.
- vidarh 11y ago
  > Contrary to popular belief, x86_64 assembler isn't really that bad to deal with. I think most beliefs regarding x86_64 asembly is largely "guilt by association" with i386... It's amazing the difference just from making use of the larger register set.
- cbsmith 11y ago
  > My zlib implementation for example is consistently 25% faster than the reference version, despite me simply "hand compiling" it straight from the C source. Yeah, but that is a very CPU bound processing pipeline. You would expect that to maximize the impact of any inefficiencies in the compiler. That you can hand tune for better performance is conceivable. That you can get a 2x win over some pretty tuned code suggests that there is something larger at work than simply tuning lots of little things.
applecore 11y ago
In some respects, assembler language is actually at a higher level than C.
- fao_ 11y ago
  Would you care to give an example? The only thing I can think of is the typeless-ness.
vidarh 11y ago
Here's a short-list of some very simple things you can easily do in assembler which are either hard for a compiler to do, or which requires all kinds of extra optimization "magic". A lot of it boils down to having more information available: * Allocate registers globally or across large substs. Especially when targeting architectures (like x86_64, but unlike i386) with decent numbers of available registers, this has lots of potential for typical applications that e.g. frequently needs to access common data structures. Compilers for many languages (e.g. C) have a hard time doing this if doing separate compilation per module (since you need to be able to link to code that hasn't been optimized the same way). You need whole-program optimization for this typically, but when programming assembler, it's the natural thing to do if you have enough registers to treat some of them as assigned to specific variables that you know will be frequently accessed. * Omit stack frames entirely or selectively. Many compilers have options for doing this, but often still ends up pushing/popping more stuff than necessary for things like local variable frames and arguments, where a programmer will often see that a function is not going to use much space and decide to put in extra effort to shuffle things around to keep things in registers only. * Selectively violate the "normal" calling conventions. E.g. if you have a utility function you often need to use in settings where it's convenient not to clobber certain registers, then you can opt to pass arguments in different registers easily. This again takes whole-program optimization for a compiler to do. * Avoid saving/restoring certain registers based on the functions you're calling. Again requires whome-program optimization for the compiler to know that the function you're calling won't clobber specific registers. * Specifically adjust what registers you're using based on what registers may be clobbered by other code you're calling to avoid having to save/restore. Other things include similarities/patterns in code that are non-obvious in a higher level language because it depends on how the code is translated, which often can allow you to re-write things to eliminate common sub-expressions that are not actually visible/present in the high level code. It's not that compilers can't do all of these if given sufficient freedom and information, but it often violates expectations of the higher level environment (e.g. separate compilation in C)
- anon4 11y ago
  This makes me think a direction worth pursuing would be to save the whole-program-analysis from the last compile pass for the new compile pass, so you can avoid re-analysing things. So you'd spend maybe 20 minutes on the first compile, then edit one .cpp file and the next compile takes 10 seconds.
coolsunglasses 11y ago
Haskell web servers have been faster than nginx on single and multi-core micro-benchmarks for years. Not implausible at all that someone using assembler could do better still.
- darkf 11y ago
  Which comparably featured Haskell servers beat nginx? Curious.
  - tome 11y ago
    Warp, apparently: https://github.com/snoyberg/posa-chapter/blob/master/warp.md#performance-of-warp https://github.com/snoyberg/posa-chapter/blob/master/warp.md... (although I don't know anything about a feature comparison)

by bsaul 11y ago

2ton_jeff 11y ago

Hey thanks! Contrary to popular belief, x86_64 assembler isn't really that bad to deal with. An eagle-eye perspective is simply that regardless of how good optimising compilers get, they can never really know my intent. My zlib implementation for example is consistently 25% faster than the reference version, despite me simply "hand compiling" it straight from the C source. There are lots of contributing factors that all add up to the end result as seen in the benchmarks. The short answer is: there is no single reason, it is the culmination of all of the underlying bits of the library that made it what it is. I added code profiling to rwasa so that you can run load tests against it and watch call graphs and individual function timings, which makes for interesting inspection of the library itself for specific "tricks" that were employed. (the library's page contains rwasa-specific profiling examples: https://2ton.com.au/HeavyThing/ https://2ton.com.au/HeavyThing/ )

JoshTriplett 11y ago
> My zlib implementation for example is consistently 25% faster than the reference version, despite me simply "hand compiling" it straight from the C source. Have you compared it to Intel's optimized implementation of zlib, at https://github.com/jtkukunas/zlib/ https://github.com/jtkukunas/zlib/ ? If you can improve on that implementation, please consider submitting a patch.
- anotherangrydev 11y ago
  Congrats on your work 2ton_jeff! Regarding zlib, is that the fastest implementation that's currently available? I rememeber stumbling into a guy that claimed his implementation was way faster (2x or more) than the original zlib, and it was a drop-in replacement and scaled fairly well. Unfortunately, I can't find it right now (it should be bookmarked on another computer).
  - JoshTriplett 11y ago
    Various people have attempted to speed up zlib; it's not that high a bar, if you're OK with not producing output binary-identical to the original zlib. Deflate compression algorithms keep references to possible LZ backreferences in a hash table, and depending on your choice of hash algorithm, and how much you prune your table versus spending memory and time storing and searching it, you'll end up emitting different backreferences. The implementation at https://github.com/jtkukunas/zlib/ https://github.com/jtkukunas/zlib/ replaces the hash algorithm with something much faster.
  - Jweb_Guru 11y ago
    libslz is really, really fast (and fairly new). It's used in the next version of haproxy. In my own tests it's proved substantially faster than both zlib and miniz.
- 2ton_jeff 11y ago
  I am aware of Intel's patch re: psubusw usage, and interestingly chose the same solution when hand-compiling it as theirs well before I saw their patch to it (in fill window, which does make a substantial difference). Have you compared my code to [your?] repo yet? I will endeavour to do so, though I am not sure submitting a fasm-based patch to that repo would make sense. Cheers
  - JoshTriplett 11y ago
    I hadn't compared the code yet; I figured it would make sense to compare performance first.
nickpsecurity 11y ago
It's the same in the high assurance systems field albeit with different goals. We're concerned with optimization-induced failures, subversion, complexity, and so on. Mainstream languages and their compilers... doesn't exactly help on this. I've been out of it a while, evangelizing & informing mainly these days. Yet, your post brings back memories. My strategy, leveraging the Write Great Code book, was to map language constructs onto assembler via macro-assembler or languages such as LISP with good metaprogramming. Then, I hand compiled the code in other's projects with my macro's. So, we took a similar approach there although my goal was to show a correspondence argument between source & asm. Meta tools turned that into full program for assembling and linking. One wild idea I had for portability was doing optimized routines of a safe HLL in a bytecode like LLVM. That knocks out most of the uncertainty of above layers that limit optimizations the most. Then, the simple optimizations that machines are good at can be performed from there along with generation of assembler. Close to portability of C and efficiency of hand-written assembler with inline available. For instance, code zlib functions in pretty optimal LLVM and let toolchain do the rest on full-optimization. Think yours will be 25% faster, 10%, similar? And I'm talking what you can code quickly rather than spend 30min-1hr optimizing by hand. Just curious to hear your thoughts as you have way more experience in that stuff.
- Joky 11y ago
  Saying that you're afraid by optimization-induced failures and then saying that you will feed some LLVM bytecode to the optimizer seems contradictory to me...
  - nickpsecurity 11y ago
    They're kind of two different things. The first was hand-compiling (or tracing) things for highly assured work. The other was a tangent where I wonder if a bytecode like LLVM could be used as a cross-platform assembler that's closer to hand-optimized assembler than C due to less knowledge of intent being required. Not to mention simpler structure. They're different things. If it's a worthwhile path, then the formal efforts on LLVM IR and verified optimizations could be combined with hand-made, inline LLVM for a safer, portable alternative to different inline assembler for each platform. Complimentary, not contradictory, when in context.
vidarh 11y ago
> Contrary to popular belief, x86_64 assembler isn't really that bad to deal with. I think most beliefs regarding x86_64 asembly is largely "guilt by association" with i386... It's amazing the difference just from making use of the larger register set.
cbsmith 11y ago
> My zlib implementation for example is consistently 25% faster than the reference version, despite me simply "hand compiling" it straight from the C source. Yeah, but that is a very CPU bound processing pipeline. You would expect that to maximize the impact of any inefficiencies in the compiler. That you can hand tune for better performance is conceivable. That you can get a 2x win over some pretty tuned code suggests that there is something larger at work than simply tuning lots of little things.

applecore 11y ago

In some respects, assembler language is actually at a higher level than C.

fao_ 11y ago
Would you care to give an example? The only thing I can think of is the typeless-ness.

vidarh 11y ago

Here's a short-list of some very simple things you can easily do in assembler which are either hard for a compiler to do, or which requires all kinds of extra optimization "magic". A lot of it boils down to having more information available: * Allocate registers globally or across large substs. Especially when targeting architectures (like x86_64, but unlike i386) with decent numbers of available registers, this has lots of potential for typical applications that e.g. frequently needs to access common data structures. Compilers for many languages (e.g. C) have a hard time doing this if doing separate compilation per module (since you need to be able to link to code that hasn't been optimized the same way). You need whole-program optimization for this typically, but when programming assembler, it's the natural thing to do if you have enough registers to treat some of them as assigned to specific variables that you know will be frequently accessed. * Omit stack frames entirely or selectively. Many compilers have options for doing this, but often still ends up pushing/popping more stuff than necessary for things like local variable frames and arguments, where a programmer will often see that a function is not going to use much space and decide to put in extra effort to shuffle things around to keep things in registers only. * Selectively violate the "normal" calling conventions. E.g. if you have a utility function you often need to use in settings where it's convenient not to clobber certain registers, then you can opt to pass arguments in different registers easily. This again takes whole-program optimization for a compiler to do. * Avoid saving/restoring certain registers based on the functions you're calling. Again requires whome-program optimization for the compiler to know that the function you're calling won't clobber specific registers. * Specifically adjust what registers you're using based on what registers may be clobbered by other code you're calling to avoid having to save/restore. Other things include similarities/patterns in code that are non-obvious in a higher level language because it depends on how the code is translated, which often can allow you to re-write things to eliminate common sub-expressions that are not actually visible/present in the high level code. It's not that compilers can't do all of these if given sufficient freedom and information, but it often violates expectations of the higher level environment (e.g. separate compilation in C)

anon4 11y ago
This makes me think a direction worth pursuing would be to save the whole-program-analysis from the last compile pass for the new compile pass, so you can avoid re-analysing things. So you'd spend maybe 20 minutes on the first compile, then edit one .cpp file and the next compile takes 10 seconds.

coolsunglasses 11y ago

Haskell web servers have been faster than nginx on single and multi-core micro-benchmarks for years. Not implausible at all that someone using assembler could do better still.

darkf 11y ago
Which comparably featured Haskell servers beat nginx? Curious.
- tome 11y ago
  Warp, apparently: https://github.com/snoyberg/posa-chapter/blob/master/warp.md#performance-of-warp https://github.com/snoyberg/posa-chapter/blob/master/warp.md... (although I don't know anything about a feature comparison)