Optimizing Ruby's JSON, Part 4

Very glad to see the work that byroot is doing as the new ruby-json maintainer!

Since I was mentioned by name in part 3, perhaps I can provide some interesting commentary:

> All this code had recently been rewritten pretty much from scratch by Luke Shumaker ... While this code is very clean and generic, with a good separation of the multiple levels of abstractions, such as bytes and codepoints, that would make it very easy to extend the escaping logic, it isn’t taking advantage of many assumptions convert_UTF8_to_JSON could make to take shortcuts.

My rewritten version was already slightly faster than the original version, so I didn't feel the need to spend more time optimizing it, at least until the simple version got merged; which I had no idea when that'd be because of silence from the then-maintainer. Every optimization would be an opportunity for more pain when rebasing away merge-conflicts; which was already painful enough the 2 times I had to do it while waiting for a reply.

> One of these for instance is that there’s no point validating the UTF-8 encoding because Ruby did it for us and it’s impossible to end up inside convert_UTF8_to_JSON with invalid UTF-8.

I don't care to dig through the history to see exactly what changed when, but: At the time I wrote it, the unit tests told me that wasn't true; if I omitted the checks for invalid UTF-8, then the tests failed.

> Another is that there are only two multi-byte characters we care about, and both start with the same 0xE2 byte, so the decoding into codepoints is a bit superfluous. ... we can re-use Mame’s lookup table, but with a twist.

I noted in the original PR description that I thought a lookup table would be faster than my decoder. I didn't use a lookup table myself (1) to keep the initial version simple to make code-review simple to increase likelihood that it got merged, and (2) the old proprietary CVTUTF code used a lookup table, and because I was so familiar with the CVTUTF code, I didn't feel comfortable being the one to to re-add a lookup table. Glad to see that my suspicion was correct and that someone else did the work!

Oj author here. While it's flattering to have Oj be the standard to beat I'd like to point out that most of the issues with Oj revolve around the JSON gem and Rails doing a monkey patch dance and Oj trying to keep pace with the changes. The Oj.mimic_JSON attempts to replace the JSON gem and only replaces the monkey patches made by that gem. The preferred approach for Oj outside of trying to mimic the JSON gem to to never monkey patch. That approach is used in all other modes that are not mimicking the JSON gem or Rails. I should point out that other Oj modes perform much better than the JSON gem and Rails modes.

Hackernews has a surprising amount of Ruby news over the large few months. As Ruby is my first true (=production) love, I'm here for it.

I've spent the last years in Python land, recently heavily LLM assisted, but I'm itching to do something with Ruby (and or Rails) again.

I haven't seen this many Ruby posts on HN since 2012.

We've had a few months of pretty regular Ruby posts now, and the last week has had one almost every single day.

I'm not a regular Rubyist, but I'm glad to see the language getting more attention.

This was really enjoyable to read - I really enjoy this kind of in-the-weeds optimisation and the author explains it all really well. I was surprised at how much Oj was willing to put on the stack! But my background is embedded and so large stack allocations have ruined my day more than once

It's pretty lame that ISO C doesn't provide integer-to-string conversion that does not go through a printf-family formatter, so that programs are still rolling their own "itoa" as the calendar turns to 2025.

Format strings are compilable in principle, so that:

  snprintf(buf, sizeof buf, "%ld", long_value);

can just turn into some compiler-specific run-time function. The compiler also can tell when the buffer is obviously large enough to hold any possible value, and use a function that doesn't need the size.

How common is that, though?

Common Lisp's format function can accept a function instead of a format string. The arguments are passed to that function and it is assumed to do the job:

  (format t (lambda (...) ...) args ...)

There is a macro called formatter which takes a format string, and compiles it to such a function.

  [8]> (format t "~1,05f" pi)
  3.14159
  NIL
  [9]> (format t "~10,5f" pi)
     3.14159
  NIL
  [10]> (format t (formatter "~10,5f") pi)
     3.14159
  NIL
  [11]> (macroexpand '(formatter "~10,5F"))
  #'(LAMBDA (STREAM #:ARG3345 &REST #:ARGS3342) (DECLARE (IGNORABLE STREAM))
     (LET ((SYSTEM::*FORMAT-CS* NIL)) (DECLARE (IGNORABLE #:ARG3345 #:ARGS3342))
      (SYSTEM::DO-FORMAT-FIXED-FLOAT STREAM NIL NIL 10 5 NIL NIL NIL #:ARG3345) #:ARGS3342)) ;
  T

In this implementation, formatter takes "~10,5f" and spins it into a (system::do-format-fixed-float ...) call where the field width and precision arguments are constants. Just the stream and numeric argument are passed in, along with a bunch of other arguments that are defaulted to nil.

I think CL implementations are allowed to apply formatter implicitly, which would make sense at least in code compiled for speed.

Just think: this stuff existed before there was a GNU C compiler. It was a huge progress when it started diagnosing mismatches between format strings literal and printf arguments.

Man, if I had a nickel every time I saw an itoa/ltoa/lltoa implementation that doesn't work on the most negative number I'd have about $10 or so, I think.

The annyoing thing about it is that all the workarounds I know about are really ain't that pretty:

1. You can hard-code the check against it and return a hardcoded string representation of it:

    if (number == -9223372036854775808) return "-9223372036854775808";

By the way, "(number && (number == -number))" condition doesn't work so don't try to be too smart about it: just compare against INT_MIN/LONG_MIN/etc.

2. You can widen the numeric type, and do the conversion in the larger integer width, but it doesn't really work for intmax_t and it's, of course, is slower. Alternatively, you can perform only the first iteration in the widened arithmetic, and do the rest in the original width, but this leads to some code duplication.

2a. You can do

    unsigned unumber = number;
    if (number < 0) unumber = -unumber;

and convert the unsigned number instead. Again, you can chose to do only the first iteration in the unsigned, on platforms where unsigned multiplication/division is slower than signed ones. Oh, and again, beware that "unsigned unumber = number < 0 ? -number : number" way of conversion doesn't work.

3. You can, instead of turning the negative numbers into positive ones and working with the positive numbers, do the opposite: turn positive numbers into negative ones and work exclusively with the negative numbers. Such conversion is safe, and division in C is required to truncate to zero, so it all works out fine except for the fact that the remainders will be negative; you'll have to deal with that.

But yeah, converting integers into strings is surprisingly slow; not as slow as converting floats, but still very noticeable. Maybe BCDs weren't such a silly idea, after all...

Would allocating a 640-byte string initially really be the right tradeoff? It seems like it could result in a lot of memory overhead if many small strings are created that don’t need that space. But it does save a copy at least

As for the int-to-string function, using the division result to do a faster modulus (eg with the div function) and possibly a lookup table seem like they’d help (there must be some good open source libraries focused on this to look at).

This makes me want to re-compare REXML and ox (from the same author as oj) which I use heavily.

> Why ato? Because C doesn’t really have strings, but arrays of bytes, hence “array to int” -> atoi.

The lore I was familiar with was that a stood for ascii.

I recommend reading the previous 3 parts too, plus I'm looking forward to the next parts. I love that it goes into details and very clearly explains the problems and solutions, at least if you're familiar with C and know some things about compiler implementations.

Really enjoyed the new article, as always!

Maybe at the end, he should have shown the two profiles again for comparison :D

Whats the reason for not merging/using Oj as the Ruby core JSON library?