Home Better JSON Pointer
Post
Cancel

Better JSON Pointer

This post was going to be something else, and somewhat more boring. Be glad you’re not reading that.

In the midst of updating JsonPointer.Net, instead of blindly forging on when metrics looked decent but the code was questionable, I stopped to consider whether I actually wanted to push out the changes I had made. In the end, I’m glad I hesitated.

In this post and at least the couple that follow, I will cover my experience trying to squeeze some more performance out of a simple, immutable type.

In the before times

The JsonPointer class is a typical object-oriented approach to implementing the JSON Pointer specification, RFC 6901.

Syntactically, a JSON Pointer is nothing more a series of string segments separated by forward slashes. All of the pointer segments follow the same rule: any tildes (~) or forward slashes (/) need to be escaped; otherwise, just use the string as-is.

A class is created to model a segment (PointerSegment), and then another class is created to house a series of them (JsonPointer). Easy.

Tack on some functionality for parsing, evaluation, and maybe some pointer math (combining and building pointers), and you have a full implementation.

An idea is formed

In thinking about how the model could be better, I realized that the class is immutable, and it doesn’t directly hold a lot of data. What if it were a struct? Then it could live on the stack, eliminating a memory allocation.

Then, instead of holding a collection of strings, it could hold just the full string and a collection of Range objects could indicate the segments as sort of “zero-allocation substrings”: one string allocation instead of an array of objects that hold strings.

This raises a question of whether the string should hold pointer-encoded segments. If it did, then .ToString() could just return the string, eliminating the need to build it, and I could provide new allocation-free string comparison methods that accounted for encoding so that users could still operate on segments.

I implemented all of this, and it worked! It actually worked quite well:

VersionnMeanErrorStdDevGen0Allocated
v4.0.112.778 us0.0546 us0.1025 us4.19628.57 KB
v5.0.011.718 us0.0335 us0.0435 us1.49153.05 KB
v4.0.11026.749 us0.5000 us0.7330 us41.961785.7 KB
v5.0.01016.719 us0.3219 us0.4186 us14.892630.47 KB
v4.0.1100286.995 us5.6853 us12.5983 us419.4336857.03 KB
v5.0.0100157.159 us2.5567 us2.1350 us149.1699304.69 KB

… for parsing. Pointer math was a bit different:

VersionnMeanErrorStdDevGen0Allocated
v4.0.11661.2 ns12.86 ns11.40 ns1.14732.34 KB
v5.0.01916.3 ns17.46 ns15.47 ns1.11202.27 KB
v4.0.1106,426.4 ns124.10 ns121.88 ns11.474623.44 KB
v5.0.0109,128.2 ns180.82 ns241.39 ns11.123722.73 KB
v4.0.110064,469.6 ns1,309.01 ns1,093.08 ns114.7461234.38 KB
v5.0.010092,437.0 ns1,766.38 ns1,963.33 ns111.3281227.34 KB

While the memory allocation decrease was… fine, the 50% run-time increase was unacceptable. I couldn’t figure out what was going on here, so I left it for about a week and started on some updates for JsonSchema.Net (post coming soon).

Initially for the pointer math, I was just creating a new string and then parsing that. The memory usage was a bit higher than what’s shown above, but the run-time was almost double. After a bit of thought, I realized I can explicitly build the string and the range array, which cut down on both the run time and the memory, but only so far as what’s shown above.

Eureka!

After a couple days, I finally figured out that by storing each segment, the old way could re-use segments between pointers. Sharing segments helps with pointer math where we’re chopping up and combining pointers.

For example, let’s combine /foo/bar and /baz. Under the old way, the pointers for those hold the arrays ['foo', 'bar'] and ['baz']. When combining them, I’d just merge the arrays: ['foo', 'bar', 'baz']. It’s allocating a new array, but not new strings. All of the segment strings stayed the same.

Under the new way, I’d actually build a new string /foo/bar/baz and then build a new array of Ranges to point to the substrings.

So this new architecture isn’t better after all.

A hybrid design

