- fwiw, and experimental lock-free insert lifo... - 2 Updates
- Vector is guaranteed to store all elements in contiguous locations? - 11 Updates
- Which exception for a buffer overrun? - 1 Update
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Oct 20 03:40PM -0700 Fwiw, this is just a little experiment. I got some free time and decided to go back into lock-free a bit. This code, in Relacy: https://github.com/dvyukov/relacy is basically C++11 so its easy to convert to a standalone C++11 program. I like to code up in Relacy to run things through its race detector. Anyway, this early stage does not use any locks to insert new nodes into random places within a LIFO. However, it does not destroy any nodes during the test. The fun part is that I can add lock-free delete using something like RCU, or a proxy collector in pure C++11 to allow for safe and dynamic deallocation of nodes. The meat is in struct ct_strange_stack. Humm... I think I might be able to get rid of one of the acquire membars in: ct_strange_stack::iterate ct_strange_stack::find_random_node ct_strange_stack::dump Humm... Anyway, here is the code: ________________________________________ /* Lock-Free Insert Experiment by: Chris M. Thomasson _____________________________________________________*/ //#define RL_DEBUGBREAK_ON_ASSERT //#define RL_MSVC_OUTPUT //#define RL_FORCE_SEQ_CST //#define RL_GC #include <relacy/relacy_std.hpp> #include <iostream> #include <vector> #include <algorithm> #define CT_READERS 4 #define CT_WRITERS 3 #define CT_THREADS (CT_WRITERS + CT_READERS) struct ct_strange_stack { struct node { std::atomic<node*> m_next; }; std::atomic<node*> m_head; ct_strange_stack() : m_head(nullptr) {} ~ct_strange_stack() { dump(); // finally, deallocate... ;^) } void push_head(node* n) { push_node(m_head, n); } void push_node(std::atomic<node*>& head, node* n) { node* cmp = m_head.load(std::memory_order_relaxed); do { n->m_next.store(cmp, std::memory_order_relaxed); } while (!m_head.compare_exchange_weak( cmp, n, std::memory_order_release )); } void iterate() { node* head = m_head.load(std::memory_order_acquire); while (head) { node* next = head->m_next.load(std::memory_order_acquire); rl::yield(1, $); head = next; } } node* find_random_node() { node* head = m_head.load(std::memory_order_acquire); while (head) { node* next = head->m_next.load(std::memory_order_acquire); unsigned long humm = rl::rand(2); if (humm == 1) { return head; } head = next; } return nullptr; } void dump() { node* head = m_head.exchange(nullptr, std::memory_order_acquire); while (head) { node* next = head->m_next.load(std::memory_order_acquire); delete head; head = next; } } }; struct ct_experiment : rl::test_suite<ct_experiment, CT_THREADS> { ct_strange_stack g_stack; // reader void reader(unsigned int tidx) { g_stack.iterate(); } // writer void writer(unsigned int tidx) { for (unsigned long i = 0; i < 3; ++i) { ct_strange_stack::node* n = new ct_strange_stack::node(); g_stack.push_head(n); } unsigned long i = 3; ct_strange_stack::node* n = nullptr; while ((n = g_stack.find_random_node()) && --i != 0) { // insert a node wrt n ct_strange_stack::node* new_node = new ct_strange_stack::node(); g_stack.push_node(n->m_next, new_node); } } void thread(unsigned int tidx) { if (tidx < CT_WRITERS) { writer(tidx); } else { reader(tidx); } } }; // Test away... Or fly? Humm... int main() { { rl::test_params p; p.iteration_count = 10000000; //p.execution_depth_limit = 33333; //p.search_type = rl::sched_bound; //p.search_type = rl::fair_full_search_scheduler_type; //p.search_type = rl::fair_context_bound_scheduler_type; rl::simulate<ct_experiment>(p); } return 0; } ________________________________________ |
| "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>: Oct 20 03:54PM -0700 On 10/20/2019 3:40 PM, Chris M. Thomasson wrote: > ct_strange_stack::dump > Humm... Anyway, here is the code: > ________________________________________ [...] > ________________________________________ Humm... This reminds me of a trick I can use when getting around to deleting arbitrary nodes: https://groups.google.com/d/topic/lock-free/X3fuuXknQF0/discussion https://pastebin.com/raw/TgTcfYtR |
| Soviet_Mario <SovietMario@CCCP.MIR>: Oct 20 01:24AM +0200 On 19/10/2019 17:02, Paavo Helde wrote: >> "sparse", or not ? > I was comparing std::string to std::vector<char>, not to > std::vector<std::string>. oh ! Now I got the point. I had always taken for granted that the "content" (of a std::string) could not be broken in slices spread over and linked somewhat. for vector<char> I did not know, but later I read the same features stated here in the 3D > character data of all those strings were contiguous or even > in order in memory, typically they would be all scattered > around. Okay. It seemed a too memory restrictive approach > character data of the string. So the character arrays of two > different strings cannot be contiguous, there must be at > least one zero byte between them. ah, nice ! So inkoking c_str() does not imply any copying ! Faster, for sure. in Basic (gambas) passing strings to C routines alas implies copying (as a basic string is zero-indifferent and stores pointer and size). -- 1) Resistere, resistere, resistere. 2) Se tutti pagano le tasse, le tasse le pagano tutti Soviet_Mario - (aka Gatto_Vizzato) |
| Paavo Helde <myfirstname@osa.pri.ee>: Oct 20 10:29AM +0300 On 20.10.2019 2:24, Soviet_Mario wrote: > ah, nice ! So inkoking c_str() does not imply any copying ! Faster, for > sure. Yes, see e.g. "https://en.cppreference.com/w/cpp/string/basic_string/c_str": "c_str() and data() perform the same function. (since C++11)" Initially the language designers wanted to leave room for clever optimizations where c_str() indeed might have involved some copying and zero terminator appending, but this did not quite work out. The rules about when iterators and pointers might get invalidated were getting unwieldy and with the raise of multithreading era optimizations like COW started to appear more like pessimizations, so in C++11 they decided to go the other way, making the invalidation rules simple and unsurprising. The main change was the requirement that no call of operator[]() may invalidate any iterators, references and pointers obtained earlier via e.g. data() or c_str(). This effectively restricted any possible basic_string implementations to always use a simple unshared contiguous zero-terminated character array. And thus data() and c_str() became the same noexcept trivial operations. One can argue that the interface of basic_string is just too broad and diffuse to allow for certain kind of optimizations like discontiguous data buffers. There is a non-standard extension std::rope provided by some implementations to solve such issues, but this is not in the official C++ standard (I guess it's considered too specialized). |
| "Öö Tiib" <ootiib@hot.ee>: Oct 20 02:30AM -0700 On Sunday, 20 October 2019 10:29:44 UTC+3, Paavo Helde wrote: > data buffers. There is a non-standard extension std::rope provided by > some implementations to solve such issues, but this is not in the > official C++ standard (I guess it's considered too specialized). AFAIK the rope was in STL of SGI (but was not in STL of HP) already before C++ standardization. It wasn't incorporated into C++ standard library. Both the name "STL" and usage of "std" namespace by those libraries has caused confusion forever. With boost it is lot easier, the differences for example between boost::unordered_set and std::unordered_set are lot simpler to discuss than the differences between "std::"hash_set of SGI STL and std::unordered_set. |
| Melzzzzz <Melzzzzz@zzzzz.com>: Oct 20 10:45AM > AFAIK the rope was in STL of SGI (but was not in STL of HP) already > before C++ standardization. It wasn't incorporated into C++ standard > library. Why? What was said against it? -- press any key to continue or any other to quit... U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi bili naoruzani. -- Mladen Gogala |
| "Öö Tiib" <ootiib@hot.ee>: Oct 20 11:32AM -0700 On Sunday, 20 October 2019 13:46:01 UTC+3, Melzzzzz wrote: > > before C++ standardization. It wasn't incorporated into C++ standard > > library. > Why? What was said against it? I have not seen any relevant WG21 discussion notes on strings and ropes. The templates themselves were quite revolutionary back then and so heavily opposed. The EC++ for example kicked templates out despite it is clear how good are templates in embedded development. Committee's focus was on standardizing what was most urgently needed and most ready to ship. Anyway some weak things slipped in (like valarray or vector<bool>) but overall it was great that C++ got standardized with library. |
| Melzzzzz <Melzzzzz@zzzzz.com>: Oct 20 06:44PM > The templates themselves were quite revolutionary back then and so heavily > opposed. The EC++ for example kicked templates out despite it is clear how > good are templates in embedded development. In that time embedded computers where really limiting, so no wander. Now embedded devices have 512MB+... Committee's focus was on standardizing what was most urgently needed and most ready > to ship. Anyway some weak things slipped in (like valarray or > vector<bool>) but overall it was great that C++ got standardized with > library. So how we got queue and deque but not rope? Strange.... -- press any key to continue or any other to quit... U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi bili naoruzani. -- Mladen Gogala |
| "Öö Tiib" <ootiib@hot.ee>: Oct 20 01:24PM -0700 On Sunday, 20 October 2019 21:45:02 UTC+3, Melzzzzz wrote: > > good are templates in embedded development. > In that time embedded computers where really limiting, so no wander. Now > embedded devices have 512MB+... So what? I think the primary issue with opponents was (and still is) that they consider templates something space consuming and inefficient. Something with shortcomings of containers of Simula or Smalltalk or with generics of Ada. However that is not the case. Templates of C++ tend let compilers to generate as time- and space-efficient code as best specialist will do by hand. > > vector<bool>) but overall it was great that C++ got standardized with > > library. > So how we got queue and deque but not rope? Strange.... Back then it felt good that we at least got more-or-less passable standard string. Otherwise each library had its own astring, bstring, cstring, ... qstring ... wxstring. . |
| Paavo Helde <myfirstname@osa.pri.ee>: Oct 20 11:33PM +0300 On 20.10.2019 21:44, Melzzzzz wrote: >> good are templates in embedded development. > In that time embedded computers where really limiting, so no wander. Now > embedded devices have 512MB+... Templates take a lot of resources only in the compiler, not in the target environment. It is true that one can instantiate a template for 10 different types and get 10x code size with bad optimizers, but if the embedded developers do not realize how many different templates they instantiate they do not deserve their paychecks. >> vector<bool>) but overall it was great that C++ got standardized with >> library. > So how we got queue and deque but not rope? Strange.... Deque is a very fine container, compared to some other like list which only got standardized because of their name while having almost no usage cases. |
| Melzzzzz <Melzzzzz@zzzzz.com>: Oct 20 09:16PM > with generics of Ada. However that is not the case. Templates of > C++ tend let compilers to generate as time- and space-efficient code > as best specialist will do by hand. I think that primary reason for ditching templates is that "write once get errors everywhere" was main problem with them. > Back then it felt good that we at least got more-or-less > passable standard string. Otherwise each library had its own astring, > bstring, cstring, ... qstring ... wxstring. Yeah, that's really annoying, having to use this string with that library.... -- press any key to continue or any other to quit... U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi bili naoruzani. -- Mladen Gogala |
| Melzzzzz <Melzzzzz@zzzzz.com>: Oct 20 09:18PM > and get 10x code size with bad optimizers, but if the embedded > developers do not realize how many different templates they instantiate > they do not deserve their paychecks. This is case now. Not when EC++ was postulated. Other thing is that exceptions were also out of question... -- press any key to continue or any other to quit... U ničemu ja ne uživam kao u svom statusu INVALIDA -- Zli Zec Na divljem zapadu i nije bilo tako puno nasilja, upravo zato jer su svi bili naoruzani. -- Mladen Gogala |
| David Brown <david.brown@hesbynett.no>: Oct 21 12:21AM +0200 On 20/10/2019 23:18, Melzzzzz wrote: >>> embedded devices have 512MB+... >> Templates take a lot of resources only in the compiler, not in the >> target environment. There are many things about EC++ that made no sense at all. It also banned namespaces - which take no resources on the target, and negligible resources on the compiler end. It is not a surprise that it never really caught on, and is now completely dead. >> and get 10x code size with bad optimizers, but if the embedded >> developers do not realize how many different templates they instantiate >> they do not deserve their paychecks. Modern tools will often reduce this extra code by combining identical functions - though this was not the case when EC++ was thrown together. > This is case now. Not when EC++ was postulated. Other thing is that > exceptions were also out of question... EC++ banned exceptions, and also multiple inheritance - many modern C++ standards (especially for embedded programming) do that. There are arguments for and against this (unlike many of EC++'s restrictions, for which there are no good justifications). |
| Jorgen Grahn <grahn+nntp@snipabacken.se>: Oct 20 10:18PM On Wed, 2019-10-16, Öö Tiib wrote: > exceptions to report errors presumably detectable before the > program executes, such as violations of logical preconditions > or class invariants." I.e. bugs. > Seems they assume that something can detect coherency of all > input data before program is ran. But there is no such thing. The way I read this thread (after snipping, reconstruction and a weekend) std::logic_error is for bugs, and std::stoi() misuses it. And that's also what you argue. Right? > No, you snipped it. ;) You wanted to see only first sentence and > not to read the context. See: >> [snip] Sorry. What happened was I was too tired to read it all (and to read the std::stoi documentation), but not too tired to read the sentence I commented on and believed that, seen in isolation, I didn't agree with it. So I complained about that isolated part, added the disclaimer, and snipped because I didn't want to imply I had read all of it. > input is coming from corrupt input data? Also for preventing > the inconsistency its caller has possibly to do most of what > stoi does itself." Ok, so std::stoi() is new with C++11, tries to grab an int from a string, and (among other things) throws std::out_of_range if the string's number doesn't fit in an int. That does seem a bit useless. > whose contents I know before program run into ints run-time > using std::stoi feels even worse logic error. I can instead > write those ints directly into code. I agree. I haven't used std::stoi, but I imagine if I /did/ use it I would have to guard individual calls in try...catch, which to me misses the point with exceptions. /Jorgen -- // Jorgen Grahn <grahn@ Oo o. . . \X/ snipabacken.se> O o . |
| 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