sizeof([ALLOCATED MEMORY])

[ballpointpenthief]

If I have malloc()'ed a pointer and want to read from it as if it were
an array, I need to know that I won't be reading past the last index.

If this is a pointer to a pointer, a common technique seems to be
setting a NULL pointer to the end of the list, and here we know that
the allocated memory has been exhausted. All good.

When this is a pointer to another type, say int, I could have a
variable that records how much memory is being allocated and use that
to track the size of the 'array'.
Alternatively, we could set the end of the 'array' to some kind of
error-code, such as 99 or MAX_INT.
I don't like either of these techniques.

So, what is a good way to stop a loop reading or writing past the
memory allocated to a pointer?
Or if possible, what is a good way of determining the size of memory
allocated to a pointer?

Cheers,
Matt

[Richard Heathfield]

ballpointpenthief said:

If I have malloc()'ed a pointer and want to read from it as if it were
an array, I need to know that I won't be reading past the last index.

When you allocate the memory, you know precisely how much memory you are
requesting.

Don't Forget (tm).

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)

[Chris McDonald]

"ballpointpenthief" <Ma*************@gmail.com> writes:

So, what is a good way to stop a loop reading or writing past the
memory allocated to a pointer?
Or if possible, what is a good way of determining the size of memory
allocated to a pointer?

Your code allocated the memory.
Your code should remember how much it allocated.

--
Chris.

[Joe Smith]

"Chris McDonald" <ch***@csse.uwa.edu.au> wrote

"ballpointpenthief" <Ma*************@gmail.com> writes:

So, what is a good way to stop a loop reading or writing past the
memory allocated to a pointer?
Or if possible, what is a good way of determining the size of memory
allocated to a pointer?

Your code allocated the memory.
Your code should remember how much it allocated.

If I understand what I've learned today, if one has a differing module other
than the one in which
p = malloc(some number);
is declared and in which memory is a burning question, then ones source
needs to declare and pass. Joe
---------
A guy says to me yesterday, if Washington hadn't crossed the Delaware in
___, then we would be paying taxes to the Queen.
But I like Elizabeth.

[Chris McDonald]

"Joe Smith" <gr**********@netzero.net> writes:

"Chris McDonald" <ch***@csse.uwa.edu.au> wrote

"ballpointpenthief" <Ma*************@gmail.com> writes:

So, what is a good way to stop a loop reading or writing past the
memory allocated to a pointer?
Or if possible, what is a good way of determining the size of memory
allocated to a pointer?
Your code allocated the memory.
Your code should remember how much it allocated.

If I understand what I've learned today, if one has a differing module other
than the one in which
p = malloc(some number);
is declared and in which memory is a burning question, then ones source
needs to declare and pass. Joe

(now, If I'm understanding you correctly) Yes, if some other code (for
which you perhaps don't have the code) performs the allocation, then if
your code needs to iterate over the memory, your code needs to know the
allocated size.

You will typically need to indicate how much memory the other routine
should allocate, or it should inform your code how much it did allocate.

In short, you cannot determine the allocated size, from the allocated
memory itself.

--
Chris.

[CBFalconer]

Chris McDonald wrote:

"Joe Smith" <gr**********@netzero.net> writes:

"Chris McDonald" <ch***@csse.uwa.edu.au> wrote

.... snip ...
Your code allocated the memory.
Your code should remember how much it allocated.

If I understand what I've learned today, if one has a differing
module other than the one in which
p = malloc(some number);
is declared and in which memory is a burning question, then ones
source needs to declare and pass. Joe

.... snip ...
In short, you cannot determine the allocated size, from the
allocated memory itself.

However, you can determine how much memory is needed by some means
or other, and perform a realloc to that size. This can lead to
snarling dogs playing tug-of-war.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

[Howard Hinnant]

In article <eJ******************************@bt.com>,
Richard Heathfield <in*****@invalid.invalid> wrote:

ballpointpenthief said:

If I have malloc()'ed a pointer and want to read from it as if it were
an array, I need to know that I won't be reading past the last index.

When you allocate the memory, you know precisely how much memory you are
requesting.

Don't Forget (tm).

However when you allocate the memory, you don't know precisely how much
you received. It could be more than you requested. And common
applications exist which could make use of that extra memory if only
they knew it existed (e.g. a dynamic array).

Major OS's provide this functionality in a non-portable fashion. Imho C
should provide a portable layer over this functionality.

-Howard

[Nils O. Selåsdal]

Howard Hinnant wrote:

In article <eJ******************************@bt.com>,
Richard Heathfield <in*****@invalid.invalid> wrote:

ballpointpenthief said:

If I have malloc()'ed a pointer and want to read from it as if it were
an array, I need to know that I won't be reading past the last index. When you allocate the memory, you know precisely how much memory you are
requesting.

Don't Forget (tm).

However when you allocate the memory, you don't know precisely how much
you received. It could be more than you requested. And common
applications exist which could make use of that extra memory if only
they knew it existed (e.g. a dynamic array).

Why would they make use of more memory than they requested instead of
just requesting that much memory in the first place ?
Major OS's provide this functionality in a non-portable fashion. Imho C
should provide a portable layer over this functionality.

No.
How horrible.

[Howard Hinnant]

In article <44********@news.wineasy.se>,
"Nils O. Selåsdal" <no******@asgaard.homelinux.org> wrote:

However when you allocate the memory, you don't know precisely how much
you received. It could be more than you requested. And common
applications exist which could make use of that extra memory if only
they knew it existed (e.g. a dynamic array).

Why would they make use of more memory than they requested instead of
just requesting that much memory in the first place ?

Perhaps I should elucidate "dynamic array".

Consider a general purpose library which manages an array of short.
This array has a length to be determined at run time, and that length
can grow or shrink over the lifetime of the array via functions such as
"insert", "resize" or "append".

A typical use case might be:

struct array_of_short
{
short* data;
size_t size;
};

array_of_short my_array = create_array_short(N);
// ...
// Fill my_array with values and do some computation with it
// ...
if (some_condition)
{
append_array_short(&my_array, M, value);
// ...
// continue computation with modified array
// ...
}

The data structure as described above has an efficiency concern:
Repeated growth in size can lead to quadratic expense due to continually
reallocating for a slightly larger size. A well known fix is to have
the array keep track of both a logical size and a physical capacity
which it can cheaply grow into:

struct array_of_short
{
short* data;
size_t size;
size_t capacity;
};

Use as before, but this new struct has an invariant: size <= capacity.

"append_array_short" and its brethren can now increase the size very
rapidly if the new size is still less than the capacity. When the new
size is greater than the capacity, these functions can reallocate the
capacity at a geometric rate (say by some growth factor between 1.5 and
2, (1+sqrt(5))/2 has been theorized as an optimum growth factor). Using
a geometric growth factor for the capacity bounds the number of
reallocations that a given array will see over its lifetime to a very
small number (compared to an incremental growth strategy).

No matter what the growth strategy for capacity, its existence is a
major motivation for finding out the amount of memory actually
allocated. create_array_short(N) may request only N*sizeof(short)
bytes, but may receive slightly more than that (for alignment purposes
or whatever). If create_array_short(N) had some way to find out how
much memory it actually received, then it makes perfect sense to set
capacity to size_received/sizeof(short) instead of to N. It makes for
higher performing code in the average case.

-Howard

[Kelsey Bjarnason]

[snips]

On Thu, 04 May 2006 14:18:31 +0000, Howard Hinnant wrote:

The data structure as described above has an efficiency concern:
Repeated growth in size can lead to quadratic expense due to continually
reallocating for a slightly larger size.

So don't do that. In simplest terms, don't add, multiply.

Assume you're adding, oh, 100 elements at each step, and starting with
1000. I'm not going to add, I'm going to scale, by 25%. By the time
you've _doubled_ your storage, mine's gone up by a factor of almost ten,
yet the _worst_ waste I will ever have is 25% of the total elements, minus
one element.

Other scaling factors work, too. Need to be more conservative? Scale by
5 or 10 per cent. Need memory to grow faster? Try 50%. Or even 100%.

Increasing by a static amount - adding 100 units at each step, etc -
strikes me as a tad silly.

[Howard Hinnant]

In article <pa****************************@gmail.com>,
Kelsey Bjarnason <kb********@gmail.com> wrote:

[snips]

On Thu, 04 May 2006 14:18:31 +0000, Howard Hinnant wrote:

The data structure as described above has an efficiency concern:
Repeated growth in size can lead to quadratic expense due to continually
reallocating for a slightly larger size.

So don't do that. In simplest terms, don't add, multiply.

Did you read my entire post or just stop here?

-Howard

[Stephen Sprunk]

"Howard Hinnant" <ho************@gmail.com> wrote in message
news:ho**********************************@syrcnyrd rs-02-ge0.nyroc.rr.com...

No matter what the growth strategy for capacity, its existence is a
major motivation for finding out the amount of memory actually
allocated. create_array_short(N) may request only N*sizeof(short)
bytes, but may receive slightly more than that (for alignment purposes
or whatever). If create_array_short(N) had some way to find out how
much memory it actually received, then it makes perfect sense to set
capacity to size_received/sizeof(short) instead of to N. It makes for
higher performing code in the average case.

You're over-optimizing here. If malloc() returns more memory than you asked
for, when you expand the array, you'll get access to it. On average, you'll
perform the same number of realloc()s with or without this optimization
unless you're expanding by a very small amount each time, in which case a
large fraction of your realloc()s will be no-ops for the implementation.

S

--
Stephen Sprunk "Stupid people surround themselves with smart
CCIE #3723 people. Smart people surround themselves with
K5SSS smart people who disagree with them." --Aaron Sorkin
*** Posted via a free Usenet account from http://www.teranews.com ***

[Stephen Sprunk]

"CBFalconer" <cb********@yahoo.com> wrote in message
news:44***************@yahoo.com...

Chris McDonald wrote:

In short, you cannot determine the allocated size, from the
allocated memory itself.

However, you can determine how much memory is needed by some means
or other, and perform a realloc to that size. This can lead to
snarling dogs playing tug-of-war.

My first thought was "how clever", but there are serious problems with this:

1. it assumes the pointer the callee received is to the start of the object
2. realloc() may relocate the object

The latter is a serious problem if you can't communicate that fact back to
the caller; it is cleaner for the interface to provide a way to indicate the
object's size to the callee in the first place so that this hack isn't
needed.

S

--
Stephen Sprunk "Stupid people surround themselves with smart
CCIE #3723 people. Smart people surround themselves with
K5SSS smart people who disagree with them." --Aaron Sorkin
*** Posted via a free Usenet account from http://www.teranews.com ***

[Howard Hinnant]

In article <44***********************@free.teranews.com>,
"Stephen Sprunk" <st*****@sprunk.org> wrote:

"Howard Hinnant" <ho************@gmail.com> wrote in message
news:ho**********************************@syrcnyrd rs-02-ge0.nyroc.rr.com...

No matter what the growth strategy for capacity, its existence is a
major motivation for finding out the amount of memory actually
allocated. create_array_short(N) may request only N*sizeof(short)
bytes, but may receive slightly more than that (for alignment purposes
or whatever). If create_array_short(N) had some way to find out how
much memory it actually received, then it makes perfect sense to set
capacity to size_received/sizeof(short) instead of to N. It makes for
higher performing code in the average case.

You're over-optimizing here. If malloc() returns more memory than you asked
for, when you expand the array, you'll get access to it. On average, you'll
perform the same number of realloc()s with or without this optimization
unless you're expanding by a very small amount each time, in which case a
large fraction of your realloc()s will be no-ops for the implementation.

Let's go through a specific example. I'm going to assume the struct I
showed before:

struct array_of_short
{
short* data;
size_t size;
size_t capacity;
};

Let's say that size == capacity == 100. Now for some reason my
algorithm decides it needs 2 more shorts. What do I do?

Today I call realloc similar to:

data = realloc(data, 3*capacity/2 * sizeof(short));

I.e. I up the capacity by 50% (or whatever growth factor you want to
use). Now under the hood lets say (and this is quite reasonable) that
the heap had already allocated 4 more bytes to data, and had another 64
bytes beyond that which it could have expanded that chunk in place. But
because my code is ignorant of the current heap structure in the
neighborhood of my pointer, the best thing I know to do is blindly ask
for a realloc expanding to 50 more shorts (assuming a 2 byte short for
this example). That in turn will trigger the heap to relocate my 200
byte array to another location.

If I had more access to the current heap structure, I could have known
that there was already room for two extra shorts allocated to me. I
could've avoided a call to realloc altogether.

Continuing along with this example: let's say instead of 2 more shorts,
my algorithm actually needed 10 more shorts. Here's my choices:

1. realloc for 10 more shorts.
2. realloc for a 50% bigger capacity.

Choice 1 risks the poor efficiency of an incremental growth strategy
(known performance problem).

Choice 2 completely wastes the 68 bytes that were sitting beyond my 200
byte buffer but had no way to find out about.

Wouldn't it be nice if I could:

A: Discover those extra 2 shorts that were allocated to me anyway.
B: Discover that I could expand in place by another 32 shorts without
the expense of relocating my array.

?

These seem like significant and obvious optimizations to me.

Indeed, I've coded them up and tested them. Given the right underlying
allocation interface one can achieve very decent performance increases
with very little effort. It won't make your code 10 times faster. But
it sure is an easy way to gain say 15% while minimizing heap
fragmentation and thrashing.

But it is only easy if you have the right allocation interface. Indeed
today the only way to achieve this type of optimization in C is to write
your own malloc/realloc/free functions (adding to the interface as
appropriate). Anyone who's written these functions (I have) knows that
this exercise can't be labeled easy.

-Howard

[Eric Sosman]

Howard Hinnant wrote On 05/04/06 17:26,:

[...]

If I had more access to the current heap structure, I could have known
that there was already room for two extra shorts allocated to me. I
could've avoided a call to realloc altogether.

IMHO, this isn't such a big deal. Or to put it another
way: if you've got an array that's (1) big enough to be a
problem and (2) expands and expands and expands and expands,
it's time to think about other data structures.

Are you familiar with any present-day file systems
that require each file to occupy contiguous disk sectors?

--
Er*********@sun.com

[Keith Thompson]

Howard Hinnant <ho************@gmail.com> writes:

In article <44***********************@free.teranews.com>,
"Stephen Sprunk" <st*****@sprunk.org> wrote:

"Howard Hinnant" <ho************@gmail.com> wrote in message
news:ho**********************************@syrcnyrd rs-02-ge0.nyroc.rr.com...

> No matter what the growth strategy for capacity, its existence is a
> major motivation for finding out the amount of memory actually
> allocated. create_array_short(N) may request only N*sizeof(short)
> bytes, but may receive slightly more than that (for alignment purposes
> or whatever). If create_array_short(N) had some way to find out how
> much memory it actually received, then it makes perfect sense to set
> capacity to size_received/sizeof(short) instead of to N. It makes for
> higher performing code in the average case.

You're over-optimizing here. If malloc() returns more memory than
you asked for, when you expand the array, you'll get access to it.
On average, you'll perform the same number of realloc()s with or
without this optimization unless you're expanding by a very small
amount each time, in which case a large fraction of your realloc()s
will be no-ops for the implementation.

Let's go through a specific example. I'm going to assume the struct I
showed before:

struct array_of_short
{
short* data;
size_t size;
size_t capacity;
};

Let's say that size == capacity == 100. Now for some reason my
algorithm decides it needs 2 more shorts. What do I do?

Today I call realloc similar to:

data = realloc(data, 3*capacity/2 * sizeof(short));

I.e. I up the capacity by 50% (or whatever growth factor you want to
use). Now under the hood lets say (and this is quite reasonable) that
the heap had already allocated 4 more bytes to data, and had another 64
bytes beyond that which it could have expanded that chunk in place. But
because my code is ignorant of the current heap structure in the
neighborhood of my pointer, the best thing I know to do is blindly ask
for a realloc expanding to 50 more shorts (assuming a 2 byte short for
this example). That in turn will trigger the heap to relocate my 200
byte array to another location.

If I had more access to the current heap structure, I could have known
that there was already room for two extra shorts allocated to me. I
could've avoided a call to realloc altogether.

No, you couldn't necessarily avoid the realloc altogether, unless the
extra memory is actually reserved. There might happen to be another
two shorts worth of storage available immediately after your allocated
space, but the system might later choose to use it for another
allocation.

More generally, if I call, say, malloc(300), the system might reserve
512 bytes for me, and might (internally) guarantee that it won't use
any of it for anything else until I call free() -- or it might
allocate 512 bytes, but remember that I only asked for 300, and later
carve out the last 128 bytes for another allocation. Or another call
to free() might result in my 300-byte allocation being at the
beginning of a contiguous chunk of 1024 bytes.

In other words, the number of bytes that are *really* reserved for a
given malloc() call isn't necessarily a meaningful question, and may
vary over time depending on things outside the program's control.

If I were going to suggest a new feature to address this (perhaps
straying off-topic a bit), I'd probably propose a new function similar
to realloc(), except that it's guaranteed not to relocate the object.
Let's call it xrealloc() (not a great name, but it will do for now).
If realloc() would have expanded or contracted the object in place,
xrealloc() is equivalent to realloc(). If realloc() would have
relocated the object, xrealloc() fails. (We wouldn't require
xrealloc() to succeed in *exactly* the same circumstances where
realloc() would expand or shrink the object in place, but it would
usually work out that way.)

If I've allocated space for 300 bytes, and I find that I need 302
bytes, I can call xrealloc(), asking for just 302 bytes. If this
succeeds, I'm done, and the call was probably very cheap. If it
fails, I can then do a more expensive realloc() call, requesting 400
or 500 bytes to leave room for future growth. And of course existing
code can ignore xrealloc() and continue to work as it always has.

This would allow an implementation to allocate more memory than you
ask for, while still permitting it to take back some of the extra
space if it needs it.

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Howard Hinnant]

