8

I have a problem that requires me to use a highly concurrent, wait free implementation of a stack. I have to preallocate all memory (no garbage collection or mallocs) in advance and it is acceptable that the stack is bounded in size (push may return false if the stack if full).

I am familiar with the stack implementation from Nir Shavit: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.8728 ... But that relies on linked lists and garbage collection. I need something that is array based.

It looks like there is one on ACM here: http://dl.acm.org/citation.cfm?id=1532611 though I am sceptical about the low download rate and citations.

The ideal answer would be reference code (in C/C++) I could simply steal :-)

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Thomas Kejser
  • 1,264
  • 1
  • 10
  • 30
  • Have you tried spinlocks ? – wildplasser Jan 17 '13 at 22:36
  • Yes, they are not wait free. Scheduler can get in the way. I need guaranteed progres – Thomas Kejser Jan 17 '13 at 23:05
  • 1
    If you run multithreaded (with more threads than CPUs) you are fundamentically never waitfree. BTW: what will the caller do once it detects a stack full condition? – wildplasser Jan 17 '13 at 23:41
  • Wildplasser: You can indeed be wait free for certain data structures, even at high concurrency (this is what lock free programming is all about)... When the stack is full, the caller will fall back on a free list that is synchronized with a spinlock. However, the full stack is a rare condition. – Thomas Kejser Jan 17 '13 at 23:51
  • 2
    When properly designed, (think: dancing links) the spinlock-wait does not have to be more than ~10 cycles. IIRC, Leslie Lamport has an algoritm for one producer, multiple consumers. Might be adaptable. Might be not. – wildplasser Jan 18 '13 at 00:01
  • There are general constructions for arbitrary data structures but they are often not practical because of the enormous overhead. So from a theoretical point of view the answer is definitely yes, but from a practically point of few I do not know the answer. – Daniel Brückner Jan 18 '13 at 00:14
  • This is a tough one. Even if one manage to implement the fixed stack, there will be troubles in handling the switch from it to the linked list in a way which garantees that the element stacking order is preserved accross both structures. – didierc Jan 18 '13 at 00:23
  • Wild: even stack queued spinlocks are not scalable for this type of solution. The cycle cost goes up A LOT on large systems (think hundreds of cycles) – Thomas Kejser Jan 18 '13 at 11:06

1 Answers1

1

Have you looked at the windows DDI InterlockedPushEntrySList() and InterlockedPopEntrySList()? They are not array based but they are lock free and use processor atomic instructions to add and remove items from the stack. It is not wait free, but maybe it can be useful to you...

David P
  • 153
  • 7
  • Hi David. I am indeed familiar with those. But I am afraid I need something that is cross platform in this case. – Thomas Kejser Jan 21 '13 at 11:22
  • FYI, those DDIs are implemented using compiler intrinsics that map to special x86/x64 instructions. They can be ported to any OS and will work on all Intel processors newer than Pentium 4. They are still not wait free but may be useful in your ultimate solution. – David P Jan 22 '13 at 00:30