Please post full reproducer then.
On Mon, May 22, 2017 at 4:42 PM, Jay Miller <jay.mil...@gmail.com> wrote:
> To be clear, the issue is that items get dropped altogether. In my test I
> have 50 threads each pushing 5000 notes to the queue with a sequence number
> and thread ID. The single consumer thread then tracks sequence numbers by
> thread ID. Under load I get things like:
>
> Items popped: 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1118 1119
> 1120 1121 1122 1123 1124 1125 1126 1127
>
> or
>
> Items popped: 2824 2825 2826 2827 2828 2829 2830 2831 2832 2833 2836 2837
> 2838 2839 2840 2841 2842 2843 2844 2845
>
> or
>
> Items popped: 2879 2880 2881 2882 2883 2884 2885 2886 2887 2888 2891 2892
> 2893 2894 2895 2896 2897 2898 2899 2900
>
> In every example I've seen 2 consecutive nodes get dropped like in these
> examples. This never happens when I replace the final "return nullptr" with
> the call to spin_pop.
>
> On Saturday, May 20, 2017 at 4:07:41 PM UTC-5, Dmitry Vyukov wrote:
>>
>> On Thu, May 18, 2017 at 6:48 AM, Jay Miller <jay.m...@gmail.com> wrote:
>> > Also it turns out I can consistently pass my test is I only replace the
>> > second // HERE with the spin_pop (the one after pushing _stub).
>> >
>> >
>> > On Wednesday, May 17, 2017 at 8:31:59 PM UTC-5, Jay Miller wrote:
>> >>
>> >> I have an C++ implementation of the MPSC queue. Under normal
>> >> circumstances it works correctly, but under heavy load it skips nodes
>> >> when
>> >> releasing. That is, in a test of many writers and a single reader,
>> >> nodes
>> >> are popped in the same order each thread wrote them, but sometimes a
>> >> node
>> >> does not get returned at all. If anyone can see what is wrong with
>> >> this I
>> >> would appreciate it very much.
>> >>
>> >> class Node
>> >> {
>> >> public:
>> >> // Atomic here as a shortcut for placing
>> >> // memory fences. Assignment is an atomic
>> >> // store with an acquire and release fence
>> >> std::atomic<Node*> next;
>> >> };
>> >>
>> >> template <typename T>
>> >> class MpscQueue
>> >> {
>> >> public:
>> >> MpscQueue()
>> >> : _head(&_stub)
>> >> , _tail(&_stub)
>> >> {
>> >> _stub.next = nullptr;
>> >> }
>> >>
>> >> void push(T* obj)
>> >> {
>> >> _push(obj);
>> >> }
>> >>
>> >> T* pop()
>> >> {
>> >> auto tail = _tail;
>> >> Node* next = tail->next;
>> >>
>> >> if (tail == &_stub)
>> >> {
>> >> if (!next)
>> >> {
>> >> return nullptr;
>> >> }
>> >> tail = next;
>> >> next = next->next;
>> >> }
>> >>
>> >> if (next)
>> >> {
>> >> _tail = next;
>> >> return static_cast<T*>(tail);
>> >> }
>> >>
>> >> if (tail != _head)
>> >> {
>> >> return nullptr; // HERE
>> >> }
>> >>
>> >> _push(&_stub);
>> >>
>> >> next = tail->next;
>> >> if (next)
>> >> {
>> >> _tail = next;
>> >> return static_cast<T*>(tail);
>> >> }
>> >>
>> >> return nullptr; // HERE
>> >> }
>> >>
>> >> private:
>> >> void _push(Node* node)
>> >> {
>> >> node->next = nullptr;
>> >> auto prev = _head.exchange(node);
>> >> prev->next = node;
>> >> }
>> >> std::atomic<Node*> _head;
>> >>
>> >> Node* _tail;
>> >> Node _stub;
>> >> };
>> >>
>> >>
>> >> As a clue, if I replace the lines above marked HERE with a call to this
>> >> function my tests always pass, except one time in one configuration
>> >> where it
>> >> entered a continuous loop.
>> >>
>> >> T* spin_pop(Node* tail)
>> >> {
>> >> do
>> >> {
>> >> _tail = tail->next;
>> >> } while (!_tail);
>> >>
>> >>
>> >> return static_cast<T*>(tail);
>> >> }
>> >
>>
>> Hi Jay,
>>
>> This algorithm is not linearizable. If push operation is preempted
>> between exchange and update of the next link, the linked list of nodes
>> is broken and there is no way pop can reach any of the subsequent
>> nodes (even if their push'es are completely finished). I guess that's
>> what you see.
>
> --
>
--
---
You received this message because you are subscribed to the Google Groups
"Scalable Synchronization Algorithms" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to lock-free+unsubscr...@googlegroups.com.
To view this discussion on the web visit
https://groups.google.com/d/msgid/lock-free/CAEeQi3tuoprrNO96yPfHPfT1Jc5LJd05orwwXGiOWuhJxOHX0Q%40mail.gmail.com.
For more options, visit https://groups.google.com/d/optout.
