12 ms·
One of the two authors here. Happy to answer questions. The intent was to open things but not publicize them at this stage but Hacker News seems to find stuff.
by glangdale 8y ago
One of the two authors here. Happy to answer questions.
The intent was to open things but not publicize them at this stage but Hacker News seems to find stuff. Wouldn't surprise me if plenty of folks follow Daniel Lemire on Github as his stuff is always interesting.
- SoSKatan 8y agoI've written my fare share of performant code over the years, but this is some next level shit. I've been reading it the last few hours. The only question I have is what is the term for that place considered two degrees past black magic? Since you live there, I have to assume you know the name.
- glangdale 8y agoIt's not magic. The things that enable writing this kind of code are essentially practice and specialization. Most people have to write code that works all all architectures and where performance is probably less critical than having a simple, workable codebase - so the opportunities to practice writing SIMD code are rare under those constraints. Unfortunately, the fragmentation of SIMD standards and various pitfalls in implementation (the much ballyhoo'ed "running AVX will make your processor clock to half its speed or something" exaggerations, for example) make a lot of people nervous about putting in the time to commit to developing expertise, which is a shame.
- SoSKatan 8y agoNot really a question, but if you ever get to the point of wondering what a good next challenging project would be, consider generalizing some of these techniques into a next generation Yacc / Bison replacement. Something that can take generic grammer rules and turn it into a high performance parsing engine. It wouldn't have to support every possible grammar or option. Json isn't that complex of a language, but even a limited set of grammar options in exchange for a performant parser could be of benefit for a very large set of problems.
- anitil 8y agoOh now that would be an interesting tool
- glangdale 8y agoIt's on the list as a research project. It's not obvious to me at this stage that the bottlenecks for more advanced parsers are necessarily going to be in the same place as they are for JSON. It might make more sense to look at a state-of-the-art parser and see if we can contribute a few tricks instead.
- imoldfella 8y agoI'm just starting to look at Tree-sitter; that might qualify as a state of the art parser that could use a few tricks.
- dkersten 8y agoThat sounds interesting. Where is the best place to follow your future work? Your & Daniel Lemire's Github, or elsewhere?
- glangdale 8y agoI might go so far as to post to branchfree.org, and Daniel posts at https://lemire.me/blog/ https://lemire.me/blog/ so either of those, plus github, ought to cover it.
- chairmanwow 8y agoAny technical blog articles you have that explain how you were able to ascertain these incredible performance gains? Kudos on some incredible work! :)
- Jerry2 8y agoI'm writing an IoT library for devices with tiny microprocessors and have been sending data as JSON or BSON (binary JSON). On the backend, I've been storing reports from IoT devices into a database (MariaDB on AWS). How crazy would it be to just store all the data as JSON files on disk (or S3 bucket) and then batch process them when I need to perform data analysis on them? If a million devices sends dozens of status reports per day, that's going to be a crapton on files... but that might be faster to process than querying the database. If you or anyone else has some opinions on this, please let me know! I'd really like to learn how people do this type of analysis at scale.
- tobilg 8y agoWe‘re using AWS Kinesis delivery streams to batch incoming JSON messages from IoT devices to Parquet files in S3. Those can directly be read by different AWS services like Redshift, EMR or Athena...
- DanFeldman 8y agoWe use Athena for all our robotics data, which we ETL into JSON. It's fantastic for queries that are simple time-slice queries, as most are because sensor data is inherently time-series. When more complicated joins are necessary, the performance is there across terabytes, and the cost is very very low, $5 per terabyte scanned (storage costs are another thing).
- RhodesianHunter 8y agoWhat bothers me about Kinesis is that it is prohibitively expensive at scale if you don't compress your data before putting it to Kinesis. But if you want to use the nice features like parquet conversion your data can't be compressed. If it could handle compressed data at the same price I would use a lot more of it.
- PhilippGille 8y agoIf you are considering using plain files instead of a DB server, you could try a compromise and use an embedded key-value store like RocksDB, LevelDB, BadgerDB etc. It's local storage only, limited query capabilities depending on the DB, but should be extremely fast.
- defen 8y agoHow hard would it be to extend the parser to handle arbitrary-precision numbers? Strictly speaking the JSON spec does not require numbers to fit into 64-bit ints / doubles.
- glangdale 8y agoDaniel Lemire did most of the work on the number handling, but our general approach was to try to do work that's similar to what the bulk of other libraries do. I believe pretty much everyone throws oversize numbers on the floor. I don't think it would be hard at all; it would just be extra effort that wasn't needed to run obvious comparisons.
- avodonosov 8y agoAny chance to have a similar thing for s-expressions? I parse GBs of them and Common Lisp reader is very slow.
- glangdale 8y agoProbably not too hard. It would come down to how easy it is to detect quoting conventions so you don't accidentally parse () chars in strings. JSON is medium-easy. I don't know where the canonical definition of s-expressions you're using comes from (is it just Common Lisp?) so I don't know how this works. We'd like to have some more examples of formats people care about - I'm interested in generalizing this work. So if you want to followup with more detail please do.
- dkersten 8y agoAs a clojure user, I care about EDN, but its probably too niche to spend your time on. https://github.com/edn-format/edn https://github.com/edn-format/edn
- nojvek 8y agoYes!!! A generalization for other kinds of simple grammars would be awesome. On another note. As a js programmer who deals with a ton of json, I would love v8 to adopt some of the tricks into their json parser.
- deleted 8y ago[deleted]
- popotamonga 8y agoAny plan for wrapper for android?
- glangdale 8y agoThis would imply an ARM port, I guess, as x86 android isn't much of a thing anymore AFAIK. I don't think either of us know much about android - not enough to do that. But an ARM port is very interesting. Since I'm no longer an Intel employee I don't see why I shouldn't skill up and do a Neon port (I got interested in SVE, but since ARM doesn't seem to want to bother releasing cores that run SVE, I'm not going to go too far down that path right now). Neon, on the other hand, is in tons of places. As far as I know all the required permutes, carryless multiplies and various other SIMD bits and pieces are there on Neon. So it's a simple matter of porting.
- m_rcin 8y agoThe big difference between RapidJson and sajson is surprising to me. When I benchmarked them their performance was comparable: https://github.com/project-gemmi/benchmarking-json https://github.com/project-gemmi/benchmarking-json . Did you use RapidJson in full-precision mode? By the way, nativejson-benchmark (from RapidJson) has a nice conformance checker that tries various corner cases. But you probably know it.
- glangdale 8y agoMore performance details beyond what's on the site will follow (in a while). We use RapidJSON in the high-performance mode not the funky mode that minimizes FP error (which is some astounding work - I had no idea that strtof was so involved!). Number conversion is not our #1 focus - doing it well is nice, but all implementations have access to the same FP tricks, so you don't really learn much by going wild on this aspect. At least, you don't unless FP conversion is your focus, in which case you should share your FP conversion code with everyone!
- leeter 8y agoYou should take a look at std::from_chars IIRC it can completely destroy other parsers within the stdlib because it's not intended to take locale into consideration. https://en.cppreference.com/w/cpp/utility/from_chars https://en.cppreference.com/w/cpp/utility/from_chars
- floofy222 8y agoI see that you are using MMX intrinsics directly, like _mm_sub_pi8, but you are never calling _mm_empty (https://software.intel.com/sites/landingpage/IntrinsicsGuide/#text=mm_em&expand=5690,2199 https://software.intel.com/sites/landingpage/IntrinsicsGuide...) as required by the SysV AMD64 ABI (and pretty much all other ABIs out there). I think the behavior of all the code that touches is undefined (it breaks the calling convention of the ABI), and while this often results in corrupted floating point values in registers, maybe you won't see much if you are not using the FPU. Still, since the function is inline, chances that this gets inlined somewhere where it could cause trouble seem high. You might want to look into that. Also, I wish this would all be written in Rust, there is great portable SIMD support over there. Might make your life easier trying to target other platforms. EDIT: as burntsushi mentions below, that's not available in stable Rust, but if you want to squeeze out the last once of performance out of the Rust compiler, chances are you won't be using that anyways.
- burntsushi 8y ago> there is great portable SIMD support over there It's not stable yet. The only stable SIMD stuff Rust supports is access to the raw x86 vendor intrinsics.
- floofy222 8y agoIf they want to squeeze out the last ounce of performance out of the Rust toolchain it probably wouldn't make sense to use stable Rust anyways, so I don't think that's a big downside. Also, they are already relying on "unstable" (non-standard conforming) C++ features (e.g. the code uses non-standard attributes behind macros, etc.). Using nightly Rust isn't worse than that per se. Using Rust does have downsides. For the type of code they are writing, the main downside would probably be losing an alternative GCC backend, which might or might not be better than LLVM for their application. Still, they would win portable SIMD and being able to target not only x86_64 but also ARM, Power, RISCV, WASM, etc., which is always cool to show in research papers. I'm not suggesting that Rust is a perfect trade-off, only that it's an interesting one depending on what they want to do.
- jackdh 8y agoWhy did you decide to write this? What was the motivation?
- glangdale 8y agoHonestly? I was trolled into it. :-) Unemployed people do weird things. I can't speak for Daniel's motivation.
- billconan 8y agoI recently saw people using gpu to parse csv files. there are also other articles on using gpu to parse json. do you think if gpu can perform well on this type of tasks?
- glangdale 8y agoI'm not aware of an article that covers a actual implementation or that has a benchmark of performance. As for GPGPU: it's possible. Our first stage of matching is very parallel. But Amdahl's law would, of course, suggest that the serial parsing step would dominate. I'm interested in this: some aspects of our very serial 'stage 2' (the parsing step) could be made parallel. This would be very interesting. Unfortunately I personally cannot be made parallel, so working on this needs to go into a big queue with a lot of other work.
- AtlasBarfed 8y agoJackson benchmarks? I've heard it's twice as fast as rapidjson.