Similarly Inactive JSON Support for iOS/macOS, Part 4: Our Keys are Numerous yet Compact

In the previous blog post (last instalment), we started building our JSON parser with promising ideas like dematerialization using a property list protocol. However, our code ended up being 50% slower than Apple’s NSJSONSerialization, primarily due to time spent in Apple’s code, leaving us with no clear solution.

Despite the challenges, we’re determined to improve its performance.

Analysis

Examining the performance profile again:

We see that -setObject:forKey:, string creation, dictionary creation, and message sending are the top CPU consumers. While optimizing dictionary creation and population seems difficult, we can focus on reducing string creation overhead.

Since most of our JSON data consists of objects (dictionaries), the majority of the strings are keys from a small, known set and relatively short. This suggests reusing keys instead of creating new copies.

Using NSDictionary for key-based lookup requires the keys to be objects, which defeats the purpose. What we need is a way to look up objects using raw C-strings (char*). Thankfully, the MPWSmallStringTable class in MPWFoundation (available for over 13 years) addresses this need.

MPWSmallStringTable

True to its name, the MPWSmallStringTable (.h / .m) allows looking up objects by small string keys using char* (+length, avoiding NUL termination) or string objects.

This class is optimized for speed, both in implementation and interface. It’s not a hash table; it directly compares characters using indexing and bucketing to minimize work and quickly discard non-matching strings.

Performance tests show it to be 5-8x faster than NSDictionary with NSString keys.

The interface provides two macros: OBJECTFORSTRINGLENGTH() requiring a length, and OBJECTFORCONSTANTSTRING(), which calculates the length at compile time using sizeof (only for constant strings, not char*).

Avoiding Allocation of Frequent Strings

With MPWSmallStringTable, we can look up common strings like keys in MPWMASONParser without allocating them.

The -setFrequentStrings: method takes an array of strings, which the parser converts into a string table mapping C-string versions to their NSString counterparts.

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

The method for creating string objects from char*s now checks the common strings table before allocating:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
-(NSString*)makeRetainedJSONStringStart:(const char*)start length:(long)len
{
	NSString *curstr;
	if ( commonStrings  ) {
		NSString *res=OBJECTFORSTRINGLENGTH( commonStrings, start, len );
		if ( res ) {
			return [res retain];
		}
	}
    ...

Trying it out

We need to inform the parser about common strings before parsing:

1
2
3
4
5
6
7
8
-(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 providing hints to the parser might seem unusual, it’s acceptable in this context.

The result? 440ms, 180ms faster than before, and either on par with or up to 5% slower than NSJSONSerialization. This is a significant improvement.

This result is surprising because both NSJSONSerialization and MPWMASONParser create NSTaggedPointerString keys, which are encoded within the pointer itself, avoiding heap allocation. Creating them should be quick, but the lookup outperforms it, possibly due to CF overhead.

What next?

MPWSmallStringTable inspires further optimizations for -setObject:forKey: and dictionary creation: using a string table with pre-computed key space and setting objects via char* keys.

Alternatively, we could use the MPWXmlAttributes class from MAX, optimized for parsing and single-use cases.

However, we should not lose sight of our goal: directly creating objects from JSON without an intermediary plist. Getting lost in details can obscure the bigger picture.

Can we achieve faster object creation? We’ll explore that in the next blog post (next instalment). For now, disabling plist creation by setting builder to nil in the parser yields a promising 160ms, suggesting significant potential for improvement.