Re: realloc() - frequency, conditions, or experiences about relocation?

From	Ben Bacarisse <ben@bsb.me.uk>
Newsgroups	comp.lang.c
Subject	Re: realloc() - frequency, conditions, or experiences about relocation?
Date	2024-06-17 15:33 +0100
Organization	A noiseless patient Spider
Message-ID	<87tthrvdtg.fsf@bsb.me.uk> (permalink)
References	<v4ojs8$gvji$1@dont-email.me> <875xu8vsen.fsf@bsb.me.uk> <v4ovqf$j5hq$1@dont-email.me> <87zfrjvqp6.fsf@bsb.me.uk> <v4pb4v$lhgk$1@dont-email.me>

Show all headers | View raw

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> On 17/06/2024 10:55, Ben Bacarisse wrote:
>> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>> 
>>> On 17/06/2024 10:18, Ben Bacarisse wrote:
>>>> Janis Papanagnou <janis_papanagnou+ng@hotmail.com> writes:
>>>>
>>>>> In a recent thread realloc() was a substantial part of the discussion.
>>>>> "Occasionally" the increased data storage will be relocated along
>>>>> with the previously stored data. On huge data sets that might be a
>>>>> performance factor. Is there any experience or are there any concrete
>>>>> factors about the conditions when this relocation happens? - I could
>>>>> imagine that it's no issue as long as you're in some kB buffer range,
>>>>> but if, say, we're using realloc() to substantially increase buffers
>>>>> often it might be an issue to consider. It would be good to get some
>>>>> feeling about that internal.
>>>> There is obviously a cost, but there is (usually) no alternative if
>>>> contiguous storage is required.  In practice, the cost is usually
>>>> moderate and can be very effectively managed by using an exponential
>>>> allocation scheme: at every reallocation multiply the storage space by
>>>> some factor greater than 1 (I often use 3/2, but doubling is often used
>>>> as well).  This results in O(log(N)) rather than O(N) allocations as in
>>>> your code that added a constant to the size.  Of course, some storage is
>>>> wasted (that /might/ be retrieved by a final realloc down to the final
>>>> size) but that's rarely significant.
>>>>
>>> So can we work it out?
>> What is "it"?
>> 
>>> Let's assume for the moment that the allocations have a semi-normal
>>> distribution,
>> What allocations?  The allocations I talked about don't have that
>> distribution.
>> 
>>> with negative values disallowed. Now ignoring the first few
>>> values, if we have allocated, say, 1K, we ought to be able to predict the
>>> value by integrating the distribution from 1k to infinity and taking the
>>> mean.
>> I have no idea what you are talking about.  What "value" are you looking
>> to calculate?
>> 
> We have a continuously growing buffer, and we want the best strategy for
> reallocations as the stream of characters comes at us. So, given we now how
> many characters have arrived, can we predict how many will arrive, and
> therefore ask for the best amount when we reallocate, so that we neither
> make too many reallocation (reallocate on every byte received) or ask for
> too much (demand SIZE_MAX memory when the first byte is received).?

Obviously not, or we'd use the prediction.  You question was probably
rhetorical, but it didn't read that way.

> Your strategy for avoiding these extremes is exponential growth.

It's odd to call it mine.  It's very widely know and used.  "The one I
mentioned" might be less confusing description.

> You
> allocate a small amount for the first few bytes. Then you use exponential
> growth, with a factor of ether 2 or 1.5. My question is whether or not we
> can be cuter. And of course we need to know the statistical distribution of
> the input files. And I'm assuming a semi-normal distribution, ignoring the
> files with small values, which we will allocate enough for anyway.
>
> And so we integrate the distribution between the point we are at and
> infinity. Then we tkae the mean. And that gives us a best estimate of how
> many bytes are to come, and therefore how much to grow the buffer by.

I would be surprised if that were worth the effort at run time.  A
static analysis of "typical" input sizes might be interesting as that
could be used to get an estimate of good factors to use, but anything
more complicated than maybe a few factors (e.g. doubling up to 1MB then
3/2 thereafter) is likely to be too messy to useful.

Also, the cost of reallocations is not constant.  Larger ones are
usually more costly than small ones, so if one were going to a lot of
effort to make run-time guesses, that cost should be factored in as
well.

-- 
Ben.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

