Re: equivalent of realloc in C++

On Mar 28, 7:17 pm, Andrei Alexandrescu
<SeeWebsiteForEm...@erdani.org> wrote:


What you mistake for "confirmation bias" is simply healthy, scientific
skepticism. After all, the efficacy of realloc() as an optimization is
a question best answered by scientific - not statistical - methods. In
other words, realloc() will not become an optimization when the
percentage of people who believe that it is - crosses some particular
threshold.

As this thread demonstrates, there are many individuals who are
(justifiably) leery of benchmarks that purport to demonstrate
particular optimizations - but do so with any kind of supporting
theoretical framework to account for the alleged improvements. And
without such a theory, there is no way to quantify the magnitude of
the improvement expected (a quantification that then could be verified
by subsequent, independent tests.)

In this case, no one has enunciated any theory that would explain how
realloc() - which can add as much cost as it saves in individual cases
- would nonetheless save costs when applied across the board. Nor has
anyone quantified how much lower the cost of inserting an item into a
std::vector (which currently has a fixed, amortized cost) would become
- were a std::vector to adopt realloc().


Fortunately, scientific questions are not decided by majority vote.
The beauty (and power) of the scientific method is that a single
individual - equipped with a sound theory - is all that is needed to
change the majority of other people's minds.

Now, anyone who sets out to show that realloc() would provide a net
benefit does face a steep, uphill climb. For one, the cost of
inserting an item into a std::vector is currently a constant
(amortized) cost. Meaning that for each item inserted, a std::vector
will (eventually) have to perform at most, one copy operation.
Therefore, to do better than a std::vector, a realloc-ing vector would
have to guarantee at least a diminishing, amortized cost. That is,
each item insertion would have to result in an ever-decreasing number
of eventual copy operations; say, 1.0 for the first item inserted,
0.95 for the twentieth, 0.9 for the fortieth and so forth. The problem
here is that realloc()'s efficacy diminishes as the vector grows.
Intuitively, the average amount of free memory adjacent to an
allocated block decreases in relative size as the size of the
allocated block - increases. So the question to answer is: how will
realloc() be able to lower the costs of insertion continually - even
as the amount of memory it can expand into becomes on average, less
and less significant?


Until someone describes the algorithm with which a std::vector would
use realloc() to improve its performance - there is nothing to test.


Yes, it is silly to try to demonstrate than a resizing algorithm that
has a linear cost will somehow be cheaper than one with a fixed,
amortized cost - all else being equal (which is not the case here). In
fact, the only way that this program's realloc-ing vector could keep
pace with a std::vector would be if the cost of each individual "copy"
operation were much cheaper for the realloc-ing vector than they are
for the std::vector (and they are: block memory transfers are in
general vastly faster than per-object copying).

In contrast, if both programs were held to the same standard (that is,
if both vectors were required to preserve their contents after
resizing), then both implementations could use the same copy operation
and the comparison between the two would have at least some measure of
validity and usefulness.


I don't know many programmers who would welcome a 6.5% speedup in
vector re-sizing if it were to leave the contents of the vector 100%
unusable. In fact, if this tradeoff is reasonable, then why does the
std::vector program perform any I/O at all? Certainly, filling the
vector with empty strings would speed up the program considerably. Why
is one program held to a much stricter standard than the other?

In reality, there should not be any surprise that a content-destroying
vector would outperform a content-preserving vector. The only surprise
is how small the difference is. What keeps the realloc-ing vector from
performing better are the larger number of extra "copy" operations
that it must perform - extra work that is slightly offset by the
relatively low cost of the block memory transfers themselves.. In any
event, this benchmark program does nothing to support the claim that
realloc() would provide any kind of benefit to a std::vector. About
the conclusion to be drawn here is that std::vector's performance
could be dramatically improved - if only the vector were not required
to preserve its contents after resizing.

To even the playing field and to make a somewhat reasonable
comparison, both programs must work correctly - and both must preserve
the contents of each container, intact. Replacing the std::string with
a POD-struct would help:

    #include <vector>
    using namespace std;

    struct S
    {
        char s[7];
    };

    int main()
    {
         S * vec = 0;
         size_t vecSize = 0;
         for (;; ++vecSize)
         {
              vec = static_cast<S*> (realloc(vec, (vecSize + 1)*
                          sizeof(S)));
              if (!vec) return 1;
              new(vec + vecSize) S;
              if (!cin.getline( &vec[vecSize].s[0],
                    sizeof(S().s), '\n') or !cin.gcount() )
                 break;
          }
     }

and:

    using namespace std;
     struct S
     {
         char s[7];
     };

     int main()
     {
          vector<S> vec;
          do
          {
                 vec.push_back(S());
          } while( cin.getline((char *) vec[vec.size()-1].s,
                   sizeof(S().s), '\n') or cin.gcount()) ;

          vec.pop_back();
     }

and the best timings that I measured for each:

     realloc:

     real 0m0.573s
     user 0m0.537s
     sys 0m0.033s

     std::vector:

     real 0m0.511s
     user 0m0.474s
     sys 0m0.035s

Greg

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