bittnkr / uniq Goto Github PK

Hello,

This is a cool library!

I'd be interested in using + contributing to this library, however the GPL is rather restrictive, especially for folks who would be interested in using this library for work projects.

Would you please consider moving to an MIT license?

Thanks!

From a formal standpoint, this implementation seems broken since you have date races on buffer[...], and C/C++11 says this is UB.

As discussed on https://stackoverflow.com/questions/25709548/lock-free-multiple-producer-consumer-queue-in-c11/59622729?noredirect=1#comment105424967_59622729 and
https://chat.stackoverflow.com/rooms/205556/discussion-between-bittnkr-and-peter-cordes

Consider this sequence of events:

• A writer calls push. It sleeps or stalls after head.compare_exchange_weak(t, t + 1) succeeds, making head=1 globally visible, but before buffer[0] = item happens.

• Another thread running pop can then see tail != head and can read buffer[0] at the same time another thread is writing it.

The safety of your code depends on read/write of buffer elements being atomic, but your in your code it's a vector<T> not vector<atomic<T>> (which you could use instead with memory_order_relaxed). You could see tearing in practice with int64_t on a 32-bit machine, e.g. compile with gcc -O3 -m32 on x86. (And of course it's obviously ISO C++ UB.)

Or with T = unsigned __int128 on a 64-bit machine. Or with T being a class type with overloaded operator= and operator bool.

It's also clearly C++ UB for pop to spin-wait on the non-atomic element value becoming non-zero.

!buffer[t & mask] could in theory be hoisted out of the loop when it's the same index every time, but in practice compilers will just reload it because t can change inside the loop.

BTW, you should probably hoist the t = tail out of the loop and just use the value from the CAS-fail load (tail.compare_exchange_weak(t, t+1); updates t on failure). Or move it to inside the spin-wait for non-empty loop.

// why was this virtual?  I don't see why you'd want that overhead
T pop() {
    T r;
    unsigned tmask, t = tail;   // unsigned so t+1 avoids signed-overflow UB
    do {
        while (t == head) {
            sched_yield(); // if empty, wait for item
            t = tail;    // no point leaving the loop if tail moved, too
        }
       tmask = t & mask;
        r = buffer[tmask];   // or buffer[tmask].load(std::memory_order_relaxed);
    }  while (!r ||
           !tail.compare_exchange_weak(t, t + 1) // tail = t+1 (ons swsr)
        );
    // no need to reload buffer[tmask]
    // and we can only leave the loop if CAS didn't modify t
    buffer[tmask] = 0;     // FIXME: this can race with a writer in an almost-full queue
    return r;
}

This doesn't fix any of the bugs, but makes it more efficient in preparation for replacing buffer with a vector or array of atomic<T>

Originally posted by @slnovak in #3 (comment)
I ran some initial benchmarks of sending 1M events via postMessage vs. uniq in the browser:

On a 2017 Macbook Air and Chrome 80.0.3987.149:

Feel free to take a look at the code for these benchmarks and let me know if you have any suggestions to change the testing approach.

https://github.com/slnovak/uniq-benchmark

Cheers!