Collection literals

Last week Ted Kremenek added support for container literals and subscripting to Clang. This was noted in various places, though mostly only as a statement and maybe an example of the new container literals. But I wanted to know how they’re implemented.

The answer is pretty easy to find. The relevant code follows a similar path within Clang as the existing NSString literals, which is to say that the guts of it live in CGObjC.cpp. You’ll now find, in addition to the familiar EmitObjCStringLiteral():

  • EmitObjCNumericLiteral()
  • EmitObjCArrayLiteral()
  • EmitObjCDictionaryLiteral()

What is unexpected is that they aren’t implemented the way you’d expect. Which is to say, the way NSString literals are implemented; as special, compile-time constructed instances that always exist. EmitObjCStringLiteral() ultimately just calls GetAddrOfConstantCFString() in CodeGenModule.cpp, which:

  1. Checks that there’s not an existing string constant with the same value, in which case it returns the address of that.
  2. Creates a global variable to be the NSString instance (actually an instance of whatever the constant string type is), and populates it with the class pointer, some flags indicating whether it’s UTF16 or not (in which case I presume it’s UTF8), the length, and a pointer to the actual string data…
  3. Which is allocated as a separate global variable.

So you end up with your actual string plus a 16-byte NSString instance in the read-only data section of your library. Pretty efficient at runtime.

Yet the new literals aren’t implemented like this at all. Numeric literals could in fact be implemented even more efficiently – NSNumber supports tagged pointers, which is where the actual pointer contains the entire object, rather than pointing to a heap-allocated instance. It doesn’t work for all numbers, of course, but it handles a lot of common cases, and a fallback to a compile-time constructed instance would be fine.

Instead, it generates a runtime call to the appropriate class constructor method on NSNumber. So you’re going to hit e.g. +[NSNumber numberWithInt:] every single time you execute a line that contains @5. Don’t forget that means it gets added to the autorelease pool. While NSNumber does keep a cache of likely-common instances (small integers near zero, for example), that’s not tuned to your particular code and it’s not going to cover many uses.

That’s all amazingly inefficient. I can only assume that this is the naive initial implementation, that will then be improved upon.

Likewise the NSArray and NSDictionary literals are also emitted as runtime calls to the appropriate class constructor method (either +[NSArray arrayWithObjects:count:] or +[NSDictionary dictionaryWithObjects:forKeys:count:], by default).

For the collections at least I can see that being slightly more rational, given that the collections are significantly more complex than simple string or number literals, and those classes have been known to change their implementations at runtime depending on their capacity and other factors.

It’s also possible that it’s implemented this way, for now, in order to support all Objective-C runtimes, not just the Mac and iOS ones. This is in CGObjC.cpp after all, not CGObjCMac.cpp. Though it’s worth noting that string literals are handled differently between the Mac/iOS and the GNU runtimes.

I hope the implementation improves. Even performance aside, there’s some potential initialisation order problems that follow from invoking actual class methods to generate the literals. I don’t know if I’d shy away from using these new literals for the initialisation of static variables or constants, but I’d think twice about it.

Leave a Comment