From -1283281189985265214 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!newsfeed00.sul.t-online.de!t-online.de!peer-uk.news.demon.net!kibo.news.demon.net!news.demon.co.uk!demon!stump.algebra.com!devnull From: hinnant@metrowerks.com (Howard Hinnant) Newsgroups: comp.std.c++ Subject: Re: Revised Allocator Proposal Date: Thu, 11 Aug 2005 05:30:05 GMT Organization: Metrowerks Lines: 362 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 X-Trace: news.demon.co.uk 1123738214 6514 158.152.254.254 (11 Aug 2005 05:30:14 GMT) X-Complaints-To: abuse@demon.net NNTP-Posting-Date: Thu, 11 Aug 2005 05:30:14 +0000 (UTC) X-Robomod: STUMP, ichudov@algebra.com (Igor Chudov) X-User-Agent: MT-NewsWatcher/3.4 (PPC Mac OS X) X-Virus-Scanned: amavisd-new at cs.mu.OZ.AU X-Received: (from fjh@localhost) by mulga.cs.mu.OZ.AU (8.12.10+Sun/8.12.9/Submit) id j7B5U5fD003194; Thu, 11 Aug 2005 15:30:05 +1000 (EST) X-Path: comp-std-cpp-robomod!not-for-mail X-NNTP-Posting-Date: Wed, 10 Aug 2005 14:48:48 EDT 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-Newsgroups: comp.std.c++ Xref: g2news1.google.com comp.std.c++:1756 {repeat submission} In article <9pchf11o63qib8h56fap5g5445gjac5ce2@4ax.com>, phalpern@halpernwightsoftware.org (Pablo Halpern) wrote: > 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). 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? > >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. That general sentiment can be widened: The programmer cannot thoughtfully associate a container with data and expect it to remain that way unless he studiously avoids passing a modifiable container to any function that he did not write himself. I.e. A useful function must document its effects. > 2. The container could end up outliving its allocator. Is this not true regardless? > 3. Memory could be leaked because an arena allocator does not control > all of the memory that it was thought to control. But it is always possible to leak memory if you misuse the tools. > 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. Perhaps shared memory allocators that reference different segments should refuse to swap, or should overload swap to do what you want (see example below). > 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 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. > >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. > 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()); > 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; > 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? 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: #include #include #include struct buff { buff(char* buf, std::size_t size) : p_(buf), buf_(buf), size_(size), orig_size_(size) {} char* allocate(std::size_t n); void deallocate(void*, std::size_t); void swap(buff& b) {std::swap(p_, b.p_); std::swap(buf_, b.buf_); std::swap(size_, b.size_); std::swap(orig_size_, b.orig_size_);} char* p_; char* buf_; std::size_t size_; std::size_t orig_size_; }; char* buff::allocate(std::size_t n) { if (n > size_) throw std::bad_alloc(); char* ret = buf_; buf_ += n; size_ -= n; return ret; } inline void buff::deallocate(void* p, std::size_t) { assert(p_ <= p && p < p_ + orig_size_); } template class arena_alloc : private buff { public: typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; typedef T* pointer; typedef const T* const_pointer; typedef T& reference; typedef const T& const_reference; typedef T value_type; template struct rebind { typedef arena_alloc other; }; arena_alloc(void* p, size_type n) : buff((char*)p, n) {} template arena_alloc(const arena_alloc& a) : buff(a) {}; pointer allocate(size_type n, const void* = 0) {return (pointer)buff::allocate(n*sizeof(T));} void deallocate(pointer p, size_type n) {buff::deallocate(p, n);} size_type max_size() const {return buff::size_ / sizeof(T);} pointer address(reference x) const {return &x;} const_pointer address(const_reference x) const {return &x;} void construct(pointer p, const T& val) {::new(p) T(val);} void destroy(pointer p) {p->~T();} void swap(arena_alloc& a) {buff::swap(a);} template bool equal(const arena_alloc& a) const {return p_ == a.p_;} private: arena_alloc& operator=(const arena_alloc&); template friend class arena_alloc; }; template inline void swap(arena_alloc& x, arena_alloc& y) { x.swap(y); } template inline bool operator==(const arena_alloc& x, const arena_alloc& y) { return x.equal(y); } template inline bool operator!=(const arena_alloc& x, const arena_alloc& y) { return !(x == y); } template void swap(std::vector >& x, std::vector >& y) { std::vector > tmp(x); x = y; y = tmp; } int main() { typedef std::vector > Vec; const unsigned N1 = 120; unsigned char buf1[N1]; const unsigned N2 = 80; unsigned char buf2[N2]; Vec v[2] = {Vec(10, 0, arena_alloc(buf1, N1)), Vec(20, 0, arena_alloc(buf2, N2))}; std::reverse(v, v+2); assert(v[0].size() == 20); assert(v[0].get_allocator() == arena_alloc(buf1, N1)); assert(v[1].size() == 10); assert(v[1].get_allocator() == arena_alloc(buf2, N2)); } The part I want to draw attention to is the overloaded swap in arena_alloc's namespace. Sorry, I used an arena allocator instead of a polymorphic allocator just to keep the demo small, but I don't think that will affect my point. Here I've turned a std::algorithm (that uses swap, and the standard swap swaps allocators in my implementation) into one that swaps without swapping allocators. The asserts do not fire in this example, and memory integrity is maintained. I.e. the above demo does exactly what you want. Now, simply comment out the overloaded swap in the above demo, and change the asserts in main and you get allocator-swapping behavior (assuming std::swap swaps allocators of course): assert(v[0].size() == 20); assert(v[1].get_allocator() == arena_alloc(buf1, N1)); assert(v[1].size() == 10); assert(v[0].get_allocator() == arena_alloc(buf2, N2)); Also in this version, I was able to reduce the size of my first buffer: const unsigned N1 = 40; // down from 120 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). -Howard --- [ 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 ]