| michael.podolsky.rrr@gmail.com: Jan 09 08:17PM -0800 If I am not mistaken, I am going to show that there is a class of concurrent algorithms which are incompatible with C++ memory model. An excerpt from https://en.cppreference.com/w/cpp/language/memory_model: "If a data race occurs, the behavior of the program is undefined." And a data race is "simultaneous" read and write operation from two threads (or two writes as well) of the non-atomic data. Now, let's consider a special kind of single-writer multiple-readers algorithm which never blocks the writer (which is a fixed dedicated thread which delivers data updates). I define it out of the context of C++, just pure processor instructions with appropriate memory barriers. We expect that our processor may read/write some memory cells in an "atomic" way i.e. as a whole and with arbitrary memory barriers we may need. The other memory cells may be read/written without such "atomic" protection. Suppose, we have a buffer of memory "B" which is to be updated by the writer and read by the multiple readers. We may add an atomic counter (initialized to zero) to this buffer and make the writer increment the counter before it starts to update the buffer and after it finishes to update it. As a result, if the reader reads this counter and sees an odd value, it knows that the buffer is currently updated. On the other side, if the counter is even, the reader may read the buffer "B", then read the counter again and if it finds it did not change from the beginning, the data read from the buffer may be considered valid. Note that the readers may need to retry their read operation or wait while the counter is odd, but the writer is never blocked. Now, of course we do not need our buffer to be an array of atomic memory cells, our protocol looks to care well about all the possible conflicts and simultaneous access to the buffer memory. Making the buffer atomic will just make our code less effective and will disallow workig with it as with an array of chars, for instance. And here we can clearly say that this algorithm, as defined, may not be implented in C++. It does allow simultaneous reads and writes of the same non-atomic buffer, but the C++ says, that such a case must be qualified as "data race" and as a result "the behavior of the program is undefined". |
| "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Jan 09 08:43PM -0800 > And a data race is "simultaneous" read and write operation from two threads (or two writes as well) of the non-atomic data. > Now, let's consider a special kind of single-writer multiple-readers algorithm which never blocks the writer (which is a fixed dedicated thread which delivers data updates). I define it out of the context of C++, just pure processor instructions with appropriate memory barriers. We expect that our processor may read/write some memory cells in an "atomic" way i.e. as a whole and with arbitrary memory barriers we may need. The other memory cells may be read/written without such "atomic" protection. > Suppose, we have a buffer of memory "B" which is to be updated by the writer and read by the multiple readers. We may add an atomic counter (initialized to zero) to this buffer and make the writer increment the counter before it starts to update the buffer and after it finishes to update it. As a result, if the reader reads this counter and sees an odd value, it knows that the buffer is currently updated. On the other side, if the counter is even, the reader may read the buffer "B", then read the counter again and if it finds it did not change from the beginning, the data read from the buffer may be considered valid. Note that the readers may need to retry their read operation or wait while the counter is odd, but the writer is never blocked. This sounds just like a seqlock. > Now, of course we do not need our buffer to be an array of atomic memory cells, our protocol looks to care well about all the possible conflicts and simultaneous access to the buffer memory. Making the buffer atomic will just make our code less effective and will disallow workig with it as with an array of chars, for instance. > And here we can clearly say that this algorithm, as defined, may not be implented in C++. It does allow simultaneous reads and writes of the same non-atomic buffer, but the C++ says, that such a case must be qualified as "data race" and as a result "the behavior of the program is undefined". We can have multiple reads per non-atomic data, think read write lock. Not 100% sure about writes, it should be a data-race. Need to think on this. Fwiw, have you seen the following "distributed" seqlock: http://www.1024cores.net/home/lock-free-algorithms/reader-writer-problem/improved-lock-free-seqlock One way, might be to hide the state behind a pointer load, and use data-dependent consume wrt the readers loading. Something like: struct state { ///[...] }; state g_state = { ... }; std::atomic<state*> m_state_ptr = &g_state; We can load state in one shot via memory order consume: state* s = m_state_ptr.load(std::memory_order_consume); Still, if the state can be concurrently read and written from/to, then its members should be atomic, wrt relaxed memory order loads. |
| michael.podolsky.rrr@gmail.com: Jan 09 10:16PM -0800 On Wednesday, January 9, 2019 at 11:43:42 PM UTC-5, Chris M. Thomasson wrote: > This sounds just like a seqlock. That's right. > Still, if the state can be concurrently read and written from/to, then > its members should be atomic, wrt relaxed memory order loads. Yes, we'll need to define the data buffer as an array of atomics in seqlock to comply to C++ rules, then use the most weak "relaxed" memory order to read or write this buffer. By doing this we just surrender to C++ limitations. Had we written the code in assembly, we would not have cared much about how we acceess the same buffer. |
| "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Jan 10 08:08AM +0100 > Suppose, we have a buffer of memory "B" which is to be updated by the writer and read by the multiple readers. We may add an atomic counter (initialized to zero) to this buffer and make the writer increment the counter before it starts to update the buffer and after it finishes to update it. As a result, if the reader reads this counter and sees an odd value, it knows that the buffer is currently updated. On the other side, if the counter is even, the reader may read the buffer "B", then read the counter again and if it finds it did not change from the beginning, the data read from the buffer may be considered valid. Note that the readers may need to retry their read operation or wait while the counter is odd, but the writer is never blocked. > Now, of course we do not need our buffer to be an array of atomic memory cells, our protocol looks to care well about all the possible conflicts and simultaneous access to the buffer memory. Making the buffer atomic will just make our code less effective and will disallow workig with it as with an array of chars, for instance. > And here we can clearly say that this algorithm, as defined, may not be implented in C++. It does allow simultaneous reads and writes of the same non-atomic buffer, but the C++ says, that such a case must be qualified as "data race" and as a result "the behavior of the program is undefined". The conclusion "may not be implemented in C++" is too general. "May not be 100% portably implemented in C++" is a more reasonable conclusion. The C++17 standard notes, in the relevant section, that there may, at least hypothetically, be systems with hardware race detection: C++17 §4.7.1/23: "Transformations that introduce a speculative read of a potentially shared memory location may not preserve the semantics of the C ++ program as defined in this International Standard, since they potentially introduce a data race. However, they are typically valid in the context of an optimizing compiler that targets a specific machine with well-defined semantics for data races. They would be invalid for a hypothetical machine that is not tolerant of races or provides hardware race detection" So it seems that the unqualified UB is in support of possible future systems that are not tolerant of data races. Or, it /could/ be a defect, that there should be some qualification that if the read data in a race, is used for anything, then you have UB. But this language would preclude the mentioned hypothetical architectures, unless also that was made part of the qualification. Which would be unusual. Cheers!, - Alf |
| "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Jan 10 01:29AM -0800 >> Still, if the state can be concurrently read and written from/to, then >> its members should be atomic, wrt relaxed memory order loads. > Yes, we'll need to define the data buffer as an array of atomics in seqlock to comply to C++ rules, then use the most weak "relaxed" memory order to read or write this buffer. By doing this we just surrender to C++ limitations. Had we written the code in assembly, we would not have cared much about how we acceess the same buffer. Well, I agree with you Michael. Fwiw, Relacy Race Detector definitely does not approve of its non-atomic's (e.g., VAR_T) being concurrently written to by multiple threads, multiple reads all day long, no conflicting writes. It tries to model the standard... ;^) |
| Chris Vine <chris@cvine--nospam--.freeserve.co.uk>: Jan 10 04:35PM On Wed, 9 Jan 2019 20:17:07 -0800 (PST) > same non-atomic buffer, but the C++ says, that such a case must be > qualified as "data race" and as a result "the behavior of the program > is undefined". Interesting, although I don't think I accept your proof, at least as stated. However it is highly refreshing to have someone post a question about a C++ related issue to this newsgroup rather than the perpetual stream of religious postings: we seem to have about 10 off-topic (religious orientated, atheist orientated, science fiction related or other ancillary nonsense) for every on-topic post at present, so thank you. According to the standard: "The execution of a program contains a data race if it contains two potentially concurrent conflicting actions, at least one of which is not atomic, and neither happens before the other, except for the special case for signal handlers described below". and "Two expression evaluations conflict if one of them modifies a memory location (4.4) and the other one reads or modifies the same memory location." There is nothing wrong with having a buffer comprising an array of non-atomic ints (or of non-atomic anything else) protected by some form of synchronization such as a mutex or semaphore, including some custom semaphore you have created yourself from memory barriers, atomic values and spinlocks. The question to be asked is whether there is some synchronization which prevents any non-atomic memory location being modified concurrently with a read or another write. What you might be thinking of is avoiding spinlocks on values which are atomic at the hardware level and doing what we used to do in the old (pre-C++11 memory model) days and use volatile built-in types (say, ints) which you know to be atomic at the hardware level, supplemented as necessary by fences to ensure visibility on your platform. But if you can do that you can achieve the identical effect with atomic ints with relaxed memory ordering (including relaxed memory ordering with an external memory barrier - there is a use for that). You can even (I think) have a std::array of std::atomic ints or a std::atomic of std::array of ints with relaxed memory ordering. (In the case of an std::atomic array of ints you must ensure you have relaxed memory ordering set for it, otherwise the implementation will insert a mutex to protect the array, which you don't want). In other words, I think that anything you can do with volatile integer types with additional fences can be done identically with a std::atomic integer types with relaxed memory ordering and additional fences. |
| michael.podolsky.rrr@gmail.com: Jan 10 10:11AM -0800 On Thursday, January 10, 2019 at 11:35:54 AM UTC-5, Chris Vine wrote: > and spinlocks. The question to be asked is whether there is some > synchronization which prevents any non-atomic memory location being > modified concurrently with a read or another write. I agree with all that you said above. But that is out of the context of my original post which discusses an algorithm which simply does not need to "protect" an access to non-atomic data with the standard synchronization primitives and achieves the correctness by the very different means. > (pre-C++11 memory model) days and use volatile built-in types (say, > ints) which you know to be atomic at the hardware level, supplemented > as necessary by fences to ensure visibility on your platform. Well, I don't see if this is related to my post either. I don't care in my algorithm about spinlocks and if I cared, I would not have a problem to make a spinlock around a C++11 atomic data. > In other words, I think that anything you can do with volatile integer > types with additional fences can be done identically with a std::atomic > integer types with relaxed memory ordering and additional fences. Well... It is true I could implement "my" algorithm (known commonly as "seqlock") by defining my data buffer as an array of atomic types, say atomic<int> or atomic<char> then accessing it with memory_order_relaxed. But 1. the point is the standard does no give me any guarantee such an access have the same effectiveness as an access to non-atomic memory. 2. Also, I cannot use strcpy() or sprintf() to write into my buffer. 3. Also, if my buffer is structured, say, has a format struct Buffer { std::atomic<int> a; std::atomic<double> ddd; } then access to the "ddd" may demand either mutex/spinlock or "bus locked" operation even for memory_order_relaxed model (surprise?) just to guarantee the atomicity. So, there is no a reasonable and effective implementation here. And the cause is our buffer is simply NOT atomic by the algorithm design and that we need to make it atomic is the result of C++ memory mode limitations. As for using std::atomic<std::array<int,1000>>, this is simply extremelly non-effective, causes massive memory copying and sychronozation (mutex/spinlock) and cannot be considered as a resolution candidate at all. |
| michael.podolsky.rrr@gmail.com: Jan 10 10:34AM -0800 > If I am not mistaken, I am going to show that there is a class of concurrent algorithms which are incompatible with C++ memory model. Replying to myself as a sort of continuation. Interestingly, I found an article "Can Seqlocks Get Along with Programming Language Memory Models?" by Hans-J. Boehm http://www.hpl.hp.com/techreports/2012/HPL-2012-68.pdf For what I could see, Boehm does not exactly consider the problem I raised here (so, his attitude and a range of discussed issues is rather different), yet it still worth reading for those interested in the topics discussed here. |
| Chris Vine <chris@cvine--nospam--.freeserve.co.uk>: Jan 10 06:46PM On Thu, 10 Jan 2019 10:11:30 -0800 (PST) > to "protect" an access to non-atomic data with the standard > synchronization primitives and achieves the correctness by the very > different means. I was covering my bases. Your "Now, of course we do not need our buffer to be an array of atomic memory cells, our protocol looks to care well about all the possible conflicts and simultaneous access to the buffer memory" seemed to involve some synchronization "protocol" which obviated the need for atomics. > Well, I don't see if this is related to my post either. I don't care > in my algorithm about spinlocks and if I cared, I would not have a > problem to make a spinlock around a C++11 atomic data. See above. > But > 1. the point is the standard does no give me any guarantee such an access > have the same effectiveness as an access to non-atomic memory. The standard provides no guarantee about volatile either as regards threads, which is your only alternative if you have no mutual exclusion and/or semaphores and/or spinlocks and don't trust std::atomic. However, for built-in types which on the particular platform in question are atomic at the hardware level, relaxed memory ordering will involve no synchronization operations in practice. Would it be nice to have something requiring that in the standard instead of being left as a quality of implementation issue? Yes, I think it would. > 2. Also, I cannot use strcpy() or sprintf() to write into my buffer. True. > then access to the "ddd" may demand either mutex/spinlock or "bus locked" > operation even for memory_order_relaxed model (surprise?) just to > guarantee the atomicity. Yes it might, but what alternative is there? > non-effective, causes massive memory copying and sychronozation > (mutex/spinlock) and cannot be considered as a resolution candidate at > all. Memory copying is something completely orthogonal to your original posting so I don't really understand what your point here is. (Copying an array would almost certainly require some explicit locking anyway). In any event you could use plain arrays and rely on pointer decay to avoid copying if you want to pass by pointer. Possibly also an array of std::atomic<int> would suit you better than an atomic array of int. But as I say I don't understand your point here. However, the overarching issue is that an array of volatile ints will have the same advantages and disadvantages as an array of std::atomic<int> with relaxed memory ordering, save that the first is not standard conforming (but works) and the second is standard conforming and also works. The code emitted will be identical. |
| Michael Powell <mwpowellhtx@gmail.com>: Jan 10 10:39AM -0800 Hello, I've got an AST I am developing to support JSON parsing using the latest VC++ (15.9.5), however, I am having difficulty persuading the compiler with my forward declarations. i.e. 1>d:\dev\boost.org\boost_1_69_0\boost\mpl\sizeof.hpp(27): error C2027: use of undefined type 'kingdom::json::object_t' In terms of JSON AST modeling, the rub appears to be in a couple of places: defining the JSON AST Array, and making the JSON AST Object available to Value. Re: semantic terminology, Value is interchangeable with Element, in view of the JSON grammar. Here's my attempt at a flattened single source example: https://wandbox.org/permlink/83c3VXZ4W1DHoEBc I seem to recall there being future issues with C++ forward declarations, but this seems to be like a bad language design decision to restrict this, especially in light of this kind of approach. I'm not sure how better to sort this out. At minimum, at least Value needs a forward declaration depending on how I arrange my headers, includes, etc. But then I still run into Value forward declaration undefined type issues. I'm not sure it's as much a language issue as much as it is possible a Boost.Variant issue, per se. Suggestions? Thanks! Michael Powell |
| Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Jan 10 06:43PM On 10/01/2019 18:39, Michael Powell wrote: > I'm not sure how better to sort this out. At minimum, at least Value needs a forward declaration depending on how I arrange my headers, includes, etc. But then I still run into Value forward declaration undefined type issues. > I'm not sure it's as much a language issue as much as it is possible a Boost.Variant issue, per se. > Suggestions? There are plenty of pre-existing C++ JSON libraries out there so why are you writing your own? Even I have written one which is implemented in terms of std::variant: https://github.com/i42output/neolib/blob/master/include/neolib/json.hpp /Flibble -- "You won't burn in hell. But be nice anyway." – Ricky Gervais "I see Atheists are fighting and killing each other again, over who doesn't believe in any God the most. Oh, no..wait.. that never happens." – Ricky Gervais "Suppose it's all true, and you walk up to the pearly gates, and are confronted by God," Bryne asked on his show The Meaning of Life. "What will Stephen Fry say to him, her, or it?" "I'd say, bone cancer in children? What's that about?" Fry replied. "How dare you? How dare you create a world to which there is such misery that is not our fault. It's not right, it's utterly, utterly evil." "Why should I respect a capricious, mean-minded, stupid God who creates a world that is so full of injustice and pain. That's what I would say." |
| "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Jan 09 04:34PM -0800 On 1/9/2019 3:17 PM, Kenny McCormack wrote: > Since New Years 2019 has come and gone, I assume you meant to write New > Years 2020. > At least... New Years Eve 2019? Sorry. |
| "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Jan 09 05:54PM -0800 On 1/9/2019 2:19 PM, Chris M. Thomasson wrote: >> If we go by >> Jewish tradition, a boy is considered a man at age 13. > 13 is just too artificial. Arbitrary in the sense that it is set by man. Think if a 13 year old got kicked in the head my a mule? Well, it might be a bit scrambled. This kid acts out because of trauma. Well, God knows exactly what happened, and is totally 100% fair. [...] unless you ask |
| "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Jan 09 02:19PM -0800 On 1/9/2019 1:59 PM, Rick C. Hodgin wrote: > On Wednesday, January 9, 2019 at 4:24:47 PM UTC-5, Chris M. Thomasson wrote: >> What is the age of accountability? > I don't know. I think it varies by individual. Agreed. Imvho, God is the only one who knows the _true_ age of accountability for any one _individual_. > If we go by > Jewish tradition, a boy is considered a man at age 13. 13 is just too artificial. Arbitrary in the sense that it is set by man. > cut down and taken out. And for a living soul... it means a > little different thing than a software app ... unless you ask > the people of Tron. Humm... I did like the original Tron. |
| "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Jan 09 06:10PM -0800 On 1/9/2019 2:19 PM, Chris M. Thomasson wrote: >> I don't know. I think it varies by individual. > Agreed. Imvho, God is the only one who knows the _true_ age of > accountability for any one _individual_. [...] > Humm... I did like the original Tron. Ahhh, I still do like the original Tron. ;^) |
| Neil Cerutti <neilc@norwich.edu>: Jan 09 07:29PM > willing to bet your soul on that? Or wouldn't you rather > change tactics and keep quiet about your religion, and so stop > making things worse for yourself and everyone else? The actual outcome of an action is inadmissable evidence in any Christian ethical system (cf. Bertrand Russell). -- Neil Cerutti |
| gazelle@shell.xmission.com (Kenny McCormack): Jan 09 07:39PM In article <79f4e5e0-7d71-41db-b9e4-5d7ade28a238@googlegroups.com>, Rick C. Hodgin <rick.c.hodgin@gmail.com> wrote: ... >I advise you to get on your knees and suck my cock. Just like a mob boss. Do what I say or suffer the consequences. -- The randomly chosen signature file that would have appeared here is more than 4 lines long. As such, it violates one or more Usenet RFCs. In order to remain in compliance with said RFCs, the actual sig can be found at the following URL: http://user.xmission.com/~gazelle/Sigs/Voltaire |
| "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Jan 09 01:01PM -0800 On 1/8/2019 4:38 PM, Kenny McCormack wrote: >>> What about my friends, Stan, Kyle and Eric? Are you praying for them, too? >> LOL! > Thank you! Glad to see that someone is following along at home... I wonder if Rick knows that you have actually visited the afterlife many times. Too many times. Poor Kenny. ;^) |
| "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Jan 09 01:24PM -0800 On 1/9/2019 3:40 AM, Rick C. Hodgin wrote: >> IF... > Original sin is real. We are born into this world without the spirit > nature, being already dead in sin, condemned to eternal Hellfire. What is the age of accountability? Kids younger than that age, get a "free" pass into Heaven, right? [...] |
| "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Jan 09 01:22PM -0800 On 1/9/2019 7:40 AM, fir wrote: >> and not just in people, but also in God and in the Bible. >> It would be to your better end, Kenny. It would serve you well. > end it moron, too much bandwidth wasted I am wondering, if CAlive is being neglected? I implore Rick to really try to reach the beta or even alpha test by New Years 2019. If Rick finds the time to include C11 threading, atomics and membars. Well, I will definitely try to use it! Will help him test it anyway, but if it has full blown C11, I will actually use it. I really am looking forward to test driving CAlive. No joke. |
| "Chris M. Thomasson" <invalid_chris_thomasson@invalid.invalid>: Jan 09 02:14PM -0800 On 1/9/2019 1:51 PM, Rick C. Hodgin wrote: > the back burner during that time. > In addition, CAlive won't run on Windows or Linux when it's first > released. It will run on my own OS, called ES/2, an OS/2 clone. Can't you port it to Windows or Linux? Not sure if I want to install a brand new OS. Well, perhaps in a virtual machine. |
| gazelle@shell.xmission.com (Kenny McCormack): Jan 09 11:17PM In article <q15olt$fna$1@dont-email.me>, Chris M. Thomasson <invalid_chris_thomasson@invalid.invalid> wrote: ... >I am wondering, if CAlive is being neglected? I implore Rick to really >try to reach the beta or even alpha test by New Years 2019. If Rick Since New Years 2019 has come and gone, I assume you meant to write New Years 2020. At least... -- It's possible that leasing office space to a Starbucks is a greater liability in today's GOP than is hitting your mother on the head with a hammer. |
| "Rick C. Hodgin" <rick.c.hodgin@gmail.com>: Jan 10 07:22AM -0800 On Wednesday, January 9, 2019 at 9:10:56 PM UTC-5, Chris M. Thomasson wrote: > On 1/9/2019 2:19 PM, Chris M. Thomasson wrote: > > Humm... I did like the original Tron. > Ahhh, I still do like the original Tron. ;^) Me too. My son's a teenager now, so I just had the opportunity to watch it with him recently. He thinks the "old school" graphics are cheesy. I try to explain to him, "Boy, it's all we had back then, and it was cutting edge. What do you think your kids will say about you and having to type or speak queries to Google, what with their thought monitoring software?" Hadn't seen Tron in maybe 20 years. Interesting concept. -- Rick C. Hodgin |
| David Brown <david.brown@hesbynett.no>: Jan 10 06:16PM +0100 On 08/01/19 22:13, Rick C. Hodgin wrote: > I have turned my back on David because of his treatment of me over > years. I still pray for him, as I do for you, Leigh. Your name is > often heard in my prayers, along with many others from these forums. And you have been told many times that I do not want your "prayers". It is this kind of personal abuse that annoys people - and makes sure that nobody ever wants to be the kind of fanatic that you are. |
| David Brown <david.brown@hesbynett.no>: Jan 10 06:19PM +0100 On 09/01/19 20:29, Neil Cerutti wrote: >> making things worse for yourself and everyone else? > The actual outcome of an action is inadmissable evidence in any > Christian ethical system (cf. Bertrand Russell). Roughly speaking, "The end justifies the means" is not good ethics? That seems reasonable. In Rick's case, the "means" are unethical, and the "ends" a complete failure, so he fails on both accounts. |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment