Memory Manipulation

[Tom]

I am seeking an efficient method to "clip" the front-end off a large
block of memory. For example, let's say there is a block of memory
holding 100,000 structures of "data" and you want to drop the first
20,000 structures and free that memory.

Must the program overwrite the first 80,000 structures?

for(int i = 0; i < 80000; ++i) data[i] = data[i+20000];

Followed by a realloc() call. Thus effectively clipping off the
back-end and not the front-end?

If the above is correct ... I understand realloc() can physically move
memory too. Thus moving once to overwrite and possible moving again to
free up a little memory. This seems very inefficient. Although I
suspect realloc() seldom moves memory when reducing the block size?
Probably occurs when increasing block size and only when a contiguous
block is available?

Any better ways to skin the cat?

Thanks.

[David T. Ashley]

"Tom" <Th********@earthlink.netwrote in message
news:df********************************@4ax.com...

>I am seeking an efficient method to "clip" the front-end off a large
block of memory. For example, let's say there is a block of memory
holding 100,000 structures of "data" and you want to drop the first
20,000 structures and free that memory.

Must the program overwrite the first 80,000 structures?

for(int i = 0; i < 80000; ++i) data[i] = data[i+20000];

Followed by a realloc() call. Thus effectively clipping off the
back-end and not the front-end?

If the above is correct ... I understand realloc() can physically move
memory too. Thus moving once to overwrite and possible moving again to
free up a little memory. This seems very inefficient. Although I
suspect realloc() seldom moves memory when reducing the block size?
Probably occurs when increasing block size and only when a contiguous
block is available?

There are two cats to skin (and gosh, I hesitate to use that idiom, because
I'm a cat owner):

CAT #1: MOVING LOTS OF MEMORY

The memmove() function will probably copy the memory more efficiently than
the array iteration above. It should be self-evident how to obtain the
pointers to pass to this function in 'C'.

CAT #2: DATA STRUCTURE

As best I know there is no standard 'C' function to effectively modify the
start address of a memory block in the way you wish.

An obvious solution is to store the array elements in the reverse order as
you've assumed above, then you can simply realloc() away the last 20,000
elements.

The most common approach in 'C' for this problem is to store an array of
pointers to the objects (and for this to be effective, a pointer has to be
much smaller than a data object). Then, the pointers are manipulated rather
than the actual data.

However, 1 realloc() and 20,000 free()s is going to take far more time than
a copy.
------------------------------------------------------------
David T. Ashley (dt*@e3ft.com)
http://www.e3ft.com (Consulting Home Page)
http://www.dtashley.com (Personal Home Page)
http://gpl.e3ft.com (GPL Publications and Projects)

[David T. Ashley]

"Tom" <Th********@earthlink.netwrote in message
news:df********************************@4ax.com...

>
Although I
suspect realloc() seldom moves memory when reducing the block size?
Probably occurs when increasing block size and only when a contiguous
block is available?

It isn't safe to make any assumptions about the way realloc() will behave
except as documented.

Your assumptions are probably reasonable, especially the decreasing block
size assumption, but ... the documented interface is the documented
interface.

------------------------------------------------------------
David T. Ashley (dt*@e3ft.com)
http://www.e3ft.com (Consulting Home Page)
http://www.dtashley.com (Personal Home Page)
http://gpl.e3ft.com (GPL Publications and Projects)

[sam_cit]

>
CAT #1: MOVING LOTS OF MEMORY

The memmove() function will probably copy the memory more efficiently than
the array iteration above. It should be self-evident how to obtain the
pointers to pass to this function in 'C'.

memmove() just moves the contents of the memory pointed by the
pointeers, however it doesn't free anything, which should be taken care
explicitly...

[Malcolm McLean]

"Tom" <Th********@earthlink.netwrote in message

>I am seeking an efficient method to "clip" the front-end off a large
block of memory. For example, let's say there is a block of memory
holding 100,000 structures of "data" and you want to drop the first
20,000 structures and free that memory.

Must the program overwrite the first 80,000 structures?

for(int i = 0; i < 80000; ++i) data[i] = data[i+20000];

Followed by a realloc() call. Thus effectively clipping off the
back-end and not the front-end?

If the above is correct ... I understand realloc() can physically move
memory too. Thus moving once to overwrite and possible moving again to
free up a little memory. This seems very inefficient. Although I
suspect realloc() seldom moves memory when reducing the block size?
Probably occurs when increasing block size and only when a contiguous
block is available?

Any better ways to skin the cat?

Realloc clips off the back. There is no standard library function to
reallocate whilst clipping off the front, so you have to to a memmove()
first followed by realloc(). Potentially you are copying the data twice.

There are three routes.

1) Use a different data structure. eg linked list rather than a big array.
This is probbaly the best answer.

2) Write your own malloc(). This isn't necessarily as bad as it seems. You
can then implent an efficient realloc_clip_front() routine.

3) Hack into the system malloc() to write realloc_clip_front(). This might
be easy but will probably be rather difficult, depending on your system. You
will have to rewrite the function to port the program.