Hi Brendon, Thanks for the observations.
It that point between the CAS and the effective release of the seat, *all other threads are free to take another seat *without restriction. As well in any point of the code. There is no a single point where any thread is blocked from getting a seat. That why I'm sure that it is lock free. The queue will only stall, if it get full (all seats *after that point are ocupied* before the next cicle.) And only if the consumers get nothing. If you have a queue of 64k positions, the other threads will have the same amount of chances to continue without locking. With our current memory availability, a queue with a million positions is pretty factible. But after some point, the benchmarks shows that there are no speed improvement in increasing the buffer size. The optimum size must fit inside the processor cache size. The optimum I found is only 64 positions. Take a look on the benchmarks <https://github.com/bittnkr/uniq#benchmarks---measuring-the-flow> I've update the docs <https://github.com/bittnkr/uniq> and I think it is clearer now. Please run the code, stress it, increase the number of threads, reduce and increase the buffer size and change the nature of the data pushed. If you do that, I believe that you will agree with me: Its so lock free as it is possible to be. Em terça-feira, 14 de janeiro de 2020 04:38:32 UTC-2, Brendon Costa escreveu: > > I was interested in your queue so had a look as well. Thanks for sharing > it. I find it interesting looking at other implementations. > > I think Dmitry is correct. See the comment inline below. From my > understanding the code locks the consumers waiting on a producer at the > point in time where I placed the comment in the code. It has a slight > advantage over a standard lock impl though as other producers are not > blocked only other consumers. > > int push(T item) { > int i; > do { > i = in; > while (i - out > mask) > sched_yield(); // if full, wait for space > } while (!isFree[i & mask] || !in.compare_exchange_weak(i, i + 1)); > > // At this point in the code, the producer has incremented "in". Until > this thread sets isFree[i & mask] = 0, all consumers are blocked waiting > on isFree[o & mask] to be false. > // Even if another producer thread adds more data. So if the OS > pre-empts this thread at this point in time > // no consumers will make any progress until the OS re-schedules this > thread to finish its work. > > buffer[i & mask] = item; > isFree[i & mask] = 0; > return i; > } > > > > On Tue, 14 Jan 2020 at 13:16, bittnkr <bit...@gmail.com <javascript:>> > wrote: > >> > >> Well, if producer is preempted, consumers are blocked from progressing. >> >> Sorry, but this isn't true. >> >> The consumers are preempted only in case of a empty queue. Which isn't a >> lock. >> >> Meaning that there is nothing to do. If you don't have active producers, >> three is nothing to consume. >> >> How can you see a lock there? >> >> Please >> >> Em seg, 13 de jan de 2020 04:35, Dmitry Vyukov <dvy...@gmail.com >> <javascript:>> escreveu: >> >>> +lock-free group again, please don't drop it >>> >>> On Mon, Jan 13, 2020 at 8:19 AM bittnkr <bit...@gmail.com <javascript:>> >>> wrote: >>> > >>> > If a thread dies at that point, my entire system is broken... >>> >>> Which means it's not lock-free. >>> >>> > But It can preempts without any problem at near zero cost. >>> >>> Well, if producer is preempted, consumers are blocked from >>> progressing. This is 100% equivalent to a mutex. If a thread is >>> preempted while holding a mutex, it also does not result in any >>> correctness problems. >>> >>> >>> > Em seg, 13 de jan de 2020 03:55, Dmitry Vyukov <dvy...@gmail.com >>> <javascript:>> escreveu: >>> >> >>> >> On Sun, Jan 12, 2020 at 7:33 PM bittnkr <bit...@gmail.com >>> <javascript:>> wrote: >>> >> > >>> >> > >>> >> > > This blocks consumes from progressing (consuming next produced >>> items) >>> >> > and is effectively a mutex. >>> >> > >>> >> > Suppose the thread A got a local copy of tail in t then is >>> preempted, >>> >> > >>> >> > another thread will get the same tail an get the seat normally. >>> >> > >>> >> > When the previous thread retakes the line, the CAS will fail, >>> because the seat was taken. >>> >> > >>> >> > Restarting the while without any kind of blocking. >>> >> > >>> >> > Where do you see a mutex here? >>> >> >>> >> I mean preemption between succeeding CAS and writing element /NULL to >>> the array. >>> >> >>> >> If a thread is terminated at that point, the whole queue is broken (no >>> >> termination-safety). >>> >> >>> >> >>> >> > Em dom, 12 de jan de 2020 04:49, Dmitry Vyukov <dvy...@gmail.com >>> <javascript:>> escreveu: >>> >> >> >>> >> >> On Sat, Jan 11, 2020 at 9:26 AM bittnkr <bit...@gmail.com >>> <javascript:>> wrote: >>> >> >> > >>> >> >> > Good observations. Thank you. >>> >> >> > >>> >> >> > If the thread preempts on those points, the seat position will >>> be held on local variables h and t. >>> >> >> >>> >> >> This blocks consumes from progressing (consuming next produced >>> items) >>> >> >> and is effectively a mutex. This makes algorithm >>> non-termination-safe >>> >> >> and non-lock-free. >>> >> >> >>> >> >> >>> >> >> > After the thread line is restored, the CAS can fail, and the >>> loop will just restart in normal flow, without any locking. >>> >> >> > >>> >> >> > I updated the docs, I think is clearer now. >>> >> >> > >>> >> >> > Em sáb., 11 de jan. de 2020 às 05:38, Dmitry Vyukov < >>> dvy...@gmail.com <javascript:>> escreveu: >>> >> >> >> >>> >> >> >> On Sat, Jan 11, 2020 at 4:09 AM bittnkr <bit...@gmail.com >>> <javascript:>> wrote: >>> >> >> >> > >>> >> >> >> > Hello Dmitry and fellows from the group. >>> >> >> >> > >>> >> >> >> > If you look carefully, you will see that there is no >>> blocking, just simple CAS, even the buffer is a common buffer. >>> >> >> >> >>> >> >> >> But consider you look inside of a spin lock, or you take a >>> >> >> >> spin-lock-based algorithm and inline all spin lock code into the >>> >> >> >> algorithm. What you will see is exactly the same -- no >>> blocking, just >>> >> >> >> a CAS. However, it does not really change anything, it's still >>> >> >> >> blocking mutex-based algorithm. >>> >> >> >> One can also combine spin lock state with some data, e.g. a >>> particular >>> >> >> >> value of a data member means "locked" and blocks progress of >>> other >>> >> >> >> threads. It makes spin lock even less visible, but again does >>> not >>> >> >> >> change anything on conceptual level. >>> >> >> >> >>> >> >> >> If I am reading the algorithm correctly, if a thread is >>> preempted >>> >> >> >> between these 2 operations: >>> >> >> >> >>> >> >> >> } while ( (data[t & mask]) || (CompareExchange(tail, t+1, t) >>> != t) ) >>> >> >> >> data[t & mask] = item // now is safe to update the buffer >>> >> >> >> >>> >> >> >> It effectively locks a mutex on the queue and blocks progress >>> of all consumers. >>> >> >> >> >>> >> >> >> There is also a similar blocks on consumer side here: >>> >> >> >> >>> >> >> >> } while ( !(data[h & mask]) || CompareExchange(head, h+1, h) >>> != h ) >>> >> >> >> data[h] = 0 // release the seat >>> >> >> >> >>> >> >> >> >>> >> >> >> > The queue only sleeps if it is empty out of it is full. But >>> this is not locking. >>> >> >> >> > >>> >> >> >> > All protection is done by the two atomic variables head an >>> tail. >>> >> >> >> > >>> >> >> >> > The cost is constant near a single CAS. For any number of >>> threads. >>> >> >> >> > >>> >> >> >> > Take a look on this benchmarks. They speaks for themselves. >>> >> >> >> > >>> >> >> >> > >>> https://github.com/bittnkr/uniq/blob/master/README.md#benchmarks >>> >> >> >> > >>> >> >> >> > Besides I don't have a formal proof, we have a test with zero >>> checksum. >>> >> >> >> > >>> >> >> >> > This is the results I have for a producer/consumer test >>> pushing random numbers is the queue. >>> >> >> >> > >>> >> >> >> > Creating 4 producers & 4 consumers >>> >> >> >> > to flow 10.000.000 items trough the queue. >>> >> >> >> > >>> >> >> >> > Produced: 10.743.668.245.000.000 >>> >> >> >> > Consumed: 5.554.289.678.184.004 >>> >> >> >> > Produced: 10.743.668.245.000.000 >>> >> >> >> > Consumed: 15.217.833.969.059.643 >>> >> >> >> > Produced: 10.743.668.245.000.000 >>> >> >> >> > Consumed: 7.380.542.769.600.801 >>> >> >> >> > Produced: 10.743.668.245.000.000 >>> >> >> >> > Consumed: 14.822.006.563.155.552 >>> >> >> >> > >>> >> >> >> > Checksum: 0 (it must be zero) >>> >> >> >> > >>> >> >> >> > The producers increase total and the consumers decrease. The >>> result for 10M random numbers is zero. >>> >> >> >> > >>> >> >> >> > Thanks for the advices, I'll investigate about this tools. >>> >> >> >> > >>> >> >> >> > Em qui, 9 de jan de 2020 04:58, Dmitry Vyukov < >>> dvy...@gmail.com <javascript:>> escreveu: >>> >> >> >> >> >>> >> >> >> >> On Wed, Jan 8, 2020 at 9:29 PM bittnkr <bit...@gmail.com >>> <javascript:>> wrote: >>> >> >> >> >> > >>> >> >> >> >> > Dear Dmitry, >>> >> >> >> >> > >>> >> >> >> >> > I found a nice solution for the problem called 3 thread >>> consensus, considered impossible on the book The art of the multiprocessor >>> programming. I think that is a breakthrough. >>> >> >> >> >> > >>> >> >> >> >> > Debating on S.O. with someone about if the solution is >>> solid or no, If it is possible to occur data races, he referred relacy. >>> >> >> >> >> > >>> >> >> >> >> > So I'm writing you to ask your opinion about the solution. >>> >> >> >> >> > >>> >> >> >> >> > Can you take a little look on it? >>> >> >> >> >> >>> >> >> >> >> +lock-free mailing list >>> >> >> >> >> >>> >> >> >> >> Hi bittnkr, >>> >> >> >> >> >>> >> >> >> >> At first glance the algorithm at >>> https://github.com/bittnkr/uniq looks >>> >> >> >> >> blocking and non-linearizable to me. >>> >> >> >> >> Very similar in nature to: >>> >> >> >> >> >>> http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue >>> >> >> >> >> >>> >> >> >> >> -- >>> >> >> >> >> Dmitry Vyukov >>> >> >> >> >> >>> >> >> >> >> All about lockfree/waitfree algorithms, multicore, >>> scalability, >>> >> >> >> >> parallel computing and related topics: >>> >> >> >> >> http://www.1024cores.net >>> >> >> >> >>> >> >> >> >>> >> >> >> >>> >> >> >> -- >>> >> >> >> Dmitry Vyukov >>> >> >> >> >>> >> >> >> All about lockfree/waitfree algorithms, multicore, scalability, >>> >> >> >> parallel computing and related topics: >>> >> >> >> http://www.1024cores.net >>> >> >> >>> >> >> >>> >> >> >>> >> >> -- >>> >> >> Dmitry Vyukov >>> >> >> >>> >> >> All about lockfree/waitfree algorithms, multicore, scalability, >>> >> >> parallel computing and related topics: >>> >> >> http://www.1024cores.net >>> >> >>> >> >>> >> >>> >> -- >>> >> Dmitry Vyukov >>> >> >>> >> All about lockfree/waitfree algorithms, multicore, scalability, >>> >> parallel computing and related topics: >>> >> http://www.1024cores.net >>> >>> >>> >>> -- >>> Dmitry Vyukov >>> >>> All about lockfree/waitfree algorithms, multicore, scalability, >>> parallel computing and related topics: >>> http://www.1024cores.net >>> >> -- >> >> --- >> 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...@googlegroups.com <javascript:>. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/lock-free/CADQeMNeRGVNckAd0PaTneVQfeXf9e-PHa8mU%2BC3iMqqkKdvgng%40mail.gmail.com >> >> <https://groups.google.com/d/msgid/lock-free/CADQeMNeRGVNckAd0PaTneVQfeXf9e-PHa8mU%2BC3iMqqkKdvgng%40mail.gmail.com?utm_medium=email&utm_source=footer> >> . >> > -- --- 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/676c2747-2d1f-4d85-af3a-06752b75d756%40googlegroups.com.
