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 10:55 +0100
Organization	A noiseless patient Spider
Message-ID	<87zfrjvqp6.fsf@bsb.me.uk> (permalink)
References	<v4ojs8$gvji$1@dont-email.me> <875xu8vsen.fsf@bsb.me.uk> <v4ovqf$j5hq$1@dont-email.me>

Show all headers | View raw

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?

-- 
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