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.

Janis

On 6/16/2024 11:08 PM, Janis Papanagnou wrote:
> 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.

[...]

It sure can be a factor to consider. Usually its pretty nice, but not so
much for certain workloads.

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.

--
Ben.

Am 17.06.2024 um 08:08 schrieb Janis Papanagnou:
> 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.
>
> Janis

realloc() is just a convenience funciton. Usually the reallocation
can't happen in-place and a second malloc() followed by a copy and
a free() does the same.
For large data it would be nice if the pages being deallocated later
would be incrementally marked as discardable after copying a portion.
This would result in only a small portion of additional physical
memory being allocated since the newly allocated pages become asso-
ciated with phyiscal pages when they're touched first. Windows has
VirtualAlloc() with MEM_RESET for that, Linux has madvise() with
MADV_DONTNEED.

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?

Let's assume for the moment that the allocations have a semi-normal
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.

--
Check out my hobby project.
http://malcolmmclean.github.io/babyxrc

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.

On 17/06/2024 08:08, Janis Papanagnou wrote:
> 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.
>
> Janis

Consider your target audience and their hardware, the target OS, and the
realistic size of your data. If the target is a PC, you can happily
malloc tens of MB at the start without a care, and for systems that do
not actually allocate system memory until you try to access the area,
there is no cost to this.

So in many situations where you are reading and parsing data from a
file, you can just do the initial malloc with more than enough space for
any realistic input file. You might still implement a realloc solution
for occasional extreme uses, and because it is nice to avoid artificial
limits for programs, but efficiency matters a lot less in those cases.

It may also be the case that even if realloc returns a different address
and logically copies a lot of data, that this is done by smarter virtual
memory mapping so that only the mapping changes, and the underlying
physical ram does not need to be copied. But I don't know if OS's and
realloc implementations are smart enough to do that.

Am 17.06.2024 um 14:15 schrieb David Brown:

> Consider your target audience and their hardware, the target OS, and the
> realistic size of your data.  If the target is a PC, you can happily
> malloc tens of MB at the start without a care, and for systems that do
> not actually allocate system memory until you try to access the area,
> there is no cost to this.

If you have a memcpy() from a to b at the end there's twice the memory
allocated even if the destination pages are assigned while touching a
page.

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).?
Your strategy for avoiding these extremes is exponential growth. 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.
--
Check out my hobby project.
http://malcolmmclean.github.io/babyxrc

On 17.06.2024 08:08, Janis Papanagnou wrote:
> 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.

Let me add...

I'd assume that there's some basic allocation size defined; some
simple test sample with a handful of bytes didn't relocate the data.
Yet I don't know whether allocated memory is managed sequentially
or has linked blocks. A peek info the source code might help. What
I found is this comment for extending chunks:[*]
* Extending forward into following adjacent free chunk.
* Shifting backwards, joining preceding adjacent space
* Both shifting backwards and extending forward.
* Extending into newly sbrked space
Going to investigate that source code[*] later...

Janis

[*] https://elixir.bootlin.com/glibc/glibc-2.1.2/source/malloc/malloc.c
(line 3077 ff)

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.

[cross-posted to: ci.stat.math]

Malcolm McLean:

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

Do you mean in the next bunch, or in total (till the end of
the buffer's lifetime)?

> 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).?
>
> Your strategy for avoiding these extremes is exponential
> growth. You allocate a small amount for the first few
> bytes. Then you use exponential growth, with a factor of
> ether 2 or 1.5.

This strategy ensures a constant ratio between the amount of
reallocated data to the length of the buffer by making
reallocations less frequent as the buffer grows.

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

You have an apriori distribution of the buffer size (can be
tracked on-the-fly, if unknown beforehand) and a partially
filled buffer. The task is to calculate the a-posteriori
distribution of /that/ buffer's final size, and then to
allocate the predicted value based on a good percentile.

How about using a percentile instead of the mean, e.g. if
the current size corresponds to percentile p, you allocate a
capacity corresponding to percentile 1-(1-p)/k , where k>1
denotes the balance between space and time efficency. For
example, if the 60th percentile of the buffer is required
and k=2, you allocate a capacity sufficient to hold
100-(100-60)/2=80% of buffers.

