Здравствуйте, vf, Вы писали:
vf>Коллеги, возникло непреодолимое желание поделиться своим велосипедом, получить комментарии, может кому пригодится Готового на .нет не нашел, вот сделал свое, с пятой попытки.
vf>Основная задача, была сделать tread-safe пул буферов для сервера, первоначально реализовал это дело через lock, скорость работы lock подхода вынудила копать дальше, в сторону Interlocked, потом узал что правильно такой подход называется lock-free, а так же, что часто возникающая проблема в таких алгоритмах называется ABA (я с ней столкнулся в 3-4 попытке).
vf>В процессе работы над пулом и появился ниже приведенный Stack. В последствии, находил ссылки на pdf-ы с алгоритмами LIFO, FIFO, но не разбирался, вероятно там тоже самое. Читал про .нет 4.0, но там, по описанию, алгоритмы основаны на SpinLock, так что возможно мое будет чуть быстрее (хотя и со своими ограничениями)
vf>vf>class SafeStackItem<T>
vf>{
vf> public T Value;
vf> public volatile Int32 Next;
vf>}
vf>class SafeStack<T>
vf> where T : class
vf>{
vf> private volatile Int32 head;
vf> private volatile Int32 count;
vf> private SafeStackItem<T>[] array;
vf> public SafeStack(SafeStackItem<T>[] array, int pushFrom, int pushCount)
vf> {
vf> this.head = -1;
vf> this.array = array;
vf> count = pushCount;
vf> head = pushFrom;
vf> for (int i = 0; i < pushCount - 1; i++)
vf> array[i + pushFrom].Next = pushFrom + i + 1;
vf> array[pushFrom + pushCount - 1].Next = -1;
vf> }
vf>#pragma warning disable 0420
vf> public Int32 Pop()
vf> {
vf> while (count > 1)
vf> {
vf> Int32 head1 = head;
vf> Int32 next1 = Interlocked.Exchange(ref array[head1].Next, -1);
vf> if (next1 >= 0)
vf> {
vf> if (Interlocked.CompareExchange(ref head, next1, head1) == head1)
vf> {
vf> Interlocked.Decrement(ref count);
vf> return head1;
vf> }
vf> else
vf> Interlocked.Exchange(ref array[head1].Next, next1);
vf> }
vf> }
vf> return -1;
vf> }
vf> public void Push(Int32 index)
vf> {
vf> Int32 head1, head2;
vf> do
vf> {
vf> head1 = head;
vf> array[index].Next = head1;
vf> head2 = Interlocked.CompareExchange(ref head, index, head1);
vf> } while (head1 != head2);
vf> Interlocked.Increment(ref count);
vf> }
vf>#pragma warning restore 0420
vf>}
vf>
Мне не понятно где и когда идёт обращение к SafeStackItem<T>.Value