4 ms·
You don't necessarily need memory barriers (implementation detail). All you need is an atomic fetch-and-add (like x86 XADD opcode). Many architectures provide
by vardump 10y ago
You don't necessarily need memory barriers (implementation detail).
All you need is an atomic fetch-and-add (like x86 XADD opcode). Many architectures provide that as a primitive. On those that don't, you have to compose it out of other atomic primitives.
- xxs 10y agoAtomic part has to notify the rest of caches to invalidate the cache line. Local latency in the best case.
- gpderetta 10y agoFYI, any store has to invalidate remote cachelines, that's taken care by the coherence protocol even before the store is actually performed. Memory barrier (and atomic operations) don't have anything to do with it.
- JoachimSchipper 10y agoWhether stores invalidate remote cachelines depends entirely on the architecture. But yes, Intel has fairly strong coherency.
- gpderetta 10y agoIt seems to me that any cache coherent system needs to do that. If multiple writers can be updating a cacheline a the same time [1] you can't talk of coherency at all. Intel is stronger as it guarantees a total ordering of modifications across all cachelines, but any coherent system will guarantee the ordering of modification of a single cacheline. [1] visibly at least. HTM complicates things a bit of course.
- imtringued 10y agoSo false sharing is the problem?
- gpderetta 10y agoIf the refcount is allocated in the same cacheline with the rest of the object, then false sharing is also a problem. But the violation of the single writer principle when updating refcounts is actually a form of true sharing.
- deleted 10y ago[deleted]
- gpderetta 10y agoif you have destructors or finalizers you do need memory barriers to make sure that any previous modification of the object happens-before the destructor is run. Also many architectures with builtin fetch-and-add bundle it with an implicit memory barrier (that includes x86).
- vardump 10y agoBut then those barriers are not for the refcount itself, but for the data the object contains. Different things. On x86, stores are always ordered anyways, so fetch-and-add doesn't need to do any implicit memory barrier.
- gpderetta 10y agoBarriers are never needed for accesses to a single location as all practical systems guarantee total ordering, that a given. But on a refcounted system the only place to put the barrier for correct visibility, it is together with the refcount update. It is true that on x86 all stores and loads have the correct implicit barriers, but you still get a store-load (including its cycle cost) with lock xadd whether you want it or not.
- barrkel 10y agoI think you need more than just fetch-and-add. Think about this: assign(value) { root.ref = value; } needs to be expanded out into: assign(value) { if (value) inc_ref(value) tmp = value atomic_swap(&root.ref, &tmp) if (tmp && dec_ref(tmp) == 0) free(tmp) } If you don't use an atomic swap, you race with other threads trying to assign to the same location. You can't decrement the destination before incrementing the source because they could be equal. You can't make the logic conditional on equality because it races. You have a harder time with this: a.b.c = value You need to inc-ref each step in the chain, keeping them in temporaries, to ensure they don't get dec-refed out from underneath you on another thread.
- vardump 10y agoBut if you have both atomic primitives available, why would you ever do that? Keyword is atomic. Fetch-and-add returns you the previous value atomically. ------- Edit: This (below) is obviously a buggy reference counting algorithm. ------- In freeing (decrementing reference count) thread A, if it was 1 before (returned value) and A added -1, the object can be freed. Because the operation is atomic, only one of two things can happen: 1) Another reference adding thread B increments it before A decreases it. So A doesn't see 1, thus won't free the object. 2) B increments it after A decremented it. So B gets zero and knows the object is invalid. (Edit: Oops, a bug: after B increments refcount, when thread C tries to do same, it would get 1 and conclude the object is valid!) If B is allowed to allocate the object again (invalid state, refcount == 0), careful synchronization needs to be done remove any races with A's deallocation.
- barrkel 10y agoI think you're hung up on multiple threads reference-counting a single instance. That's not where reference counting as a GC approach gets difficult. It's when you're updating references to values.