From 3158374099986221294 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!newsfeed.stueberl.de!peer-uk.news.demon.net!kibo.news.demon.net!mutlu.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: Tue, 26 Jul 2005 20:51:31 GMT Organization: Metrowerks Lines: 99 Sender: mail2news@demon.net Approved: fjh@cs.mu.oz.au (Fergus Henderson , moderator of comp.std.c++) Message-ID: References: <7ibbe1hu4omoqsfibanas46idf9u6i5hjo@4ax.com> NNTP-Posting-Host: news.news.demon.net X-Trace: news.demon.co.uk 1122411099 15079 158.152.254.254 (26 Jul 2005 20:51:39 GMT) X-Complaints-To: abuse@demon.net NNTP-Posting-Date: Tue, 26 Jul 2005 20:51:39 +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 j6QKpVT2029029; Wed, 27 Jul 2005 06:51:31 +1000 (EST) X-Path: comp-std-cpp-robomod!not-for-mail X-NNTP-Posting-Date: Tue, 26 Jul 2005 16:39:35 EDT X-Delivered-To: std-c++@ucar.edu X-Spamscanner: mailbox4.ucsd.edu (v1.6 Apr 6 2005 07:48:50, -0.0/5.0 3.0.0) X-Authentication-Warning: mulga.cs.mu.OZ.AU: fjh set sender to devnull@stump.algebra.com using -f X-Newsgroups: comp.std.c++ X-MailScanner: PASSED (v1.2.8 10821 j6QKdjcO010795 mailbox4.ucsd.edu) Xref: g2news1.google.com comp.std.c++:1509 In article <7ibbe1hu4omoqsfibanas46idf9u6i5hjo@4ax.com>, phalpern@halpernwightsoftware.org (Pablo Halpern) wrote: > This morning I posted a revision to my allocator proposal at: > http://home.earthlink.net/~phalpern/cpp/HalpernAllocatorProposal.pdf In private correspondence Pablo asked me to express my concerns publicly. So here goes... I have serious reservations about making the default allocator a non-empty class (as proposed). The current overhead for the Freescale vector (with default allocator) is 3 words. If I am not mistaken, this proposal would mandate a 4 word overhead. That may not sound like much at first, but when considering containers of containers, a 33% jump in space overhead is significant. And the overhead jump for other containers (that often store multiple allocators) can be worse: list and set overhead jumps from 3 words to 5 words, 67% (in the Freescale implementation). All that being said, I'm very much in favor of improved support for client-defined stateful allocators, including the ability for different objects of the same type to get their memory from different sources. And I'm also in favor of support for unequal allocators (e.g. private buffers). Indeed it is the unequal (private buffer) application that motivates option 3 of lwg 431: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2004/n1599.html If swap exchanges memory ownership between containers, then allocator state (which may be required to deallocate that memory) should follow the memory it owns. This is analogous to tr1::shared_ptr and its custom deleter. The memory and the deleter are paired at construction time. And though one can pass around ownership of this memory from shared_ptr to shared_ptr, you can not separate the memory from the deleter that owns it. If you transfer memory ownership, you also implicitly transfer ownership of the paired deleter too. std::unique_ptr will be formally proposed in a paper this fall, and will also have custom deleter support, and will also inseparably bind the memory and its deleter. Once a container's allocator allocates memory, then that allocator is just a deleter, and must be inseparably bound to that allocated memory (if we are going to support unequal allocators, and transfer of memory ownership among containers). If instead we refuse to transfer memory ownership among containers (and so make swap O(N), or sometimes O(N)), then we will have a situation similar to list::size(). People won't be able to use it because just the threat of something changing from O(1) to O(N) is enough to make something useless. And to make things even worse, it takes what should be a non-throwing operation and turns it into something that could throw. This completely invalidates code such as: template inline std::pair& strong_assign_pair(std::pair& x, std::pair y) { x.first.swap(y.first); x.second.swap(y.second); // assumes nothrow return x; } All that being said, if an allocator author really doesn't want his allocator to swap when the container swaps, then that is trivial to accomplish: inline void swap(my_allocator&, my_allocator&) {} The proposed swap (formally swap_value) with the strong exception guarantee is extravagantly expensive when allocators are unequal. It requires a complete copy to be made of both containers, temporarily requiring 4 containers in memory at once. This goes completely against the current philosophy in the standard: support the strongest exception safety guarantees you can that don't incur extra overhead. Quite frankly if my swap suddenly decided it needed to make temporary copies of both arguments, I'd much rather get an assert or an exception to let me know. Then if I really wanted to go to that expense, I'd make it explicit rather than hiding it under something named swap. An O(N) swap, max_size, or size (all allowed by the standard) is so counterintuitive that it is dangerous, especially to generic code. It is like putting operator[](size_t) on std::list. Just say no. ;-) -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 ]