--
() ascii ribbon campaign -- against html e-mail
/\ www.asciiribbon.org -- against proprietary attachments

Ben Bacarisse to Malcolm McLean:

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

Not so obvious to me, for the exponential algorithm may be
the best when the distribution of buffer size is /not/
known, whereas Malcolm is interested in the cases when we
know it.

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

I think it is a modern English idiom, which I dislike as
well. StackOverflow is full of questions starting like:
"How do you do this?" and "How do I do that?" They are
informal ways of the more literary "How does one do this?"
or "What is the way to do that?"

--
() ascii ribbon campaign -- against html e-mail
/\ www.asciiribbon.org -- against proprietary attachments

On 17/06/2024 15:33, Ben Bacarisse wrote:
> 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.
>

I usually keep track:

struct
{ size_t used;
size_t allocated;
void *data;
};

Then, if used + new_size is more than what's already been allocated then
a realloc will be required.

Start with an initial allocated size that's 'resonable' - the happy path
will never need any reallocs.

Otherwise multiply by some factor. Typicall I just double it.

On 17/06/2024 15:33, Ben Bacarisse wrote:
> 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.
>
There's virualy no run-time effort, unless you ask caller to pass in a
customised distribution, which you analyse on the fly, which would be
quite a bit of work.
All the work is done beforehand. We need a statistical distribution of
the files sizes of the files we are interesed in. So, probably, text
files on personal computers. Then we'll excude the small files, say
under 1kb which will have an odd distribution for various reasons, and
which we are not interested in as we can easily afford 1k as an initial
buffer.

And we're probably looking at a semi- normal, maybe log- normal
distribution. There's no reason to suspect it would be anything odd. And
with the normal distribution there is no closed form integral, but
tables of integrals are published.

So we convert 1K to a Z-score, integrate from that to infinity, halve
the result, and that gives us an estimate of the most likely file size -
having established that the file is over 1k, half will be below and half
above this size. So that's the next amount to realloc. Say, for the sake
of argument, 4K. Then we do the same thing, starting from 4k, and
working out the most likely file size, given that the file is over 4K.
Now the disribution tends to flatten out towards the tail, so if best
guess, given at least 1K, was 4K, best guess diven 4k, won't be 8K. It
will be 10k, maybe 12k. Do the same again for 12k. And we'll get a
series of numbers like this.

1k, 4k, 10k, 20k, 50k, 120k, 500k, 2MB, 8MB ...

and so on, rapidly increasing to SIZE_MAX. And then at runtime we just
hardcode those in, it's a lookup table with not too many entries.

Becuase we've chosen the mean, half the time you will reallocate. You
can easily fine tune the strategy by choosing a proportion other than
0.5, depending on whether saving memory or reducing allocations is more
important to you.

and the hard part is getting some real statistics to work on.
>
> 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.
>
Unfortunately yes. Real optimisation problems can be almost impossible
for reasons like this. iF the cost of reallocations isn't constant,
tou've got to put in correctiong factors, and then what was a fairly
simple procedure becomes difficult.

--
Check out my hobby project.
http://malcolmmclean.github.io/babyxrc

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.

I've not found a use for realloc in the last forty five years, myself.

I suspect that the performance issues are not an issue for relatively
small datasets, and are often exhibited during the non-performance critical
'setup' phase of an algorithm.

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

>>
>> I have no idea what you are talking about. What "value" are you looking
>> to calculate?
>>
>We have a continuously growing buffer,

At this point, you should be asking yourself
if there are better alternatives for storing
the incoming data than to a continuously growing
dynamically allocated piecemeal buffer.

C character stdio tends to work well for streaming applications
(i.e. pipelines where the input is (minimally) processed and forwarded
to the output), but not so efficiently for applications that need to
look at the data en masse.

Personnally, I'd mmap the input file and eschew stdio completely
and just walk through memory with the appropriate pointer.

(mmap showed up in the late 80s, so you can pretend it
is C90 if you like).

On Mon, 17 Jun 2024 16:50:07 GMT
scott@slp53.sl.home (Scott Lurndal) 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.
>
> I've not found a use for realloc in the last forty five years, myself.
>

