mikeash.com pyblog/friday-qa-2012-07-27-lets-build-tagged-pointers.html comments

mikeash - 2016-11-22 15:10:09

Tue, 22 Nov 2016 15:10:09 GMT

Alex: If your pointers are 16-byte aligned, then a tagged pointer could be identified by having any of the lower four bits be non-zero. That would allow for 15 tagged classes, rather than only 8 as the Objective-C implementation does.

One problem is that pointers aren't necessarily 16-byte aligned. Objects allocated on the heap are, but things like class pointers or constant strings may not be. You should at least be able to count on 8-byte alignment on a 64-bit CPU, so you could identify a tagged pointer based on any of the lower three bits being 1.

I'd speculate that only checking the least significant bit is faster (and this is an operation that has to be done as part of the message sending fast path) and Apple probably doesn't really need more than 8 tagged classes anyway, at least for now.

Alex - 2016-11-20 17:40:26

Sun, 20 Nov 2016 17:40:26 GMT

"For whatever reason, the Objective-C implementation of tagged pointers has the bottom bit always set to 1 in a tagged pointer, with the other three bits indicating the class of the tagged pointer. I'm not sure why they chose to implement it in this way"

This is how every implementation of tagged pointers I've seen works. How else would you implement it?

J Osborne - 2012-08-17 18:06:02

Fri, 17 Aug 2012 18:06:02 GMT

A less historic bit addressable machine then the C205 would be the TI34010 and TI34020 which are a late 1980's, early 1990's combination of a general purpose CPU and a graphics processor.

There was even a C compiler available. More then one in fact.

Well technically those are the CPUs, the machines would be all of MicroProse's arcade line (F-15 Strike Eagle, B.O.T.T.S., the tank game that I worked on but can't remember the name of), and also NARC and Hard Drivin' (which at the time I thought was a 680x0 with custom microcode, but I guess I was mistaken).

Of corse in addition to being bit addressable these machines also had polygon painting instructions :-)

Matthew Burke - 2012-08-14 16:31:09

Tue, 14 Aug 2012 16:31:09 GMT

Mike, a very lucid explanation (as always).

For anybody interested in another implementation of this idea, I recommend reading http://www.lua.org/doc/jucs05.pdf which describes Lua's implementation. Section 3 of the paper describes how values are represented. The paper is a little out of date--it describes Lua 5.0; the current version is 5.2. For specific details, Lua's source is quite readable. The relevant portion is found at http://www.lua.org/source/5.2/lobject.h.html.

mikeash - 2012-08-13 18:09:55

Mon, 13 Aug 2012 18:09:55 GMT

Warmi: I don't think that's an accurate characterization. These are still objects, they're just objects that can be stored directly within the pointer. As for system-specific non-portable hacks, that's true but also applies to everything your compiler outputs, as well as a good chunk of the runtime. (The objc_msgSend is written in assembly, and is definitely not portable.)

Not everything has to be portable. Tagged pointers can be turned off at the flip of a switch and everything keeps working fine, just a bit more slowly, so there's literally no risk here. If Apple introduces a platform where the current code doesn't work, they can either fix it up to work there, or they can turn it off.

I'm a bit surprised by the negative reactions to this stuff from some of the commenters. This is an ancient and time-honored technique that has many upsides and no downside whatsoever the way Apple implemented it, aside from the (relatively minor) engineering time needed to build it.

Warmi - 2012-08-11 05:42:05

Sat, 11 Aug 2012 05:42:05 GMT

Hmm so you come up with a language/framework where you declare that everything is an object ... And then you go ahead and implement incredibly system specific and non portable hacks because it turns out that making everything into an object makes your code crawl.

Clever.

Dave Polaschek - 2012-08-06 13:55:29

Mon, 06 Aug 2012 13:55:29 GMT

Historical note - there were systems (the Control Data Cyber 205 was one) in which pointers had no alignment restrictions - pointers were 64-bit (the native word size of the machine) but were BIT-aligned. The C205 didn't have a rotate or bit-shift instruction. If you wanted such a result, you simply set your pointer to the correct bit of the word and read (or wrote) the data that way. Yeah, there would be a performance-hit (3 clocks instead of 1 for the read or write, IIRC) if your pointer & 0x40 was non-zero, and you had to be careful if you didn't want to affect the next word in memory, but it would work.

NIkita Pestrov - 2012-08-03 21:31:58

Fri, 03 Aug 2012 21:31:58 GMT

Here is the russian version of the Theory part)
http://habrahabr.ru/post/149012/

Nikita Pestrov - 2012-08-03 17:36:09

Fri, 03 Aug 2012 17:36:09 GMT

Thank you for a great article, Mike!

Richard Stacpoole - 2012-07-30 02:47:15

Mon, 30 Jul 2012 02:47:15 GMT

I was also thinking of the work done to make 32 bit clean code.
Not using any bits above the 48bits the hardware can read will help with this. I just hope that tricks like this don't lead to other problems in the future.
Thanks for the replies.

Daniel Eggert - 2012-07-29 10:52:54

Sun, 29 Jul 2012 10:52:54 GMT

It's worth noting that this optimisation is not really about saving memory. Yes, a tagged pointer NSNumber will use less memory than a "real" object, but the huge performance benefit comes from not having to allocate and deallocate objects.

Creating a new object is very, very expensive as compared to creating a local variable.

int a = 42;
int b = 128;
int c = a + b;

is literally "for free" compared to

id d = [[NSObject alloc] init];

Allocation has to call malloc, which has to thread safe, may go off and mess with the virtual memory system etc. Then the object has to be initialised etc. There's a lot going on there that you don't see. Creating a tagged pointer for an NSNumber is orders of magnitude faster because it doesn't have to do any of that.

mikeash - 2012-07-27 19:07:03

Fri, 27 Jul 2012 19:07:03 GMT

Chris L: Fortunately, there's no possibility for such trouble here. Since the creation of tagged pointers is limited to Apple frameworks, they are free to change the implementation at will to suit any new architecture changes that occur, without breaking any third-party code.

bbum - 2012-07-27 15:52:22

Fri, 27 Jul 2012 15:52:22 GMT

It is only dangerous if you break the API contract. In particular, direct access to the "isa" of an object was deprecated with the modern runtime. Since all of the other runtime functions (and NSObject API) are aware of tagged pointers, a tagged pointer behaves just like any other object when viewed through the public API.

Chris L - 2012-07-27 15:14:00

Fri, 27 Jul 2012 15:14:00 GMT

It reminds me of when a lot of Mac software had to be rewritten to be "32-bit clean".

mikeash - 2012-07-27 15:03:52

Fri, 27 Jul 2012 15:03:52 GMT

Richard Stacpoole: What exactly is dangerous about it? It's tricky, but if you do it correctly, it works fine.

Nicolas Bouilleaud - 2012-07-27 14:27:25

Fri, 27 Jul 2012 14:27:25 GMT

I made a few experiments with Tagged Pointers a while ago on Lion.

http://github.com/n-b/TaggedPointersTests

One interesting finding is that although Apple did the "safe" thing with NSNumbers representing doubles, they went with all the trouble for NSDate : NSDate objects are conceptually equivalent to an NSTimeInterval (a double). If the double value "fits" in the 7 first bytes, the NSDate is actually a tagged pointer.

Richard Stacpoole - 2012-07-27 14:16:10

Fri, 27 Jul 2012 14:16:10 GMT

Isn't even Apple using this just asking for trouble? I appreciate code performance improvements as much as the next person but do we really need to play such dangerous games?