10 ms·
Very nice work. But could you please explain why counting digits quickly (or even slowly) is useful for a JSON serializer? This is lower level than I'm used to
by orra 2y ago
Very nice work. But could you please explain why counting digits quickly (or even slowly) is useful for a JSON serializer? This is lower level than I'm used to working. Is this so you can alloc the right amount of memory, or something else?
- ComputerGuru 2y agoYes. And for string formatting in general such as sprintf to calculate buffer size. Also for proposes of calculating length for string padding and alignment.
- o11c 2y agoHonestly? Most of the time you can use an approximation. At worst you allocate a single extra byte unless your integers are hundreds of bits long (I worked this out once but I forget where I left the details). Just multiply by the ratio of logs or something like that.
- Nevermark 2y agoNice. The best kind of optimization: Go lazy, to go fast. I often go slow, to go fast. But lazy is the supremum.
- eapriv 2y agoIsn’t “the ratio of logs” going to be slower?
- o11c 2y agoI mean the constant logs of the bases; you get to hard-code this in the algorithm. One interesting coincidence is that log₁₀(2) ~= log₂(10) - 3, thus the 83 ~= 78 below. If you use an 8-bit shift, depending on which direction you're going, you multiply the input length by 851 (which is 3*256 + 83) or 78, then shift by 8. This starts being wasteful at 23 bits, but is pretty cheap on 8-bit CPUs. For a more accurate approximation (slackening at 289 bits), 217706 (3<<16 + 21098) or 19729, then >> 16
- exyi 2y agoI'd assume that the serializer is writing directly into the output buffer, so you'd have to shift everything left by one character if you overallocate. With the added checks for this, it might be faster to compute it precisely the first time.
- vbezhenar 2y agoBecause JSON is not well suitable as a fast machine exchange format and people trying to make it work anyway. If you ask me, JSON serializers should be simple and slow, and if you need speed, change wire format for something intrinsically fast. I understand that this is not the approach that people will take, most developers prefer simple interface with complex implementation over complex interface with simple implementation. But my opinion is that implementation simplicity is what matters in the end.
- touisteur 2y agoAnother way of seeing this is: whatever way people are using JSON, over a fleet of all the machines running the parser (or serializer), reducing the execution time (a good enough proxy to energy consumption) on the whole fleet is worthwile. Especially if it has zero impact on the code calling this parser/serializer (so, no second-order energy spent because of the change breaking some API or contract).
- GuB-42 2y agoI think it is the case: first allocate the space, then write. However, I am not sure how significant the gain is here. Actually printing the number requires a division every digit, maybe 2 or 3, which I believe is much slower than even naive digit counting, and you will have to do it eventually. Maybe it is worth it if there is parallelism involved: write the JSON with blank spaces for the numbers, then have another thread write the numbers. Writing the numbers is computationally expensive because of the divisions, so if you have a lot of large numbers, it may be worth dedicating some cores to this task.
- realtimechris 2y agoNo, you only require division for digit-counts greater than or equal to 10: https://github.com/RealTimeChris/Jsonifier/blob/dev/Include/jsonifier/IToStr.hpp#L71-L410 https://github.com/RealTimeChris/Jsonifier/blob/dev/Include/...
- realtimechris 2y agoSo we can properly dispatch the correct length-based function with minimal branching to detect which length to serialize for: https://github.com/RealTimeChris/Jsonifier/blob/dev/Include/jsonifier/IToStr.hpp#L412-L478 https://github.com/RealTimeChris/Jsonifier/blob/dev/Include/...