From -1718661345924128817 X-Google-Thread: f78e5,27c2a088314ec0a9 X-Google-Attributes: gidf78e5,public X-Google-Language: ENGLISH,ASCII-7-bit Path: g2news1.google.com!news2.google.com!proxad.net!news2.telebyte.nl!border2.nntp.ams.giganews.com!border1.nntp.ams.giganews.com!nntp.giganews.com!news-hub.cableinet.net!blueyonder!peer-uk.news.demon.net!kibo.news.demon.net!news.demon.co.uk!demon!stump.algebra.com!devnull From: dhruvbird@gmx.net ("Dhruv Matani") Newsgroups: comp.std.c++ Subject: Re: should std::vector<> exponential growth rate be followed strictly in times of low availabe memory. Date: Sat, 6 Nov 2004 18:39:21 GMT Lines: 90 Sender: mail2news@demon.net Approved: fjh@cs.mu.oz.au (Fergus Henderson , moderator of comp.std.c++) Message-ID: References: <417E434E.5000209@bubblescope.net> <4fvjo0t07isfber4rblifh56jmiq2glrnj@4ax.com> <4fb4137d.0411050721.1934c7c0@posting.google.com> NNTP-Posting-Host: news.news.demon.net Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: 8bit X-Trace: news.demon.co.uk 1099766382 19614 158.152.254.254 (6 Nov 2004 18:39:42 GMT) X-Complaints-To: abuse@demon.net NNTP-Posting-Date: Sat, 6 Nov 2004 18:39:42 +0000 (UTC) X-Robomod: STUMP, ichudov@algebra.com (Igor Chudov) X-User-Agent: Pan/0.13.3 (That cat's something I can't explain) X-Orig-X-Trace: news.uni-berlin.de GDt1Qnkx+SMVvqs7lQdpfQAKSVU+Myr42Rir8/iKt3FHMRqFdG X-Virus-Scanned: by 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 iA6IdLop027691; Sun, 7 Nov 2004 05:39:21 +1100 (EST) X-Path: comp-std-cpp-robomod!not-for-mail 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++:3299 On Fri, 05 Nov 2004 15:52:42 +0000, johnchx wrote: > dhruvbird@gmx.net ("Dhruv Matani") wrote > >> 2. Every insertion involves touching a lot of data, so places where data >> is coming in at a very fast rate, this is unacceptable. > > If you need *consistently* fast push_back() times -- to keep up with a > fast input source, for instance -- then vector's amortized-constant > time probably won't be good enough. Amortized-constant time is fine > if you don't mind the application grinding to a halt from time to time > while reallocation is performed, but it sounds like you may not be > able to afford it. You're probably right, but before going one way or the other I would like to profile and see for myself what the actual situation would be like practically. I would tend to agree with your observation as of now though. > >> Here, I know in advance the maximum size of the vector, but in other cases >> I might not. > > Your best bet is probably to use vector only if you know the maximum > size in advance. If you can reserve() sufficient space up-front, you > don't have to worry about re-allocation. If you can't, and you can't > afford long copy times while receiving input, you'll probably be > better off with a deque. Yes, even Michael Karcher has mentioned that, and it seems like a nice prospect. Again, iteration would suffer here. And believe me, iteration is quite slow compared to vector's, but I have to first concretely apply both the containers and time and then make any non-naive observations. > >> Now, given that fact that I have say 2GB of Phy. mem. I >> should not be consrtained by the exponential growth policy. > > Physical memory is probably irrelevant. The real constraint is more > likely to be the amount of unfragmented space available in the portion > of the virtual address space of the process which is earmarked for > heap allocation. If you don't absolutely need the entire data > structure to be in a single continguous chunk of address space, you'll > get better results (fewer bad_alloc exceptions, no copies, no > reallocation delays) from a deque. Yes. > > Of course, it's not hard to implement your "reallocation fallback" > policy with a wrapper function like this: > > template < class T, class A > > void modified_push_back ( std::vector& v, const T& t ) > { > try { > v.push_back(t); > } > catch (std::bad_alloc&) { > std::vector v2; > v2.reserve(v.capacity() + 1 ); // or whatever > std::copy( v.begin(), v.end(), std::back_inserter(v2) ); > v.swap(v2); > } I don't think this would work for the simple reason that a vector implementation is not required to allocate ONLY n bytes(memory for n objects) after a reserve(n) command. The guarantee is that at least n objects can be inserted(assuming that it is empty initially) without reallocation. The vector can do this internally: vector::reserve(int n) { int new_size = std::max(this->capacity()*2, n); // Normal stuff. } And we would be back to square one. Regards, -Dhruv. --- [ 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 ]