Edit: this link posted by another commenter gives a nice overview of the tradeoffs between the methods and it has very nice graphs to boot https://spin.atomicobject.com/2014/09/03/visualizing-garbage...
That is, with ARC, the more garbage you generate, the more work will be spent on the GC vs normal program flow. In contrast, with tracing/copying, you can generate as much garbage as you want, without affecting GC time; but, the more memory you actually use, the more time you will spend in GC.
A is for Automatic, as in the compiler adds the calls needed to manage the reference counting.
If the language and compiler can guarantee a reference is strictly contained within a thread, it doesn't have to be atomic. Usually that is not the case, so atomic operations are used.
- your application is using close to 100% available RAM
- you don't care about the impact of all those extra writes clogging up CPU caches and bouncing cache lines back and forth across internal buses
- you can't afford to pay for a small amount of extra RAM
In that case reference counting sounds ideal. Good luck!
If you're on the server then just buy more RAM and use a GC, I agree.
But if you're making consumer software then buying more RAM isn't an option. Additionally, RAM costs battery life even when it isn't in use.
- ARC (upper case): Automatic Reference Counting (in Swift/ObjC)
- Arc (title case): Atomic reference counting (in Rust)
I assume OP intended the former.
Choosing to use automatic reference counting in a language is a design choice, with positives and negatives. Atomic reference counting is an implementation detail, a strict necessity whenever you can't be sure an object will only be referenced by one thread (in essence, non-atomic reference counting is just an optimization).
What do you mean by 'usage'? References don't change when reading or writing the data being reference counted, they change when being passed to a function or returned from one. In C++ it's rare that you would even use reference counting, since that essentially means you don't know the lifetime of your value. Most variables are going to be on the stack and the vast majority of dynamic allocation is going to be referenced from a single scope at one time.
The reality is that it takes gross incompetence to have a speed impact from reference counting.
> In C++ it's rare that you would even use reference counting, since that essentially means you don't know the lifetime of your value
Sure, because it is a manual memory managed language with RC being an escape hatch only. But there are plenty of problems/programs where you simply can’t know the lifetime of your objects, e.g. Chrome uses a proper GC for C++ as well.
I don't know what you mean by escape hatch, but it generally just isn't necessary and memory is managed automatically by scope. The bigger point here is that it just isn't a significant part of execution time.
But there are plenty of problems/programs where you simply can’t know the lifetime of your objects
Like what? I can only think of one, which is passing memory allocated in one thread to another thread.
Chrome uses a proper GC for C++ as well
This is an anecdote, it doesn't prove or disprove anything in the bigger picture.
That’s just an implementation detail. The point is that the object’s lifetime is only known at runtime and will be reclaimed when a counter reaches zero, this is reference counting. Whether you have to manually inc/dec that counter, or the language does it for you through some abstraction is besides the point, it is automatic memory management either way, as it.. manages memory automatically.
> Like what? I can only think of one, which is passing memory allocated in one thread to another thread
Any programming language, both parsing into an AST, AST manipulations, interpretation (and that is a very wide category, not only for things you would think of as proper languages). But even some games may want to use GC for some in-game objects, as the lifetime of those is fundamentally dependent on user action.
Would the litany of managed languages and their widespread usage be less anecdotal?
both parsing into an AST, AST manipulations, interpretation even some games may want to use GC for some in-game objects, as the lifetime of those is fundamentally dependent on user action
Here you are conflating the lifetime of resources inside the various scopes of a program with dynamic resources in a game. These are not the same thing. Language level reference counting will not save you or help you to know when to unload a level or a texture. Just because there is control over resources doesn't mean reference counting. Likewise even in something like java you need to set links to heap allocated objects to null so that they can be garbage collected. The language doesn't magically know when you need to unload a level.
> only necessary when giving memory allocated in one thread to another thread
RC count can be larger than one even when only a single thread using it. But I’m not familiar with this usage and it is not really RC for memory management anymore, more like a lock-less data structure.
I wasn’t talking about texture/level loading/unloading because it is more complex, but things like using scripting languages for part of the game logic.
I think you're just repeating yourself, but I'm not sure what question you're answering.
RC count can be larger than one even when only a single thread using it. But I’m not familiar with this usage and it is not really RC for memory management anymore, more like a lock-less data structure.
I don't understand what you are saying here.
things like using scripting languages for part of the game logic.
Scripting languages are slow for a lot of reasons, like pointer chasing and excessive memory allocations. Reference counting is a very small piece of that puzzle.
I don't think anyone is debating that.
not suitable for lock-free algorithms and may overflow the stack.
This you will have to explain. I see people make vague assertions like this but I never see a good explanation.
You can do that in multiple ways.
First you can use the extra bits of a pointer for a counter to fit it all into 64 bits.
Second, you can use a 128 bit compare and swap which has been supported by CPUs for about 20 years now.
Third, you can not use pointers and use indices of whatever bit resolution you want, using the extra bits for a counter.
Finally, how does a garbage collector change this ?
If make a long list using shared_ptr will overflow the stack when the head destructor executes.
If we set aside for a second the insanity in making a linked list where every pointer destruction calls the next pointer in the list's destructor, how is this unique to a shared_ptr ?
Stack overflow is not unique to a shared_ptr, but GC pointers don't have this problem
No one should ever have this problem. It is a ridiculous way to make a linked list in the first place.
You told me something was impossible to do without garbage collection and I explained three different ways that I've already done it, then you just keep trying to talk about something that was never up for discussion in the first place. You hallucinated shared_ptr into the conversation from nowhere.
Without talking about smart pointers, what am I missing from the list above? Why do some lock free algorithms need garbage collection?
Why don't you answer my questions above? They confront the ABA problem directly since I explained three ways to keep counts paired with pointers or indices. What can't be done without a garbage collector? Why do you keep giving vague recommendations to read about general topics? Give me a specific deeply technical answer if you can.
When you want to allocate an index you check the current index and version, and replace it with the index points to if the version is the same. Freeing is the reverse since you have an index to give the list.
These indices are used to coordinate to a second array where you can store whatever data you want.
Here are some other techniques.
https://people.csail.mit.edu/shanir/publications/Lock_Free.p... https://www.boost.org/doc/libs/1_55_0/boost/lockfree/stack.h... https://lumian2015.github.io/lockFreeProgramming/lock-free-s...
Still, I'm not sure what garbage collection changes about these techniques. Lock free lists have been studied for a long time, they have nothing to do with memory allocation.
Described algorithms ignore the ABA problem.
I literally wrote a method for doing that, an index with a version that can be checked to make sure nothing changed.
Also if you're going to say that heavily tested implementations ignore the ABA problem you need to explain why you think that or why you think they won't work and again, why garbage collection changes anything.
stores pointers on 48 bits which is not enough on new architectures.
48 bits is the size of the memory controller on modern CPUs and exceeding that would need over 281 terabytes of memory.
Again, the original question is what lock free algorithm can be done with garbage collection that can't be done without it?
New processors use 56 bits of virtual address. It doesn't matter if you have that much memory, because addresses are virtual. Also, newer versions of Android do not allow the use of unused address bits.
This is again, your assertion, it isn't evidence or an explanation of any kind, you just keep saying the same thing. The link you have is people discussing a bunch of surrounding issues.
Fundamentally, allocation of arbitrary memory just doesn't have to be ingrained in the lock free data structure. As soon as you can deal with 64 bits at a time, you can store pointers. There are lock free heap allocators and lock free block allocators that can be combined with whatever you are using to deal lock free with integers/pointers.
Freeing memory is going to be a matter of ownership. If you pop a pointer, that thread should own it. Not only that, but a pointer combined with a reference count can always be used if necessary and again, 128 bit compare and swap has been around for 20 years.
I didn't see what you're talking about in the 15 year old message board discussion and I think if there was something specific and clear you would have copied and pasted it.
I also think that if you had any understanding of what you're saying, you would have given an explanation yourself.
So go ahead and actually put something here that you can back up. It is a common scenario where someone has no real evidence to link something adjacent and then tell someone to 'go find it in this link'.
int lfstack_pop(_Atomic lfstack_t \*lfstack)
{
lfstack_t next;
lfstack_t orig = atomic_load(lfstack);
do
{
if (orig.head == NULL) // undefined behavior !!!
{
return -1;
}
next.head = orig.head->next;
} while (!atomic_compare_exchange_weak(lfstack,&orig,next));
free(orig.head);
return 0;
}
Can you focus and nail down one claim with specifics before moving on to something else?
I've already done all the things you claim are impossible. That's how I know what you're saying is nonsense. Avoiding a double free on a pointer can always be done with atomic reference counting so that only one thread claims ownership. That's the whole story. You haven't given a shred of evidence to explain what garbage collection enables something that was previously impossible.
It is obvious that if you had something you could say that directly applies to what you claimed before (some algorithms can't be done without garbage collection), that you would have already said it a long time ago.
How would you implement a graph that requires heap allocation for each node and supports adding/removing nodes and links with purely scope-based memory management (no shared_ptr or equivalent, no tracing GC), while still reclaiming memory as soon as possible (so no arena-based solutions)?
There are also single-threaded concurrent scenarios where object ownership can be ambiguous, but those are similar to the multi-threaded scenarios you discuss.
What’s manual rc like?
E.g., the Arc type in Rust. Rust, for example, has a separate Rc type. Rc should outperform Arc, but cannot be shared across threads.