Port of http_parser to llparse.
NOTE: Only trunk and upcoming 6.0.1 version of clang are supported at the moment
Let's face it, http_parser is practically unmaintainable. Even introduction of a single new method results in a significant code churn.
This project aims to:
- Make it maintainable
- Verifiable
- Improving benchmarks where possible
Over time, different approaches for improving http_parser's code base
were tried. However, all of them failed due to resulting significant performance
degradation. Most of this degradation comes from the extensive spilling
that is inevitable for such large function as http_parser_execute.
Splitting the big switch statement into small functions naively should work,
but, in practice, is feasible only through using a dispatch loop in
http_parser_execute, which is slow due to lots of failed branch predictions.
The loop can be avoided by use of tail calls, but their generation can not
be enforced in C language.
To overcome this impediment, this project utilizes llparse for converting
the switch statement into LLVM bitcode. Small functions for each separate
state of the parser are created and linked together through musttail
calls.
The end result of such process is a binary bitcode file, that could be compiled to machine code with clang compiler.
So far llhttp outperforms http_parser:
| input size | bandwidth | reqs/sec | time | |
|---|---|---|---|---|
| llhttp | 8192.00 mb | 1032.35 mb/s | 2009462.01 | 8.22 s |
| http_parser | 8192.00 mb | 603.73 mb/s | 1217410.95 | 13.57 s |
llhttp is faster by approximately 71%.
llhttp project has less 1000 LoC (lines of code), while the same code in http_parser is implemented in approximately 2000 LoC. All optimizations and multi-character matching in llhttp is generated automatically, and thus doesn't add any extra maintenance cost.
The state machine graph is encoded explicitly in llhttp.
WIP.
This software is licensed under the MIT License.
Copyright Fedor Indutny, 2018.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.