Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   sizeof([ALLOCATED MEMORY]) (http://www.velocityreviews.com/forums/t442589-sizeof-allocated-memory.html)

ballpointpenthief 05-03-2006 12:15 AM

sizeof([ALLOCATED MEMORY])
 
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 05-03-2006 12:28 AM

Re: sizeof([ALLOCATED MEMORY])
 
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 05-03-2006 12:33 AM

Re: sizeof([ALLOCATED MEMORY])
 
"ballpointpenthief" <Matt.Smiglarski@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 05-03-2006 01:48 AM

Re: sizeof([ALLOCATED MEMORY])
 

"Chris McDonald" <chris@csse.uwa.edu.au> wrote
> "ballpointpenthief" <Matt.Smiglarski@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 05-03-2006 02:00 AM

Re: sizeof([ALLOCATED MEMORY])
 
"Joe Smith" <grumpy196884@netzero.net> writes:

>"Chris McDonald" <chris@csse.uwa.edu.au> wrote
>> "ballpointpenthief" <Matt.Smiglarski@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 05-03-2006 03:04 AM

Re: sizeof([ALLOCATED MEMORY])
 
Chris McDonald wrote:
> "Joe Smith" <grumpy196884@netzero.net> writes:
>>"Chris McDonald" <chris@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 05-03-2006 05:10 PM

Re: sizeof([ALLOCATED MEMORY])
 
In article <eJ6dnTe9u7iOZMrZnZ2dnUVZ8sydnZ2d@bt.com>,
Richard Heathfield <invalid@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

=?ISO-8859-1?Q?=22Nils_O=2E_Sel=E5sdal=22?= 05-04-2006 12:41 AM

Re: sizeof([ALLOCATED MEMORY])
 
Howard Hinnant wrote:
> In article <eJ6dnTe9u7iOZMrZnZ2dnUVZ8sydnZ2d@bt.com>,
> Richard Heathfield <invalid@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 05-04-2006 02:18 PM

Re: sizeof([ALLOCATED MEMORY])
 
In article <44594dcf$1@news.wineasy.se>,
"Nils O. Selåsdal" <noselasd@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 05-04-2006 04:32 PM

Re: sizeof([ALLOCATED MEMORY])
 
[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.




All times are GMT. The time now is 10:38 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.