Work Stealing Deque

[erincatto]

Hi Doug,

Your blog mentioned a future post on LockLessMultiReadPipe. I would gladly read such a post.

I've learned this data structure is commonly called a bounded work stealing deque. Is the enkiTS implementation derived from any published work? I'm curious about the array of atomic flags. I'm guessing these are used to reduce contention on the read count.

[dougbinks]

Hi Erin,

Sadly I do not recall the implementations I researched when I wrote the LockLessMultiReadPipe, though I do recall that it is similar but not the same as some approaches.

The m_Flags field's exists to reduce CAS operations on the read count. There may be a better way around this, I believe I tested some other algorithms but this proved the best when used in enkiTS on the systems I tried.

[erincatto]

If you look at Unreal, they have TWorkStealingQueueBase2 which also has an array of atomics (FAlignedElement). They even spread these out by 128 bytes. So I thought there might be a common reference for this technique.

[dougbinks]

I did try adding separating these by a cache line, but this added a large memory overhead for a fairly low performance gain. Given UE already has a fairly high memory use that's probably an acceptable win for them.