Bit Hacking
July 21st, 2011Lion is the first operating system to require, and to fully take advantage of, 64-bit addressing modes in the Intel chips that power Apple’s Macintosh computers. One of the side-effects of this is that every object identifier in Mac OS X’s Cocoa programming framework (typically an address in memory), is now twice as long as it was in a 32-bit environment.
Apple has apparently taken advantage of the 64-bit runtime in Lion by optimizing the Objective C runtime itself to use some of these extra bits for, shall we say, clever purposes. Bavarious describes an optimization through which Apple is able to replace previously full-fledged opaque objects such as NSNumber with an object-placeholder that exists entirely as the 64-bit “object address” itself. This means that, for a wide range of “simple” objects, no additional memory allocation is required, and no retain/release memory management is required for the “object.”
The trick relies on a implementation detail of the system, that allocated blocks of memory will always be aligned at 16-byte offsets into the address space. This leaves a bunch of numbers that can be represented in 64-bits, that cannot reasonably be assigned to any other object. To understand this practically, imagine that your neighborhood’s postal addresses are all assigned at offsets of 10: 30, 40, 50, etc. A clever postal service could institute an addressing system that uses an “invalid” address such as “31,” to perhaps mean “deliver to 30 with expedited afternoon delivery.”
Cleverness like this with encoding extra information in memory addresses is a time-honored tradition. I recall the days of 24-bit addressing on classic Mac OS, where Apple, and many 3rd party developers, observed that the high 8 bits of a typical memory address could be tweaked and used to store additional information, because the system would never reference those bits when resolving a particular address.
In those days, using those extra bits turned out to be a pretty significant headache when 32-bit addressing ultimately came along, and lots of code had this “crufty” treatment of addresses to clean up. Perhaps it is a memory of situations like this that caused Jon “Wolf” Rentzsch to comment in his bookmarking of the above-referenced blog post:
“Every tagged pointer has its lowest bit set, hence tagged pointers are odd integers” Strikes me as a really bad idea. [Emphasis Mine]
But the difference now, in this scenario, is the “cute hacking” is all being done by a central power, with and in terms of opaque objects that only Apple has the authority to change. I think this is a really clever hack that will undoubtedly lead to some serious performance gains in Lion and beyond. It’s hard to imagine specific outcomes that will make Apple regret adopting this strategy. In the worst case scenario, an addressing system of future Macs will not leave any “spare” bits to be exploited, so the runtime will simply revert to its previous behavior.