tag:blogger.com,1999:blog-8231772264325864647.post4853245704774494784..comments2024-03-22T19:05:00.088+01:00Comments on Concurrency Freaks: CRTurn Queue - The first MPMC memory-unbounded wait-free queue with memory reclamationPedro Ramalhetehttp://www.blogger.com/profile/01340437958052998917noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-8231772264325864647.post-47267031218788153372019-08-28T08:13:12.969+02:002019-08-28T08:13:12.969+02:00This is a trick I learned from Dave Dice (I hope I...This is a trick I learned from Dave Dice (I hope I don't misquote him): when a cache line is requested on x86, sometimes the pre-fetcher will request the next adjacent cache line. This means that the next cache line also becomes a source of false sharing. As such, to fully eliminate false-sharing, the padding should be two cache lines => 128 bytes.<br /><br />Notice that alignas(128) doesn't really guarantee that the compiler will respect the 128 bytes alignment, but it's an effort.Pedro Ramalhetehttps://www.blogger.com/profile/01340437958052998917noreply@blogger.comtag:blogger.com,1999:blog-8231772264325864647.post-91618666750351850992019-08-28T05:29:47.449+02:002019-08-28T05:29:47.449+02:00Hi, as I know, cache line size of L1 and L2 is 64b...Hi, as I know, cache line size of L1 and L2 is 64bytes. Why you use 128 in the code 'CLPAD = 128/sizeof(std::atomic);'?Anonymoushttps://www.blogger.com/profile/02027015073959655283noreply@blogger.comtag:blogger.com,1999:blog-8231772264325864647.post-9020396996299351092019-02-27T21:06:10.883+01:002019-02-27T21:06:10.883+01:00Thank you for the pointer. I was successfully able...Thank you for the pointer. I was successfully able to modify the LCRQ implementation to shared memory using Boost interprocess shared memory allocator. I know that kinda makes it locking because the allocator is locking, but I can live with that trade off. <br /><br />I needed something for IPC in a 3 process simulation. Benchmarks here - https://github.com/r10a/threads_exp/tree/LCRQueue<br /><br />I am also in the process of converting it into a block-when necessary queue so the threads can sleep when the queue is empty to save CPU power.Rohithttps://www.blogger.com/profile/11542592900825069817noreply@blogger.comtag:blogger.com,1999:blog-8231772264325864647.post-52978845202663300262019-02-27T21:05:04.828+01:002019-02-27T21:05:04.828+01:00This comment has been removed by the author.Rohithttps://www.blogger.com/profile/11542592900825069817noreply@blogger.comtag:blogger.com,1999:blog-8231772264325864647.post-89787413964848147392019-02-02T18:25:16.452+01:002019-02-02T18:25:16.452+01:00You would need an allocator for shared memory, som...You would need an allocator for shared memory, something like Doug Lea's alloctor. It wouldn't be wait-free (or event lock-free).<br />How about using LCRQ? It needs double-word CAS (which exits on x86) and you have a single node and re-use, except in some special circumstances.<br />https://github.com/pramalhe/ConcurrencyFreaks/blob/master/CPP/queues/LCRQueue.hpp<br />We have a few non-blocking memory bounded queues but we haven't published the paper yet, so we can't put up the code online.Pedro Ramalhetehttps://www.blogger.com/profile/01340437958052998917noreply@blogger.comtag:blogger.com,1999:blog-8231772264325864647.post-85554084737957772712019-02-01T22:24:48.428+01:002019-02-01T22:24:48.428+01:00The performance of this queue is very good. Can an...The performance of this queue is very good. Can anyone tell me how I can go about modifying this queue for IPC/Shared memory?Rohitnoreply@blogger.comtag:blogger.com,1999:blog-8231772264325864647.post-82122239332121743992018-10-18T10:43:52.794+02:002018-10-18T10:43:52.794+02:00I've just created a wait-free mpmc queue in 10...I've just created a wait-free mpmc queue in 100+ lines of C++11 code: <br />https://github.com/MengRao/WFMPMC<br /><br />Can you help check?<br /><br />Thanks,<br />MengAnonymoushttps://www.blogger.com/profile/16993429693420594623noreply@blogger.comtag:blogger.com,1999:blog-8231772264325864647.post-37378511363203401222016-10-27T16:04:08.700+02:002016-10-27T16:04:08.700+02:00See my problem, too :-). JackSee my problem, too :-). JackAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-8231772264325864647.post-91745421810031701092016-10-27T15:34:12.800+02:002016-10-27T15:34:12.800+02:00Huhh I'm afraid I don't understand how is ...Huhh I'm afraid I don't understand how is it possible to achieve unique tids using std::unordered_map (without using a mutex)<br />Perhaps there is a trick I'm missing?<br />If so, feel free to drop me an email with more details at pramalhe gmail com, or better yet, submit a pull request on githb :)<br /><br />PS: I hope you checked for tid < MAX_THREADS (instead of tid <= MAX_THREADS), otherwise there will be errors due to "array out of bounds".Pedro Ramalhetehttps://www.blogger.com/profile/01340437958052998917noreply@blogger.comtag:blogger.com,1999:blog-8231772264325864647.post-13843402384882724272016-10-27T15:21:00.260+02:002016-10-27T15:21:00.260+02:00I think you can check as much as you can and leave...I think you can check as much as you can and leave to the user what you can't. In my test of your queue I had to check for positive tid numbers, tid <=MAX_THREADS and store mapping for generated tids in std::unordered_map tids_;<br />All this can be done in inside the queue and the user should not see/use tids at all.<br />JackAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-8231772264325864647.post-907382948312694202016-10-27T15:10:48.239+02:002016-10-27T15:10:48.239+02:00Hi Jack,
We don't check boundaries for tid bec...Hi Jack,<br />We don't check boundaries for tid because there is an even bigger constraint/assumption: that the tids must be unique. This is very difficult to check in practice so we just don't do it and it's up to the user/caller to guarantee that. If the user can't even chose a positive tid lower than MAX_THREADS, then it's unlikely that he'll chose unique tids, and he won't be able to use this queue anyways.Pedro Ramalhetehttps://www.blogger.com/profile/01340437958052998917noreply@blogger.comtag:blogger.com,1999:blog-8231772264325864647.post-75975567446663738412016-10-27T14:14:47.721+02:002016-10-27T14:14:47.721+02:00C'tor needs to throw when maxThreads out of ra...C'tor needs to throw when maxThreads out of range. Calls to enqueue and dequeue should fail when tid out of range. Checking for those values being negative can be avoided by changing parameters from int to unsigned...<br />Jack GoralAnonymousnoreply@blogger.com