In article <ln************@nuthaus.mib.org>,
Keith Thompson <ks***@mib.org> wrote:

If I had more access to the current heap structure, I could have known
that there was already room for two extra shorts allocated to me. I
could've avoided a call to realloc altogether.
No, you couldn't necessarily avoid the realloc altogether, unless the
extra memory is actually reserved. There might happen to be another
two shorts worth of storage available immediately after your allocated
space, but the system might later choose to use it for another
allocation.

There are two issues here (I'm guilty of introducing the second one in
my last post).

1. The allocator may give you extra memory for free but currently has
no way to tell you that.

2. The allocator may have extra memory located directly after what it
has allocated to you and that amount may vary with time.

In my previous example I attempted to address both of these.

I heartily agree that insight into #2 is the bigger performance win.
However, insight into #1 is practically cost free (there's a dollar on
the sidewalk, do you pick it up, or is it too much trouble to bend
over?).
If I were going to suggest a new feature to address this (perhaps
straying off-topic a bit), I'd probably propose a new function similar
to realloc(), except that it's guaranteed not to relocate the object.
Let's call it xrealloc() (not a great name, but it will do for now).
If realloc() would have expanded or contracted the object in place,
xrealloc() is equivalent to realloc(). If realloc() would have
relocated the object, xrealloc() fails. (We wouldn't require
xrealloc() to succeed in *exactly* the same circumstances where
realloc() would expand or shrink the object in place, but it would
usually work out that way.)

If I've allocated space for 300 bytes, and I find that I need 302
bytes, I can call xrealloc(), asking for just 302 bytes. If this
succeeds, I'm done, and the call was probably very cheap. If it
fails, I can then do a more expensive realloc() call, requesting 400
or 500 bytes to leave room for future growth. And of course existing
code can ignore xrealloc() and continue to work as it always has.

This would allow an implementation to allocate more memory than you
ask for, while still permitting it to take back some of the extra
space if it needs it.

I think that's an excellent idea. Perhaps there is some refinement
still to be done here. But the basic idea is fundamentally a win-win.

-Howard

[Howard Hinnant]

In article <1146780106.641149@news1nwk>,
Eric Sosman <Er*********@sun.com> wrote:

Howard Hinnant wrote On 05/04/06 17:26,:

[...]

If I had more access to the current heap structure, I could have known
that there was already room for two extra shorts allocated to me. I
could've avoided a call to realloc altogether.
IMHO, this isn't such a big deal. Or to put it another
way: if you've got an array that's (1) big enough to be a
problem and (2) expands and expands and expands and expands,
it's time to think about other data structures.

Having multiple data structures in your tool box is always a good thing.
Sometimes you need contiguous array, sometimes you need a linked list,
sometimes a hash table or tree, etc. That being said, the contiguous
array is the workhorse of data structures. It's the one I find myself
reaching for most often. Even when I have no idea how much it will grow.
Are you familiar with any present-day file systems
that require each file to occupy contiguous disk sectors?

Nope. But I am intimately familiar with an in-ram data structure which
stores a set of contiguous arrays (and makes it look contiguous). Every
once in a while it comes in very handy.

-Howard

[Keith Thompson]

Howard Hinnant <ho************@gmail.com> writes:

In article <ln************@nuthaus.mib.org>,
Keith Thompson <ks***@mib.org> wrote:

[snip xrealloc() idea]

This would allow an implementation to allocate more memory than you
ask for, while still permitting it to take back some of the extra
space if it needs it.

I think that's an excellent idea. Perhaps there is some refinement
still to be done here. But the basic idea is fundamentally a win-win.

Thanks. On the other hand, there's always the danger of creeping
featurism. The potential complexity of a memory allocation system is
nearly unbounded. For example, it might sometimes make sense to make
a request like:

I need a chunk of at least 300 bytes of data. I'll probably need
to expand it to 500 bytes later on, so reserve 500 if you can; if
not, I'll settle for 300. I *might* need to expand it to 4000
bytes eventually, so optimize for that case if you can. Tell me
how many bytes you were actually able to allocate. And I'm also
going to need to allocate a 10000 byte chunk; if you can't satisfy
that request immediately, let me exactly what my options are for
freeing other chunks of allocated memory to make that allocation
possible.

(Substitute larger sizes and/or more allocations to make this scenario
realistic on a modern non-embedded system.)

In general, you want to optimize for your program's actual usage
pattern, without necessarily knowing in advance what that's going to
be. Just defining the data structures to describe what you want and
what the system can give you would be a daunting task, let alone
actually implementing it. There has to be a tradeoff between having a
simple interface and adding more functionality.

One could argue that the C's current malloc/realloc/free interface is
the best tradeoff. A malloc/realloc/xrealloc/free interface would
certainly provide some options that don't currently exist, but it's
not clear that it would be worth the added complexity (or that it
wouldn't).

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Howard Hinnant]

In article <ln************@nuthaus.mib.org>,
Keith Thompson <ks***@mib.org> wrote:

Just defining the data structures to describe what you want and
what the system can give you would be a daunting task, let alone
actually implementing it. There has to be a tradeoff between having a
simple interface and adding more functionality.

