Re: [lock-free] Re: About my Distributed Sequential lock

I've looked at DRWLOCK.PAS and it looks exactly the same as; http://www.1024cores.net/home/lock-free-algorithms/reader-writer-problem/distributed-reader-writer-mutex What is novel there? On Thu, Feb 5, 2015 at 8:36 PM, Amine Moulay Ramdane amine...@gmail.com wrote: Dmitry Vyukov wrote: I don't

Re: [lock-free] Question on relaxed atomic optimizations in MPMC queue

On Thu, Jan 29, 2015 at 1:37 AM, Pedro Ramalhete prama...@gmail.com wrote: Hi Dmitry, I have a question regarding the MPMC queue on your site http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue On the enqueue() method, aren't you worried that the store on

Re: [lock-free] Fast single-reader many-writer concurrent hash table

On Mon, Mar 16, 2015 at 4:22 AM, sbahra sba...@repnop.org wrote: Hi all, I'd love your thoughts on http://backtrace.io/blog/blog/2015/03/13/workload-specialization/ or at least hope it's useful to some folks! I've been using this a few years now, and decided to spend some time documenting

Re: [lock-free] Pros and Concerns for using packed pointers to solve ABA instead of DCAS

On Sat, Jun 20, 2015 at 6:56 PM, Eugene Zatepyakin zatepya...@gmail.com wrote: Hi Dmitry, thanx for your explanation. i did quick tests on iOS platform and it seems to support DwCAS (that was quicks runs and i'm not 100% sure) i also read in some articles that it is enough to only increment

[lock-free] Re: mpmc queue reset and count method

On Mon, Nov 9, 2015 at 7:15 PM, Bernard Harmel wrote: > Hi, > > I saw your bounded mpmc queue > (http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue) > in the spdlog library (https://github.com/gabime/spdlog) > This is a great piece of code and I was

[lock-free] Re: Lock free question

On Sat, Nov 21, 2015 at 2:15 AM, Rajinder Yadav wrote: > Hello Dmitry, > > I would like to thank you for your excellent write up on lock-free > programming. I have a question and was wondering if you might be able to > explain how I might be able to update multiple

Re: [lock-free] Re: low overhead mpsc and work-stealing

91e010, 0x91e030, 0x91e050, 0x91e070, 0x91e090, 0x91e0b0, 0x91e0d0, > 0x91e0f0, 0x91e110, 0x91e130, 0x91e150, 0x91e170, 0x91e190, 0x91e1b0, > 0x91e1d0, 0x91e1f0, 0x91e210, 0x91e230, 0x91e250, 0x91e270, > Nothing to pop! > > Nothing to pop! > > Nothing to pop! > > Nothin

Re: [lock-free] Index pool

On Sat, Jan 14, 2017 at 5:22 PM, 'Karl' via Scalable Synchronization Algorithms wrote: > I'm looking for a non-blocking index pool, i.e., a finite set of integers in > the range [0,n) where get() returns an arbitrary integer from the set and > put(x) writes index x

Re: [lock-free] Bounded MPMC queue exception safety

On Thu, Nov 3, 2016 at 8:36 PM, Miral Mirality wrote: > Hi Dmitry, > > Pondering the bounded MPMC queue at > http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue > (very clever design, by the way, as I've said before). > > In the case where enqueue has

Re: [lock-free] Re: your MPMC queue - two problems?

On Fri, Nov 25, 2016 at 1:50 PM, Miral Mirality <uec...@gmail.com> wrote: > On 25/11/2016 19:46, "Dmitry Vyukov" <dvyu...@gmail.com> wrote: >> > While uniform licensing is not strictly mandatory in Boost, AFAIK, I >> > think >> > technically

[lock-free] Re: Relacy CAS release + acquire error?

On Mon, Dec 19, 2016 at 4:18 AM, Alex Khripin wrote: > Hi Dmitry, > First -- relacy is great, thank you for providing this tool and all the > other stuff on 1024cores. > > Second -- I ran into a hiccup. This might be something I don't properly > understand in the C++11

Re: [lock-free] Work-stealing with LIFO local pop and FIFO steal

On Mon, Jul 31, 2017 at 9:14 PM, wrote: > Hi all, > > I've been using the following lock-free work-stealing deque for a while: > https://blog.molecular-matters.com/2015/09/25/job-system-2-0-lock-free-work-stealing-part-3-going-lock-free/ > I'm not using an MPMC queue since pops

Re: [lock-free] Re: Issues with intrusive mpsc queue

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>

Re: [lock-free] Re: Issues with intrusive mpsc queue

On Thu, May 18, 2017 at 6:48 AM, Jay Miller 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

Re: [lock-free] Question about JCTools MPMC queue

On Fri, May 26, 2017 at 12:10 PM, Sharath Gururaj wrote: > Thanks Nitsan and Dmitry for the clear explanation of #2 > I understand it now. > > However, In the case of concurrent queues, > I'm not sure if we should interpret the offer() semantics of java in such a > strict way.

Re: [lock-free] regarding mpmc bounded queue

On Sun, Oct 15, 2017 at 11:40 AM, user1990 k wrote: > Dear All, > > I was trying to understand this. > http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue > > Let me consider enqueue scenario [ both threads ] > > Thread 1 in core 0 | Thread 2 in

Re: [lock-free] Single target proxy collector

On Tue, Oct 31, 2017 at 8:32 AM, Chris M. Thomasson wrote: > On Friday, February 15, 2013 at 1:16:36 AM UTC-8, Anthony Williams wrote: >> >> On 14/02/13 23:07, jseig...@gmail.com wrote: >> > C11 and C++11 left out the most powerful atomic primitives. Despite >> > that you

Re: [lock-free] One reason why I like atomic_thread_fence...

On Sat, Mar 31, 2018 at 10:41 PM, Chris M. Thomasson wrote: > Notice how there is an acquire barrier inside of the CAS loop within the > enqueue and dequeue functions of: > > > http://www.1024cores.net/home/lock-free-algorithms/queues/bounded-mpmc-queue > > > ? > > > Well,

Re: [lock-free] One reason why I like atomic_thread_fence...

On Mon, Apr 9, 2018 at 3:38 AM, Chris M. Thomasson <cris...@charter.net> wrote: > On Saturday, April 7, 2018 at 1:46:20 AM UTC-7, Dmitry Vyukov wrote: >> >> On Thu, Apr 5, 2018 at 10:03 PM, Chris M. Thomasson <cri...@charter.net> >> wrote: >> > On Tuesday,

Re: [lock-free] One reason why I like atomic_thread_fence...

On Mon, Apr 16, 2018 at 12:32 AM, Chris M. Thomasson <cris...@charter.net> wrote: > > > On Friday, April 13, 2018 at 11:45:51 PM UTC-7, Dmitry Vyukov wrote: >> >> On Mon, Apr 9, 2018 at 3:38 AM, Chris M. Thomasson <cri...@charter.net> >> wrote: >> >

Re: [lock-free] Simple DWCAS based Proxy Collector, refined... ;^)

On Tue, Mar 27, 2018 at 11:23 PM, Chris M. Thomasson wrote: > Fwiw Dmitry, I have been working with fractals a lot lately, and was > wondering if I could still program a proxy collector from scratch. Remember > my old collector here: > >

Re: [lock-free] A Wait-Free MPMC Queue

On Thu, Oct 18, 2018 at 10:02 AM Anthony Williams wrote: > > On 18/10/2018 09:23, 饶萌 wrote: > > I've just created a real wait-free MPMC queue in 100+ lines of C++11 > > code: WFMPMC . > > > > Appreciate it if you can help check. > > This is not wait free. If you

Re: [lock-free] A Wait-Free MPMC Queue

On Fri, Oct 19, 2018 at 5:41 PM Anthony Williams wrote: > > On 19/10/2018 17:15, Dmitry Vyukov wrote: > > On Thu, Oct 18, 2018 at 10:02 AM Anthony Williams > > wrote: > >> > >> On 18/10/2018 09:23, 饶萌 wrote: > >>> I've just created a real wait-f

[lock-free] wait-free combiner lock

Hi, An interesting wait-free combiner lock with 2 XCHG to enqueue work: https://github.com/romkatv/action-chain/blob/master/src/action_chain.h This is somewhat similar to the XCHG-based enqueue here: http://www.1024cores.net/home/lock-free-algorithms/queues/non-intrusive-mpsc-node-based-queue

[lock-free] Re: Question about your MPMC code

event occurs when you observe it by definition, there is no other way to define it (think of relativity theory and speed of light). If you observe it, it happened. If you don't see it, it did not happen yet. > On Sat, Nov 10, 2018 at 7:24 PM Dmitry Vyukov wrote: >> >> On Sat, Nov 1

[lock-free] Re: Question about your MPMC code

On Sat, Nov 10, 2018 at 4:37 PM Guang Han wrote: > > Hi Dmitry, > >I came across your MPMC code on 1024 cores website. It is very well > written with awesome performance. It has the best performance than any other > MPMC queue i can find online. I have one quick question I hope you can help

Re: [lock-free] what happened when `mpscq_node_t* prev = XCHG(>head,n)`

On Fri, Nov 16, 2018 at 11:15 AM by byaiu wrote: > > Hi, > I'm reading <> and found the code in > mpscq_push `mpscq_node_t* prev = XCHG(>head,n)` confusing. > mpscq figure Hi by, I don't have permissions to view the link you posted. I assume you mean this algorithm:

Re: [lock-free] Re: Simple Example, Very Basic Per-Thread Proxy GC...

On Sun, Dec 23, 2018 at 7:31 AM Chris M. Thomasson wrote: > On Monday, December 17, 2018 at 11:23:20 PM UTC-8, Chris M. Thomasson > wrote: >> >> If interested, I can give more details. For now, here is the code in >> the form of a Relacy Test Unit: Can you

Re: [lock-free] Re: Simple Example, Very Basic Per-Thread Proxy GC...

On Thu, Dec 20, 2018 at 12:17 AM Chris M. Thomasson wrote: > > On Wednesday, December 19, 2018 at 2:02:31 AM UTC-8, Dmitry Vyukov wrote: >> >> On Wed, Dec 19, 2018 at 7:05 AM Chris M. Thomasson >> wrote: >> > >> > On Monday, December 17, 2018 at 11:23:2

[lock-free] Re: Actor scheduler source code availability

On Wed, Dec 12, 2018 at 1:04 PM Per wrote: > > Hi Dmitry, > > First, I want to thank you for the fantastic resource you have put together > on 1024cores.net. I have found it very helpful in my studies on lockfree > algorithms. > > I have a question that I was hoping you could help me with. The

Re: [lock-free] Re: Scalable hash map

On Fri, Dec 28, 2018 at 1:22 PM wrote: > > Hi, > > sorry for resurrecting this old thread! > > The link to the files (http://groups.google.com/group/lock-free/files) no > longer works. > I've downloaded the hash_map.zip file from your homepage, but this version of > the code only supports

Re: [lock-free] Re: What is the most simple SPSC queue?

On Fri, Dec 28, 2018 at 10:57 AM segn wrote: > > W dniu czwartek, 13 grudnia 2018 07:54:14 UTC+1 użytkownik segn napisał: >> >> Basically I'm looking for implementation of the same queue. In the project, >> the same principle was used for both thread-thread single-direction >> communication

Re: [lock-free] Re: Simple Example, Very Basic Per-Thread Proxy GC...

On Wed, Dec 19, 2018 at 7:05 AM Chris M. Thomasson wrote: > > On Monday, December 17, 2018 at 11:23:20 PM UTC-8, Chris M. Thomasson wrote: >> >> If interested, I can give more details. For now, here is the code in the >> form of a Relacy Test Unit: Can you give a short executive summary? What

Re: [lock-free] Experimental Read/Write Mutex..

On Wed, Feb 20, 2019 at 1:31 AM Chris M. Thomasson wrote: > > On Monday, February 18, 2019 at 12:13:21 PM UTC-8, Dmitry Vyukov wrote: >> >> On Sun, Feb 17, 2019 at 11:51 PM Chris M. Thomasson >> wrote: >> > >> > On Saturday, February 16, 2019

Re: [lock-free] Re: Experimental Read/Write Mutex..

On Tue, Feb 26, 2019 at 11:47 PM Chris M. Thomasson wrote: > > On Tuesday, February 26, 2019 at 12:10:02 AM UTC-8, Dmitry Vyukov wrote: >> >> On Wed, Feb 20, 2019 at 7:51 AM Chris M. Thomasson >> wrote: >> > >> > Fwiw, I wrote a crude new benchmark tha

[lock-free] TensorFlow scheduler

Hi, TensorFlow CPU task scheduler I wrote some time ago: https://bitbucket.org/eigen/eigen/src/9fdbc9e653c1adc64db1078fd2ec899c1e33ba0c/unsupported/Eigen/CXX11/src/ThreadPool/NonBlockingThreadPool.h?at=default=file-view-default

Re: [lock-free] Re: TensorFlow scheduler

On Wed, Mar 6, 2019 at 7:11 AM Chris M. Thomasson wrote: >>> >>> Hi, >>> >>> TensorFlow CPU task scheduler I wrote some time ago: >>> >>>

Re: [lock-free] Re: TensorFlow scheduler

On Fri, Mar 1, 2019 at 8:27 AM Chris M. Thomasson wrote: > > On Wednesday, February 27, 2019 at 1:35:04 AM UTC-8, Dmitry Vyukov wrote: >> >> Hi, >> >> TensorFlow CPU task scheduler I wrote some time ago: >> >> https://bitbucket.org/eigen/eigen/sr

Re: [lock-free] Experimental Read/Write Mutex..

On Sun, Feb 17, 2019 at 12:34 AM Chris M. Thomasson wrote: > > Fwiw, here is a simple benchmark for an older read/write algorithm I invented: > > > https://pastebin.com/raw/xCBHY9qd > > > It should compile fine on MSVC 2017 and GCC with -std=c++17. There is a macro > in the code called

[lock-free] Abseil/nsync Mutex

Hi, FYI, if you haven't seen this yet: https://github.com/abseil/abseil-cpp/blob/master/absl/synchronization/mutex.h https://github.com/abseil/abseil-cpp/blob/master/absl/synchronization/mutex.cc Some minor improvements are possible, but overall it's a piece of art. Originally developed by Mike

Re: [lock-free] Experimental Read/Write Mutex..

On Sun, Feb 17, 2019 at 11:51 PM Chris M. Thomasson wrote: > > On Saturday, February 16, 2019 at 11:24:42 PM UTC-8, Dmitry Vyukov wrote: >> >> On Sun, Feb 17, 2019 at 12:34 AM Chris M. Thomasson >> wrote: >> > >> > Fwiw, here is a simple ben

[lock-free] eventually fair mutex

Hi, I did this change some time ago, but thought it's still worth sharing (better late than never!): https://go-review.googlesource.com/c/go/+/34310/ https://go-review.googlesource.com/c/go/+/34310/8/src/sync/mutex.go There are mutexes that let threads in in strict FIFO order. This is good for

[lock-free] Re: 3-thread consensus.

t 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:

[lock-free] Re: 3-thread consensus.

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. > &

[lock-free] Re: 3-thread consensus.

tex. 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

[lock-free] Re: 3-thread consensus.

t /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 escreveu: >> >> On Sat, Jan 11, 2020 at 9:26 AM bittnkr wrote: >> > >> > Good observations. Thank you.

[lock-free] Re: MPMC atomic queue

On Tue, Nov 5, 2019 at 5:48 AM Erez Strauss wrote: > > Hi Dmitry, > > Good morning. > > Thank you for your mpmc queue. > > Recently, I published on github the following MPMC atomic queue. > > https://github.com/erez-strauss/lockfree_mpmc_queue > > It is atomic lockfree queue. > I'll appreciate

[lock-free] Re: 3-thread consensus.

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 escreveu: >> >> On Sun, Jan 12, 2020 a

Re: [lock-free] Re: 3-thread consensus.

sday, 14 January 2020 03:16:23 UTC+1, bittnkr 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

Re: [lock-free] Linux membarrier syscall

On Fri, Jun 9, 2023 at 8:00 AM Joseph Seigh wrote: > > Anyone know the difference between MEMBARRIER_CMD_PRIVATE_EXPEDITED and > MEMBARRIER_CMD_PRIVATE_EXPEDITED_SYNC_CORE for membarrier. > > It would be nice if it actually does what I think it does. I really don't > want to have to read from

Re: [lock-free] Linux membarrier syscall

t, 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/ae8349fc-a322-421f-8acd-9a8c4aa3a32an%40googlegroups.com. -- Dmitry Vyukov All about lockfree/waitfree algorithms, multicore, scalab

Re: [lock-free] Linux membarrier syscall

a rseq section (effectively atomic memory-to-memory move wrt to the current CPU). > Joe Seigh > > On Tuesday, June 13, 2023 at 3:03:34 AM UTC-4 Dmitry Vyukov wrote: >> >> On Fri, Jun 9, 2023 at 8:00 AM Joseph Seigh wrote: >> > >> > A