Hi,
Will someone please tell me, How malloc allocating memory from heap & what
data structure it is using to do so.
regards
Ardhendu
13  2530 
"Ardhendu Nandan" <ar*************@rediffmail.com> wrote in message
news:41**************************@posting.google.c om... Hi,
Will someone please tell me, How malloc allocating memory from heap &
what data structure it is using to do so.
Check out Knuth: The art of computer programming, Vol II (IIRC).
In short, there is no *single* answer, it depends on the implementation.
There are many ways of doing this, each having a specific set of pro's and
con's.
Ardhendu Nandan wrote: Will someone please tell me,
"How does malloc allocate memory from heap
& what data structure it is using to do so."
Free storage is managed by a "free list".
The whimsical term "heap" is a pun
which old IBM programmers used to distinguish
their implementation of a free list from a stack.
malloc searches the free list for a fragment
of free storage that is large enough
to accommodate the requested allocation
and removes it from the free list.
free inserts the deallocated storage
back into the free list merging it with
any adjacent fragment(s) of free storage.
E. Robert Tisdale wrote: Ardhendu Nandan wrote:
Will someone please tell me,
"How does malloc allocate memory from heap
& what data structure it is using to do so."
Free storage is managed by a "free list".
The whimsical term "heap" is a pun
which old IBM programmers used to distinguish
their implementation of a free list from a stack.
malloc searches the free list for a fragment
of free storage that is large enough
to accommodate the requested allocation
and removes it from the free list.
free inserts the deallocated storage
back into the free list merging it with
any adjacent fragment(s) of free storage.
The term "heap" may or may not have originated with
IBM, and may or may not be a pun (if it is, it's too
subtle for me). As for the remaining points:
- Some implementations may use a "free list" to
manage dynamic memory. Some use several such
lists. Some use trees, bit-maps, or other
data structures not well described by the term
"list."
- Some malloc() implementations search for free
storage. Others simply have it ready to dole
out, without any search required.
- Some free() implementations merge the released
storage with adjacent free areas. Others do
not, or do so only in some circumstances.
The Standard specifies what the memory management
functions must do, but not how they are to do it -- this
gives the implementor wide latitude in choosing data
structures and algorithms that suit the platform well.
The choices vary, and more widely than Mr. Tisdale's
reply suggests.
-- Er*********@sun.com
Eric Sosman wrote: E. Robert Tisdale wrote:
Ardhendu Nandan wrote:
Will someone please tell me,
"How does malloc allocate memory from heap
& what data structure it is using to do so."
Free storage is managed by a "free list".
The whimsical term "heap" is a pun
which old IBM programmers used to distinguish
their implementation of a free list from a stack.
malloc searches the free list for a fragment
of free storage that is large enough
to accommodate the requested allocation
and removes it from the free list.
free inserts the deallocated storage
back into the free list merging it with
any adjacent fragment(s) of free storage.
The term "heap" may or may not have originated with
IBM, and may or may not be a pun (if it is, it's too
subtle for me). As for the remaining points:
- Some implementations may use a "free list" to
manage dynamic memory. Some use several such
lists. Some use trees, bit-maps, or other
data structures not well described by the term
"list."
- Some malloc() implementations search for free
storage. Others simply have it ready to dole
out, without any search required.
- Some free() implementations merge the released
storage with adjacent free areas. Others do
not, or do so only in some circumstances.
The Standard specifies what the memory management
functions must do, but not how they are to do it -- this
gives the implementor wide latitude in choosing data
structures and algorithms that suit the platform well.
The choices vary, and more widely than Mr. Tisdale's
reply suggests.
Examples?
E. Robert Tisdale wrote: Eric Sosman wrote:
E. Robert Tisdale wrote:
Ardhendu Nandan wrote:
Will someone please tell me,
"How does malloc allocate memory from heap
& what data structure it is using to do so."
Free storage is managed by a "free list".
The whimsical term "heap" is a pun
which old IBM programmers used to distinguish
their implementation of a free list from a stack.
malloc searches the free list for a fragment
of free storage that is large enough
to accommodate the requested allocation
and removes it from the free list.
free inserts the deallocated storage
back into the free list merging it with
any adjacent fragment(s) of free storage.
The term "heap" may or may not have originated with
IBM, and may or may not be a pun (if it is, it's too
subtle for me). As for the remaining points:
- Some implementations may use a "free list" to
manage dynamic memory. Some use several such
lists. Some use trees, bit-maps, or other
data structures not well described by the term
"list."
- Some malloc() implementations search for free
storage. Others simply have it ready to dole
out, without any search required.
- Some free() implementations merge the released
storage with adjacent free areas. Others do
not, or do so only in some circumstances.
The Standard specifies what the memory management
functions must do, but not how they are to do it -- this
gives the implementor wide latitude in choosing data
structures and algorithms that suit the platform well.
The choices vary, and more widely than Mr. Tisdale's
reply suggests.
Examples?
"Buddy system" allocators use a tree, not a list,
and coalesce adjacent freed areas only if they are
buddies (and require no search to find the adjacent
buddy, either).
"Thread-hot" allocators usually have separate data
structures for each thread or group of threads, plus
some kind of cross-thread coordination.
"Pure mmap()" allocators just grab a new memory
block from the O/S at each malloc() and return it at
each free(), without trying to keep track of allocated
and available regions at all. (Admittedly this example
is a little shaky because "the O/S" is part of "the
implementation" and is presumably doing some record-
keeping of its own. Still, it's far from certain that
the O/S keeps track of your memory with a "free list"
or anything much like it.)
-- Er*********@sun.com
Eric Sosman wrote: E. Robert Tisdale wrote:
Eric Sosman wrote:
E. Robert Tisdale wrote:
Ardhendu Nandan wrote:
>Will someone please tell me,
>"How does malloc allocate memory from heap
>& what data structure it is using to do so."
Free storage is managed by a "free list".
The whimsical term "heap" is a pun
which old IBM programmers used to distinguish
their implementation of a free list from a stack.
malloc searches the free list for a fragment
of free storage that is large enough
to accommodate the requested allocation
and removes it from the free list.
free inserts the deallocated storage
back into the free list merging it with
any adjacent fragment(s) of free storage.
The term "heap" may or may not have originated with
IBM, and may or may not be a pun (if it is, it's too
subtle for me). As for the remaining points:
- Some implementations may use a "free list" to
manage dynamic memory. Some use several such
lists. Some use trees, bit-maps, or other
data structures not well described by the term
"list."
- Some malloc() implementations search for free
storage. Others simply have it ready to dole
out, without any search required.
- Some free() implementations merge the released
storage with adjacent free areas. Others do
not, or do so only in some circumstances.
The Standard specifies what the memory management
functions must do, but not how they are to do it -- this
gives the implementor wide latitude in choosing data
structures and algorithms that suit the platform well.
The choices vary, and more widely than Mr. Tisdale's
reply suggests.
Examples?
"Buddy system" allocators use a tree, not a list,
and coalesce adjacent freed areas only if they are
buddies (and require no search to find the adjacent
buddy, either).
"Thread-hot" allocators usually have separate data
structures for each thread or group of threads, plus
some kind of cross-thread coordination.
"Pure mmap()" allocators just grab a new memory
block from the O/S at each malloc() and return it at
each free(), without trying to keep track of allocated
and available regions at all. (Admittedly this example
is a little shaky because "the O/S" is part of "the
implementation" and is presumably doing some record-
keeping of its own. Still, it's far from certain that
the O/S keeps track of your memory with a "free list"
or anything much like it.)
Actually, I was hoping that
you could name popular implementations
which did *not* use a free list.
You seem to be trying to convince someone
that a free list is not a typical, common or popular
implementation of free storage management.
Do your examples represent widely used implementations?
Or are they obscure exceptions
that are of importance to almost no one?
In article <cn**********@nntp1.jpl.nasa.gov>,
E. Robert Tisdale <E.**************@jpl.nasa.gov> wrote: malloc searches the free list for a fragment
of free storage that is large enough
to accommodate the requested allocation
and removes it from the free list.
Free lists do not necessarily have to be searched. Implementations
that always allocate, say, power-of-two sized blocks are likely to use
a list for each size, so that no searching is needed. I believe that
the implementations on the machines I am using to post this message
have that property.
-- Richard
Eric Sosman <er*********@sun.com> wrote: E. Robert Tisdale wrote:
The whimsical term "heap" is a pun
which old IBM programmers used to distinguish
their implementation of a free list from a stack.
The term "heap" may or may not have originated with
IBM, and may or may not be a pun (if it is, it's too
subtle for me).
Or too blunt. A heap is very like a stack, only less neatly structured.
Richard
E. Robert Tisdale wrote:
Actually, I was hoping that
you could name popular implementations
which did *not* use a free list.
You seem to be trying to convince someone
that a free list is not a typical, common or popular
implementation of free storage management.
Do your examples represent widely used implementations?
Or are they obscure exceptions
that are of importance to almost no one?
What I seem to be doing is only partly under my
control; the eye of the beholder has much to do with
it. My intent was to refute your implication that
all malloc()/etc. implementations (1) used free lists,
(2) conducted searches through them, and (3) combined
adjacent free areas.
The "obscure exceptions" include Solaris (which
provides about half a dozen different implementations
with different data structures and different trade-
offs), the Hoard thread-optimized memory allocator,
and (I'm led to believe) at least some of the Linux
library implementations. Whether these are "of
importance" is another eye-of-the-beholder matter.
Let me turn the question around: Can you come up
with a non-"obscure" C implementation that *does* use
a mere list to manage its memory? Whether you call it
"bloat" or "scale," implementations today are called
upon to manage far more memory than those of even five
years ago, never mind those of earlier times. O(N)
methods that were tolerable on 16-bit machines began
to show strain (and began to be replaced) in 32-bit
environments, and are simply not tenable in the 64-bit
world. All the major implementors have faced this
problem over the last couple decades, and I would be
frankly astonished if any of them failed to respond by
adopting fancier data structures than the list. So, go
to it: Hunt up the malloc() implementations for Solaris,
Linux, HP-UX, Windows, AIX, OpenVMS, Tru64, ... and let
us know who's still in the Stone Age.
-- Er*********@sun.com rl*@hoekstra-uitgeverij.nl (Richard Bos) writes: Eric Sosman <er*********@sun.com> wrote:
E. Robert Tisdale wrote:
> The whimsical term "heap" is a pun
> which old IBM programmers used to distinguish
> their implementation of a free list from a stack.
The term "heap" may or may not have originated with
IBM, and may or may not be a pun (if it is, it's too
subtle for me).
Or too blunt. A heap is very like a stack, only less neatly structured.
Seems to me it's not a pun at all, just a (not entirely literal) use
of the word. To be a pun, it would have to play on a similarity in
the pronunciation of two words or phrases. Not that it matters, of
course.
--
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.
In article <ln************@nuthaus.mib.org>, Keith Thompson <ks***@mib.org> writes: rl*@hoekstra-uitgeverij.nl (Richard Bos) writes: Eric Sosman <er*********@sun.com> wrote:
The term "heap" may or may not have originated with
IBM, and may or may not be a pun (if it is, it's too
subtle for me).
Or too blunt. A heap is very like a stack, only less neatly structured.
Seems to me it's not a pun at all, just a (not entirely literal) use
of the word. To be a pun, it would have to play on a similarity in
the pronunciation of two words or phrases.
That's certainly one possible definition of "pun", but in rhetoric
and poetics technical definitions of "pun" rarely restrict the trope
to accidents of pronunciation. For example, Richard Lanham writes:
Puns come in so many different forms that one scholar (Walter
Redfern, _Puns_) confesses at the beginning of his book that he
gave up trying to identify the separate species.
(_A Handlist of Rhetorical Terms_, 2nd ed, 127)
Among the examples Lanham cites to illustrate the pun is JFK's
infamous "Ich bin ein Berliner", which is a grammatical pun, not one
of pronunciation (and an inadvertent one at that).
In Lanham's analysis the typical rhetorical pun is a "bistable
illusion" at the word level - he likens it to irony in diction. He
goes on to identify both adnominatio (playing on the sound of words)
and paronomasia (playing on the sense of words) as types of pun,
though he says antanaclasis (one word used in two contrasting senses,
or substitution of a word for its homonym, or repetition of a word
but in different senses) is "closest to the simple English pun" (127,
128, 12).
The use of "heap" derived from "stack" is arguably an example of
paronomasia. However, it strikes me as no more than an extended
metaphor. "Stack" is used because the data structure is
metaphorically a stack of items; thus the association with a heap of
items doesn't require any play on meanings of "stack". (Had "stack"
been coined in its computer usage for some other reason - say, as
some sort of acronym, or from a proper name - then we'd have a clear
case of punning.)
However, this is more a poetic than a rhetorical trope, and poetics
is a notoriously subjective field of inquiry.
--
Michael Wojcik mi************@microfocus.com
We are subdued to what we work in. (E M Forster) mw*****@newsguy.com (Michael Wojcik) wrote: Among the examples Lanham cites to illustrate the pun is JFK's
infamous "Ich bin ein Berliner", which is a grammatical pun, not one
of pronunciation (and an inadvertent one at that).
Agh... no, it isn't. Ask any Berliner.
Richard
In article <41****************@news.individual.net>, rl*@hoekstra-uitgeverij.nl (Richard Bos) writes: mw*****@newsguy.com (Michael Wojcik) wrote:
Among the examples Lanham cites to illustrate the pun is JFK's
infamous "Ich bin ein Berliner", which is a grammatical pun, not one
of pronunciation (and an inadvertent one at that).
Agh... no, it isn't. Ask any Berliner.
I don't care whether it is or not; I'm reporting Lanham's example,
not one of my own. (And yes, I've read far more discussion about
whether this was or wasn't an error, funny, etc, than I could
possibly want.)
--
Michael Wojcik mi************@microfocus.com This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics
by: Chris S. |
last post by:
Is it possible to determine how much memory is allocated by an arbitrary
Python object? There doesn't seem to be anything in the docs about this,
but considering that Python manages memory...
|
by: Roman Hartmann |
last post by:
hello,
I do have a question regarding structs. I have a struct (profil) which
has a pointer to another struct (point). The struct profil stores the
coordinates of points.
The problem is that I...
|
by: berthelot samuel |
last post by:
Hi,
I'm trying to develop an application for modeling 3D objects from
Bezier patches, but I have a memory allocation problem. Here are my
structures:
typedef struct _vector3 {
union
{
struct...
|
by: Joerg Schwerdtfeger |
last post by:
Hi folks,
how can I determine the total main-memory size and the size of free
memory available in bytes?
I tried to use mallinfo() from malloc.h - resulting some strange values
in Windows...
|
by: RoSsIaCrIiLoIA |
last post by:
why not to build
a malloc_m() and a free_m() that *check* (if memory_debug=1) if
1) there are some errors in bounds of *all* allocated arrays
from them (and trace-print the path of code that make...
|
by: Dan Nilsen |
last post by:
Hi!
I'm writing a small piece of software that basically runs on an
embedded system with a Power-PC cpu. This runs on a stripped down
version of Linux - Busybox.
As I'm writing a piece of...
|
by: Johan Tibell |
last post by:
I've written a piece of code that uses sockets a lot (I know that
sockets aren't portable C, this is not a question about sockets per
se). Much of my code ended up looking like this:
if...
|
by: Ken |
last post by:
In C programming, I want to know in what situations we should use
static memory allocation instead of dynamic memory allocation. My
understanding is that static memory allocation like using array...
|
by: Peterwkc |
last post by:
Hello all expert, i have two program which make me desperate bu after i have noticed the forum, my future is become brightness back.
By the way, my problem is like this i the first program was...
|
by: jeungster |
last post by:
Hello,
I'm trying to track down a memory issue with a C++ application that
I'm working on:
In a nutshell, the resident memory usage of my program continues to
grow as the program runs. It...
|
by: emmanuelkatto |
last post by:
Hi All, I am Emmanuel katto from Uganda. I want to ask what challenges you've faced while migrating a website to cloud.
Please let me know.
Thanks!
Emmanuel
|
by: BarryA |
last post by:
What are the essential steps and strategies outlined in the Data Structures and Algorithms (DSA) roadmap for aspiring data scientists? How can individuals effectively utilize this roadmap to progress...
|
by: nemocccc |
last post by:
hello, everyone, I want to develop a software for my android phone for daily needs, any suggestions?
|
by: Sonnysonu |
last post by:
This is the data of csv file
1 2 3
1 2 3
1 2 3
1 2 3
2 3
2 3
3
the lengths should be different i have to store the data by column-wise with in the specific length.
suppose the i have to...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
|
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and...
| |