I thought some more about the two approaches. The old approach does pointer math really well, but I don’t like that I have an object (JsonPointer) that contains more objects (PointerSegment) that each contain strings. That seems wasteful.

Also, why did I make it a struct? Structs should be a fixed size, and strings are never a fixed size (which is a major reason string is a class). Secondly, the memory of a struct should also live on the stack, and strings and arrays (even arrays of structs) are stored on the heap; so really it’s only the container that’s on the stack. A struct just isn’t the right choice for this type, so I should change it back to a class.

What if the pointer just held the strings directly instead of having a secondary PointerSegment class? In the old design, PointerSegment handled all of the decoding/encoding logic, so that would have to live somewhere else, but that’s fine. So I don’t need a model for the segments; plain strings will do.

Lastly, I could make it implement IReadOnlyList<string>. That would give users a .Count property, an indexer to access segments, and allow them to iterate over segments directly.

A new implementation

Taking in all of this analysis, I updated JsonPointer again:

  • It’s a class again.
  • It holds an array of (decoded) strings for the segments.
  • It will cache its string representation.
    • Parsing a pointer already has the string; just store it.
    • Constructing a pointer and calling .ToString() builds on the fly and caches.

PointerSegment, which had also been changed to a struct in the first set of changes, remains a struct and acts as an intermediate type so that building pointers in code can mix strings and integer indices. (See the .Create() method used in the code samples below.) Keeping this as a struct means no allocations.

I fixed all of my tests and ran the benchmarks again:

ParsingCountMeanErrorStdDevGen0Allocated
5.0.013.825 us0.0760 us0.0961 us3.08236.3 KB
5.0.01036.155 us0.6979 us0.9074 us30.822862.97 KB
5.0.0100362.064 us6.7056 us6.2724 us308.1055629.69 KB
MathCountMeanErrorStdDevGen0Allocated
5.0.01538.2 ns10.12 ns10.83 ns0.97942 KB
5.0.0105,188.1 ns97.80 ns104.65 ns9.788520 KB
5.0.010058,245.0 ns646.43 ns539.80 ns97.9004200 KB

For parsing, run time is higher, generally about 30%, but allocations are down 26%.

For pointer math, run time and allocations are both down, about 20% and 15%, respectively.

I’m comfortable with the parsing time being a bit higher since I expect more usage of the pointer math.

Some new toys

In addition to the simple indexer you get from IReadOnlyList<string>, if you’re working in .Net 8, you also get a Range indexer which allows you to create a pointer using a subset of the segments. This is really handy when you want to get the parent of a pointer

1
2
var pointer = JsonPointer.Create("foo", "bar", 5, "baz");
var parent = pointer[..^1];  // /foo/bar/5

or maybe the relative local pointer (i.e. the last segment)

1
2
var pointer = JsonPointer.Create("foo", "bar", 5, "baz");
var local = pointer[^1..];  // /baz

These operations are pretty common in JsonSchema.Net.

For those of you who haven’t made it to .Net 8 just yet, this functionality is also available as methods:

1
2
3
var pointer = JsonPointer.Create("foo", "bar", 5, "baz");
var parent = pointer.GetAncestor(1);  // /foo/bar/5
var local = pointer.GetLocal(1);      // /baz

Personally, I like the indexer syntax. I was concerned at first that having an indexer return a new object might feel unorthodox to some developers, but that’s exactly what string does when you use a Range index to get a substring, so I’m fine with it.

Wrap up

I like where this landed a lot more than where it was in the middle. Something just felt off with the design, and I was having trouble isolating what the issue was. I like that PointerSegment isn’t part of the model anymore, and it’s just “syntax candy” to help build pointers. I really like the performance.

I learned a lot about memory management, which will be the subject of the next post. But more than that, I learned that sometimes inaction is the right action. I hesitated, and the library is better for it.

If you like the work I put out, and would like to help ensure that I keep it up, please consider becoming a sponsor!

This post is licensed under CC BY 4.0 by the author.

JSON Logic Without Models

Lessons in Memory Management