Yes, I may have been wrong on that part. Or it was planned but not started yet. Or Chris Lattner read that post and thought "we've gotta get on that". Or whatever.
Regardless of that, a lot of details match (opt into it, side-by-side with C and Objective-C, compiler based on LLVM, not based on C, modern language, specifically made to match the frameworks).
The timing's interesting on this one. The blog post is from 19th June 2010; Chris Lattner says he started working on Swift in July 2010, "with only a few people knowing of its existence", but presumably with some approval from higher-ups.
I love Siracusa, but what he's been saying is "well, they're gonna need something or they'll fall behind". Which is a fine bet and was a prescient analysis even in the rounds before. Copland 2010 was his idea in 2005 that they'd essentially have something new and modern by 2010, which they didn't, but they had started evolving Objective-C again and added GC, so they hadn't been completely standing around.
I made a separate bet, saying that "they're working on a new language with these characteristics". For four years, this was an insane idea, they're not going to go all that trouble just to chuck Objective-C, I was mad and should be ignored. This week, that line of dismissal argument changed into "in hindsight, he was only stating the painfully obvious and anyone could have done that", which is nice and weird and a reversal fit for Steve Jobs.
That said, both Siracusa and I completely missed ARC, which is basically probably what made Swift worthwhile.
Speculation on a new language from Apple has been going on for ages. Lots of people have discussed the possibility for years. There are no details in this prediction beyond "a new language", some obvious stuff like "it'll be modern", and some wrong stuff like the implication that it will use garbage collection. This is not a very interesting prediction. Just coincidental, and not particularly so.
Moreover, the specific predictions turned out to be wrong: Swift has no garbage collection (ARC is not GC), and is not a completely clean slate but is using the ObjC runtime.
No points for "based on LLVM" and "opt-in as you please side by side with Objective-C"? (Side by side with Objective-C probably does not require the Obj-C runtime, but it's hard to see how it wouldn't want to use it.)
I did not predict ARC. I'm not a genius, oracle, memory management expert or compiler writer.
Given the sheer quantity of people who post their thoughts about Apple, you can probably find one or two who made an accurate prediction about any product release.
"The relevance of the theorem is questionable—the probability of a universe full of monkeys typing a complete work such as Shakespeare's Hamlet is so tiny that the chance of it occurring during a period of time hundreds of thousands of orders of magnitude longer than the age of the universe is extremely low (but technically not zero)."
Actually it's about a single monkey typing for an infinite amount of time. Which is the best thing you can hope for, since you can't really get an infinite amount of monkeys.
So the thesis is the only reason they would switch to LLVM is if they wanted to abstract away from Objective-C?
I'm no compiler expert but I do know Apple rolled out Automatic Reference Counting in 2011 (one year after this post), a pretty f'ing massive compiler-based feature. That was probably the biggest leap forward in Objective-C in a decade. For those not familiar, that's the thing that automates memory management but without the runtime overhead of garbage collection, instead using static code analysis to figure out where to compile in the commands to release memory. So I'm guessing LLVM had something to do with that.
And it's nothing particularly special. Automatic reference counting has been going on since the 1950s. There's even an AI Koan about it. It's a nice addition to Objective-C but it's nothing new.
ARC is a reasonably straightforward feature that can largely be thought of as a syntactic pre-pass. Figure out which fields on objects need to have refcount instrumentation, insert the appropriate incref and decref before and after the write, respectively.
That said, the runtime overhead of reference counting is significant and works against the cache architecture of modern CPUs. In a refcounted system, a simple field update Update(obj, offset, target) becomes the following:
In assembly, in the best case, this roughly translates to:
1. Memory load (to get obj[offset])
2. Memory load (toget obj[offset]->refcount)
3. Decrement (refcount of old value)
4. Memory store (to update obj[offset]->refcount)
5. Test (to see if old value is now dead)
6. Memory increment (to update target->refCount - 1 instruction on x86/x64, 3 on ARM)
7. Store
Let's assume the best case: the old object being dereferenced does not become dead, and the branch predictor is good with the Test, so (5) is the cost of an ALU instruction and no misprediction penalty.
However, memory accesses at (2) and (4) are at arbitrary locations on the heap. The old value in the field points to an object anywhere on the heap, and the new value being stored points to an object anywhere on the heap. Neither of these memory locations are as likely to be as relevant to the current working set as the memory of the object being written to. After (2) and (4), you've gone through a bit of cache churn.
Now, this is happening on every single write. It's a HUGE overhead. Secondly, because refcounting doesn't really have an understanding of the object heap as a whole, it's generally impossible to do moving memory management for these languages. This means one of two things: either an expensive |malloc| for all allocations, or if you're using pool-based allocation - fragmentation of memory.
A modern GC reduces this overhead quite a bit. The state-of-the-art currently in reducing the overhead here is the combination of generational GC with card-marking for the older generations. Memory allocation cost is literally 3-4 instructions, and there's no fragmentation. Most object writes are cheap, since most activity happens in the nursery where write barriers don't need to be updated. The average write overhead for pointer-writes into the nursery is an extra load and a bit-test, but this extra load is from the same memory space that the field-write will be writing to, so either it's already in cache or going to be pulled in soon. Pointer writes to non-nursery objects have a larger overhead, but this is still smaller than doing the corresponding refcount checks.
The big advantage of refcounting is how this overhead is split up across program runtime. Proper GC has the issue of pause times due to garbage collection. Modern designs have basically eliminated pause times as it relates to general computing, but it can still be an issue in games etc. where a GC in the middle of frame, even a few ms long, can cause a frame skip.
Refcounting has its uses and its advantages, but it's dangerous to think of it as having no runtime overhead. It has a HEAVY cost on performance and it thrashes memory and it works against CPU cache architectures.
I don't get how your code works. Why do you decrement first, then increment?
Regardless, your explanation is mostly correct. There will be an incref/decref pair for most accesses. However, LLVM (and Apple's refcount implementation) does 2 very important optimizations:
- LLVM can recognize (via static code analysis) redundant incref/decref pairs and take them out.
- I can't find the link for it right now, but Objective-C usually stores refcount inside the pointer (in other words, the memory address) itself. So as long as your refcount is small enough (which it will be 99% of the time), incref and decrefs don't thrash caches but work on the value already in register.
My code doesn't work under race conditions. You're right the increment should be done before and the decrement after to avoid races. I just banged out the logic without giving it too much thought.
On removing redundant incref/decref pairs - this is nice, but it seems mostly a benefit because of the "automatic" part, not the refcounting part. Developers dealing with manual refcounting would probably recognize places where refcount manipulation is redundant and just elide them. A naive automation ends up inserting them everywhere, and this helps bring that back to what a "smart developer" would have written anyway.
On your second point, I've heard about this trick - in particular in smalltalk implementations. It's something I haven't fully looked into. It seems like the in-pointer refcount would only be valid if the pointer never escaped the function frame. More generally, you'd have to be able to guarantee that a particular pointer is the only reference to an object before the refcount could be stored in the pointer bits itself.
If you have more insight into the implementation of this, I'd be interested in hearing it. This "small refcount pointer tagging" thing is something I've been meaning to understand better but haven't gotten around to.
They store it in isa field. Still, as long as you also call any virtual method of the object (or due to cache lines, use any field), it will still be pretty fast.
If you look down into the comments (on the original post), he says "My guess for what xlang would actually look like is rather close to Objective-C without the C." Pretty good prediction considering they used almost the same phrase in the announcement.
33 comments
[ 5.1 ms ] story [ 87.4 ms ] threadRegardless of that, a lot of details match (opt into it, side-by-side with C and Objective-C, compiler based on LLVM, not based on C, modern language, specifically made to match the frameworks).
I made a separate bet, saying that "they're working on a new language with these characteristics". For four years, this was an insane idea, they're not going to go all that trouble just to chuck Objective-C, I was mad and should be ignored. This week, that line of dismissal argument changed into "in hindsight, he was only stating the painfully obvious and anyone could have done that", which is nice and weird and a reversal fit for Steve Jobs.
That said, both Siracusa and I completely missed ARC, which is basically probably what made Swift worthwhile.
I did not predict ARC. I'm not a genius, oracle, memory management expert or compiler writer.
http://en.wikipedia.org/wiki/Infinite_monkey_theorem
And even if somehow you did, that single monkey won't do as they have trouble focusing on a task and tend to die after non-infinite time periods.
So unless we can bridge the "infinite monkey problem" and the concomitant "infinite monkey poop problem", I'm afraid monkey Hamlet shall stay unwrit.
I'm no compiler expert but I do know Apple rolled out Automatic Reference Counting in 2011 (one year after this post), a pretty f'ing massive compiler-based feature. That was probably the biggest leap forward in Objective-C in a decade. For those not familiar, that's the thing that automates memory management but without the runtime overhead of garbage collection, instead using static code analysis to figure out where to compile in the commands to release memory. So I'm guessing LLVM had something to do with that.
There was even a WWDC session about it when ARC was made available.
cekvenich.vic (at) gmail.com
That said, the runtime overhead of reference counting is significant and works against the cache architecture of modern CPUs. In a refcounted system, a simple field update Update(obj, offset, target) becomes the following:
In assembly, in the best case, this roughly translates to: Let's assume the best case: the old object being dereferenced does not become dead, and the branch predictor is good with the Test, so (5) is the cost of an ALU instruction and no misprediction penalty.However, memory accesses at (2) and (4) are at arbitrary locations on the heap. The old value in the field points to an object anywhere on the heap, and the new value being stored points to an object anywhere on the heap. Neither of these memory locations are as likely to be as relevant to the current working set as the memory of the object being written to. After (2) and (4), you've gone through a bit of cache churn.
Now, this is happening on every single write. It's a HUGE overhead. Secondly, because refcounting doesn't really have an understanding of the object heap as a whole, it's generally impossible to do moving memory management for these languages. This means one of two things: either an expensive |malloc| for all allocations, or if you're using pool-based allocation - fragmentation of memory.
A modern GC reduces this overhead quite a bit. The state-of-the-art currently in reducing the overhead here is the combination of generational GC with card-marking for the older generations. Memory allocation cost is literally 3-4 instructions, and there's no fragmentation. Most object writes are cheap, since most activity happens in the nursery where write barriers don't need to be updated. The average write overhead for pointer-writes into the nursery is an extra load and a bit-test, but this extra load is from the same memory space that the field-write will be writing to, so either it's already in cache or going to be pulled in soon. Pointer writes to non-nursery objects have a larger overhead, but this is still smaller than doing the corresponding refcount checks.
The big advantage of refcounting is how this overhead is split up across program runtime. Proper GC has the issue of pause times due to garbage collection. Modern designs have basically eliminated pause times as it relates to general computing, but it can still be an issue in games etc. where a GC in the middle of frame, even a few ms long, can cause a frame skip.
Refcounting has its uses and its advantages, but it's dangerous to think of it as having no runtime overhead. It has a HEAVY cost on performance and it thrashes memory and it works against CPU cache architectures.
Regardless, your explanation is mostly correct. There will be an incref/decref pair for most accesses. However, LLVM (and Apple's refcount implementation) does 2 very important optimizations:
- LLVM can recognize (via static code analysis) redundant incref/decref pairs and take them out.
- I can't find the link for it right now, but Objective-C usually stores refcount inside the pointer (in other words, the memory address) itself. So as long as your refcount is small enough (which it will be 99% of the time), incref and decrefs don't thrash caches but work on the value already in register.
On removing redundant incref/decref pairs - this is nice, but it seems mostly a benefit because of the "automatic" part, not the refcounting part. Developers dealing with manual refcounting would probably recognize places where refcount manipulation is redundant and just elide them. A naive automation ends up inserting them everywhere, and this helps bring that back to what a "smart developer" would have written anyway.
On your second point, I've heard about this trick - in particular in smalltalk implementations. It's something I haven't fully looked into. It seems like the in-pointer refcount would only be valid if the pointer never escaped the function frame. More generally, you'd have to be able to guarantee that a particular pointer is the only reference to an object before the refcount could be stored in the pointer bits itself.
If you have more insight into the implementation of this, I'd be interested in hearing it. This "small refcount pointer tagging" thing is something I've been meaning to understand better but haven't gotten around to.
https://www.mikeash.com/pyblog/friday-qa-2013-09-27-arm64-an...
They store it in isa field. Still, as long as you also call any virtual method of the object (or due to cache lines, use any field), it will still be pretty fast.