Talk:Load-Link/Store-Conditional

From Wikipedia, the free encyclopedia

Citation for CAS-based lock-free reference counting in the face of a changing object-graph, please? --Chris Purcell 11:55, 19 June 2006 (UTC)

I was just about to post on the talk page asking about this very point, and another one, but your edit got through before mine. Here it is:

Hasn't it been proven that DCAS can be implemented on top of CAS (in constant time and linear-in-threads space)? If so, then the fact that lock-free reference counting in the face of a changing object graph can be implemented in DCAS (as the previous version said) means it can be implemeneted in CAS, does it not?

On another issue, the previous version of the page had this sentence:

• Some CPU assumes the address being accessed exclusively be configured write-through mode.

I didn't know what this meant. I rewrote it as this:

• Some CPUs require the address being accessed exclusively to be configured in write-through mode.

However, because I couldn't figure out the original sentence, I may have misrepresented something.Falcotron 12:07, 19 June 2006 (UTC)

I don't understand the original sentence either, so without a citation it's probably best to remove it in case it's inaccurate. (Your rewriting appears to conserve truth!)

DCAS can be implemented on top of CAS, but only with out-of-line memory management, which means it can't be used to implement reference counting! --Chris Purcell 12:11, 19 June 2006 (UTC)

I thought I recently read a paper showing how DCAS-on-top-of-CAS could be used for refcounting as long as it's intrusive in the objects or the allocator. I may well be misremembering. I'll have to think it through or find the reference. Falcotron 12:36, 19 June 2006 (UTC)

[edit] Weak LL/SC vs. CAS

It's my understanding that most of the research on lock-free algorithms with LL/SC is not applicable to (most) weak implementations. And the phrase "... as it breaks many theoretical LL/SC algorithms..." sounds like it backs me up here.

True. However, the research is also not applicable to CAS.

Yes, but there's separate research on CAS, which is applicable to all real-world CAS implementations.

And all CAS ones :)

Further, even algorithms that are not broken are often affected, in that spuriously severed links mean spuriously repeated update attempts. (Whether this has a practical impact on performance, I don't know.) By contrast, the spuriously preserved links of CAS either break an algorithm, or have no effect whatsoever.

I'm afraid I have no idea what you mean here. What are "spuriously preserved links of CAS"?

Sorry; I was badly stretching a metaphor that I hadn't even made explicit. If a value is changed and restored between the test read and the CAS, it looks like the load and store are "linked," but they're not. Is that clearer?

Anyway, unless there has been recent research on using LL/SC on real-world CPUs that I'm not aware of (which is definitely possible), this is a serious practical restriction to implementing lock-free algorithms with weak LL/SC. This was what I was intending to say (although I apparently didn't say it very well). Falcotron 12:28, 19 June 2006 (UTC)

Weak LL/SC on real-world CPUs gives a very effective lock-free implementation of CAS. In fact, they will typically be fair, as well as very unlikely to fail spuriously, since they are implemented with a simple cacheline lock; the only thing likely to cause spurious failure, apart from attempting to nest another LL, is pre-emption. Indeed, modern Intel CPUs actually break CAS down into a microcode LL/SC.

If any load from a different address will break a link, isn't an SC more likely to fail spuriously than a CAS? Doesn't this make it harder to predict/guarantee the efficiency of LL/SC algorithms?

A weak LL/SC pair implementing a CAS is essentially identical to a CAS on modern hardware, and you can make lock-free progress guarantees under only very minor assumptions about the preemptive nastiness of the OS.

Either way, this comment is more applicable to my previous point than to this one: much LL/SC research cannot be applied to most LL/SC-capable CPUs, but all CAS research can be applied to all CAS-capable CPUs. If you're saying that in practice you really can use weak LL/SC for most important algorithms, I'll buy that. Or if I'm just out of date on the LL/SC research, I'll definitely buy that.

Yes, in practice you really can use weak LL/SC wherever you can use CAS.

So, in conclusion, there is no problem implementing lock-free algorithms with weak LL/SC that's not also a problem for CAS. --Chris Purcell 12:54, 19 June 2006 (UTC)

Based on what you're saying, it sounds like it might be worth changing the end of my "Weakness is relative" sentence to say that "most real-world implementations can be used for [many|most] algorithms."

If you want to.

Anyway, thanks for your patience. Falcotron 14:00, 19 June 2006 (UTC)

No problem! Peer review is fun ;) --Chris Purcell 16:43, 19 June 2006 (UTC)