From -4787610615813489185 X-Google-Thread: f78e5,574518e5c7a60feb X-Google-Attributes: gidf78e5,public X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!news2.google.com!proxad.net!newsfeed.stueberl.de!peer-uk.news.demon.net!kibo.news.demon.net!news.demon.co.uk!demon!stump.algebra.com!devnull From: phalpern@halpernwightsoftware.org (Pablo Halpern) Newsgroups: comp.std.c++ Subject: Re: Revised Allocator Proposal Date: Tue, 9 Aug 2005 14:45:28 GMT Organization: EarthLink Inc. -- http://www.EarthLink.net Lines: 186 Sender: mail2news@demon.net Approved: fjh@cs.mu.oz.au (Fergus Henderson , moderator of comp.std.c++) Message-ID: <9pchf11o63qib8h56fap5g5445gjac5ce2@4ax.com> References: <7ibbe1hu4omoqsfibanas46idf9u6i5hjo@4ax.com> NNTP-Posting-Host: news.news.demon.net Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit X-Trace: news.demon.co.uk 1123598736 20865 158.152.254.254 (9 Aug 2005 14:45:36 GMT) X-Complaints-To: abuse@demon.net NNTP-Posting-Date: Tue, 9 Aug 2005 14:45:36 +0000 (UTC) X-Robomod: STUMP, ichudov@algebra.com (Igor Chudov) X-Virus-Scanned: amavisd-new at cs.mu.OZ.AU X-Path: comp-std-cpp-robomod!not-for-mail X-Received: (from fjh@localhost) by mulga.cs.mu.OZ.AU (8.12.10+Sun/8.12.9/Submit) id j79EjSxu000057; Wed, 10 Aug 2005 00:45:28 +1000 (EST) X-NNTP-Posting-Date: Tue, 09 Aug 2005 07:35:32 PDT X-Delivered-To: std-c++@ucar.edu X-Authentication-Warning: mulga.cs.mu.OZ.AU: fjh set sender to devnull@stump.algebra.com using -f X-Newsreader: Forte Agent 1.93/32.576 English (American) X-Newsgroups: comp.std.c++ Xref: g2news1.google.com comp.std.c++:1727 Howard Hinnant wrote: >In article , > Pablo Halpern wrote: > > >Given standard containers of type C, values c1 and c2: > >To exchange memory ownership you do: > >swap(c1, c2); > >To exchange values without exchanging memory ownership you do: > >{C tmp(c1); c1 = c2; c2 = tmp;} > >I don't think we need new names for these simple operations. If we want to do generic programming, then both operations must be named. swap_value is needed because only by using a named algorithm can one specialize the algorithm for specific types. For example, a type that does not use allocators could implement swap_value with the same efficiency (and no-throw guarantee) as swap_move (what you are calling simply swap). >And I >really don't think we want to change the observable semantics of either >one. And making either one act like the other would be changing >observable semantics. Specifically, if swap ceases to exchange memory >ownership, changes include: > >1. Exception safety goes from nothrow to basic, unless more memory is >thrown at the problem to create a strong guarantee. > >2. Outstanding iterators/pointers/references are now invalidated. > >3. For vector and string, there are observable differences via the >capacity() member (capacities are no longer exchanged). > >4. Performance goes from O(1) to O(N). > >5. Memory swell goes from 0 to N, or if we adopt the strong variant 2N. If, on the other hand, swap ceases to associate a container with the allocator that was used at construction then: 1. The purpose of associating a specific container with a specific allocator is undermined. The programmer cannot thoughtfully associate a container with an allocator and expect it to remain that way unless he studiously avoids passing a modifiable container to any function that he did not write himself. 2. The container could end up outliving its allocator. 3. Memory could be leaked because an arena allocator does not control all of the memory that it was thought to control. 4. Memory allocated with one allocator could accidentally, end up holding pointers to memory that was allocated with a different allocator, causing problems with, e.g. shared memory. >What we do need to do is add support for unequal allocators. If in >doing that, we can preserve the interface (with existing semantics) we >already have today, then I believe the programming community will be >better off for it. I believe it can be done. I tried, and ended up with the compromises you already mentioned (loss of the nothrow guarantee and a chance that swap would be O(N), etc.). When all allocators of a given type compare equal, then all three swap guarantees hold: O(1), nothrow, and no movement of allocators. Once they can be unequal, something has to give. Our core disagreement is over what should be given up by default. My point of view is that allocators are a heck of a lot more useful and theoretically consistent if we keep the no-movement guarantee -- so much so that I am willing to give up the other guarantees, knowing that careful use of swap could restore those guarantees in places where they are compromised. Your point of view (I'm sure you'll correct me if I'm mis-stating it) is that perserving the other two guarantees for existing code is paramount, even if one cannot fully control the life of the allocator (i.e., one cannot expect the allocator to remain unchanged when calling a function that one did not write and which makes no explicit guarantees). >> I'd be curious to know how you control when memory is returned from the >> arena allocator if the allocator can suddenly end up used by an >> unrelated object. Have you ever written an arena allocator that >> allocates from a stack buffer? > >Yes. Speaking not just about allocators and containers, but more >broadly, whenever I give a stack based pointer or reference to an >object, I am careful to note the relative lifetimes. I am careful when >I give an arena allocator to a container, and I am careful when I give a >stack-based rdbuf to a stream. Which means that you cannot call a function that might swap the containers either today or in a future revision. This works for small performance tweeks, but do we want to relegate allocators to small performance tweeks? Was it worth the complexity to add them in the first place? >> You seem to be dismissing the need to control allocator lifetime, > >Not at all. I understand that issue and have written much code to >ensure such lifetime issues are not violated. > >I am in sympathy with your motivations. But I believe we can achieve >some (not all) of your objectives with far smaller changes to the >std::lib. I'm sure there are things we could agree on. Are there any parts of my proposal that you would like to see adopted? >Specifically I believe we can seamlessly support non-equal arena >allocators, and with some restrictions, non-equal shared memory >allocators. Seamlessly support non-equal arena allocators? Please explain. Some restrictions on shared memory allocators? >I do not believe we can support a polymorphic default allocator, nor do >I believe we can reverse the decision made a decade ago that the choice >of allocator effects a container's type (I don't mean to imply that we >can't support user-defined polymorphic allocators). With careful use of swap(), one can keep all the needed guarantees, so lets move away from that issue for the moment. Let's also step away from the default allocator issue and talk about other aspects of the proposal. To make allocators more useful, I proposed: 1. That it be possible to explicitly specify an allocator on copy-construction and that a container indicate (via a trait) that it can be copy-constructed with an extra allocator argument. (Yes, I know that this is not technically copy-construction. I'm talking about intended effect -- which is to copy something while specifying the allocator for the copy.) 2. Taking advantage of the trait described above, that the allocator used for a container be shared with the elements of that container. 3. That containers with different TYPES of allocators be able to inter-operate, i.e., the type of the allocator does not always affect the type of the container. The last point requires polymorphic allocators. Unequal allocators assume a new dimention when the allocator in question is polymophic because, unlike the arena or "restricted shared memory" examples, the underlying allocation mechanism for each allocator can be fundamentally different. If the allocator for an object changes, then the object is not only allocating into a different region, it may be using an entirely different allocation mechanism. This so goes against the grain of what the programmer is trying to do, that it makes me wonder if polymorphic allocators are useful under that circumstance. To make them useful, I proposed a semantic for swap that would preserve a container's allocator state (and thus its allocator type, in the case of polymorphic allocators). For polymorphic allocators, at least, this has been fundamental to my use of allocators for some time. If we want to support polymorphic allocators, I ask that, at the very least, there be an allocator trait to indicate whether the allocator should be allowed to be swapped - thus determining the swap algorithm for a container instantiated with that allocator type. Traits let us support all of my proposal except the default polymorphic allocator without impinging on currently-expected behavior. Indeed, nothing would change for existing code. So, while I'm not sure you necessarily care about or support the rest of the proposal, would you agree that it is at least not horibly objectionable if we remove the polymorphic default allocator and made swap controlable by a trait? If we can get that far, then we can discuss whether the default allocator should be polymorphic. Pablo Halpern phalpern@halpernwightsoftware.com Author: The C++ Standard Library from Scratch http://www.halpernwightsoftware.com/stdlib-scratch --- [ comp.std.c++ is moderated. To submit articles, try just posting with ] [ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ] [ --- Please see the FAQ before posting. --- ] [ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]