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

[Howard Hinnant]

In article <44***************@yahoo.com>,
CBFalconer <cb********@yahoo.com> wrote:

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.

I never said that sizeof_alloc(p) should have O(1) complexity. That
indeed would be over constraining. The "one time use" allocator still
must know the sizeof_alloc(p) in order to realloc; in the same way that
strlen(s) knows the size of the string s. One way or another, it must
know the size of the old memory to copy.

The smart interface would combine an allocation (e.g. malloc), with the
size query, so that an efficient implementation is more likely:

I'm requesting N bytes. Please give me the pointer (if able) and the
actual number of bytes it is pointing to.

-Howard

[CBFalconer]

Howard Hinnant wrote:

In article <44***************@yahoo.com>,
CBFalconer <cb********@yahoo.com> wrote:

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.

I never said that sizeof_alloc(p) should have O(1) complexity. That
indeed would be over constraining. The "one time use" allocator still
must know the sizeof_alloc(p) in order to realloc; in the same way that
strlen(s) knows the size of the string s. One way or another, it must
know the size of the old memory to copy.

Read again please. I postulated a copy mechanism that detected the
equivalent of EOF. Much like:

while (*dest++ = *source++) continue;

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

[Tomás]

CBFalconer posted:

while (*dest++ = *source++) continue;

Redundant, yet nonetheless depictive, use of "continue".

I wonder, however, if it would hinder the compiler's optimization?
-Tomás

[pete]

Tomás wrote:

CBFalconer posted:

while (*dest++ = *source++) continue;

Redundant, yet nonetheless depictive, use of "continue".

There are some style guidlines against writing code like this:
while (*dest++ = *source++);
because it looks like an accident.

Myself, I would write that this way:
do {
*dest = *source++;
} while (*dest++ != 0);

I'm not into cramming vertical space.

--
pete

[Tomás]

pete posted:

There are some style guidlines against writing code like this:
while (*dest++ = *source++);
because it looks like an accident.

while (*dest++ = *source++); /* Not an accident */

;)

Myself, I would write that this way:
do {
*dest = *source++;
} while (*dest++ != 0);

More than one way to skin a cat. If I were looking for the most efficient
way, I'd use the "register" keyword for "dest" and "source", and I'd
probably do the following:

while ( *dest = *source ) ++dest, ++source;

This would remove the redundant last incrementation.

-Tomás

[pete]

Tomás wrote:

More than one way to skin a cat.
If I were looking for the most efficient way,
I'd use the "register" keyword for "dest" and "source",
I don't use the register keyword.

"Smaller, faster programs can be expected if register
declarations are used appropriately, but future improvements
in code generation may render them unnecessary."
-- K&R, A 8.1, 1978
and I'd probably do the following:

while ( *dest = *source ) ++dest, ++source;

This would remove the redundant last incrementation.

http://www.prism.uvsq.fr/~cedb/local_copies/lee.html
Optimization is simply waste of programmer time if any of these
statements are true:
parts of the program haven't been written yet
the program is not fully tested and debugged
it seems to run fast enough already

Jackson's Rules of Optimisation:
Rule 1: Don't do it.
Rule 2: (for experts only) Don't do it yet - that is, not until you
have a perfectly clear and unoptimized solution.
- Michael Jackson

--
pete

[Tomás]

pete posted:

Jackson's Rules of Optimisation:
Rule 1: Don't do it.
Rule 2: (for experts only) Don't do it yet - that is, not until you
have a perfectly clear and unoptimized solution.
- Michael Jackson

I prefer to think for myself -- I tend to be more open-minded, more
creative, more inventive, more intuitive, and more intelligent than the
person who's trying to spoon-feed me guidelines.

The following code is A-OK by me:

void Strcpy( register char* dest, register const char* source )
{
while ( *dest = *source ) ++dest, ++source;
}
You have your way of doing things, and I have mine. I'm sure we both get
the job done... but I get that extra sprinkle of satisfaction from knowing
I perfected the code to the best of my ability.

-Tomás

[Al Balmer]

On Tue, 16 May 2006 04:21:29 GMT, "Tomás" <NU**@NULL.NULL> wrote:

pete posted:

Jackson's Rules of Optimisation:
Rule 1: Don't do it.
Rule 2: (for experts only) Don't do it yet - that is, not until you
have a perfectly clear and unoptimized solution.
- Michael Jackson

Rule 2.5: It's much easier to make correct code fast than to make fast
code correct.

I prefer to think for myself -- I tend to be more open-minded, more
creative, more inventive, more intuitive, and more intelligent than the
person who's trying to spoon-feed me guidelines.

The following code is A-OK by me:

void Strcpy( register char* dest, register const char* source )
{
while ( *dest = *source ) ++dest, ++source;
}
You have your way of doing things, and I have mine. I'm sure we both get
the job done... but I get that extra sprinkle of satisfaction from knowing
I perfected the code to the best of my ability.