One could argue that the C's current malloc/realloc/free interface is
the best tradeoff. A malloc/realloc/xrealloc/free interface would
certainly provide some options that don't currently exist, but it's
not clear that it would be worth the added complexity (or that it
wouldn't).

Excellent points all.

I propose that a good saddle point between complexity and simplification
is somewhere near:

1. How much memory did you actually give me?

2. You gave me a N-byte block (and thanks). I'm interested in
expanding it (in-place) to at a minimum of (N+Nmin) bytes, and perhaps
to a maximum of (N+Nmax) bytes. Can you help me do that?

3. You gave me a N-byte block (and thanks). I no longer need a large
part of this memory and would like to recycle it. Can you shrink this
block in-place such that it is no smaller than M bytes?

My proposal focuses more on the immediate, and not so much on the "what
I might change my mind to in the future". Imho, the client is better
informed to predict future needs and should pose its questions such that
it hides those details from the allocation system and just asks more
specific questions.

-Howard

[CBFalconer]

Howard Hinnant wrote:

"Stephen Sprunk" <st*****@sprunk.org> wrote:

"Howard Hinnant" <ho************@gmail.com> wrote in message

No matter what the growth strategy for capacity, its existence
is a major motivation for finding out the amount of memory
actually allocated. create_array_short(N) may request only
N*sizeof(short) bytes, but may receive slightly more than that
(for alignment purposes or whatever). If create_array_short(N)
had some way to find out how much memory it actually received,
then it makes perfect sense to set capacity to
size_received/sizeof(short) instead of to N. It makes for
higher performing code in the average case.

You're over-optimizing here. If malloc() returns more memory
than you asked for, when you expand the array, you'll get
access to it. On average, you'll perform the same number of
realloc()s with or without this optimization unless you're
expanding by a very small amount each time, in which case a
large fraction of your realloc()s will be no-ops for the
implementation.

Let's go through a specific example. I'm going to assume the
struct I showed before:

Why bother with all these gyrations? The malloc package for your
system probably understands your system better than you do, and can
take advantage of its peculiarities. As am example, here is an
excerpt from the realloc code in my nmalloc package for DJGPP,
which attempts to avoid moving data (among other things)

/* if decreasing simply reduce size and move excess to free */
if (szneed <= m->sz) {
DBGPRTR(EOL " Realloc is reducing");
if ((m->sz - szneed) >= MINSAVE) {
m = split(&m1, szneed);
mv2freelist(m1);
}
/* else just return old pointer, i.e. NOP */
}
else if (szneed > ((ulong)(INT_MAX - 65536))) {
/* reject excessive size request */
p = NULL; goto exeunt;
}
else if (ISFREE(m->next) &&
(szneed <= (m->sz + m->next->sz)) ) {
/* the 'next' block is free and adequate so use it */
DBGPRTR(EOL " Realloc is combining, next is free");
m = m1 = combinehi(m);
/* now split off the excess, if any */
if ((m->sz - szneed) >= MINSAVE) {
m = split(&m1, szneed);
mv2freelist(m1);
}
/* else m is the oversized return block */
}
else if ((lastsbrk == m->next) &&

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

[CBFalconer]

Stephen Sprunk wrote:

"CBFalconer" <cb********@yahoo.com> wrote in message

Chris McDonald wrote:

In short, you cannot determine the allocated size, from the
allocated memory itself.

However, you can determine how much memory is needed by some means
or other, and perform a realloc to that size. This can lead to
snarling dogs playing tug-of-war.

My first thought was "how clever", but there are serious problems
with this:

1. it assumes the pointer the callee received is to the start of
the object
2. realloc() may relocate the object

No it doesn't, and besides I do not recommend the strategy. There
is never any guarantee that realloc will return the same pointer.
Some systems try to.

The latter is a serious problem if you can't communicate that fact
back to the caller; it is cleaner for the interface to provide a
way to indicate the object's size to the callee in the first place
so that this hack isn't needed.

It was intended to point out the absurdity of such strategies.
Unless you are excessively amused by snarling dogs playing
tug-of-war.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

[Kelsey Bjarnason]

On Thu, 04 May 2006 16:43:00 +0000, Howard Hinnant wrote:

In article <pa****************************@gmail.com>,
Kelsey Bjarnason <kb********@gmail.com> wrote:

[snips]

On Thu, 04 May 2006 14:18:31 +0000, Howard Hinnant wrote:

> The data structure as described above has an efficiency concern:
> Repeated growth in size can lead to quadratic expense due to continually
> reallocating for a slightly larger size.

So don't do that. In simplest terms, don't add, multiply.

Did you read my entire post or just stop here?

-Howard

I read the entire thing, but it seemed little better than the original
post; it completely fails to grasp, despite the discussion of multipliers,
that they're the actual solution to the problem at hand, and it fails to
grasp the obvious point that if you need N bytes, allocate N bytes, don't
allocate n-m and pray.

It also failed to grasp a trivial solution if it's the allocations, rather
than the consumption, that is the problem: allocate once, into a single
large buffer, and dole out parcels of it yourself.

So, basically, it was a lot of text, no content. What part did I miss?

[Robert Latest]

On 2006-05-04, Keith Thompson <ks***@mib.org> wrote:

If I were going to suggest a new feature to address this (perhaps
straying off-topic a bit), I'd probably propose a new function similar
to realloc(), except that it's guaranteed not to relocate the object.
Let's call it xrealloc() (not a great name, but it will do for now).
If realloc() would have expanded or contracted the object in place,
xrealloc() is equivalent to realloc(). If realloc() would have
relocated the object, xrealloc() fails. (We wouldn't require
xrealloc() to succeed in *exactly* the same circumstances where
realloc() would expand or shrink the object in place, but it would
usually work out that way.)

If I've allocated space for 300 bytes, and I find that I need 302
bytes, I can call xrealloc(), asking for just 302 bytes. If this
succeeds, I'm done, and the call was probably very cheap. If it
fails, I can then do a more expensive realloc() call, requesting 400
or 500 bytes to leave room for future growth. And of course existing
code can ignore xrealloc() and continue to work as it always has.

This would allow an implementation to allocate more memory than you
ask for, while still permitting it to take back some of the extra
space if it needs it.

Well, I really can't see much of a point in this. Either you need
memory or you don't. Your proposed xrealloc() thing would make
programs behave like on a bazaar: "I'd like 1000 bytes more
memory" -- "Sure, it's gonna cost you though. But you can have
300 cheap if you want". Now what can a sensible program make of
that information?

The real issue is that you can optimize memory usage only if you
know the memory management strategy of your implementation. I
can't think there of a sensible way to learn much about this from
within a C program, let alone portably. Even if it existed -- if
memory performance was such a big issue with a particular
program, I woudn't leave it up to the implementation to decide on
strategies but rather write platform-specific modules based on
solid knowledge of the underlying mechanisms.

Graphics programs come to mind as software that needs hight
memory handling performance. If you ever used Adobe Photoshop
(Windows) and Gimp (Linux) on the same hardware you know what I'm
talking about. Photoshop is incredibly fast on images that nearly
bring the system down when opened in Gimp. I don't think that
Windows' memory system is that much better; I think Photoshop has
a dedicated, hightly optimized memory handling system built in.

robert

[Howard Hinnant]

In article <sl**********************@localhost.localdomain> ,
Robert Latest <bo*******@yahoo.com> wrote:

Well, I really can't see much of a point in this. Either you need
memory or you don't. Your proposed xrealloc() thing would make
programs behave like on a bazaar: "I'd like 1000 bytes more
memory" -- "Sure, it's gonna cost you though. But you can have
300 cheap if you want". Now what can a sensible program make of
that information?
I think I see the disconnect.

Some of us seem to be discussing writing custom code for a known task at
hand. Some of us are even discussing writing custom versions of malloc:
It also failed to grasp a trivial solution if it's the allocations, rather
than the consumption, that is the problem: allocate once, into a single
large buffer, and dole out parcels of it yourself.

What I am attempting to communicate (and obviously not doing a good job
of it) is writing a reusable (or semi-reusable) library in C that models
a dynamic array. For the definition of dynamic array I'm using that
found in Wikipedia, which does a much better job of describing it than
I've done here:

http://en.wikipedia.org/wiki/Dynamic_array

If you go through the exercise of writing a reusable dynamic array in C
(as people do, e.g.
http://geta.life.uiuc.edu/~gary/prog...ca105b/Array.c ),
then you eventually end up with code that looks something like
"addToArray" found at the above link:

void
addToArray (Array array, void *element)
{
<snip>
if (array->elements == array->maxSize) {
array->maxSize *= 2;
array->array = (void **) realloc (array->array, array->maxSize
* sizeof (void *));
<snip>
}
}

(a partial listing in an attempt to respect the author's GPL copyright).

What reasonable steps can the C standard take to help the average C
programmer write a more efficient version of "addToArray"? Common
implementations of malloc/realloc/free have properties that could easily
be exploited here if only those properties were exposed (e.g. how much
free memory currently resides after the allocation pointed to by
array->array?)

The dynamic array data structure is so prevalent in software design and
use today that it warrants this kind of attention to detail.

-Howard

[Ben Pfaff]

Howard Hinnant <ho************@gmail.com> writes:

If you go through the exercise of writing a reusable dynamic array in C
(as people do, e.g.
http://geta.life.uiuc.edu/~gary/prog...ca105b/Array.c ),
then you eventually end up with code that looks something like
"addToArray" found at the above link:

I kind of like the x2nrealloc function that some GNU software
uses. It's a little more flexible and simpler to use than the
typical dynamic array. Here's the documentation:

/* If P is null, allocate a block of at least *PN such objects;
otherwise, reallocate P so that it contains more than *PN objects
each of S bytes. *PN must be nonzero unless P is null, and S must
be nonzero. Set *PN to the new number of objects, and return the
pointer to the new block. *PN is never set to zero, and the
returned pointer is never null.

Repeated reallocations are guaranteed to make progress, either by
allocating an initial block with a nonzero size, or by allocating a
larger block.

In the following implementation, nonzero sizes are doubled so that
repeated reallocations have O(N log N) overall cost rather than
O(N**2) cost, but the specification for this function does not
guarantee that sizes are doubled.

Here is an example of use:

int *p = NULL;
size_t used = 0;
size_t allocated = 0;

void
append_int (int value)
{
if (used == allocated)
p = x2nrealloc (p, &allocated, sizeof *p);
p[used++] = value;
}

This causes x2nrealloc to allocate a block of some nonzero size the
first time it is called.

To have finer-grained control over the initial size, set *PN to a
nonzero value before calling this function with P == NULL. For
example:

int *p = NULL;
size_t used = 0;
size_t allocated = 0;
size_t allocated1 = 1000;

void
append_int (int value)
{
if (used == allocated)
{
p = x2nrealloc (p, &allocated1, sizeof *p);
allocated = allocated1;
}
p[used++] = value;
}

*/

--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}

[Ben Pfaff]

Howard Hinnant <ho************@gmail.com> writes:

(a partial listing in an attempt to respect the author's GPL copyright).

The GPL[*] encourages distribution of source code, so it's a
little weird to consider a partial listing as a way of respecting
it.
[*] Which is a license, not a copyright.
--
"You call this a *C* question? What the hell are you smoking?" --Kaz

[Ion Gaztañaga]

Ben Pfaff(e)k dio:

Howard Hinnant <ho************@gmail.com> writes:

If you go through the exercise of writing a reusable dynamic array in C
(as people do, e.g.
http://geta.life.uiuc.edu/~gary/prog...ca105b/Array.c ),
then you eventually end up with code that looks something like
"addToArray" found at the above link:

I kind of like the x2nrealloc function that some GNU software
uses. It's a little more flexible and simpler to use than the
typical dynamic array. Here's the documentation:

The C reallocation feature, in my opinion, misses some important points
that make memory allocation suboptimal, and disallows some C++
features:

-> Not all objects stored in the buffer can be binary copied. An struct
can have a pointer to itself, for example. This problem is obvious when
using C allocation functions to build C++ allocators for non POD
objects. Realloc binary copies automatically data, so we can't use
realloc for non binary copyable objects. We need a memory
reallocation/allocation function that has an option to disable data
copying.

-> We can't specify both a minimum size for allocation/reallocation and
a preferred size. We have to guess a reallocation size (for example,
doubling the size). Most of the times, we need to insert N extra
objects in a buffer with S objects, and currently we call realloc
doubling the size -> S*2. However, maybe the current block can be
expanded between N and S*2. Obviously, we prefer an expansion than a
reallocation:

allocate_at_least(p
,S+N /*min size*/
,S*2 /*preferred size*/
&allocated);

The meaning: if the current block can be expanded at least to S+N, do
it, otherwise try to allocate S*2, otherwise, allocate S+N, otherwise
return 0. Checking for expansion is very cheap, and if the next block
is free with a size between N and S, we can avoid the fragmentation and
reuse that space. This makes buffer expansion more probable, minimizes
allocations and improves performance.

-> In many realloc implementations, we can't expand backwards. Imagine
the following common situation, after some allocation/deallocation
operations:

| free1 | current_buffer | free2 |

free1 and free2 are not big enough to hold S+N elements, but free1 +
current_buffer + free2 is big enough. This reallocation is very fast
(surely constant time) in most implementations (for example using a
doubly linked list of memory blocks). Apart from this, locality is
improved since the previous block can be in the same memory page. Less
size overhead, less fragmentation, more locality and avoiding an
unneeded allocation. Unconditional backwards reallocation can disallow
any reallocation for complex c++ objects (for example, objects whose
constructor can throw) if we need strong exception guarantee. So I
would make backwards expansion optional.

----

The overhead of memory allocation is in many known applications the
biggest bottleneck. Minimizing unneeded allocations and using expansion
possibilities will reduce memory usage, will improve locality and will
improve speed.

Regards,

Ion

[Malcolm]

"Howard Hinnant" <ho************@gmail.com> wrote

Some of us seem to be discussing writing custom code for a known task at
hand. Some of us are even discussing writing custom versions of malloc:
I've got a whole armoury of memory allocation routines.

It also failed to grasp a trivial solution if it's the allocations,
rather
than the consumption, that is the problem: allocate once, into a single
large buffer, and dole out parcels of it yourself.

What I am attempting to communicate (and obviously not doing a good job
of it) is writing a reusable (or semi-reusable) library in C that models
a dynamic array. For the definition of dynamic array I'm using that
found in Wikipedia, which does a much better job of describing it than
I've done here:

http://en.wikipedia.org/wiki/Dynamic_array

If you go through the exercise of writing a reusable dynamic array in C
(as people do, e.g.
http://geta.life.uiuc.edu/~gary/prog...ca105b/Array.c ),
then you eventually end up with code that looks something like
"addToArray" found at the above link:

void
addToArray (Array array, void *element)
{
<snip>
if (array->elements == array->maxSize) {
array->maxSize *= 2;
array->array = (void **) realloc (array->array, array->maxSize
* sizeof (void *));
<snip>
}
}

(a partial listing in an attempt to respect the author's GPL copyright).

What reasonable steps can the C standard take to help the average C
programmer write a more efficient version of "addToArray"? Common
implementations of malloc/realloc/free have properties that could easily
be exploited here if only those properties were exposed (e.g. how much
free memory currently resides after the allocation pointed to by
array->array?)

The dynamic array data structure is so prevalent in software design and
use today that it warrants this kind of attention to detail.

Basically you don't do it like that.
The problem is that the generic AddToArray() function has an interface which
is too clunky considering the triviality of the underlying algorithm.

The answer is that the array will represent something in the real world,
which can be encapsulated.

eg
/* keep these opaque */
typedef struct
{
char *name;
char *title;
float salary;
} EMPOYEE;

typedef struct
{
EMPLOYEE *employees;
int Nemployees;
} PAYROLL;

Expose these

int getNemployees(PAYROLL *p);
void addemployee(PAYROLL *p, char *name, char *title);
void setsalary(PAYROLL *p, char *name, float salary);
void runpayroll(PAYROLL *p);

Now we need to decide at a general level what the program will do should it
run out of memory. Maybe we want to terminate with an error message, maybe
we want to pass back a flag, maybe we want to silently suppress the error.
The place to put this logic in is after the call to realloc - and messing
about with a general function means that we need to set error handling
strategies and so forth, and the whole thing becomes very difficult to use.

There could also be other errors, such as two employees with the same name,
or unrecognised job titles. Again, it makes sense to consider what to do at
more or less the same level.

Now let's say that our program runs too slowly, because of the continuous
reallocation of massive list of employees. Again, this is the level at which
to tackle the problem, and move to a tree or linked list structure, or maybe
store in extra capacity. Again, if we are running into efficiency problems,
the solution will be determined by the other characteristics of the problem
at hand - do we need to sort the employees, is it important to allow fast
random access, do we delete as well as add employees?

--
Website www.personal.leeds.ac.uk/bgy1mm
Programming goodies.

[Howard Hinnant]

In article <lu********************@bt.com>,
"Malcolm" <re*******@btinternet.com> wrote:

The dynamic array data structure is so prevalent in software design and
use today that it warrants this kind of attention to detail.

Basically you don't do it like that.

Negating the usefulness of the dynamic array is unconvincing in the
extreme.

There are many useful data structures in modern software design. The
dynamic array is not only one of those useful data structures, it is one
of the most often used. That is not to say that it is a silver bullet
or anything like that. Indeed other data structures are often the right
choice, including the fixed size (even if the size is selected at
runtime) array.

But the dynamic array is an extremely useful data structure. It is not
always called "dynamic array". "Introduction to Algorithms" by Cormen,
Leiserson and Rivest (a very well respected book) refers to this data
structure as "dynamic table". Whatever you call it, it is a valuable
tool in the programmer's toolbox.

-Howard

[Robert Latest]

On 6 May 2006 03:08:17 -0700,
Ion Gaztañaga <ig********@gmail.com> wrote
in Msg. <11**********************@i39g2000cwa.googlegroups .com>

The overhead of memory allocation is in many known applications the
biggest bottleneck. Minimizing unneeded allocations and using expansion
possibilities will reduce memory usage, will improve locality and will
improve speed.

Absolutely, but the C language (and the C standard) is not the place for
it. If the the performance of your app hinges on efficient memory
managent, you must implement it yourself (or use an existing library).
And that is a good thing.

robert

[Robert Latest]

On 6 May 2006 03:08:17 -0700,
Ion Gaztañaga <ig********@gmail.com> wrote
in Msg. <11**********************@i39g2000cwa.googlegroups .com>

allocate_at_least(p
,S+N /*min size*/
,S*2 /*preferred size*/
&allocated);

The implementation of realloc is perfectly free to anticipate future
buffer growth in this way. Leave optimization to the implementation,
don't mandate it in the Standard.

robert

[Robert Latest]

On Fri, 05 May 2006 14:26:23 GMT,
Howard Hinnant <ho************@gmail.com> wrote
in Msg. <ho**********************************@syrcnyrdrs-02-ge0.nyroc.rr.com>

What reasonable steps can the C standard take to help the average C
programmer write a more efficient version of [...]

It can't, and it shouldn't. Efficiency is beyond the scope of the C
language definition.

robert

[Ion Gaztañaga]

> Absolutely, but the C language (and the C standard) is not the place for

it. If the the performance of your app hinges on efficient memory
managent, you must implement it yourself (or use an existing library).
And that is a good thing.

Why not? If the C standard can offer a better mechanism than the
actual, it's a perfect place to implement it, IMHO.

Regards,

Ion

[Ion Gaztañaga]

> > allocate_at_least(p

,S+N /*min size*/
,S*2 /*preferred size*/
&allocated);

The implementation of realloc is perfectly free to anticipate future
buffer growth in this way. Leave optimization to the implementation,
don't mandate it in the Standard.

The implementation can't know what the application needs. If you want
to insert N new objects, you have 2 choices:

-> Realloc Current + N
-> Realloc Current*2

If you choose the first you have more chances to success, but you will
suffer a lot of more memory allocation because the growing factor will
be slow. If you choose the second, you are trying to avoid
reallocations but you have less chances to succed in expansion. The
implementation can never know what's the best option.

If proposed approach, the implementation is also free to anticipate.
You request between S+N and S*2 but the implementation is free to
allocate more if it wants so. Remember that the user obtains the
reallocated size.

I have implemented this approach in C++ and I can really tell you that
there is a big performance win in some applications. Obviously, you
might argue that this is not adequate for the standard. In my opinion,
however, a good memory allocation interface is a basic building block
for a language. Specially for C, since it's a language concerned with
speed and resource usage.

Regards,

Ion

[Howard Hinnant]

In article <4c*************@individual.net>,
Robert Latest <bo*******@yahoo.com> wrote:

On Fri, 05 May 2006 14:26:23 GMT,
Howard Hinnant <ho************@gmail.com> wrote
in Msg.
<ho**********************************@syrcnyrdrs-02-ge0.nyroc.rr.com>

What reasonable steps can the C standard take to help the average C
programmer write a more efficient version of [...]

It can't, and it shouldn't. Efficiency is beyond the scope of the C
language definition.

No one is discussing mandated efficiency.

The proposal is an expanded interface giving the programmer more
information about the runtime state of his program at little or no cost.
The information does not need to be generated, it already exists. It's
just that there is currently no interface with which to obtain this
information. It has been shown that this extra information can have a
positive impact on program performance (not standard library efficiency)
if utilized. Programs that do not need or want this extra information
are free to ignore it at no cost.

If you mean that an efficient library interface is beyond the scope of
the C language definition, I think you do the creators of this
definition a disservice. Personally I'm impressed that so many aspects
of C have withstood the test of time over the past 30 years. Given all
of the advances in software development in this time frame, it could not
have done so well without a fundamentally sound and useful interface.

I believe only a small part of this interface needs a minor tweak to
keep up with changing times.

-Howard

[Stephen Sprunk]

"Ion Gaztañaga" <ig********@gmail.com> wrote in message
news:11*********************@j33g2000cwa.googlegro ups.com...

The implementation can't know what the application needs. If you want
to insert N new objects, you have 2 choices:

-> Realloc Current + N
-> Realloc Current*2

If you choose the first you have more chances to success, but you will
suffer a lot of more memory allocation because the growing factor will
be slow. If you choose the second, you are trying to avoid
reallocations but you have less chances to succed in expansion. The
implementation can never know what's the best option.

If proposed approach, the implementation is also free to anticipate.
You request between S+N and S*2 but the implementation is free to
allocate more if it wants so. Remember that the user obtains the
reallocated size.
The reality is that most C implementations only allocate memory in
power-of-two sizes, so if you do many realloc()s with a size of current+N,
the vast majority of your calls will return within a few instructions.
I have implemented this approach in C++ and I can really tell you that
there is a big performance win in some applications. Obviously, you
might argue that this is not adequate for the standard. In my opinion,
however, a good memory allocation interface is a basic building block
for a language. Specially for C, since it's a language concerned with
speed and resource usage.

All this suggestion adds to any modern implemenation is a reduction in the
number of calls to realloc(), not the amount of real work done by the user's
code or by the implementation code. If all those no-op calls actually have
a measurable impact on your application's performance, then you're free to
either tinker with the implementation's code or to insert another layer on
top of the C interface that allows you to do away with them.

Standard C provides an interface that works very well in the vast majority
of cases, but if you're not happy with it, C also allows you to do your own
thing in defiance of the standard. That's the beauty (and ugliness) of C --
you're free to ignore it and do something different if needed.

S

--
Stephen Sprunk "Stupid people surround themselves with smart
CCIE #3723 people. Smart people surround themselves with
K5SSS smart people who disagree with them." --Aaron Sorkin
*** Posted via a free Usenet account from http://www.teranews.com ***

[Ion Gaztañaga]

> The reality is that most C implementations only allocate memory in

power-of-two sizes, so if you do many realloc()s with a size of current+N,
the vast majority of your calls will return within a few instructions.
In the implementations I know, they use mixed algorithms with
merging/coalescing blocks that are not power of two. For example Doug
Lea allocator uses mixed algorithms including sizes that are not power
of two. Power of two only allocation (Kingsley type allocation) leads
to a huge memory waste, since we would waste the half of the memory in
internal fragmentation.
All this suggestion adds to any modern implemenation is a reduction in the
number of calls to realloc(), not the amount of real work done by the user's
code or by the implementation code. If all those no-op calls actually have
a measurable impact on your application's performance, then you're free to
either tinker with the implementation's code or to insert another layer on
top of the C interface that allows you to do away with them.
If I use a minimum size/preferred size approach I avoid real work. If
minimum size expansion is successful, I avoid an allocation + copy (and
fragmentation). So I'm not saving only calls but also new allocations +
copies. I'm also saving memory. It's always better to have a
minimum_size expansion than request a preferred_size (current*2)
allocation + a copy.
Standard C provides an interface that works very well in the vast majority
of cases, but if you're not happy with it, C also allows you to do your own
thing in defiance of the standard. That's the beauty (and ugliness) of C --
you're free to ignore it and do something different if needed.

You are right, but the changes in the implementation are minor. All the
information is already there: Realloc has to see if it can expand the
memory to preferred_size, so it knows current size and the maximum
expansion size. If this fails, it just has to try the same minimum
size. If that fails, it will try to allocate new memory. The size of
the block is there, so it can return it easily. Implementation of the
proposal is very easy, once we have realloc. We can change realloc in a
day to obtain this. However, programming your own allocation algorithm
is a huge work, since allocation/reallocations implementations are
complex to program and realloc will be perfectly tuned by vendors. I'm
proposing just a minor interface to get the best performance of the
already stored memory information.

Regards,

Ion

[Robert Latest]

On 2006-05-11, Ion Gaztañaga <ig********@gmail.com> wrote:

Specially for C, since it's a language concerned with
speed and resource usage.

No it isn't: (n869.txt is a late draft of C99)

$ for f in {speed,efficiency,performance,resource}; do grep $f n869.txt; done
exceptions. The programmer can achieve the efficiency of
$

robert

[Robert Latest]

On 2006-05-12, Ion Gaztañaga <ig********@gmail.com> wrote:

[ a lot of good stuff ]

You are right, and you know a lot about the subject of memory
allocation. But I think it would be wrong to burden the language
itself with these matters. Like I said before, an application
whose performance *really* depends critically on the details of
memory management should use a dedicated library that is
fine-tuned to deal with the problem at hand. The proposed
"minimum -- optimum" extension of realloc could potentially help
in this matter because it would be possible for an implementation
to provide performance-optimized memory management with this
function, but since the Standard couldn't possibly make a
statement about the performance gein, implementations would be
free to implement it as a trivial wrapper around realloc(). Which
would have gained you exactly nothing.

So if you don't need the performance just use realloc. If you
really need it, get a dedicated (and probably platform-specific)
library to do it for you.

robert

[Robert Latest]

On 2006-05-11, Howard Hinnant <ho************@gmail.com> wrote:

The proposal is an expanded interface giving the programmer more
information about the runtime state of his program at little or no cost.
The information does not need to be generated, it already exists.
Correct. The information, to remind myself and the thread in
general, is the usable size of the memory block *really* obtained
in a malloc() call.
It's
just that there is currently no interface with which to obtain this
information.
Correct.
It has been shown that this extra information can have a
positive impact on program performance (not standard library efficiency)
if utilized. Programs that do not need or want this extra information
are free to ignore it at no cost.
Correct.
If you mean that an efficient library interface is beyond the scope of
the C language definition, I think you do the creators of this
definition a disservice.
Probably.
Personally I'm impressed that so many aspects
of C have withstood the test of time over the past 30 years.
So am I.
Given all
of the advances in software development in this time frame, it could not
have done so well without a fundamentally sound and useful interface.
True. Although parts of the interface are a little braindead.
I believe only a small part of this interface needs a minor tweak to
keep up with changing times.

I would like to see it as a commonly available extension. There
is no need to put it into the language itself.

There's a funny conundrum: Let's say that the allocated size of a
memory were available to the programmer just by calling a
function on the pointer to it -- like you said, an easily
implemented feature because the information is there. This would
immediately render the interface to each and every function that
requires a "buffer size" argument to accompany a pointer to
buffer space (such as fgets()) clumsy and stupid. Like in
fgets(buffer, memsize(buffer), stream)

I would be interested to see if there is actually a sound
*technical* reason why the "allocated-size" information cannot be
made available through the C interface, such as that there could
be implementations on which this information is *not* available.

robert

[Keith Thompson]

Robert Latest <bo*******@yahoo.com> writes:

On 2006-05-11, Howard Hinnant <ho************@gmail.com> wrote:

The proposal is an expanded interface giving the programmer more
information about the runtime state of his program at little or no cost.
The information does not need to be generated, it already exists.
Correct. The information, to remind myself and the thread in
general, is the usable size of the memory block *really* obtained
in a malloc() call.

You're assuming the information is there. I can imagine that it might
be either nonexistent or meaningless in some implementations. (I
don't know enough about actual implementations to know how common this
is.)

[...]
There's a funny conundrum: Let's say that the allocated size of a
memory were available to the programmer just by calling a
function on the pointer to it -- like you said, an easily
implemented feature because the information is there. This would
immediately render the interface to each and every function that
requires a "buffer size" argument to accompany a pointer to
buffer space (such as fgets()) clumsy and stupid. Like in
fgets(buffer, memsize(buffer), stream)

Consider:
char buffer[80];
fgets(buffer, sizeof buffer, stream);
Since buffer isn't allocated by malloc(), there's no way fgets() can
determine how much space is allocated to it.

Presumably the memsize() function would invoke undefined behavior if
invoked with a pointer that doesn't point to space allocated by
malloc().

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[CBFalconer]

Robert Latest wrote:

.... snip ...
I would be interested to see if there is actually a sound
*technical* reason why the "allocated-size" information cannot be
made available through the C interface, such as that there could
be implementations on which this information is *not* available.

Yes, there is. Any such function would obviously be system
specific, which is not a problem. However it could only be called
on pointers that had been allocated via malloc in the first place.
This does not apply to most pointers.

Another reason is that a system call will obviously never be as
efficient as a single data access, which is what is required for
simply remembering.

It is conceded that we already have the limitation to malloced
pointers for calls to free and realloc. This is one of the great
insecurities of the C pointer system. It is also the sort of
limitation that, in practice, makes runtime checking impossible.

There is also no reason why the information should be available.
Consider a system in which all memory is 'use once and discard'.
Not many such exist, outside the DeathStar series.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>

[Joe Wright]

Robert Latest wrote:

On 2006-05-11, Howard Hinnant <ho************@gmail.com> wrote:

The proposal is an expanded interface giving the programmer more
information about the runtime state of his program at little or no cost.
The information does not need to be generated, it already exists.

Correct. The information, to remind myself and the thread in
general, is the usable size of the memory block *really* obtained
in a malloc() call.

It's
just that there is currently no interface with which to obtain this
information.

Correct.

It has been shown that this extra information can have a
positive impact on program performance (not standard library efficiency)
if utilized. Programs that do not need or want this extra information
are free to ignore it at no cost.

Correct.

If you mean that an efficient library interface is beyond the scope of
the C language definition, I think you do the creators of this
definition a disservice.

Probably.

Personally I'm impressed that so many aspects
of C have withstood the test of time over the past 30 years.

So am I.

Given all
of the advances in software development in this time frame, it could not
have done so well without a fundamentally sound and useful interface.

True. Although parts of the interface are a little braindead.

I believe only a small part of this interface needs a minor tweak to
keep up with changing times.

I would like to see it as a commonly available extension. There
is no need to put it into the language itself.

There's a funny conundrum: Let's say that the allocated size of a
memory were available to the programmer just by calling a
function on the pointer to it -- like you said, an easily
implemented feature because the information is there. This would
immediately render the interface to each and every function that
requires a "buffer size" argument to accompany a pointer to
buffer space (such as fgets()) clumsy and stupid. Like in
fgets(buffer, memsize(buffer), stream)

I would be interested to see if there is actually a sound
*technical* reason why the "allocated-size" information cannot be
made available through the C interface, such as that there could
be implementations on which this information is *not* available.

robert

A couple of years ago I created just such a system. It involves spoofing
such that *alloc and free call a wrapper which saves the requested size
and the returned pointer in a node in a linked list. I implemented a new
function, 'size_t size(void *);' which trips through the list, finds the
pointer and returns the size. The free() function is also wrapped such
that if the pointer is not found, it is a NOP such that attempts to
'free' wild or indeterminate pointers are blocked.

--
Joe Wright
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---

[Gordon Burditt]

>There's a funny conundrum: Let's say that the allocated size of a

memory were available to the programmer just by calling a
function on the pointer to it -- like you said, an easily
implemented feature because the information is there. This would
The information is there *FOR MALLOC'D MEMORY* and for the *beginning*
of a malloc'd buffer.
immediately render the interface to each and every function that
requires a "buffer size" argument to accompany a pointer to
buffer space (such as fgets()) clumsy and stupid. Like in
fgets(buffer, memsize(buffer), stream)
There is no rule that the pointer passed to fgets() must be obtained
from malloc(), or that you only pass a pointer to the beginning
of such an area to fgets().
I would be interested to see if there is actually a sound
*technical* reason why the "allocated-size" information cannot be
made available through the C interface, such as that there could
be implementations on which this information is *not* available.

I think trying to debug a program that uses the "allocated-size"
information incorrectly would be a problem, especially if it
malfunctions only on systems where "what-you-requested-is-what-you-get"
but the system you're testing on doesn't do that.

Note that there are systems where you cannot (at least not cheaply)
validate a pointer that supposedly came from malloc(), and you
cannot find the beginning of a block given a pointer into it. And
you can't find the size of a buffer not allocated by malloc on
almost every system.

Gordon L. Burditt

[Keith Thompson]

Joe Wright <jo********@comcast.net> writes:
[...]

A couple of years ago I created just such a system. It involves
spoofing such that *alloc and free call a wrapper which saves the
requested size and the returned pointer in a node in a linked list. I
implemented a new function, 'size_t size(void *);' which trips through
the list, finds the pointer and returns the size. The free() function
is also wrapped such that if the pointer is not found, it is a NOP
such that attempts to 'free' wild or indeterminate pointers are
blocked.

Sounds interesting. It would have been even more interesting if your
free() wrapper had indicated an error if the pointer is not found.
This could be used to discover bugs rather than just masking them.
(If your program free()s an invalid pointer, ignoring the problem
isn't likely to fix the underlying problem.)

--
Keith Thompson (The_Other_Keith) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Joe Wright]

Keith Thompson wrote:

Joe Wright <jo********@comcast.net> writes:
[...]

A couple of years ago I created just such a system. It involves
spoofing such that *alloc and free call a wrapper which saves the
requested size and the returned pointer in a node in a linked list. I
implemented a new function, 'size_t size(void *);' which trips through
the list, finds the pointer and returns the size. The free() function
is also wrapped such that if the pointer is not found, it is a NOP
such that attempts to 'free' wild or indeterminate pointers are
blocked.

Sounds interesting. It would have been even more interesting if your
free() wrapper had indicated an error if the pointer is not found.
This could be used to discover bugs rather than just masking them.
(If your program free()s an invalid pointer, ignoring the problem
isn't likely to fix the underlying problem.)

I did think about that but I am not trying to 'fix' the problem, but
rather to make it go away. You can pass any pointer you like to my
free() and if the pointer is valid, the memory is freed. If it is not,
nothing happens.

--
Joe Wright
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---

[Howard Hinnant]

In article <ln************@nuthaus.mib.org>,
Keith Thompson <ks***@mib.org> wrote:

Robert Latest <bo*******@yahoo.com> writes:

On 2006-05-11, Howard Hinnant <ho************@gmail.com> wrote:

The proposal is an expanded interface giving the programmer more
information about the runtime state of his program at little or no cost.
The information does not need to be generated, it already exists.

Correct. The information, to remind myself and the thread in
general, is the usable size of the memory block *really* obtained
in a malloc() call.

You're assuming the information is there. I can imagine that it might
be either nonexistent or meaningless in some implementations. (I
don't know enough about actual implementations to know how common this
is.)

I know. I've written commercial malloc systems for both desktop and
embedded (even bareboard) systems. If you're going to implement the C
realloc interface, you have to know the size of a pointer passed to you.
Furthermore, in such systems if the concept of adjacent blocks exists,
you can answer what the size of those blocks are, and whether or not
they are allocated. If the concept of adjacent blocks does not exist in
the allocator, then the answer to the question: Is there free memory
adjacent to this block of memory? Is: No.

It is pretty simple and cheap to answer these questions. It is
expensive not to be able to ask these questions.

-Howard

[S.Tobias]

Robert Latest <bo*******@yahoo.com> wrote:

On 2006-05-11, Ion Gaztañaga <ig********@gmail.com> wrote:

Specially for C, since it's a language concerned with
speed and resource usage.

No it isn't: (n869.txt is a late draft of C99)

$ for f in {speed,efficiency,performance,resource}; do grep $f n869.txt; done
exceptions. The programmer can achieve the efficiency of

....by using "dedicated (and probably platform-specific) libraries"?
[checking...] No.
# exceptions. The programmer can achieve the efficiency of
# translation-time evaluation through static
# initialization, such as
# const static double one_third = 1.0/3.0;
(It's part of a footnote.)

From the same text file:
# This International Standard specifies the form and
# establishes the interpretation of programs expressed in the
# programming language C. Its purpose is to promote
# portability, reliability, maintainability, and efficient
# execution of C language programs on a variety of computing
# systems.

--
Stan Tobias
mailx `echo si***@FamOuS.BedBuG.pAlS.INVALID | sed s/[[:upper:]]//g`

[CBFalconer]

Howard Hinnant wrote:

Keith Thompson <ks***@mib.org> wrote:

.... snip ...

You're assuming the information is there. I can imagine that it
might be either nonexistent or meaningless in some implementations.
(I don't know enough about actual implementations to know how
common this is.)

I know. I've written commercial malloc systems for both desktop and
embedded (even bareboard) systems. If you're going to implement the C
realloc interface, you have to know the size of a pointer passed to you.

Not necessarily. Consider the hypothetical "one time use"
allocater. realloc need only allocate a new chunk of the
appropriate size and copy the old over. It doesn't need to know
the size of the old, even for the copying if it can detect 'the
end' by some other means, analogous to encountering EOF.

The only known system that does this is the DeathStar, and then
only when it will expose coding failures.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>