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

[Robert Latest]

On 6 May 2006 03:08:17 -0700,
Ion Gaztañaga <ig********@gma il.com> wrote
in Msg. <11************ **********@i39g 2000cwa.googleg roups.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********@gma il.com> wrote
in Msg. <11************ **********@i39g 2000cwa.googleg roups.com>

allocate_at_lea st(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************ *************** *******@syrcnyr drs-02-ge0.nyroc.rr.co m>

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_lea st(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.ne t>,
Robert Latest <bo*******@yaho o.com> wrote:

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

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********@gma il.com> wrote in message
news:11******** *************@j 33g2000cwa.goog legroups.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********@gma il.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,efficien cy,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********@gma il.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