Did you find use for std::vector:resize()?
If yes, that could be major reason behind not finding use for realloc().
Another possible reason is coding for environments where dynamic
allocation either not used at all or used only during start up.

At least for me those are major reasons why I very rarely used realloc
since beginning of programming as a pro.

> I suspect that the performance issues are not an issue for relatively
> small datasets, and are often exhibited during the non-performance
> critical 'setup' phase of an algorithm.

On 17/06/2024 11:31, Malcolm McLean wrote:
> 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?
>
> Let's assume for the moment that the allocations have a semi-normal
> 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.
>

First, there is no reason for assuming such a distribution, other than
saying "lots of things are roughly normal".

Secondly, knowing the distribution gives you /no/ information about any
given particular case. You know the distribution for the results of
rolling two die - does that mean you can predict the next roll?

Thirdly, not all distributions have a mean (look up the Cauchy
distribution if you like).

Fourthly, even if you know the mean, it tells you nothing of use.

Knowing a bit about the distribution of file sizes can be useful, but
not nearly in the way you describe here. If you know that the files are
rarely or never bigger than 10 MB, malloc 10 MB and forget the realloc.
If you know they are often bigger than that, mmap the file and forget
the realloc.

Michael S <already5chosen@yahoo.com> writes:
>On Mon, 17 Jun 2024 16:50:07 GMT
>scott@slp53.sl.home (Scott Lurndal) 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.
>>
>> I've not found a use for realloc in the last forty five years, myself.
>>
>
>Did you find use for std::vector:resize()?

I'm pretty sure (checks) that I posted this reply to comp.lang.c.

std::vector::resize() doesn't work well from C (well, I can mangle
the names and use an explicit this pointer, but why bother?).

>If yes, that could be major reason behind not finding use for realloc().
>Another possible reason is coding for environments where dynamic
>allocation either not used at all or used only during start up.

Or because the algorithms used don't call for realloc. Or there
are better alternatives (like mmap).

On 6/17/2024 8:15 AM, Richard Harnden wrote:
> On 17/06/2024 15:33, Ben Bacarisse wrote:
>> 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.
>>
>
> I usually keep track:
>
> struct
> {
>     size_t used;
>     size_t allocated;
>     void *data;
> };
>
> Then, if used + new_size is more than what's already been allocated then
> a realloc will be required.

Fwiw, I remember way back using an n-ary tree of regions to accomplish
it. The trigger for creating a new region was very similar to your
logic. It performed pretty good and did not use realloc. Indeed it was
for a special use case. I remember having region partitions that would
link to other regions. Actually, it kind of reminded me of a strange
version of ropes:

https://en.wikipedia.org/wiki/Rope_(data_structure)

Fwiw, here is my old C code for a region:

https://pastebin.com/raw/f37a23918
(raw text, no ads)

Iirc, I first mentioned it in:

https://groups.google.com/g/comp.lang.c/c/7oaJFWKVCTw/m/sSWYU9BUS_QJ

>
> Start with an initial allocated size that's 'resonable' - the happy path
> will never need any reallocs.
>
> Otherwise multiply by some factor.  Typicall I just double it.
>
>
>

On 6/17/2024 9:58 AM, Scott Lurndal wrote:
> 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:
>>>
>
>>>
>>> I have no idea what you are talking about. What "value" are you looking
>>> to calculate?
>>>
>> We have a continuously growing buffer,
>
> At this point, you should be asking yourself
> if there are better alternatives for storing
> the incoming data than to a continuously growing
> dynamically allocated piecemeal buffer.
>
> C character stdio tends to work well for streaming applications
> (i.e. pipelines where the input is (minimally) processed and forwarded
> to the output), but not so efficiently for applications that need to
> look at the data en masse.

Indeed.

> Personnally, I'd mmap the input file and eschew stdio completely
> and just walk through memory with the appropriate pointer.

That works for sure. Actually, its been a while since I have used memory
mapped files. I made a little database thing with them that multiple
processes could use, lock-free... ;^)

Also, I remember a nifty trick to use memory mapped files with certain
lock-free algorithms. I need to find that old post over on
comp.programming.threads. Have a feeling that its going to be hard to find!

