In order to know whether an arena is empty, you need to have walked, at a minimum, each object that was in the arena. That applies for copying collections too as during the copy phase you've walked and inspected each object that might be copied into the arena at least once. Arenas do not reduce the cost of garbage collection to O(1). And in any event arenas are not solely the preserve of sweeping or sweeping+copying collectors.
A reference counting collector that _cannot_ break cycles (like in Swift) might have lower algorithmic complexity. I'm not sure.
The biggest bone of contention with reference counting is the constant adjustment of the reference count of objects on the stack. OTOH, the bone of contention with sweeping collectors is constantly walking all extant objects, including ones not directly on the stack.
There are various optimizations you can make to one or the other or both; many arguments about how real-world scenarios tax one or the other model; and many arguments about which is easier to optimize. But at the end of the day reference counting is no worse in terms of algorithmic complexity than sweeping. What matters most will be the quality of implementation. Is the compiler smart enough to know that an object passed 3 routines deep doesn't really escape the stack scope? If it can do that, it can elide all the cost of either approach.
Thanks for the paper touching on reference counting work queues, I hadn't paid much attention to that approach since proponents tend to focus on instantly reclaiming each dead object. I still find semi-space copying (move O(live) objects and ignore O(dead) objects where dead >> live) to be not just one alternative but an enormous win I'd almost never forego, since buying more memory is so much easier than buying more CPU and bus throughput and has been for years.
I have trouble believing that behind-the-scenes escape analysis is very effective on real-world code. Look at how much painfully explicit source annotation Rust found they needed.
What matters most will be the quality of implementation. Is the compiler smart enough to know that an object passed 3 routines deep doesn't really escape the stack scope? If it can do that, it can elide all the cost of either approach.
This is the plan with Swift and what makes it zippy.
bone of contention with sweeping collectors is constantly walking
The real problem is that you cannot determine when the program will pause. It makes interactive and soft realtime impossible with gc. (Hard realtime should not run a generic allocator at all.) You can't write anything but servers and unpleasantly unresponsive apps.
Android developers have to carefully jump through hoops to avoid allocating any RAM at all if they don't want to bug their users. For years when the chips were slow, ref counting was a major competitive advantage for iPhone. A hundred-billion dollar win.
And then there's system software. You can't afford a live, unpredictable runtime messing with you in systems code so anything that touches low level code can't use gc. There's a disincentive to really invest in a language that simply can't ever do a full stack, even if you're unlikely to need to write a device driver anytime soon. That's why no major browsers, performant ACID databases, or fast app servers depend on RAM gc.
The algorithmic complexity of a sweeping collector is identical to that of a reference counting collector that can also break cycles. See A Unified Theory of Garbage Collection at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.146....
A reference counting collector that _cannot_ break cycles (like in Swift) might have lower algorithmic complexity. I'm not sure.
The biggest bone of contention with reference counting is the constant adjustment of the reference count of objects on the stack. OTOH, the bone of contention with sweeping collectors is constantly walking all extant objects, including ones not directly on the stack.
There are various optimizations you can make to one or the other or both; many arguments about how real-world scenarios tax one or the other model; and many arguments about which is easier to optimize. But at the end of the day reference counting is no worse in terms of algorithmic complexity than sweeping. What matters most will be the quality of implementation. Is the compiler smart enough to know that an object passed 3 routines deep doesn't really escape the stack scope? If it can do that, it can elide all the cost of either approach.