metablog: Equally Lethargic JSON Support for iOS/macOS, Part 4: Our Keys are Small but Legion

In our last instalment, we started implementing our JSON parser with lots of good ideas, such as dematerialization via a property list protocol, but immediately fell flat on our face with our code being 50% slower than NSJSONSerialization. And what's worse, there wasn't an obvious way out, as the bulk of the time was spent in Apple code.

Nobody said this was going to be easy.

Analysis

Let's have another look at the profile:

The top 4 consumers of CPU are -setObject:forKey:, string creation, dictionary creation and message sending. I don't really know what to do about either creating those dictionaries we have to create or setting their contents, so what about string creation?

Although making string creation itself faster is unlikely, what we can do is reduce the number of strings we create: since most of our JSON payload consists of objects né dictionaries, the vast majority of our strings is actually going to be string keys. So they will come from a small set of known strings and be on the small-ish side. Particularly the former suggests that we should re-use keys, rather than creating multiple new copies.

The usual way to look up something with a known key is an NSDictionary, but alas that would require the keys we look up to already be objects, meaning we would have to create string objects to look up our sting object values, rather defeating the purpose of the exercise.

What we would need is a way of looking up objects by raw C-Sting, an unadorned char*. Fortunately, I've been here before, so the required class has been in MPWFoundation for a little over 13 years. (What's the "Trump smug face emoticon?)

MPWSmallSStringTable

The MPWSmallStringTable (.h / .m ) class is exactly what it says on the tin: a table for looking up objects by (small) string keys. And it is accessible by char* (+length, don't want to require NUL termination) in addition to string objects.

Quite a bit of work went into making this fast, both the implementation and the interface. It is not a hash table, it compares chars directly, using indexing and bucketing to expend as little work as possible while discarding non-matching strings.

In fact, since performance is its primary reason for existing, its unit tests include performance comparisons against an NSDictionary with NSString keys, which currently clock in at 5-8x faster.

The interface includes two macros: OBJECTFORSTRINGLENGTH() and OBJECTFORCONSTANTSTRING(). You need to give the former a length, the latter figures the size out compile time using the sizeof operator, which really does return the length of string constants. Don't use it with non-constant strings (so char*) as there sizeof will return the size of the pointer.

Avoiding Allocation of Frequent Strings

With MPWSmallStringTable at hand, we can now use it in MPWMASONParser to look up common strings like our keys without allocating them.

The -setFrequentStrings: method we saw declared in the interface takes an array of strings, which the parser turns into a string table mapping from the C-Sting versions of those to the NSString version.


-(void)setFrequentStrings:(NSArray*)strings
{
	[self setCommonStrings:[[[MPWSmallStringTable alloc] initWithKeys:strings values:strings] autorelease]];
}

The method that is supposed to create string objects from char*s starts as follows:


-(NSString*)makeRetainedJSONStringStart:(const char*)start length:(long)len
{
	NSString *curstr;
	if ( commonStrings  ) {
		NSString *res=OBJECTFORSTRINGLENGTH( commonStrings, start, len );
		if ( res ) {
			return [res retain];
		}
	}
    ...

So we first check the common stings table, and only if we don't find it there do we drop down to the code to allocated the string. (Yeah, the -retain is probably questionable, though currently necessary)

Trying it out

Now all we need to do is tell the parser about those common strings before we ask it to parse JSON.


-(void)decodeMPWDicts:(NSData*)json
{
    NSArray *keys=@[ @"hi", @"there", @"comment"];
    MPWMASONParser *parser=[MPWMASONParser parser];
    [parser setFrequentStrings:keys];
    NSArray* plistResult = [parser parsedData:json];
    NSLog(@"MPWMASON %@ with %ld dicts",[plistResult firstObject],[plistResult count]);
}

While this seems a bit tacky, telling a JSON parser what to expect beforehand at least a little seems par for the course, so whatever.

How does that fare? Well, 440ms, which is 180ms faster than before and anywhere from as fast as NSJSONSerialization to 5% slower. Good enough for now.

This result is actually a bit surprising, because the keys that are created by both NSJSONSerialization and MPWMASONParser happen to be instances of NSTaggedPointerString. These strings do not get allocated on the heap, the entire string contents are cleverly encoded in the object pointer itself. Creating these should only be a couple of shifts and ORs, but apparently that takes (significantly) longer than doing the lookup, or more likely CF adds other overhead. This was certainly the case with the original tagged CFNumber, where just doing the shift+OR yourself was massively faster than calling CFNumberCreate().

What next?

Having MPWSmallStringTable immediately suggests ways of tackling the other expensive parts we identified in the profile, -setObject:forKey: and dictionary creation: use a string table with pre-computed key space, then set the objects via char* keys.

Another alternative is to use the MPWXmlAttributes class from MAX, which is optimized for the parsing and use-once case.

However, all this loses sight of the fact that we aren't actually interested in producing a plist. We want to create objects, ideally without creating that plist. This is a common pitfall I see in optimization work: getting so caught up in the details (because there is a lot of detail, and it tends to be important) that one loses sight of the context, the big picture so to speak.

Can this, creating objects from JSON, now be done more quickly? That will be in the next instalment. But as a taste of what's possible, we can just set the builder to nil, in order to see how the parser does when not having to create a plist.

The result: 160ms.

So yes, this can probably work, but it is work.

metablog

Thursday, April 16, 2020

Equally Lethargic JSON Support for iOS/macOS, Part 4: Our Keys are Small but Legion

Analysis

MPWSmallSStringTable

Avoiding Allocation of Frequent Strings

Trying it out

What next?

TOC

No comments:

Post a Comment