> (mmap showed up in the late 80s, so you can pretend it
> is C90 if you like).

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
[...]
> 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).?
[...]

That's going to depend on the behavior of the implementations
realloc() function.

malloc() and realloc() typically allocate more memory than they're
asked for, so that another realloc() call can often expand the
allocated memory in place.

I have a small test program that uses realloc() to expand a 1-byte
allocated buffer to 2 bytes, then 3, then 4, and so on. In one
implementation, in one test run, it reallocates at 25 bytes, and
then not again until just over 128 kbytes. Other implementations
behave differently.

A realloc() call that's able to return its first argument is likely
to be much quicker than one that does an actual reallocation.
If you want to fine tune for performance, you'll have to allow
for the implementation you're using, either by performing run-time
measurements or by analyzing the implementation (which could change
in the next release).

Multiplying the size by 2 or 1.5 as needed is likely to be good enough.

--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
void Void(void) { Void(); } /* The recursive call of the void */

On 18/06/2024 00:39, Keith Thompson wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
> [...]
>> 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).?
> [...]
>
> That's going to depend on the behavior of the implementations
> realloc() function.
>
> malloc() and realloc() typically allocate more memory than they're
> asked for, so that another realloc() call can often expand the
> allocated memory in place.
>
> I have a small test program that uses realloc() to expand a 1-byte
> allocated buffer to 2 bytes, then 3, then 4, and so on. In one
> implementation, in one test run, it reallocates at 25 bytes, and
> then not again until just over 128 kbytes. Other implementations
> behave differently.
>
> A realloc() call that's able to return its first argument is likely
> to be much quicker than one that does an actual reallocation.
> If you want to fine tune for performance, you'll have to allow
> for the implementation you're using, either by performing run-time
> measurements or by analyzing the implementation (which could change
> in the next release).
>
> Multiplying the size by 2 or 1.5 as needed is likely to be good enough.
>
A small test program can hog all of memory for itself, and so isn't a
good test. What matters is where you're running something like a video
game, and the artists stuff the comupter's memory full of artwork until
it runs out, and then slowly and reluctantly remove their masterworks
until the other routines have enough memory to run. So the game won't
run out of memory, but only just. It's very tight.

--
Check out my hobby project.
http://malcolmmclean.github.io/babyxrc

Anton Shepelev <anton.txt@g{oogle}mail.com> writes:

> Ben Bacarisse to Malcolm McLean:
>
>> [next is a comment from Malcolm]
>>
>>> 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.
>
> I think it is a modern English idiom, which I dislike as
> well. StackOverflow is full of questions starting like:
> "How do you do this?" and "How do I do that?" They are
> informal ways of the more literary "How does one do this?"
> or "What is the way to do that?"

I have a different take here. First the "your" of "your
strategy" reads as a definite pronoun, meaning it refers
specifically to Ben and not to some unknown other party.
(And incidentally is subtly insulting because of that,
whether it was meant that way or not.)

Second the use of "you" to mean an unspecified other person
is not idiom but standard usage. The word "you" is both a
definite pronoun and an indefinite pronoun, depending on
context. The word "they" also has this property. Consider
these two examples:

The bank downtown was robbed. They haven't been caught
yet.

They say the sheriff isn't going to run for re-election.

In the first example "they" is a definite pronoun, referring
to the people who robbed the bank. In the second example,
"they" is an indefinite pronoun, referring to unspecified
people in general (perhaps but not necessarily everyone).
The word "you" is similar: it can mean specifically the
listener, or it can mean generically anyone in a broader
audience, even those who never hear or read the statement
with "you" in it.

The word "one" used as a pronoun is more formal, and to me
at least often sounds stilted. In US English "one" is most
often an indefinite pronoun, either second person or third
person. But "one" can also be used as a first person
definite pronoun (referring to the speaker), which an online
reference tells me is chiefly British English. (I would
guess that this usage predominates in "the Queen's English"
dialect of English, but I have very little experience in
such things.)

Finally I would normally read "I" as a first person definite
pronoun, and not an indefinite pronoun. So I don't have any
problem with someone saying "how should I ..." when asking
for advice. They aren't asking how someone else should ...
but how they should ..., and what advice I might give could
very well depend on who is doing the asking.