From 2573157790149283652 X-Google-Thread: f78e5,574518e5c7a60feb X-Google-Attributes: gidf78e5,public X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!news4.google.com!news.glorb.com!border1.nntp.dca.giganews.com!border2.nntp.dca.giganews.com!nntp.giganews.com!nx02.iad01.newshosting.com!newshosting.com!newsfeed.icl.net!newsfeed.fjserv.net!peer-uk.news.demon.net!kibo.news.demon.net!news.demon.co.uk!demon!stump.algebra.com!devnull From: phalpern@halpernwightsoftware.com (Pablo Halpern) Newsgroups: comp.std.c++ Subject: Re: Revised Allocator Proposal Date: Wed, 17 Aug 2005 03:01:12 GMT Organization: EarthLink Inc. -- http://www.EarthLink.net Lines: 181 Sender: mail2news@demon.net Approved: fjh@cs.mu.oz.au (Fergus Henderson , moderator of comp.std.c++) Message-ID: References: <7ibbe1hu4omoqsfibanas46idf9u6i5hjo@4ax.com> <9pchf11o63qib8h56fap5g5445gjac5ce2@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 1124247690 195 158.152.254.254 (17 Aug 2005 03:01:30 GMT) X-Complaints-To: abuse@demon.net NNTP-Posting-Date: Wed, 17 Aug 2005 03:01:30 +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 j7H31CTm002064; Wed, 17 Aug 2005 13:01:12 +1000 (EST) X-NNTP-Posting-Date: Tue, 16 Aug 2005 06:34:29 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++:1828 hinnant@metrowerks.com (Howard Hinnant) wrote: >In article <9pchf11o63qib8h56fap5g5445gjac5ce2@4ax.com>, > phalpern@halpernwightsoftware.org (Pablo Halpern) wrote: > >> Howard Hinnant wrote: >> . > >swap_value may be a useful function. But I'm still wondering if it >needs to be standardized. And maybe swap_everything_but_the_allocator >would be a better name? I'll be glad to quibble about names when the main concepts are agreed to. . >I took a look at some of the std::algorithms that use swap, and I am not >convinced at all that a no-movement guarantee would be universally >useful. For example consider: > >typedef std::vector > Vec; >std::deque data; >.. >// populate data >.. >std::reverse(data.begin(), data.end()); > >Now ether the call to reverse is an O(N) process and the allocators have >been reversed as well as the T's. Or this is an O(N*M) process and the >T's have been reversed but the allocators haven't. > >Either way will work. Which is best? The first is (at least) M times >faster and consumes less memory. My proposal specifically mentions that certain standard algorithms (notably the sort algorithms) should use swap_object and should be documented as such. I think that needs to be broadened to include any aloghrithm that shifts objects within an iterator range. That would include most standard algorithms that use swap today. It is interesting to note that this particular use of swap has nothing to do with exception safety (since sort, reverse, etc work on objects that don't guarantee a nothrow or O(1) swap). >> >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? > >Simply that swap swaps allocators, nothing more. When arena allocators >are swapped, they swap arenas. In the deque reverse example above, >the last Vec would now reference the arena that the first Vec used to >and vice-versa. Then what you call support is really non-support. Just defining what happens does not make it good, it just makes your limitations explicit. This does not give us a means for associating an allocator with an object and being sure that the allocator does not move. (You do partially address this issue below...) >> 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.) > >What's wrong with this existing constructor? > >template > container(InputIterator first, InputIterator last, > const Allocator& = Allocator()); Doesn't work well inside of templates. Some objects may use allocators but not use iterators. A vector cannot share its allocator with an object of type X unless it knows (at compile time) how to construct a copy of an X using a specific allocator. The extra constructor and the trait that indicates the presence of that constructor let's a container share its allocator with any class designed to support this idiom. > >> 2. Taking advantage of the trait described above, that the allocator >> used for a container be shared with the elements of that container. > >What's wrong with? > >typedef vector > Vec; >deque > data; This shares the TYPE of allocator with elemements, but not the allocator INSTANCE information. It also doesn't allow the 'data' object to be used easily or efficiently with other types of vector: vector normalVec; // Logic to insert normalVec into data: { Vec extraCopy(normalVec.begin(), normalVec.end(), data.get_allocator(); data.push_back(extraCopy); } While the above could be made into a template function, it shouldn't need to be. Inserting something into a container should not require such complication or inefficiency. IMO, the fact that a container's type is bound to its allocator type is the main reason that allocators are so rarely used. It is why I advocate a polymorphic allocator. [lots of quoted material snipped] > >Here's a demo of std::reverse that doesn't swap allocators. Sorry for >the length, but most of it is just to make a demo allocator: [allocator imp snipped] >template >void >swap(std::vector >& x, > std::vector >& y) >{ > std::vector > tmp(x); > x = y; > y = tmp; >} Allocators are already hard for most people to grasp. Forcing a user to use partial template specialization whenever they want to use an allocator of a specific type is pretty burdensome. Also, where would this declaration of swap go? It can't be in because doesn't know about arena_alloc. It can be in "arena_alloc.h" but then we can only overload it for the known containers. User-defined or third-party container libraries would be left out. [snip] > >The point of this demo is to demonstrate a few points: > >1. If swap swaps allocators, containers with unequal allocators can be >safe, fast, and memory efficient. > >2. If you don't want your allocators to be swapped, you can overload >swap to get the behavior you want. This is still safe, but no longer >fast, and memory efficient. > >We get all this flexibility with a very tiny change in the std::lib: >swap(container, container) swaps the container's allocators. I don't >see a need for swap traits. You can already customize swap (at least in >the working paper - N1804). But overloading swap in this way does NOT give me what I want. With the overload EVERY use of swap will use this version, which is unncessarily slow in the case where a swap_move would be appropriate (e.g. sorting, reverse, etc.) It is for this reason that I want TWO swap functions, one that is used when you absolutely don't want to swap the allocator (and are willing to give up certain guarantees), and the other to be used when you don't mind swapping the allocator. I might concede that the default swap should swap the allocator (I'm not conceding yet, but I am thinking about it). But I am not ready to give up a separate swap_value algorithm that does not swap allocators. If for no other reason, the sheer existance of a standard swap_value alternative should give engineers pause to consider which type of swap they really need. Honestly, I'm not sure why you are so resistant to this small addition. Swap is not the core of my proposal. In fact, this discussion is making me think that my proposal might have a better chance if I eliminate mention of issue 431 entirely, since it seems to distract attention from the core concepts. 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 ]