News for hackers. Stuff that matters.
Re:A Journey building a fast JSON parser and full JSONPath, ... by peterohler on Sunday July 05, 2020 @09:32AM (#23738512)
I'll get the code up on the OjC repo in the next day or two. You are right, there should be reproducible benchmarks to back up the statement.
Re:A Journey building a fast JSON parser and full JSONPath, ... by peterohler on Sunday July 05, 2020 @11:11AM (#23739252)
Re:A Journey building a fast JSON parser and full JSONPath, ... by lsr0 on Sunday July 05, 2020 @01:38PM (#23740380)
These results aren't reproducible when both are compiled with -O3 (similar results with -O2):

  ojc_parse_str    1000000 entries in  709.300 msecs. ( 1409 iterations/msec)
  simdjson_parse   1000000 entries in  450.724 msecs. ( 2218 iterations/msec)
In those results simdjson is roughly 60% faster.

Telling simdjson we have aligned input gives us further improvement:

  simdjson_parse   1000000 entries in  369.234 msecs. ( 2708 iterations/msec)
About 90% faster. Example changes:

   simd_parse(const char *str, int64_t iter) {
       simdjson::dom::parser parser;
       int64_t   dt;
  +    auto   padded = simdjson::padded_string(std::string_view(str));
       int64_t   start = clock_micro();
   
       for (int i = iter; 0 < i; i--) {
  -        simdjson::dom::element doc = parser.parse(str, strlen(str));
  +        simdjson::dom::element doc = parser.parse(padded);
       }
       dt = clock_micro() - start;
Re:A Journey building a fast JSON parser and full JSONPath, ... by abaines on Sunday July 05, 2020 @12:58PM (#23740090)
These are my results on an (admittedly old) Intel i3-2120 CPU @ 3.30GHz. Compiling both programs with -O3:

    ojc_parse_str    1000000 entries in 3607.615 msecs. (  277 iterations/msec)
    simdjson_parse   1000000 entries in  418.997 msecs. ( 2386 iterations/msec)
and might as well throw in my own parser...

    uj_parse   1000000 entries in 1959.731 msecs. (  510 iterations/msec)
The -O3 seems to make a large difference for simdjson.
Re:A Journey building a fast JSON parser and full JSONPath, ... by peterohler on Sunday July 05, 2020 @01:38PM (#23740381)
Shockingly different. The -O3 option made hardly any difference with OjC but more than a 10x difference with simdjson. I'll be removing the claim from the OjC readme.

Thank you for being civil with your reply. Much appreciated.

Re:A Journey building a fast JSON parser and full JSONPath, ... by jkeiser on Sunday July 05, 2020 @06:02PM (#23742475)
What I've learned from this (as a simdjson author) is that we need to update the quick start in the README to have -O3. I was so psyched about the fact that we now compiled warning-free without any parameters ... that I didn't stop to think that some people would go "huh I did what they told me and simdjson is slow, wtf." Because we evidently told you to compile it in debug mode in the quick start :)

simdjson relies deeply on inlining to let us write performant code that is also readable.

Sorry to have sent you down a blind alley!

One thing to note: if you want to get good numbers to chew on, we have a bunch of really good real world examples, of ALL sizes (simdjson is about big and small), in the jsonexamples/ directory of simdjson. And if you want to check ojc's validation, there are a number of pass.json and fail.json files in the jsonchecker/ directory.

Re:A Journey building a fast JSON parser and full JSONPath, ... by glangdale on Sunday July 05, 2020 @06:13PM (#23742561)
The structuring of simdjson is considerably easier to read if we rely on -O3. In order to get the same performance at lower levels of optimization we need to do a lot of manual things that make the source code quite difficult to read and work with.
Re:A Journey building a fast JSON parser and full JSONPath, ... by beached_whale on Sunday July 05, 2020 @01:09PM (#23740178)
One thing to note with benchmarks like this, they are the norm, but they measure the time to validate a document and do not reflect much of the real word where we reify the JSON back to native data structures. Few benchmarks get that far , I suspect much of it is that the setup is tedious.
Re:A Journey building a fast JSON parser and full JSONPath, ... by hyperman1 on Sunday July 05, 2020 @11:35AM (#23739443)
i see you are using strlen in the inner loop in simdjson which is an extra O(n) operation.

UPDATE and your test data is quite short. You're maybe mostly measuring startup overhead?

Re:A Journey building a fast JSON parser and full JSONPath, ... by peterohler on Sunday July 05, 2020 @11:52AM (#23739578)
I tried to make the test realistic. Agreed that in a benchmark where the string is the same every time the length could be hard coded but in a real world scenario the length of a string is not known until you get the length.

As for the length of the test, I also tried with 10 times the number of iterations with the same results but then the simbbench takes almost a minute to complete. I figured 5 seconds was good enough to get the results and someone can bump up the iterations if they want to.

Re:A Journey building a fast JSON parser and full JSONPath, ... by glangdale on Sunday July 05, 2020 @06:33PM (#23742680)
As discussed elsewhere, simdjson is comfortable with the notion that JSON files might be of different sizes, but does rather better if you can pad the buffers that it reads data into. This is required to avoid the small but real risk that it reads over a page boundary in its SIMD loops.

The test is not realistic. Measuring performance on small cases is a legitimate use case, of course, but using the same data every time means that both ojc and simdjson will train the branch predictor almost perfectly on any modern architecture. This will help either parser during its "branchy" code, which is all of ojc and a significant portion of simdjson (despite all our yelling about how great SIMD is, once we have tokens, we go to a fairly traditional state machine).

On a tiny message, startup costs are probably more significant. Fixing buffer alignment, -O3, and working with larger messages I would not be shocked to see a factor of 20x. There's nothing wrong with ojc but it is a typical parsing strategy that isn't all that different from the other 'normal' JSON parsing libraries that we evaluate (RapidJSON, sajson, dropbox, fastjson, gason, ultrajson, jsmn, cJSON, and JSON for Modern C++).

It's not clear to me why you were so convinced that your library, by extension, would run 10-25x faster than all these other libraries. With the exception of RapidJSON and sajson - which have some performance tricks to go faster - most of these libraries read input in the same way.

Re:A Journey building a fast JSON parser and full JSONPath, ... by gliptic on Sunday July 05, 2020 @12:21PM (#23739793)
If you read the docs, you can see that the string must be allocated to len+SIMDJSON_PADDING bytes. I suppose that still works by accident because it's followed by other static data.

EDIT: Actually, there is a parameter 'realloc_if_needed' that defaults to true and that will reallocate the string because it assumes you haven't padded it. You're likely just measuring malloc performance.

Re:A Journey building a fast JSON parser and full JSONPath, ... by peterohler on Sunday July 05, 2020 @12:37PM (#23739924)
I suspect the need to reallocate in simdjson is a factor in performance but that is really part of the benchmark. When using a parser it would be a very rare case to have the luxury of embedding the string to be parsed in the code. Usually a string comes in through some other means such as over HTTP or maybe a simple socket. Then again it could be passed from some other part of an application. If the parser has a requirement to expand the string to modify it in some fashion then a realloc or really a malloc and copy is part of the parsing process.
Re:A Journey building a fast JSON parser and full JSONPath, ... by jkeiser on Sunday July 05, 2020 @05:52PM (#23742404)
simdjson doesn't care what is in the padding and won't modify it; it just needs the buffer the string lives in to have 32 extra addressable (allocated) bytes. It doesn't ever use the bytes to make decisions, but it may read them as certain critical algorithms run faster when you overshoot a tiny bit and correct after.

Most real world applications like sockets read into a buffer, and can easily meet this requirement.

If you are interested to know what it's for, the place where it parses/unescapes a string is a good example. Instead of copying byte by byte, it generally copies 16-32 raw bytes at a time, and just sort of caps it off at the end quote, even though it might have copied a little extra. Here's some pseudocode (note this isn't the full algorithm, I left a out some error conditions and escape parsing for clarity):

  // Check the quote
  if (in[i] == '"') {
    i++;
    len = 0;
    while (true) {
      // Use simd to copy 32 bytes from input to output
      chunk = in[i..i+32];
      out[len..len+32] = chunk;

      // Note we already wrote 32 bytes, and NOW check if there was a quote in there
      if (int quote = chunk.find('"')) {
        len += quote;
        break;
      }
      len += 32; // No quote, so keep parsing the string
      i += 32;
    }
  }
Re:A Journey building a fast JSON parser and full JSONPath, ... by glangdale on Sunday July 05, 2020 @06:17PM (#23742588)
Yes, this is exactly why simdjson wants padding. It certainly doesn't need the string to be embedded in source or any such nonsense.

I wish there was a standardized attribute that C++ knew about that pretty much just said "hey, we're not right next to some memory-managed disaster, and if you read off this buffer, you promise not to use the results".

It is awful practice to read off the end of a buffer and let those bytes affect your behavior, but it is almost always harmless to read extra bytes (and mask them off or ignore them) unless you're next to a page boundary or in some dangerous region of memory that's mappped to some device.

This attribute would also need to be understood by tools like Valgrind (to the extent that valgrind can/can't track whether you're feeding this nonsense into a computation, which it handles pretty well).

Re:A Journey building a fast JSON parser and full JSONPath, ... by gliptic on Sunday July 05, 2020 @05:21PM (#23742123)
You don't have to embed the string in the code, obviously. If you want to use a certain lib, I'm sure you can arrange for the buffer to be slightly bigger.
Re:A Journey building a fast JSON parser and full JSONPath, ... by hyperman1 on Sunday July 05, 2020 @11:59AM (#23739636)
Sorry, this is not realistic in C. The moment you get the json data, you have to also get the length, or you could not allocate enough memory for it.

Also, number of iterations is not the issue. Length of the input is. What happens if you r json is a few kb, is bigger than l1/l2 cache, ....

Re:A Journey building a fast JSON parser and full JSONPath, ... by peterohler on Sunday July 05, 2020 @12:22PM (#23739799)
Have you tried running the tests with a pre-calculated length? When I made that change there was no noticeable difference. The iterations/msec went from 195 to 192 which is not statistically significant.

I have no doubt a more complete set of benchmarks could be made with various sized JSON and from file as well as string. This was put together quickly to get an answer to the questions raised in this post. Since it does seem to be a topic of interest I'll expand and cleanup the tests in the future but for now it does give at least one data point.

You might notice that the somdjson::dom::parser is reused. Without that optimization to allow warming up the iteration/msec was only 160.

Re:A Journey building a fast JSON parser and full JSONPath, ... by hyperman1 on Sunday July 05, 2020 @12:41PM (#23739969)
Nope. You've got a code review from an interested random stranger on the net that spend 10s looking at your code, who noticed something suspect is going on.

Given your response, I spent 10s extra reading the simdjson docs and noting you violate the SIMDJSON_PADDING requirement. So either your code is a crash waiting to happen, or you use a very non- optimal code path in simdjson that requires it to re-copy all data.

That's also the maximum amount of attention you'l get from this random stranger. my time is up ;-)

Re:A Journey building a fast JSON parser and full JSONPath, ... by peterohler on Sunday July 05, 2020 @01:15PM (#23740228)
The code example followed was in the simdjson basics.md. The example in the error handling example left off the realloc_if_needed argument which does default to true. I have updated the tests to be explicit that third argument is set for clarity.

As for the path in simdjson being non-optimum and having to copy bytes, that should be expected if the string is to be modified. The buf argument type is a const after all so it should not be modified. In any case, glangdale's code is clean and solid so I doubt his code is anything but optimized and the examples correct.

Re:A Journey building a fast JSON parser and full JSONPath, ... by hyperman1 on Sunday July 05, 2020 @01:50PM (#23740467)
You can thank the cat on my lap for some bonus attention. I'll try to answer some points in this and other threads of yours. All this from a simdjson non-expert with a reasonable amount of C experience.

Suppose there is a socket with json data. What you do is, at init you create 1 or more buffers of, say, 64kb+required padding. Then, when epoll or whatever says there is data, you call read on this buffer. This gives you a length.

At this point, you have a padded buffer and a length, so requirements for simdjson(reallocifneeded=false) are met, so you can now parse at full speed. When done, reuse the buffer for the next epoll/read cycle.

There are complications, of course. Data is not guaranteed to arrive all together in 1 read call. There might be a http library feeding you. All of this amounts to mostly buffering and chunking. When carefull, they can be solved in a mostly zero copy way, ready for optimal simdjson.

The example simdjson code you refer to is a kind of demo mode. It gets you of the ground quickly, but is far from optimal.

I assume simdjson does not write to the buffer. It just reads more than 1 byte at once, so if it reads say 8 bytes and there is only 1 left, it will read 7 bytes of random junk. And discard them when it notices its unheeded optimism. However, it needs to be allowed to read these extra bytes without causing a SISEGV, hence the padding.

UPDATE all of this an educated guess, the simdjson authors are welcome to fix/finetune whatever I said.

Re:A Journey building a fast JSON parser and full JSONPath, ... by hyperman1 on Sunday July 05, 2020 @03:56PM (#23741422)
Seeing the downvotes I assume something is wrong in here. Feel free to add a correction.
Re:A Journey building a fast JSON parser and full JSONPath, ... by svnpenn on Sunday July 05, 2020 @04:32PM (#23741693)
The issue is youve been pretty arrogant/rude over multiple comments. Talking about your time like its some kind of gift from the heavens.
Re:A Journey building a fast JSON parser and full JSONPath, ... by hyperman1 on Sunday July 05, 2020 @05:36PM (#23742270)
Ok sorry. Apologies to everyone involved, the author first of all. It wasn't ment like that, for what its worth, but it clearly came out like that.
Re:A Journey building a fast JSON parser and full JSONPath, ... by glangdale on Sunday July 05, 2020 @09:37AM (#23738541)
Can you explain what you were measuring and what the general "GB/s"-type numbers you were seeing from both systems were?
Re:A Journey building a fast JSON parser and full JSONPath, ... by peterohler on Sunday July 05, 2020 @09:48AM (#23738603)
I was measuring extracting each piece of data in a JSON document on the assumption that all the data was needed as apposed to just a single field and then noting the time it took for each parser to complete. I will get the benchmarks code up.

That being said, simdjson does take an interesting approach and for just pulling out specific parts of a JSON document it is very fast.

Re:A Journey building a fast JSON parser and full JSONPath, ... by glangdale on Sunday July 05, 2020 @10:01AM (#23738699)
I'm confused as to how you did these measurements, then.

simdjson is designed to do the opposite of what you describe - nearly all the intellectual work in simdjson was focused on parsing a whole document in one hit, not on "pulling out specific parts of a JSON document".

So, I'm quite unclear on how you could derive a measurement that made us look fast on pulling out specific parts of a JSON document. That being said, I don't have a lot of experience with the current simdjson DOM traversal code and maybe there's some terrible "buried treasure" there (I mean sarcastically - i.e. we have some dumb decisions, maybe?) that you're tripping over. But the one-shot "parse" should be fast.

Anyhow, if you could try to code up something to show parsing speeds on workloads similar to what we describe at https://github.com/simdjson/simdjson it would be very interesting. We've made the effort to make all our benchmarks repeatable - if your approach is faster it would be cool and surprising.

That latter task is a valid use case, and interesting in itself, but not something we really knew how to measure and write about. The problem is with those sort of benchmarks is that they tend to resemble a "ask yourself a question then answer it" - I couldn't think of a good way of coming up with a set of "let's query a JSON file for a specific thing" benchmark that didn't seem ludicrously contrived.

Re:A Journey building a fast JSON parser and full JSONPath, ... by peterohler on Sunday July 05, 2020 @10:15AM (#23738802)
What I tried was getting each member of a parsed/loaded doc vs a single element. If I was using the library incorrectly my apologies. When I put the code up maybe you can give suggestions on how to make it more realistic. I will gladly retract my performance statement if it turns out I was using your library incorrectly.
Re:A Journey building a fast JSON parser and full JSONPath, ... by peterohler on Sunday July 05, 2020 @11:11AM (#23739251)
Re:A Journey building a fast JSON parser and full JSONPath, ... by tjko on Sunday July 05, 2020 @12:30PM (#23739875)
Do you not need to specify optimization flags when compiling?
Re:A Journey building a fast JSON parser and full JSONPath, ... by peterohler on Sunday July 05, 2020 @12:50PM (#23740037)
The -O3 optimization is just an optimization. It made a 1% difference in performance. It's just something I had in the Makefile I copied.
Re:A Journey building a fast JSON parser and full JSONPath, ... by shadeslayer_ on Sunday July 05, 2020 @10:06AM (#23738730)
well, now I'm invested in this.