By: rwessel (rwessel.delete@this.yahoo.com), August 26, 2022 6:08 pm
Room: Moderated Discussions
Linus Torvalds (torvalds.delete@this.linux-foundation.org) on August 26, 2022 11:01 am wrote:
> Michael S (already5chosen.delete@this.yahoo.com) on August 26, 2022 3:46 am wrote:
> >
> > I would guess that if we enumerate cases that are
> > A. Useful in parctice
> > B. Can not be done with 1 cache line
> > C. Can be done with unlimited number of distinct lines
> > then about half of them can be done with 2 distinct lines.
>
> No, I really do think that 3 distinct lines are pretty much required - since
> the most obvious case I can think of (doubly linked list) needs it.
>
> And yes, yes, if you look up DCAS and doubly linked lists, you'll find that people
> talk about just two lines for that operation - but that's not for a doubly linked list
> that is coherent with a lock, that's for a purely unlocked doubly linked list.
>
> In fact, I suspect that you actually really want four lines, because while three should be sufficient
> for a doubly linked list (modifying the two entries on both sides, and checking the lock), you probably
> do want to also hold/modify the cacheline of the entry itself that you are adding or removing.
>
> Yes, you can probably make do without that fourth entry - When adding an entry to the linked
> list you can pre-fill the prev/next pointers of the new entry before actually doing the operation
> - and that's the kinds of tricks that you have to do when you only have one entry and you
> are using 'cmpxchg' or 'll/sc' to do simpler lock-free singly-linked lists.
>
> But I do suspect that four cachelines is noticeably better than three,
> and two is just simply not sufficient for a lot of simple things.
>
> That said, even just two is probably usable for some things. People who implement locking
> would use it internally, I bet, and it might be sufficient for a number of "test condition
> consistent with a lock" situations. I just think that "doubly linked list handling co-existing
> with a lock" is probably worth considering as a minimally useful thing.
>
> I dunno.
>
> I suspect in the end it's one of those things where it's just not
> useful enough: locking works, and usually works well enough.
FWIW, Z Perform Locked Operation supports up to compare-and-swap-and-triple-store, but keeps the lock itself separately. So roughly four the way you're counting.
> Michael S (already5chosen.delete@this.yahoo.com) on August 26, 2022 3:46 am wrote:
> >
> > I would guess that if we enumerate cases that are
> > A. Useful in parctice
> > B. Can not be done with 1 cache line
> > C. Can be done with unlimited number of distinct lines
> > then about half of them can be done with 2 distinct lines.
>
> No, I really do think that 3 distinct lines are pretty much required - since
> the most obvious case I can think of (doubly linked list) needs it.
>
> And yes, yes, if you look up DCAS and doubly linked lists, you'll find that people
> talk about just two lines for that operation - but that's not for a doubly linked list
> that is coherent with a lock, that's for a purely unlocked doubly linked list.
>
> In fact, I suspect that you actually really want four lines, because while three should be sufficient
> for a doubly linked list (modifying the two entries on both sides, and checking the lock), you probably
> do want to also hold/modify the cacheline of the entry itself that you are adding or removing.
>
> Yes, you can probably make do without that fourth entry - When adding an entry to the linked
> list you can pre-fill the prev/next pointers of the new entry before actually doing the operation
> - and that's the kinds of tricks that you have to do when you only have one entry and you
> are using 'cmpxchg' or 'll/sc' to do simpler lock-free singly-linked lists.
>
> But I do suspect that four cachelines is noticeably better than three,
> and two is just simply not sufficient for a lot of simple things.
>
> That said, even just two is probably usable for some things. People who implement locking
> would use it internally, I bet, and it might be sufficient for a number of "test condition
> consistent with a lock" situations. I just think that "doubly linked list handling co-existing
> with a lock" is probably worth considering as a minimally useful thing.
>
> I dunno.
>
> I suspect in the end it's one of those things where it's just not
> useful enough: locking works, and usually works well enough.
FWIW, Z Perform Locked Operation supports up to compare-and-swap-and-triple-store, but keeps the lock itself separately. So roughly four the way you're counting.
