Repository navigation
Optimize for server requests/responses #312
Description
Thoughts for discussion, and a few suggestions:
A large % of json parsed in this world is parsed as server requests and responses. There are a few relevant characteristics here:
- Throughput of a single document still matters, but bulk throughput is the bottleneck for such a server--specifically, how many documents you can parse at a time.
- POST requests (the main place you do JSON, though sometimes it gets encoded into a query parameter in the URL) tend to be very small (in many cases
{}, but often something like{ "q": "name = 'john'" }). In fact, if you could measure every valid JSON document ever, you'd find a very significant percentage are the strings{}and{ }. - Responses from a given endpoint (not all) tend to be very similar sizes because an endpoint tends to have a single record schema (which often have similar length) and the endpoint type dictates a lot about the response as well.
- POST endpoints designed to do an operation, for example, will usually return short responses:
{}or{ "success": "true" }. - GET endpoints designed to return a single record will often return small or small-ish responses like
{ "id": 1, "name": "john" }--particularly, endpoints like this that return < 64 bytes are likely to do so frequently. - GET endpoints designed to return a list of records are much harder to predict, but many will be small, for two reasons: first, many lists are just empty :) And second, the entries in a lists generally don't return the whole record and tend to be small, so a surprising number of nonempty lists will fit in under 64 bytes:
[ { "id": 1 }, { "id": 10 }, { "id": 20 } ]for example.
- POST endpoints designed to do an operation, for example, will usually return short responses:
- Depending on the country you are in, endpoints returning user-facing strings and communication will return non-ASCII UTF-8 on nearly every call. However, even in those countries, these endpoints tend to live alongside other endpoints that only ever return ASCII (for computer to computer communication). In these countries, branch misprediction of UTF-8 in a server will probably be pretty high. And since most of the documents are not going to be huge (a single message, a single customer ...) you don't always get the benefit of the fact that a single document will probably have UTF-8 in nearly every chunk, or nowhere.
All this is to say, we might do well to think about the effects of misprediction in a typical server architecture, where a thread pool is used to handle all requests and threads have no affinity to a given endpoint or JSON profile. In these situations, where there are many different endpoints. My thoughts:
- Can we get simdjson to match other JSON parsers when parsing loads and loads of small (< 64 byte) documents?
- Can we reduce misprediction for users who know which of their endpoints have mostly small documents and which have lots of UTF-8? For example, a separate copy of the function for each situation, which the user calls and the processor does branch prediction differently each time? Would the instruction cache effect overwhelm the benefit of fewer mispredictions?
- Much more "pie in the sky" crazy mode: for super high load situations on endpoints with lots of small documents: I'm curious if simdjson could parse multiple documents in bulk, benefitting from a "batch mode" where multiple documents are crammed together in a single queue. The user could have a small parsing thread pool and cram documents together, asking simdjson to parse them in bulk whenever the buffer reaches 64 bytes or a timeout occurs. Latency increases but overall throughput might be improved.
Activity
lemire commentedon Sep 13, 2019
Handling tiny documents very fast is certainly possible and fun. However, it is almost an entirely different problem. That is not to say that we shouldn't or couldn't do it... but it almost certainly best handled with a different/new code base.
Would you open this as a new issue?
UTF-8 validation is a small part of our parsing as things stand now. Have you tried running benchmarks?
This is very similar to an existing issue, see #188
jkeiser commentedon Oct 6, 2019
I guess I'm interested in having a valid choice of the fastest JSON parser overall, because I see in simdjson an actual chance to fight global warming :) Bulk processing a la the ndjson thing might help a ton with server throughput, even if it reduces average latency by a little bit. Either way, we should at least have benchmarks and find out exactly what.
Will do!
@lemire Unless I'm way off in my benchmarks, the UTF-8 check nearly doubles stage 1 iteration time (adds about 75%), even without misprediction.
Source:
./parse -tfbaseline-structurals-2.jsonand./parse -tfbaseline-utf-8.json, both 640KB files with 2 structurals per block, one of which has UTF-8 in every block.(I don't have a good measure of overall impact because one file has numbers and one has strings, which stage 2 treats differently. I'll fix that when I have a moment.)
lemire commentedon Oct 6, 2019
I’m game to pursue this.
There are things we know regarding the processing of small batches... the overhead (e.g. the memory allocation, function calls) that is negligible when the data has a non-trivial size end up dominating the running time.
Also the metrics need to change... instead of GB/s, you want to move toward measures like documents per second...
I’ll check your UTF-8 benchmark.
lemire commentedon Oct 7, 2019
Back to UTF-8...
You are correct that in the example you refer to (baseline-utf-8.json), utf-8 validation uses half of the running time. I invite you to contribute at least some of these synthetic cases to master so we can include them in our ongoing performance tests.
I don't think I ever saw such a relatively high UTF-8 cost in a JSON file.
Stage 1, in your example, on one test machine goes from 3.4 GB/s to 6.4 GB/s if I disable UTF-8 validation. That means that UTF-8 validation runs at 3.4 GB/s in this case if my math is correct.
For the next simdjson version, I'd like to move UTF-8 validation to the string tape. Doing so in this case should drastically lower the cost since only a small fraction of the input is actually string content. The idea would be to only run UTF-8 validation on string content.
This means that we should be able to get a nice speed bump for baseline-utf-8.json.
Hence I reiterate that it would be interesting to have it as part of our core benchmarks.
jkeiser commentedon Oct 8, 2019
Yep, those are part of a set of files including misprediction cost measurement, as well as feature based performance reporting to help figure it what tradeoffs you are making. It needs a few updates before I'm ready to make it a pr, though.
jkeiser commentedon Oct 8, 2019
@lemire note that this is in-context perf impact of UTF-8, which can differ in either direction from the actual impact. If UTF-8 validation causes a long pole to get longer and stop soaking up CPU with parallel instructions, the impact of UTF-8 validation could be higher than its actual cost. If it causes a higher instructions-per-cycle with parallel instructions, then the actual cost will be lower.
At any rate, I think you're 100% right about moving it to the string tape. It's going to be the highest-density place to run it, bar none.
lemire commentedon Oct 8, 2019
(I meant 3.4GB/s.)
You are correct that it is not independent tasks.
I am thinking that we might want to store keys differently; keys are typically ASCII.
jkeiser commentedon Oct 8, 2019
Yeah. Also, keys tend to have VERY high duplication rate across a single file, and are often looked up by name, meaning hashing and dedup might actually buy something.
Even more, because they are typically unescaped, you could dedup before you unescape or write to the string tape, and because they are ASCII, you wouldn't have to worry about Unicode equality canonicalization--just a straight hash of the bytes would be enough for comparison (sans hash collisions, which I don't know what to think about). Keys that had non-normalized Unicode or backslashes wouldn't get deduped, but it might be win anyway.
Heh, getting off topic. As far as optimizing for server requests/responses, I am hoping that SIMD and branch-free techniques will make us faster for documents >= 64 bytes. I think I can live with being slower or at least not faster on < 64 bytes, as long as it's not a huge multiplier. Regardless, we should measure how our processing time for smaller documents compares the same way we do with big ones (and at what point it gets better) just so people can make informed decisions on whether simdjson fits their production load or whether they need a hybrid.
lemire commentedon Oct 8, 2019
I think that a good first step would be to write a benchmark. Simulate a stream of server responses.
jkeiser commentedon Jan 10, 2020
For this purpose, I think "parse a generically representative spread of JSON responses," for example, 10% 16-byte, 50% 256-byte, 25% 1K, 10% 1M, 5% 10M, is a reasonable benchmark. Percentages may vary, I'm anecdotizing based on servers I've built or used. 16-byte is empty requests/responses. 256-byte are small single objects and lists. 1K is large single objects and reasonably-sized lists. 1M-10M is Just About Everything Else.
Parsing JSON requests will be a different proportion, but it's a good start.
jkeiser commentedon Mar 10, 2020
It looks to me like we are already faster than the competition for pretty much all file sizes. Running parsingcompetition on all files in jsonexamples (with enough iterations to get a low-ish error margin):
We should make sure and make that point when marketing: it's not just large files.
jkeiser commentedon Mar 10, 2020
A graph:
lemire commentedon Mar 10, 2020
That's great news. I can't believe I did not run these benchmarks for myself some time ago.
Of course, we want memory allocation to be done ahead of time... otherwise we probably suffer. So if you are going to eat just one tiny JSON, we are probably not super competitive. Of course, if you are just going to eat one tiny JSON, parsing performance is probably not high on your list of priorities.
Thanks for documenting this... we probably should update the README accordingly.
Do we close this issue, now?
jkeiser commentedon Mar 10, 2020
I think so. Streaming parsing would make it easier too, but this is the big blocker.