It's even possible that the compiler can optimize this code in spite
of your attempt to interfere ;-)

--
Al Balmer
Sun City, AZ

[Zara]

On Tue, 16 May 2006 04:21:29 GMT, "Tomás" <NU**@NULL.NULL> wrote:

pete posted:

Jackson's Rules of Optimisation:
Rule 1: Don't do it.
Rule 2: (for experts only) Don't do it yet - that is, not until you
have a perfectly clear and unoptimized solution.
- Michael Jackson

I prefer to think for myself -- I tend to be more open-minded, more
creative, more inventive, more intuitive, and more intelligent than the
person who's trying to spoon-feed me guidelines.

The following code is A-OK by me:

void Strcpy( register char* dest, register const char* source )
{
while ( *dest = *source ) ++dest, ++source;
}
You have your way of doing things, and I have mine. I'm sure we both get
the job done... but I get that extra sprinkle of satisfaction from knowing
I perfected the code to the best of my ability.

-Tomás

Well, you could be surprised to see the assembler code geenrated by
the compiler. Many timed, the followin lines give all of them the same
final code:

while ( *dest = *source ) ++dest, ++source;

for(;*dest = *source;++dest,++source);

while ( *dest++ = *source++ );

for(;*dest++ = *source++;);

None of them is the most optimal until proven woth some profiler. You
may choose your preferred style, but don't take for grnated it is the
more optimized solution. Optimum solutions may be optimum in code size
but not in speed, or the contrary, or optimum in local stack size but
not in code size, or whatever.

Profile the results of your compiler. This is not a guideline, this is
the only recognized way to find where to optimize your code.

Best regards,

Zara

[Tomás]

while ( *dest = *source ) ++dest, ++source;
This one doesn't do a redundant final incrementation.

for(;*dest = *source;++dest,++source);

Nor does this one.

while ( *dest++ = *source++ );

This one does however.

for(;*dest++ = *source++;);

As does this one.
-Tomás

[Zara]

On Tue, 16 May 2006 07:58:28 GMT, "Tomás" <NU**@NULL.NULL> wrote:

while ( *dest = *source ) ++dest, ++source;

This one doesn't do a redundant final incrementation.

for(;*dest = *source;++dest,++source);

Nor does this one.

while ( *dest++ = *source++ );

This one does however.

for(;*dest++ = *source++;);

As does this one.
-Tomás

Dont jump too fast to conclusions:

for(;*dest=*source;++dest,++source);

is compiled under one very popular compiler as the following flow in
pseudo-code

JUMPTO :TEST:
:LOOP:
READ dest
INC
STORE dest
READ source
INC source
STORE source
:TEST:
READ source
READ @source
READ dest
STORE @dest
IFNOTZERO JUMPTO :LOOP:

for(;*dest++=*source++;);

is compiled under same compiler as the following flow in pseudo-code

:LOOP:
READ source
READ @source
INC source
STORE source
READ dest
STORE @dest
INC dest
STORE @dest
IFNOTZERO JUMPTO :LOOP:

Which is more optimized in code-size and, probably, also in time.
"Let the profiler tell you" is good advice, always.

Best regards,

Zara

[CBFalconer]

"Tomás" wrote:

pete posted:

There are some style guidlines against writing code like this:
while (*dest++ = *source++);
because it looks like an accident.

while (*dest++ = *source++); /* Not an accident */

Not only have you fouled up the attributions, but you have fouled
the quote. It is considered very bad form to edit quotations. I
actually wrote:

while (*dest++ = *source++) continue;

as an analogy to something else.

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

[Flash Gordon]

Tomás wrote:

while ( *dest = *source ) ++dest, ++source;

This one doesn't do a redundant final incrementation.

for(;*dest = *source;++dest,++source);

Nor does this one.

while ( *dest++ = *source++ );

This one does however.

for(;*dest++ = *source++;);

As does this one.

Yet as was noted by the person posting them, they all produced the same
machine code thus illustrating that there is no point in selecting one
for reasons of efficiency. At least, not unless you have verified that
on your implementation it really will be more efficient.

No doubt this was in a situation where dest and source were not used
after the loop.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc

[Flash Gordon]

CBFalconer wrote:

"Tomás" wrote:

pete posted:

There are some style guidlines against writing code like this:
while (*dest++ = *source++);
because it looks like an accident.

while (*dest++ = *source++); /* Not an accident */

Not only have you fouled up the attributions, but you have fouled
the quote. It is considered very bad form to edit quotations. I
actually wrote:

while (*dest++ = *source++) continue;

as an analogy to something else.

You've made a mistake, Chuck. Tomas was replying to pete, not you, and
pete did post the quoted material.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc

[CBFalconer]

Flash Gordon wrote:

CBFalconer wrote:

"Tomás" wrote:

pete posted:

There are some style guidlines against writing code like this:
while (*dest++ = *source++);
because it looks like an accident.
while (*dest++ = *source++); /* Not an accident */

Not only have you fouled up the attributions, but you have fouled
the quote. It is considered very bad form to edit quotations. I
actually wrote:

while (*dest++ = *source++) continue;

as an analogy to something else.

You've made a mistake, Chuck. Tomas was replying to pete, not you, and
pete did post the quoted material.

Could well be. It is threaded here as a reply to me, and was
received before the pete article arrived. Netscape is known to
have anomalies when the References chain grows too long. So when I
saw that the only article with that phrase in it was mine, which
included the 'continue'. Apologies to Tomas.

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

[Tomás]

CBFalconer posted:

Apologies to Tomas.

No problem.
(Which reminds me I've to upgrade to the lastest version of XNews some
time soon... )
-Tomás

[Ion Gaztañaga]

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

For the extended malloc interface we should see how malloc is
implemented to see if size information is there and is fast to obtain.

I don't know any malloc implementation that does not store the size. So
if the size is there in all known implementations, it's logical to
propose new functions. If all known malloc implementations (check every
C library out there to check this) store the size, I think that we
should use that information to get better performance and less memory
use.

Maybe obtaining the size is not constant time in the "one time use"
allocator and you must do something similar to "strlen()", but let's be
practical: there is not such allocator in the real world, and I doubt
it will ever exist.

So let's asume that the size information is there and is very cheap to
obtain. Now we can discuss if proposed functions improve performance or
not, or they are useful enough enough to include them in the standard.
I can understand that you can think that those advanced reallocation
functions are not useful because you might never need them for general
purpose C programming. I think that memory reallocation is a common
pattern for a lot of C programs, and that there is an easy way to
improve their performance through these functions.

Regards,

Ion

[CBFalconer]

"Tomás" wrote:

CBFalconer posted:

Apologies to Tomas.

No problem.

(Which reminds me I've to upgrade to the lastest version of XNews
some time soon... )

Your posts are invariably threaded to the wrong parent, and I
suspect the reference headers are fouled and incorrectly
truncated. This could well be caused by Xnews, which I understand
to be fairly reliable in general. So I encourage the upgrade.

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

[Stephen Sprunk]

"Ion Gaztañaga" <ig********@gmail.com> wrote in message
news:11**********************@j55g2000cwa.googlegr oups.com...

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.
For the extended malloc interface we should see how malloc is
implemented to see if size information is there and is fast to obtain.

I don't know any malloc implementation that does not store the size. So
if the size is there in all known implementations, it's logical to
propose new functions. If all known malloc implementations (check every
C library out there to check this) store the size, I think that we
should use that information to get better performance and less memory
use.

<OT>
For most implementations, the size of the allocated block is trivially easy
to discover -- it's usually a few bytes before the address malloc() or
realloc() returns. Check the implementations that you care about, put in
#ifdefs that detect those implementations and deal with them, and leave in
some portable code to handle everything else.
</OT>
Maybe obtaining the size is not constant time in the "one time use"
allocator and you must do something similar to "strlen()", but let's be
practical: there is not such allocator in the real world, and I doubt
it will ever exist.

IIRC, such an allocator was recommended on clc the other day to someone
whose normal malloc() didn't fit on an embedded system with only a few kB of
memory. I'm pretty sure someone, somewhere has implemented such before
because it's useful in certain cases.

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

[Herbert Rosenau]

On Tue, 16 May 2006 07:58:28 UTC, "Tomßs" <NU**@NULL.NULL> wrote:

while ( *dest = *source ) ++dest, ++source;
This one doesn't do a redundant final incrementation.

Says who? One of the mashines I had do use such loop it had an extra
cost of dest--, source--; at the end of the loop. The cause: the
mashine had an mashine code like

*dest++ = *source++;

as single memory to memory instruction, but not equivalent without the
increments.
So to get the final pointers right both hand needed an separate
decrement to fit the "as if" clause.

for(;*dest = *source;++dest,++source);

Nor does this one.

Says who? See above.

while ( *dest++ = *source++ );

This one does however.

Best optimum because 'as if' qualifies as 'really done'. Except: don't
save spaces!
while (*dest++ = *source++) ;
= that little space helps to see that
the body is empty. More readable would be: bring the semicolon on the
next line on one more indention.

for(;*dest++ = *source++;);

As does this one.

Yep.

As I found out since about 1990: save typing but don't save on
meaningfull comments so good as possible and let the copiler do the
optimising on mashine code level. It will do better as you ever will
get it in acceptable time.

