What is the "efficient lock-free dequeue implementation"? If it implies that thread 0 work queue (for example) could be lock-free, why don't we need a lock to ensure that two different threads don't steal the same continuation from a thread? Am I understanding the term "lock-free" correctly?
kayvonf
@patrickbot. Good question. However, if you don't mind, I'd like to defer answering this question until the lecture on... you guessed it... Lock-free data structures.
1pct
Why remote threads steal from the "head" of the queue and local threads steal form the "tail" of the queue? What is the benefit of doing this?
thomasts
@1pct See Kayvon's comment on the previous slide
Local threads take the most recent item from the queue because the data is the data that is most recently touched -- might be able to get cache locality benefits. Remote threads take the last item in the queue because it the largest piece of work -- the cost of stealing is amortized out by the large amount of work.
lol
@thomasts It is not necessarily the largest piece of work.
What is the "efficient lock-free dequeue implementation"? If it implies that thread 0 work queue (for example) could be lock-free, why don't we need a lock to ensure that two different threads don't steal the same continuation from a thread? Am I understanding the term "lock-free" correctly?
@patrickbot. Good question. However, if you don't mind, I'd like to defer answering this question until the lecture on... you guessed it... Lock-free data structures.
Why remote threads steal from the "head" of the queue and local threads steal form the "tail" of the queue? What is the benefit of doing this?
@1pct See Kayvon's comment on the previous slide
Local threads take the most recent item from the queue because the data is the data that is most recently touched -- might be able to get cache locality benefits. Remote threads take the last item in the queue because it the largest piece of work -- the cost of stealing is amortized out by the large amount of work.
@thomasts It is not necessarily the largest piece of work.
@1pct See slide 46.