realloc() - frequency, conditions, or experiences about relocation? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-06-17 08:08 +0200
  Re: realloc() - frequency, conditions, or experiences about relocation? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-06-16 23:34 -0700
  Re: realloc() - frequency, conditions, or experiences about relocation? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-17 10:18 +0100
    Re: realloc() - frequency, conditions, or experiences about relocation? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-06-17 10:31 +0100
      Re: realloc() - frequency, conditions, or experiences about relocation? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-17 10:55 +0100
        Re: realloc() - frequency, conditions, or experiences about relocation? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-06-17 13:45 +0100
          Re: realloc() - frequency, conditions, or experiences about relocation? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-17 15:33 +0100
            Re: realloc() - frequency, conditions, or experiences about relocation? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2024-06-17 18:10 +0300
              Re: realloc() - frequency, conditions, or experiences about relocation? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-06-18 00:09 -0700
                Re: realloc() - frequency, conditions, or experiences about relocation? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-06-18 11:19 +0100
                Re: realloc() - frequency, conditions, or experiences about relocation? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-06-18 11:46 +0100
                Re: realloc() - frequency, conditions, or experiences about relocation? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-06-24 09:32 -0700
                Re: realloc() - frequency, conditions, or experiences about relocation? David Brown <david.brown@hesbynett.no> - 2024-06-24 19:19 +0200
                Indefinite pronouns [was:Re: realloc() - frequency, conditions, or experiences about relocation?] Anton Shepelev <anton.txt@gmail.moc> - 2024-06-20 02:51 +0300
                Re: Indefinite pronouns vallor <vallor@cultnix.org> - 2024-06-20 00:34 +0000
                Re: Indefinite pronouns David Brown <david.brown@hesbynett.no> - 2024-06-21 12:59 +0200
                Re: Indefinite pronouns Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-06-21 10:31 -0700
                Re: Indefinite pronouns [was:Re: realloc() - frequency, conditions, or experiences about relocation?] gazelle@shell.xmission.com (Kenny McCormack) - 2024-06-20 12:10 +0000
                Re: Indefinite pronouns [was: Re: <something technical>] Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-06-20 15:04 +0200
                Re: Indefinite pronouns [was:Re: realloc() - frequency, conditions, or experiences about relocation?] Cri-Cri <cri@cri.cri.invalid> - 2024-06-21 00:55 +0000
                Re: Indefinite pronouns [was:Re: realloc() - frequency, conditions, or experiences about relocation?] Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-06-20 23:23 -0700
            Re: realloc() - frequency, conditions, or experiences about relocation? Richard Harnden <richard.nospam@gmail.invalid> - 2024-06-17 16:15 +0100
              Re: realloc() - frequency, conditions, or experiences about relocation? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-06-17 13:05 -0700
            Re: realloc() - frequency, conditions, or experiences about relocation? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-06-17 16:36 +0100
          Re: realloc() - frequency, conditions, or experiences about relocation? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2024-06-17 18:02 +0300
            Re: realloc() - frequency, conditions, or experiences about relocation? "David Jones" <dajhawk18xx@@nowhere.com> - 2024-06-18 17:59 +0000
            Re: realloc() - frequency, conditions, or experiences about relocation? davidd02@tpg.com.au (David Duffy) - 2024-06-19 06:48 +0000
              Re: realloc() - frequency, conditions, or experiences about relocation? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-06-19 10:12 +0100
                Re: realloc() - frequency, conditions, or experiences about relocation? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-19 16:36 +0100
                Re: realloc() - frequency, conditions, or experiences about relocation? David Brown <david.brown@hesbynett.no> - 2024-06-19 19:41 +0200
                Re: realloc() - frequency, conditions, or experiences about relocation? Ben Bacarisse <ben@bsb.me.uk> - 2024-06-19 22:24 +0100
                Re: realloc() - frequency, conditions, or experiences about relocation? David Brown <david.brown@hesbynett.no> - 2024-06-20 13:22 +0200
                Re: realloc() - frequency, conditions, or experiences about relocation? Anton Shepelev <anton.txt@gmail.moc> - 2024-06-20 01:53 +0300
              Re: realloc() - frequency, conditions, or experiences about relocation? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2024-06-19 15:20 +0300
          Re: realloc() - frequency, conditions, or experiences about relocation? scott@slp53.sl.home (Scott Lurndal) - 2024-06-17 16:58 +0000
            Re: realloc() - frequency, conditions, or experiences about relocation? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-06-17 13:12 -0700
          Re: realloc() - frequency, conditions, or experiences about relocation? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-06-17 16:39 -0700
            Re: realloc() - frequency, conditions, or experiences about relocation? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-06-18 06:12 +0100
            Re: realloc() - frequency, conditions, or experiences about relocation? Bonita Montero <Bonita.Montero@gmail.com> - 2024-06-18 09:56 +0200
      Re: realloc() - frequency, conditions, or experiences about relocation? David Brown <david.brown@hesbynett.no> - 2024-06-17 20:11 +0200
  Re: realloc() - frequency, conditions, or experiences about relocation? Bonita Montero <Bonita.Montero@gmail.com> - 2024-06-17 11:22 +0200
    Re: realloc() - frequency, conditions, or experiences about relocation? Vir Campestris <vir.campestris@invalid.invalid> - 2024-06-20 21:08 +0100
      Re: realloc() - frequency, conditions, or experiences about relocation? Bonita Montero <Bonita.Montero@gmail.com> - 2024-06-21 21:12 +0200
        Re: realloc() - frequency, conditions, or experiences about relocation? Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-06-24 08:40 +0000
          Re: realloc() - frequency, conditions, or experiences about relocation? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-06-24 02:55 -0700
            Re: realloc() - frequency, conditions, or experiences about relocation? David Brown <david.brown@hesbynett.no> - 2024-06-24 13:40 +0200
              Re: realloc() - frequency, conditions, or experiences about relocation? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-06-24 18:50 +0100
                Re: realloc() - frequency, conditions, or experiences about relocation? scott@slp53.sl.home (Scott Lurndal) - 2024-06-24 18:20 +0000
                Re: realloc() - frequency, conditions, or experiences about relocation? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-06-24 14:28 -0700
                Re: realloc() - frequency, conditions, or experiences about relocation? Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2024-06-25 00:22 +0100
                Re: realloc() - frequency, conditions, or experiences about relocation? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-06-24 18:31 -0700
                Re: realloc() - frequency, conditions, or experiences about relocation? Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-06-25 07:06 +0000
                Re: realloc() - frequency, conditions, or experiences about relocation? Bonita Montero <Bonita.Montero@gmail.com> - 2024-06-25 10:38 +0200
                Re: realloc() - frequency, conditions, or experiences about relocation? Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-06-26 00:51 +0000
              Re: realloc() - frequency, conditions, or experiences about relocation? "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2024-06-24 12:33 -0700
                Re: realloc() - frequency, conditions, or experiences about relocation? Bonita Montero <Bonita.Montero@gmail.com> - 2024-06-24 21:48 +0200
              Re: realloc() - frequency, conditions, or experiences about relocation? Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-06-24 22:59 +0000
            Re: realloc() - frequency, conditions, or experiences about relocation? Bonita Montero <Bonita.Montero@gmail.com> - 2024-06-24 16:19 +0200
            Re: realloc() - frequency, conditions, or experiences about relocation? Lawrence D'Oliveiro <ldo@nz.invalid> - 2024-06-25 07:02 +0000
              Re: realloc() - frequency, conditions, or experiences about relocation? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2024-06-25 03:05 -0700
                Re: realloc() - frequency, conditions, or experiences about relocation? Richard Damon <richard@damon-family.org> - 2024-06-25 07:21 -0400
          Re: realloc() - frequency, conditions, or experiences about relocation? Bonita Montero <Bonita.Montero@gmail.com> - 2024-06-24 16:16 +0200
            Down the hall, past the water cooler, third door on the left... (Was: realloc() - frequency, conditions, or experiences about) relocation? gazelle@shell.xmission.com (Kenny McCormack) - 2024-06-24 15:44 +0000
              Re: Down the hall, past the water cooler, third door on the left... (Was: realloc() - frequency, conditions, or experiences about) relocation? Bonita Montero <Bonita.Montero@gmail.com> - 2024-06-24 20:16 +0200
  Re: realloc() - frequency, conditions, or experiences about relocation? David Brown <david.brown@hesbynett.no> - 2024-06-17 14:15 +0200
    Re: realloc() - frequency, conditions, or experiences about relocation? Bonita Montero <Bonita.Montero@gmail.com> - 2024-06-17 14:18 +0200
  Re: realloc() - frequency, conditions, or experiences about relocation? Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2024-06-17 15:21 +0200
  Re: realloc() - frequency, conditions, or experiences about relocation? scott@slp53.sl.home (Scott Lurndal) - 2024-06-17 16:50 +0000
    Re: realloc() - frequency, conditions, or experiences about relocation? Michael S <already5chosen@yahoo.com> - 2024-06-17 20:20 +0300
      Re: realloc() - frequency, conditions, or experiences about relocation? scott@slp53.sl.home (Scott Lurndal) - 2024-06-17 19:02 +0000
  Re: realloc() - frequency, conditions, or experiences about relocation? Rosario19 <Ros@invalid.invalid> - 2024-06-18 11:50 +0200
  Re: realloc() - frequency, conditions, or experiences about relocation? Bonita Montero <Bonita.Montero@gmail.com> - 2024-06-25 10:48 +0200
    Re: realloc() - frequency, conditions, or experiences about relocation? Vir Campestris <vir.campestris@invalid.invalid> - 2024-06-25 11:55 +0100
      Re: realloc() - frequency, conditions, or experiences about relocation? Bonita Montero <Bonita.Montero@gmail.com> - 2024-06-25 13:28 +0200
        Re: realloc() - frequency, conditions, or experiences about relocation? Vir Campestris <vir.campestris@invalid.invalid> - 2024-06-26 12:15 +0100
          Re: realloc() - frequency, conditions, or experiences about relocation? Bonita Montero <Bonita.Montero@gmail.com> - 2024-06-26 15:01 +0200
    Re: realloc() - frequency, conditions, or experiences about relocation? DFS <nospam@dfs.com> - 2024-06-25 09:56 -0400
      Re: realloc() - frequency, conditions, or experiences about relocation? Bonita Montero <Bonita.Montero@gmail.com> - 2024-06-25 16:16 +0200

csiph-web