Meaningfull comments needed for maintenance after haing the code
untouched for 12 month or longer. Save typing means: write compact
code without consideration of beginners in programming but don't
require with real experts with more than 5 years extensive experience.

Don't mircro optimazion by hand because the next compiler version may
turn back that in its absolute contrary. Rethink the algorithm you use
will give a better optimazion anyway.

Use the highest possible warning level even on the final compile with
highest optimazion, remove any diagnostic the compiler may give by
resolving the cause - but use casts only when you have rethinking the
logic and you knows exactly that you knows absolutely that you knows
exactly why you have to cast and there is nothing else that can be
done, but never cast when it is only to get the compiler quiet.

--
Tschau/Bye
Herbert

Visit http://www.ecomstation.de the home of german eComStation
eComStation 1.2 Deutsch ist da!

[Default User]

CBFalconer wrote:

"Tomás" wrote:

CBFalconer posted:

Apologies to Tomas.

No problem.

(Which reminds me I've to upgrade to the lastest version of XNews
some time soon... )

Your posts are invariably threaded to the wrong parent, and I
suspect the reference headers are fouled and incorrectly
truncated. This could well be caused by Xnews, which I understand
to be fairly reliable in general. So I encourage the upgrade.

Hmmm. Doing a quick look at the entire thread, Tomas's messages seem to
be properly threaded for me.


Brian

[CBFalconer]

Default User wrote:

CBFalconer wrote:

"Tomás" wrote:

CBFalconer posted:

> Apologies to Tomas.

No problem.

(Which reminds me I've to upgrade to the lastest version of XNews
some time soon... )

Your posts are invariably threaded to the wrong parent, and I
suspect the reference headers are fouled and incorrectly
truncated. This could well be caused by Xnews, which I understand
to be fairly reliable in general. So I encourage the upgrade.

Hmmm. Doing a quick look at the entire thread, Tomas's messages seem to
be properly threaded for me.

I now suspect it is netscapes fault here. My reply to Tomas has 21
references, your reply to me has 20 references. References are
supposed to be cut off at 20, by deleting the 2nd oldest, and it
appears NS has not done this. Then Tomas's reply ignored the last
ref linking to me, and cut things back correctly.

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

[ais523]

Ion Gaztañaga wrote:

<snip>

I don't know any malloc implementation that does not store the size.

<snip>

IIRC, DOS has system calls that act identically to malloc, realloc, and
free, except that they only accept sizes that are multiples of 16
octets (which is the alignment of the resulting pointer). It would seem
reasonable for a DOS implementation of malloc to use these system calls
to do the allocation, rounding up sizes. From the C library, unless the
size was stored separately (which would impose a performance penalty),
the size of a malloc would be impossible to determine after the malloc
had been done. Although presumably the DOS kernel itself would be
keeping track of the size somewhere, there is no portable (within DOS)
method of determining what it is. (I don't know if this method was ever
used in practice on a DOS implementation.)

(Despite the OS-specifity, I think this is ontopic because a malloc
implementation which doesn't store the size was requested.)

[Ben Pfaff]

"ais523" <ai****@bham.ac.uk> writes:

Ion Gaztaqaga wrote:

<snip>

I don't know any malloc implementation that does not store the size.

<snip>

IIRC, DOS has system calls that act identically to malloc, realloc, and
free, except that they only accept sizes that are multiples of 16
octets (which is the alignment of the resulting pointer).
[...]

Most implementations round up to some granularity, but they store
the rounded size. DOS does this too, if I recall correctly.
--
"I don't have C&V for that handy, but I've got Dan Pop."
--E. Gibbons

[CBFalconer]

ais523 wrote:

Ion Gaztañaga wrote:

<snip>

I don't know any malloc implementation that does not store the size.

<snip>

IIRC, DOS has system calls that act identically to malloc, realloc, and
free, except that they only accept sizes that are multiples of 16
octets (which is the alignment of the resulting pointer). It would seem
reasonable for a DOS implementation of malloc to use these system calls
to do the allocation, rounding up sizes. From the C library, unless the
size was stored separately (which would impose a performance penalty),
the size of a malloc would be impossible to determine after the malloc
had been done. Although presumably the DOS kernel itself would be
keeping track of the size somewhere, there is no portable (within DOS)
method of determining what it is. (I don't know if this method was ever
used in practice on a DOS implementation.)

(Despite the OS-specifity, I think this is ontopic because a malloc
implementation which doesn't store the size was requested.)

And you haven't found one. The DOS system stores the size in the
16 bytes immediately preceding the assigned memory, so everything
is accessible via a segment register.

--
Some informative links:
news:news.announce.newusers
http://www.geocities.com/nnqweb/
http://www.catb.org/~esr/faqs/smart-questions.html
http://www.caliburn.nl/topposting.html
http://www.netmeister.org/news/learn2quote.html