- Why does vector::reserve() not grow exponentially ? - 13 Updates
| Paavo Helde <myfirstname@osa.pri.ee>: Jun 19 11:21AM +0300 19.06.2021 00:41 Sam kirjutas: > that are quite rare, but the end result is still a fugly shared_ptr. The > problems with shared_ptr are fundamental, and are beyond the reach of > fancy constructors and factories. I believe shared_ptr is fine for what it was meant - a generally usable thread-safe smart pointer suitable for general use. It's true that for more specialized use cases one still needs to use custom solutions. That's the same as for iostreams, or for strtod() for that matter. For me, the biggest drawback of std::shared_ptr is that it is multithread-safe. This means that it has to contain some thread synchronization, however lightweight it is. With modern hardware, I can have tens of threads running in full speed in parallel, if they each attempt to synchronize with each other, thousands of times per second, this is bound to have an impact. Compared with the expense of that, the amount of pointers (1 or 2), even the number of dynamic allocations (1 or 2) pale in comparison (the dynamic allocations happen much more rarely then refcount updates). So in our codebase there is a custom non-synchronized smart-pointer used for all the "data" classes (as opposed to "entity" classes). And you were right, it is based on intrusive refcounting in a super root class, just because all of the code is under our control anyway. As it it not thread-safe, it requires extra care needs to be taken that no such pointer is ever accessed from multiple threads at the same time. For passing data to another thread deep copies are needed, etc. The committee voted against of having a non-synchronized smartpointer class in the standard, in the fear this could easily cause subtle bugs which are hard to debug. And guess what? They were right! Over the years I have needed to fix several such bugs in my own code. I remember times when the bug just refused to express itself on my 4-core machine and I needed to find another 8-core machine and run the program for hours, to just trigger it. So if I would sit on the committee, I would also vote against having such thing in the standard. C++ is already hard to use and full of gotchas even without it. And to be honest, considering it now should be classified as a slowish "safe easily usable class", there is really nothing wrong in adding an extra pointer or an extra allocation for making it even more easily usable. TLDR; I agree with your criticism against std::shared_ptr, but on the other hand I believe its current design was and is the best one to standardize. |
| "Öö Tiib" <ootiib@hot.ee>: Jun 19 02:53AM -0700 > macro language, which helps. But the most basic thing is to have types to map > into, types that are agreeable to both the library author and library user, > standard types. I've lately found that Flatbuffers is great. Other JSONs are bad in schema validation. All CBORs, BSONs and ASN.1s are slower as binary or unwieldy in embedded. Flatbuffers parses and generates json passably, generates code, has nice schema, has some support to RPC, is documented and tooled close to perfectly. I don't think that other languages have better support to something like Flatbuffers so I don't see how we are losing. The translation layer between C++ classes (like std::unordered_map, boost::intrusive::set or boost::base_collection) and those flat buffers is orthogonal to communication level. I *want* it to be separate and loosely coupled. |
| David Brown <david.brown@hesbynett.no>: Jun 19 12:32PM +0200 On 19/06/2021 00:01, Sam wrote: > Since the end result of make_shared must be a 100% compatible, stock > shared_ptr you still end up having to carry two pointers on your back > instead of one, for no good reason. There /is/ a good reason - you just gave it! Ask yourself about the cost of having a second pointer here (assuming a modern 64-bit multi-core processor - the kind you are likely to be using when you have shared pointers). When the pointers are widely separate, it means two potential cache misses or other memory costs (lines in another core's cache, etc.). When they are tightly together - as they are after "make_shared" - they will probably be fetched together by cache and memory readahead. This means you only have /one/ big memory cost you might have to pay. Each cache miss can be several hundred times the cost of a pointer access when there is a cache hit. Having a second pointer will be an immeasurably small effect in real use of shared pointers, as long as it is tied closely to the real data. It is certainly possible to make intrusive shared pointer systems (where the shared pointer control data is attached directly to the object), but that means working with a new kind of object, not compatible with your original one. If you are doing something where maximal efficiency justifies the effort, you would want to create such a specialised structure. But for many cases, share_ptr gives you a simple, reliable and efficient way of sharing data. > is how Java does objects, and C++ can benefit from learning a few things > from Java (including non-broken exception-correctness that's enforced at > compile time, but I digress). There is no one right answer that is always for all cases. But there is a huge difference between saying "I think /this/ way would be better for how I want to write my code" and "It's a completely worthless pile of junk." |
| "Öö Tiib" <ootiib@hot.ee>: Jun 19 03:33AM -0700 On Saturday, 19 June 2021 at 01:01:38 UTC+3, Sam wrote: > throws an exception). > Now you can enforce, at compile-time, a non-null smart pointer. > The current shared_ptr is a mess, and is beyond repair. Good analysis. I would happily add weak_ptr and shared_from_this to the painful mess. On one hand user of it feels inconvenient like MacGyver using Swiss Army Knife for all works and on other hand it is really efficient for nothing in particular. But ... lets try to be constructive. ;-) What can be better? |
| Sam <sam@email-scan.com>: Jun 19 09:08AM -0400 Paavo Helde writes: > For me, the biggest drawback of std::shared_ptr is that it is multithread- > safe. This means that it has to contain some thread synchronization, however The thread synchronization should be nothing beyond keeping the reference counter as a std::atomic object. Nothing more should be needed, for 99% of the use cases. Some kind of locking is needed to support weak references, that's the only situation where actual locking is needed. But, for garden-variety smart pointers, an atomic counter is all that's needed whose overhead is quite negligible. > Compared with the expense of that, the amount of pointers (1 or 2), even the > number of dynamic allocations (1 or 2) pale in comparison (the dynamic > allocations happen much more rarely then refcount updates). Well the amount of pointers becomes a factor here not merely because of the smart pointer itself, but because of shared_ptr dumb design, of using two pointers instead of one. > all the "data" classes (as opposed to "entity" classes). And you were right, > it is based on intrusive refcounting in a super root class, just because all > of the code is under our control anyway. And if you make it atomic, you'll get thread safety. If you actually go ahead and try to measure the additional overhead, I'd be surprised if you'd be able to actually measure anything. |
| Sam <sam@email-scan.com>: Jun 19 09:12AM -0400 David Brown writes: > are after "make_shared" - they will probably be fetched together by > cache and memory readahead. This means you only have /one/ big memory > cost you might have to pay. You can't eliminate the fact that any kind of movement requires twice as much data to shuffle around. If your shared_ptr is constructed and spends its entire lifetime in one place, then I'll buy that argument. But that's rarely the use case. Smart pointers get copied, moved around, passed all over the place. And now that imposes twice as much penalty, because you have to move or copy two pointers intead of one. |
| David Brown <david.brown@hesbynett.no>: Jun 19 03:24PM +0200 On 19/06/2021 15:12, Sam wrote: > much data to shuffle around. > If your shared_ptr is constructed and spends its entire lifetime in one > place, then I'll buy that argument. But that's rarely the use case. Construction via make_shared is the normal case, not the rare case. > Smart pointers get copied, moved around, passed all over the place. > And now that imposes twice as much penalty, because you have to move or > copy two pointers intead of one. Each bit of code or data that is sharing a shared pointer needs to keep track of a pointer to the shared pointer control structure. This control structure is /not/ moved around or copied - the whole thing only works because every user of the shared pointer accesses the same control structure. It is the control structure that holds reference counters, pointers to destructors, pointers to the object itself, etc. It is designed precisely so that the bit that gets passed around or copied is just a single pointer. |
| Sam <sam@email-scan.com>: Jun 19 09:38AM -0400 Öö Tiib writes: > Good analysis. I would happily add weak_ptr and shared_from_this to the > painful mess. On one hand user of it feels inconvenient like MacGyver Yes, I forgot shared_from_this. Which goes away when you have an object super-root. Weak pointers are complicated, but its possible to confine their penalty to the actual construction of a weak pointer, recovery of a strong pointer from a weak one, and the destruction of the object (when its reference count goes to 0). Otherwise they are a non-factor. > using Swiss Army Knife for all works and on other hand it is really > efficient for nothing in particular. But ... lets try to be constructive. ;-) > What can be better? Your own. Roll your own. That's what I did, and I mostly described what I did here: https://www.libcxx.org/refobj.html |
| "Öö Tiib" <ootiib@hot.ee>: Jun 19 12:50PM -0700 On Saturday, 19 June 2021 at 16:38:44 UTC+3, Sam wrote: > > What can be better? > Your own. Roll your own. That's what I did, and I mostly described what I > did here: https://www.libcxx.org/refobj.html Hmm. It is trouble. I want intrusive ref counting and I want weak references. When I try then it always ends with something like what make_shared does, the only advantage being that I can keep those combined objects in array. Do you have reference to some published hint how to make it? |
| Paavo Helde <myfirstname@osa.pri.ee>: Jun 19 11:27PM +0300 19.06.2021 16:38 Sam kirjutas: >> painful mess. On one hand user of it feels inconvenient like MacGyver > Yes, I forgot shared_from_this. Which goes away when you have an object > super-root. shared_from_this is tricky because it can be easily invoked during the destruction or construction, but the result cannot be correct (as the most derived object does not exist). In C++11 they made it UB unfortunately, but in C++17 they came to their senses and are throwing an exception instead. Alas, this means yet some overhead. |
| Sam <sam@email-scan.com>: Jun 19 05:33PM -0400 David Brown writes: > > If your shared_ptr is constructed and spends its entire lifetime in one > > place, then I'll buy that argument. But that's rarely the use case. > Construction via make_shared is the normal case, not the rare case. You still end up with a shared_ptr consisting of two pointers. > control structure is /not/ moved around or copied - the whole thing only > works because every user of the shared pointer accesses the same control > structure. The shared_ptr itself gets moved around. This happens every time you pass the shared_ptr to a function by value or move it somewhere. Now you have two copy two pointers instead of one. |
| Sam <sam@email-scan.com>: Jun 19 05:46PM -0400 Öö Tiib writes: > When I try then it always ends with something like what make_shared does, > the only advantage being that I can keep those combined objects in array. > Do you have reference to some published hint how to make it? I don't have any white papers. The capsule summary is that the object super- root has an seconday, internal object attached to it the first time a weak pointer gets created. A weak pointer is effectively a regular strong reference-counting pointer to this object. Constructing another weak pointer just returns a reference to this object. So the weak pointer infrastructure itself is just reusing strong pointer infrastructure, to maintain itself. Then there's a big song-and-dance routine that happens whenever: 1) The reference count of the original object goes down to zero and the last remaining pointer wants to destroy it, and finds the weak metadata object that's attached to it. 2) When a weak pointer attempts to recover a reference to the strong object (the weak pointer's object maintains a raw pointer to the original object). The song-and-dance number involves some locking (the locking synchronizes the raw pointer), in order to work things out when there's a race condition with 1 and 2 happening at the same time (in different execution threads). The execution thread that ended up decrementing the original object's reference count to zero and sets its sight on destroying it will eventually reach one of two conclusions: A) Another execution thread recovered a strong reference to this object at the same time, so it's reference count is not zero any more. This execution thread quietly goes on on its own merry way without delete-ing the original object. B) "A" didn't happen, the object ends up getting delete-d as usual, nullifying its raw pointer from the weak medata object. The weak metadata object gets behind, any subsequent attempts to recover a strong reference from it will fail. And since the weak metadata object is itself a reference- counted object (strongly referenced by the individual weak pointers) when all those go away, the weak metadata object gets destroyed. And everyone lives happily ever after. Weak pointers only introduce a little bit of extra overhead when destroying an object with weak pointers, when they exist, and otherwise carry minimal costs. |
| Sam <sam@email-scan.com>: Jun 19 05:50PM -0400 Paavo Helde writes: > derived object does not exist). In C++11 they made it UB unfortunately, but > in C++17 they came to their senses and are throwing an exception instead. > Alas, this means yet some overhead. Yup. I worked out that issue independently in my implementaiton. I chose a compromise between UB and a thrown exception, and decided to abort() in this situation. Throwing an exception is too fugly, and, besides, I'm pretty sure that destructors are noexcept by default, these days. So, throwing an exception a destructor, at least, produces the same outcome. |
| 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