Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #71967 > unrolled thread

Cheap malloc()

Back to article view | Back to comp.lang.c

Contents

  Cheap malloc() Philipp Klaus Krause <pkk@spth.de> - 2015-10-05 14:09 +0200
    Re: Cheap malloc() Robert Wessel <robertwessel2@yahoo.com> - 2015-10-05 09:52 -0500
    Re: Cheap malloc() Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-10-05 11:04 -0400
      Re: Cheap malloc() BGB <cr88192@hotmail.com> - 2015-10-05 20:36 -0500
      Re: Cheap malloc() Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-10-06 07:54 -0400
        Re: Cheap malloc() BGB <cr88192@hotmail.com> - 2015-10-06 08:06 -0500
          Re: Cheap malloc() Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-10-07 07:46 -0400
            Re: Cheap malloc() BGB <cr88192@hotmail.com> - 2015-10-07 07:35 -0500
        Re: Cheap malloc() glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-06 23:29 +0000
    Re: Cheap malloc() supercat@casperkitty.com - 2015-10-05 08:12 -0700
    Re: Cheap malloc() glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-05 16:34 +0000
      Re: Cheap malloc() Philipp Klaus Krause <pkk@spth.de> - 2015-10-07 14:50 +0200
        Re: Cheap malloc() BGB <cr88192@hotmail.com> - 2015-10-07 08:45 -0500
          Re: Cheap malloc() Philipp Klaus Krause <pkk@spth.de> - 2015-10-07 19:33 +0200
            Re: Cheap malloc() BGB <cr88192@hotmail.com> - 2015-10-07 15:40 -0500
        Re: Cheap malloc() glen herrmannsfeldt <gah@ugcs.caltech.edu> - 2015-10-08 01:10 +0000
          Re: Cheap malloc() Eric Sosman <esosman@comcast-dot-net.invalid> - 2015-10-08 08:08 -0400
    Re: Cheap malloc() Bartc <bc@freeuk.com> - 2015-10-06 13:47 +0100
      Re: Cheap malloc() Philipp Klaus Krause <pkk@spth.de> - 2015-10-07 14:48 +0200

#71967 — Cheap malloc()

The classic malloc() implementation seems to be a linked list of chunks,
each chunk having a header with a pointer to the next chunk and a size
documenting how much of the current chunk is allocated, and how much is
free.
There has been research into implementations that reduce fragmentation
(e.g. best fit instead of classic first fit), or improve speed (e.g.
doubly-linked list for a faster free()). But I didn't find something on
making memory management cheaper in terms of overhead.

So I came up with the following idea, which seems quite natural to me,
but I haven't seen it anywhere else. It only stores a single pointer per
allocated block, and has thus quite low overhead.

typedef struct header XDATA header_t;

struct header
{
	header_t *next; // Next block. Linked list of all blocks, terminated by
pointer to end of heap (or to the byte beyond the end of the heap).
	header_t *next_free; // Next free block. Used in free blocks only.
Overlaps with user data in non-free blocks. Linked list of free blocks,
0-terminated.
};

header_t *XDATA __sdcc_heap_free; // First free block, 0 if no free blocks.

It uses a linked list of blocks. Each block is either allocated or free.
The list of free blocks comes and no memory cost, since it is stored in
free blocks only (well, it makes malloc() allocate at least
sizeof(header_t *), even for malloc(1) so that when we later free() the
block, we can put it into the free list, but that seems a negligible
cost to me).
This results in a resonably fast malloc(), which only needs to search
through the list of free blocks at very low overhead.

Are there other malloc() implementations with such low overhead around?

Philipp

P.S.: The malloc() is intended to replace the current one in SDCC, and
thus is intended to work well for SDCC's target architectures - 8-bit
with no alignment restrictions, typically 128B to 64KB of RAM; the XDATA
is defined as a named address space for sometarget architectures (8051
and related).

[toc] | [next] | [standalone]

#71970

On Mon, 05 Oct 2015 14:09:14 +0200, Philipp Klaus Krause <pkk@spth.de>
wrote:

>The classic malloc() implementation seems to be a linked list of chunks,
>each chunk having a header with a pointer to the next chunk and a size
>documenting how much of the current chunk is allocated, and how much is
>free.
>There has been research into implementations that reduce fragmentation
>(e.g. best fit instead of classic first fit), or improve speed (e.g.
>doubly-linked list for a faster free()). But I didn't find something on
>making memory management cheaper in terms of overhead.
>
>So I came up with the following idea, which seems quite natural to me,
>but I haven't seen it anywhere else. It only stores a single pointer per
>allocated block, and has thus quite low overhead.
>
>typedef struct header XDATA header_t;
>
>struct header
>{
>	header_t *next; // Next block. Linked list of all blocks, terminated by
>pointer to end of heap (or to the byte beyond the end of the heap).
>	header_t *next_free; // Next free block. Used in free blocks only.
>Overlaps with user data in non-free blocks. Linked list of free blocks,
>0-terminated.
>};
>
>header_t *XDATA __sdcc_heap_free; // First free block, 0 if no free blocks.
>
>It uses a linked list of blocks. Each block is either allocated or free.
>The list of free blocks comes and no memory cost, since it is stored in
>free blocks only (well, it makes malloc() allocate at least
>sizeof(header_t *), even for malloc(1) so that when we later free() the
>block, we can put it into the free list, but that seems a negligible
>cost to me).
>This results in a resonably fast malloc(), which only needs to search
>through the list of free blocks at very low overhead.
>
>Are there other malloc() implementations with such low overhead around?
>
>Philipp
>
>P.S.: The malloc() is intended to replace the current one in SDCC, and
>thus is intended to work well for SDCC's target architectures - 8-bit
>with no alignment restrictions, typically 128B to 64KB of RAM; the XDATA
>is defined as a named address space for sometarget architectures (8051
>and related).


A linked list of the free blocks *is* the common naive/basic heap
implementation.  And it's not fast - the list of free blocks can be
very long (although with only 64KB of memory, it can't be all that
slow).

[toc] | [prev] | [next] | [standalone]

#71971

On 10/5/2015 8:09 AM, Philipp Klaus Krause wrote:
> The classic malloc() implementation seems to be a linked list of chunks,
> each chunk having a header with a pointer to the next chunk and a size
> documenting how much of the current chunk is allocated, and how much is
> free.
> There has been research into implementations that reduce fragmentation
> (e.g. best fit instead of classic first fit), or improve speed (e.g.
> doubly-linked list for a faster free()). But I didn't find something on
> making memory management cheaper in terms of overhead.
>
> So I came up with the following idea, which seems quite natural to me,
> but I haven't seen it anywhere else. It only stores a single pointer per
> allocated block, and has thus quite low overhead.
>
> typedef struct header XDATA header_t;
>
> struct header
> {
> 	header_t *next; // Next block. Linked list of all blocks, terminated by
> pointer to end of heap (or to the byte beyond the end of the heap).
> 	header_t *next_free; // Next free block. Used in free blocks only.
> Overlaps with user data in non-free blocks. Linked list of free blocks,
> 0-terminated.
> };
>
> header_t *XDATA __sdcc_heap_free; // First free block, 0 if no free blocks.
>
> It uses a linked list of blocks. Each block is either allocated or free.
> The list of free blocks comes and no memory cost, since it is stored in
> free blocks only (well, it makes malloc() allocate at least
> sizeof(header_t *), even for malloc(1) so that when we later free() the
> block, we can put it into the free list, but that seems a negligible
> cost to me).
> This results in a resonably fast malloc(), which only needs to search
> through the list of free blocks at very low overhead.
>
> Are there other malloc() implementations with such low overhead around?
>
> Philipp
>
> P.S.: The malloc() is intended to replace the current one in SDCC, and
> thus is intended to work well for SDCC's target architectures - 8-bit
> with no alignment restrictions, typically 128B to 64KB of RAM; the XDATA
> is defined as a named address space for sometarget architectures (8051
> and related).

     With 128B of memory, I doubt that dynamic allocation is appropriate
at all.  From, oh, 8K upwards your scheme's parsimony may be worth
while, particularly if smallish allocations predominate.  In larger
memory arenas, though, all that rummaging through linked lists will
likely become intolerable.  (At a PPOE a quarter-century ago we found
linked lists too slow for memory arenas of ~4M, and wrote our own
substitutes for the vendor-supplied allocator.)

     Another strategy to consider is to chop the memory into small
"atoms" of identical size, maybe 16-64B, and use a bit vector to
record the availability of each atom.  To allocate, you search the
bit vector (a word at a time) for a suitable span of available atoms,
then flip their bits and return a pointer.  Freeing is even easier,
and coalescing adjacent freed blocks is, er, free.  The overhead
for an N-atom allocation is just N bits, although you might waste
as much as ATOMSIZE-1 bytes.  The maintenance speed may repay the
memory waste -- or may not; study your request stream.

     Other, more sophisticated schemes certainly exist, but I'm not
convinced they'd be of much use at the memory sizes you mention.

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

[toc] | [prev] | [next] | [standalone]

#72018

On 10/5/2015 10:04 AM, Eric Sosman wrote:
> On 10/5/2015 8:09 AM, Philipp Klaus Krause wrote:
>> The classic malloc() implementation seems to be a linked list of chunks,
>> each chunk having a header with a pointer to the next chunk and a size
>> documenting how much of the current chunk is allocated, and how much is
>> free.
>> There has been research into implementations that reduce fragmentation
>> (e.g. best fit instead of classic first fit), or improve speed (e.g.
>> doubly-linked list for a faster free()). But I didn't find something on
>> making memory management cheaper in terms of overhead.
>>
>> So I came up with the following idea, which seems quite natural to me,
>> but I haven't seen it anywhere else. It only stores a single pointer per
>> allocated block, and has thus quite low overhead.
>>
>> typedef struct header XDATA header_t;
>>
>> struct header
>> {
>>     header_t *next; // Next block. Linked list of all blocks,
>> terminated by
>> pointer to end of heap (or to the byte beyond the end of the heap).
>>     header_t *next_free; // Next free block. Used in free blocks only.
>> Overlaps with user data in non-free blocks. Linked list of free blocks,
>> 0-terminated.
>> };
>>
>> header_t *XDATA __sdcc_heap_free; // First free block, 0 if no free
>> blocks.
>>
>> It uses a linked list of blocks. Each block is either allocated or free.
>> The list of free blocks comes and no memory cost, since it is stored in
>> free blocks only (well, it makes malloc() allocate at least
>> sizeof(header_t *), even for malloc(1) so that when we later free() the
>> block, we can put it into the free list, but that seems a negligible
>> cost to me).
>> This results in a resonably fast malloc(), which only needs to search
>> through the list of free blocks at very low overhead.
>>
>> Are there other malloc() implementations with such low overhead around?
>>
>> Philipp
>>
>> P.S.: The malloc() is intended to replace the current one in SDCC, and
>> thus is intended to work well for SDCC's target architectures - 8-bit
>> with no alignment restrictions, typically 128B to 64KB of RAM; the XDATA
>> is defined as a named address space for sometarget architectures (8051
>> and related).
>
>      With 128B of memory, I doubt that dynamic allocation is appropriate
> at all.  From, oh, 8K upwards your scheme's parsimony may be worth
> while, particularly if smallish allocations predominate.  In larger
> memory arenas, though, all that rummaging through linked lists will
> likely become intolerable.  (At a PPOE a quarter-century ago we found
> linked lists too slow for memory arenas of ~4M, and wrote our own
> substitutes for the vendor-supplied allocator.)
>

I started doing MM's mostly because the C-library malloc's would often 
wasted huge amounts of space for small allocations, and in my codebases 
small allocations came up fairly often.


>      Another strategy to consider is to chop the memory into small
> "atoms" of identical size, maybe 16-64B, and use a bit vector to
> record the availability of each atom.  To allocate, you search the
> bit vector (a word at a time) for a suitable span of available atoms,
> then flip their bits and return a pointer.  Freeing is even easier,
> and coalescing adjacent freed blocks is, er, free.  The overhead
> for an N-atom allocation is just N bits, although you might waste
> as much as ATOMSIZE-1 bytes.  The maintenance speed may repay the
> memory waste -- or may not; study your request stream.
>

this is basically how my memory allocators have tended to work for 
allocating small objects. just I had tended to call them "cells" rather 
than "atoms", but either way.

then you only need a few bits per cell.
an optimization to speed up searching was to keep track of a rover, 
which will reduce endlessly scanning over the same areas of memory 
looking for free space.

another trick was doing trickery in the searching to avoid checking bits 
in areas where it could be determined that no sufficient run could exist 
in that space.


>      Other, more sophisticated schemes certainly exist, but I'm not
> convinced they'd be of much use at the memory sizes you mention.
>

yeah.

[toc] | [prev] | [next] | [standalone]

#72039

On 10/5/2015 11:04 AM, Eric Sosman wrote:
>[...]
>      Another strategy to consider is to chop the memory into small
> "atoms" of identical size, maybe 16-64B, and use a bit vector to
> record the availability of each atom.  To allocate, you search the
> bit vector (a word at a time) for a suitable span of available atoms,
> then flip their bits and return a pointer.  Freeing is even easier,
> and coalescing adjacent freed blocks is, er, free.  The overhead
> for an N-atom allocation is just N bits, although you might waste
> as much as ATOMSIZE-1 bytes.  The maintenance speed may repay the
> memory waste -- or may not; study your request stream.

     Sorry: I omitted something here.  The scheme as described will
support `ptr = malloc(size)' but not `free(ptr)' -- you need an
`xfree(ptr, size)' instead, because the size of the allocation has
not been recorded anywhere.

     One possibility is to change the API and rely on the caller to
provide the size (he knew it when the request was made, so he
ought to know it still).  This has the possible advantage that
you can xfree() a partial allocation, something free() can't do.

     On the other hand, it may be burdensome to ask the caller
to lug the size around everywhere the pointer goes.  You can get
free() behavior back again by inflating each allocation slightly
and sticking a size word just before the payload, in a "traditional"
manner.  However, this increases the overhead -- to more (probably)
than the scheme you originally proposed, because of the bit vector.
Still, bit vector maintenance is likely to be much faster than
fiddling with the linked lists.

     Sorry for the incomplete description.

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

[toc] | [prev] | [next] | [standalone]

#72041

On 10/6/2015 6:54 AM, Eric Sosman wrote:
> On 10/5/2015 11:04 AM, Eric Sosman wrote:
>> [...]
>>      Another strategy to consider is to chop the memory into small
>> "atoms" of identical size, maybe 16-64B, and use a bit vector to
>> record the availability of each atom.  To allocate, you search the
>> bit vector (a word at a time) for a suitable span of available atoms,
>> then flip their bits and return a pointer.  Freeing is even easier,
>> and coalescing adjacent freed blocks is, er, free.  The overhead
>> for an N-atom allocation is just N bits, although you might waste
>> as much as ATOMSIZE-1 bytes.  The maintenance speed may repay the
>> memory waste -- or may not; study your request stream.
>
>      Sorry: I omitted something here.  The scheme as described will
> support `ptr = malloc(size)' but not `free(ptr)' -- you need an
> `xfree(ptr, size)' instead, because the size of the allocation has
> not been recorded anywhere.
>
>      One possibility is to change the API and rely on the caller to
> provide the size (he knew it when the request was made, so he
> ought to know it still).  This has the possible advantage that
> you can xfree() a partial allocation, something free() can't do.
>
>      On the other hand, it may be burdensome to ask the caller
> to lug the size around everywhere the pointer goes.  You can get
> free() behavior back again by inflating each allocation slightly
> and sticking a size word just before the payload, in a "traditional"
> manner.  However, this increases the overhead -- to more (probably)
> than the scheme you originally proposed, because of the bit vector.
> Still, bit vector maintenance is likely to be much faster than
> fiddling with the linked lists.
>

you can also address it by using 2 bits per cell/atom, say:
   00=free
   01=object head
   10=object body
   11=reserved/locked memory or similar.

when you free, the allocator resets the head, followed by any body bits, 
terminating when it encounters something different.

[toc] | [prev] | [next] | [standalone]

#72129

On 10/6/2015 9:06 AM, BGB wrote:
> On 10/6/2015 6:54 AM, Eric Sosman wrote:
>> On 10/5/2015 11:04 AM, Eric Sosman wrote:
>>> [...]
>>>      Another strategy to consider is to chop the memory into small
>>> "atoms" of identical size, maybe 16-64B, and use a bit vector to
>>> record the availability of each atom.  To allocate, you search the
>>> bit vector (a word at a time) for a suitable span of available atoms,
>>> then flip their bits and return a pointer.  Freeing is even easier,
>>> and coalescing adjacent freed blocks is, er, free.  The overhead
>>> for an N-atom allocation is just N bits, although you might waste
>>> as much as ATOMSIZE-1 bytes.  The maintenance speed may repay the
>>> memory waste -- or may not; study your request stream.
>>
>>      Sorry: I omitted something here.  The scheme as described will
>> support `ptr = malloc(size)' but not `free(ptr)' -- you need an
>> `xfree(ptr, size)' instead, because the size of the allocation has
>> not been recorded anywhere.
>>  [...]
>
> you can also address it by using 2 bits per cell/atom, say:
>    00=free
>    01=object head
>    10=object body
>    11=reserved/locked memory or similar.
>
> when you free, the allocator resets the head, followed by any body bits,
> terminating when it encounters something different.

     Nice.  As a small refinement, I'd suggest using two parallel
vectors of single bits rather than one vector of two-bit fields.
It's easier to check that a word is all-1's (or all-0's) than
to test whether a mixture of 1's and 0's happens to contain a
suitably-positioned 00.  Also, since each of the searches (for
free atoms or for a start-of-block atom) cares only about one of
the two bits, it will run faster if it scans twice as many per
word operation.

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

[toc] | [prev] | [next] | [standalone]

#72131

On 10/7/2015 6:46 AM, Eric Sosman wrote:
> On 10/6/2015 9:06 AM, BGB wrote:
>> On 10/6/2015 6:54 AM, Eric Sosman wrote:
>>> On 10/5/2015 11:04 AM, Eric Sosman wrote:
>>>> [...]
>>>>      Another strategy to consider is to chop the memory into small
>>>> "atoms" of identical size, maybe 16-64B, and use a bit vector to
>>>> record the availability of each atom.  To allocate, you search the
>>>> bit vector (a word at a time) for a suitable span of available atoms,
>>>> then flip their bits and return a pointer.  Freeing is even easier,
>>>> and coalescing adjacent freed blocks is, er, free.  The overhead
>>>> for an N-atom allocation is just N bits, although you might waste
>>>> as much as ATOMSIZE-1 bytes.  The maintenance speed may repay the
>>>> memory waste -- or may not; study your request stream.
>>>
>>>      Sorry: I omitted something here.  The scheme as described will
>>> support `ptr = malloc(size)' but not `free(ptr)' -- you need an
>>> `xfree(ptr, size)' instead, because the size of the allocation has
>>> not been recorded anywhere.
>>>  [...]
>>
>> you can also address it by using 2 bits per cell/atom, say:
>>    00=free
>>    01=object head
>>    10=object body
>>    11=reserved/locked memory or similar.
>>
>> when you free, the allocator resets the head, followed by any body bits,
>> terminating when it encounters something different.
>
>      Nice.  As a small refinement, I'd suggest using two parallel
> vectors of single bits rather than one vector of two-bit fields.
> It's easier to check that a word is all-1's (or all-0's) than
> to test whether a mixture of 1's and 0's happens to contain a
> suitably-positioned 00.  Also, since each of the searches (for
> free atoms or for a start-of-block atom) cares only about one of
> the two bits, it will run faster if it scans twice as many per
> word operation.
>

not certain, while block-level operations could be cheaper, working with 
individual entries could effectively double the number of shifts and 
masks needed in many cases (often both bits being checked at-once by the 
operation, vs needing to pull the bits from both maps).

it is possible to test whether a word has all 1s or all 0s in a given 
position via a mask:

ex: ((bw&0x55555555)!=0x55555555) or ((bw&0x55555555)!=0x00000000)

for checking for free atoms, both bits need to be 0, so one can do:
   (bw!=0x00000000), there are non-free atoms
or:
   (((bw|(bw>>1))&0x55555555)!=0x55555555), free atoms exist.


a person could also reorganize the entries:
   00=free
   01=reserved/locked memory or similar.
   10=object body
   11=object head

which makes a few compromises in the logic (cheaper to detect free entries).

[toc] | [prev] | [next] | [standalone]

#72096

Eric Sosman <esosman@comcast-dot-net.invalid> wrote:

(snip)

>     Sorry: I omitted something here.  The scheme as described will
> support `ptr = malloc(size)' but not `free(ptr)' -- you need an
> `xfree(ptr, size)' instead, because the size of the allocation has
> not been recorded anywhere.

As I might have noted elsewhere, this is how OS/360 GETMAIN
and FREEMAIN work.
 
>     One possibility is to change the API and rely on the caller to
> provide the size (he knew it when the request was made, so he
> ought to know it still).  This has the possible advantage that
> you can xfree() a partial allocation, something free() can't do.

and this is, it seeme to me, why they work that way.

Though GETMAIN has an additional feature that I haven't seen
discussed, and that is the variable GETMAIN. You can give
a minimum and maximum amount, and the system will find some
value in between, or fail.

That could be useful, for example, in buffers where larger buffers
would be more efficient, but only if the memory is available.
 
>     On the other hand, it may be burdensome to ask the caller
> to lug the size around everywhere the pointer goes.  You can get
> free() behavior back again by inflating each allocation slightly
> and sticking a size word just before the payload, in a "traditional"
> manner.  However, this increases the overhead -- to more (probably)
> than the scheme you originally proposed, because of the bit vector.
> Still, bit vector maintenance is likely to be much faster than
> fiddling with the linked lists.
 
>     Sorry for the incomplete description.

-- glen
 

[toc] | [prev] | [next] | [standalone]

#71972

On Monday, October 5, 2015 at 7:09:23 AM UTC-5, Philipp Klaus Krause wrote:
> There has been research into implementations that reduce fragmentation
> (e.g. best fit instead of classic first fit), or improve speed (e.g.
> doubly-linked list for a faster free()). But I didn't find something on
> making memory management cheaper in terms of overhead.

If memory-allocation code is written to optimize the performance of
certain patterns of memory usage, those patterns of usage will be faster
but other patterns will be slower.  It's not uncommon for embedded systems
to omit malloc/free entirely and replace them with alloc, mark, and release
functions such that calling "mark" will return an object which, if given
to "release", will cancel all allocations performed since the corresponding
"mark".  Such systems can achieve deterministic performance which is better
than the optimum possible mark/free, but at the expense of being unable to
release a block without releasing everything that was allocated after it.
If there is no need to do such a thing, however, mark/release has a lot of
advantages.

Another approach which can be helpful is to use memory handles, such that
the allocation function doesn't return a pointer but instead returns a
pointer to a structure that contains information about the allocation
including its current address.  An advantage of this approach is that if
code avoids keeping a copy of the physical block address during any call
that might access memory, the system can relocate blocks of memory as
needed to consolidate multiple small gaps into one larger one.

The purpose of malloc/free is not to provide the best possible means of
memory management, but rather to provide a means which will work decently
well under a wide range of conditions.  It's often possible to implement
memory allocation methods which will work better in specialized situations
than malloc/free, but malloc/free is guaranteed to exist in any hosted
environment and will be an option in most embedded environments as well.

[toc] | [prev] | [next] | [standalone]

#71983

Philipp Klaus Krause <pkk@spth.de> wrote:
> The classic malloc() implementation seems to be a linked list of chunks,
> each chunk having a header with a pointer to the next chunk and a size
> documenting how much of the current chunk is allocated, and how much is
> free.

As far as I know, that is pretty much right.

Well, the list is usually called the free list, as I believe it
describes the unallocated part. When a region is freed, it is
combined with neighboring free regions so there isn't excess
fragmentation. In the case of malloc, each allocated region
needs a length.

For another way to do it, consider OS/360 (and still in z/OS)
GETMAIN, which allows one to FREEMAIN part of an allocated block.
For FREEMAIN, you give the address and length, which might be in
the middle of a previous GETMAINed block. C doesn't have this
ability.

> There has been research into implementations that reduce fragmentation
> (e.g. best fit instead of classic first fit), or improve speed (e.g.
> doubly-linked list for a faster free()). But I didn't find something on
> making memory management cheaper in terms of overhead.

Seems to me a big problem with the classical way is that it
is horrible in a paged memory system, where the block might be
paged out. 

I have heard that there are fixes for that problem, but haven't
tried to follow them.
 
> So I came up with the following idea, which seems quite natural to me,
> but I haven't seen it anywhere else. It only stores a single pointer per
> allocated block, and has thus quite low overhead.
 
(snip of C code)

> It uses a linked list of blocks. Each block is either allocated or free.
> The list of free blocks comes and no memory cost, since it is stored in
> free blocks only (well, it makes malloc() allocate at least
> sizeof(header_t *), even for malloc(1) so that when we later free() the
> block, we can put it into the free list, but that seems a negligible
> cost to me).

> This results in a resonably fast malloc(), which only needs to search
> through the list of free blocks at very low overhead.

Searching a linked list is O(N). If you do it N times, the result
is O(N**2). It is not cache friendly or virtual memory friendly.
 
> Are there other malloc() implementations with such low overhead around?
 
> Philipp
 
> P.S.: The malloc() is intended to replace the current one in SDCC, and
> thus is intended to work well for SDCC's target architectures - 8-bit
> with no alignment restrictions, typically 128B to 64KB of RAM; the XDATA
> is defined as a named address space for sometarget architectures (8051
> and related).

OK, maybe you don't need to consider virtual memory.

-- glen

[toc] | [prev] | [next] | [standalone]

#72133

On 05.10.2015 18:34, glen herrmannsfeldt wrote:
> 
>> It uses a linked list of blocks. Each block is either allocated or free.
>> The list of free blocks comes and no memory cost, since it is stored in
>> free blocks only (well, it makes malloc() allocate at least
>> sizeof(header_t *), even for malloc(1) so that when we later free() the
>> block, we can put it into the free list, but that seems a negligible
>> cost to me).
> 
>> This results in a resonably fast malloc(), which only needs to search
>> through the list of free blocks at very low overhead.
> 
> Searching a linked list is O(N). If you do it N times, the result
> is O(N**2). It is not cache friendly or virtual memory friendly.

But as long as there is no fragmentation, malloc will work in O(1),since
the first element in the list will always be the only free block, which
will contain all free memory, making it fast.

Philipp

[toc] | [prev] | [next] | [standalone]

#72136

On 10/7/2015 7:50 AM, Philipp Klaus Krause wrote:
> On 05.10.2015 18:34, glen herrmannsfeldt wrote:
>>
>>> It uses a linked list of blocks. Each block is either allocated or free.
>>> The list of free blocks comes and no memory cost, since it is stored in
>>> free blocks only (well, it makes malloc() allocate at least
>>> sizeof(header_t *), even for malloc(1) so that when we later free() the
>>> block, we can put it into the free list, but that seems a negligible
>>> cost to me).
>>
>>> This results in a resonably fast malloc(), which only needs to search
>>> through the list of free blocks at very low overhead.
>>
>> Searching a linked list is O(N). If you do it N times, the result
>> is O(N**2). It is not cache friendly or virtual memory friendly.
>
> But as long as there is no fragmentation, malloc will work in O(1),since
> the first element in the list will always be the only free block, which
> will contain all free memory, making it fast.
>

for more realistic settings, you can also divide the free-lists up by 
object size ranges, and know that if a memory block is present in a 
given free-list, it is of a particular size range.

one example would be organizing them as a log2 with a few fractional 
bits. say (values chosen for convinience): 256, 320, 384, 448, 512, 640, 
... or: 256, 288, 320, 352, ...

you round to the size you want, grab the first item in the list that 
fits, and (if relevant) hack off the end and add it back to the 
free-list (in its appropriate size-range).

if you fail to find a block in a given size-range, check the next larger 
size range, and so on.


a little fudging may be relevant, say, to avoid scenarios where you are 
endlessly allocating/freeing a given sized block, but each time it is 
allocated it automatically pulls from the next larger list.

one solution is to "quantize" the sizes such that all of the blocks in a 
given free-list are exactly the same size, then allocations always round 
up and you can always use the first free block in a given list (no 
search needed), but at the cost that any fractional bits beyond the 
free-list size amount to wasted space.

for larger objects, this "fractional" loss (from rounding) can 
potentially be significant. the main alternative is a more complex 
strategy, like using AVL trees filled with memory spans or similar.


though, IME, large objects tend to be pretty rare, so it would be 
possible to use rounding for medium-sized objects, but use a best-fit 
strategy for larger memory blocks.


this isn't exclusive with my else-thread mention of using cells and a 
bitmap, which is mostly best suited to small allocations, whereas 
free-lists are better for larger allocations.


say, for example:
   0B-1kB: small object (cell+bitmap, possible: free-list as cache)
   1kB-256kB: medium object (free-list, rounded size)
   256kB-16MB: larger object (free-list, non-rounded size)
   16MB+: large object (free-list, best fit)

[toc] | [prev] | [next] | [standalone]

#72145

On 07.10.2015 15:45, BGB wrote:
> On 10/7/2015 7:50 AM, Philipp Klaus Krause wrote:
>> On 05.10.2015 18:34, glen herrmannsfeldt wrote:
>>>
>>>> It uses a linked list of blocks. Each block is either allocated or
>>>> free.
>>>> The list of free blocks comes and no memory cost, since it is stored in
>>>> free blocks only (well, it makes malloc() allocate at least
>>>> sizeof(header_t *), even for malloc(1) so that when we later free() the
>>>> block, we can put it into the free list, but that seems a negligible
>>>> cost to me).
>>>
>>>> This results in a resonably fast malloc(), which only needs to search
>>>> through the list of free blocks at very low overhead.
>>>
>>> Searching a linked list is O(N). If you do it N times, the result
>>> is O(N**2). It is not cache friendly or virtual memory friendly.
>>
>> But as long as there is no fragmentation, malloc will work in O(1),since
>> the first element in the list will always be the only free block, which
>> will contain all free memory, making it fast.
>>
> 
> for more realistic settings, you can also divide the free-lists up by
> object size ranges, and know that if a memory block is present in a
> given free-list, it is of a particular size range.
> 
> […]


Resulting in a far too complicated malloc() with much too high code size.

> 
> 
> say, for example:
>   0B-1kB: small object (cell+bitmap, possible: free-list as cache)
>   1kB-256kB: medium object (free-list, rounded size)
>   256kB-16MB: larger object (free-list, non-rounded size)
>   16MB+: large object (free-list, best fit)

Uh, our default heap size for most target architectures is 1KB.

Philipp

[toc] | [prev] | [next] | [standalone]

#72155

On 10/7/2015 12:33 PM, Philipp Klaus Krause wrote:
> On 07.10.2015 15:45, BGB wrote:
>> On 10/7/2015 7:50 AM, Philipp Klaus Krause wrote:
>>> On 05.10.2015 18:34, glen herrmannsfeldt wrote:
>>>>
>>>>> It uses a linked list of blocks. Each block is either allocated or
>>>>> free.
>>>>> The list of free blocks comes and no memory cost, since it is stored in
>>>>> free blocks only (well, it makes malloc() allocate at least
>>>>> sizeof(header_t *), even for malloc(1) so that when we later free() the
>>>>> block, we can put it into the free list, but that seems a negligible
>>>>> cost to me).
>>>>
>>>>> This results in a resonably fast malloc(), which only needs to search
>>>>> through the list of free blocks at very low overhead.
>>>>
>>>> Searching a linked list is O(N). If you do it N times, the result
>>>> is O(N**2). It is not cache friendly or virtual memory friendly.
>>>
>>> But as long as there is no fragmentation, malloc will work in O(1),since
>>> the first element in the list will always be the only free block, which
>>> will contain all free memory, making it fast.
>>>
>>
>> for more realistic settings, you can also divide the free-lists up by
>> object size ranges, and know that if a memory block is present in a
>> given free-list, it is of a particular size range.
>>
>> […]
>
>
> Resulting in a far too complicated malloc() with much too high code size.
>

possibly, though the logic for finding the size-range will probably not 
be all that large (over the single free list), as it can be done in a 
few lines of C code (a while loop and a few integer operations).


>>
>>
>> say, for example:
>>    0B-1kB: small object (cell+bitmap, possible: free-list as cache)
>>    1kB-256kB: medium object (free-list, rounded size)
>>    256kB-16MB: larger object (free-list, non-rounded size)
>>    16MB+: large object (free-list, best fit)
>
> Uh, our default heap size for most target architectures is 1KB.
>

fair enough.
probably bitmaps and atoms for this case.

I got thinking of something that would work well for heaps around 1M 
times as large...


FWIW, I have used chips with only about 1/8 as much RAM (and less ROM 
than you have RAM).

you don't use heap allocation on these though, pretty much solely global 
variables and some space for the stack.

[toc] | [prev] | [next] | [standalone]

#72166

Philipp Klaus Krause <pkk@spth.de> wrote:

(snip, regarding malloc() strategy, I wrote)

>> Searching a linked list is O(N). If you do it N times, the result
>> is O(N**2). It is not cache friendly or virtual memory friendly.
 
> But as long as there is no fragmentation, malloc will work in O(1),since
> the first element in the list will always be the only free block, which
> will contain all free memory, making it fast.

The case that interests me most is web browsers. After some time,
accessing pages, switching tabs, accessing more, and especially
if any are facebook, browsers start paging. You switch tabs, and
wait seconds or even minutes for paging until it updates the screen.

You are very lucky if you avoid fragmentation. That is rare.

-- glen

[toc] | [prev] | [next] | [standalone]

#72192

On 10/7/2015 9:10 PM, glen herrmannsfeldt wrote:
>[...]
> You are very lucky if you avoid fragmentation. That is rare.

     J.M. Robson published a paper (forty-four years ago!) proving that
no allocator is immune to fragmentation unless it can relocate in-use
blocks.  Knuth summarizes and illustrates some of Robson's argument;
in particular, *every* allocation scheme can be driven to failure with
memory only 2/3 full, by an unfortunate sequence of allocations and
releases of just two distinct block sizes.  TAOCP 2.5, exercises 36-40.

-- 
esosman@comcast-dot-net.invalid
"Don't be afraid of work. Make work afraid of you." -- TLM

[toc] | [prev] | [next] | [standalone]

#72040

On 05/10/2015 13:09, Philipp Klaus Krause wrote:

> But I didn't find something on
> making memory management cheaper in terms of overhead.
>
> So I came up with the following idea, which seems quite natural to me,
> but I haven't seen it anywhere else. It only stores a single pointer per
> allocated block, and has thus quite low overhead.

> It uses a linked list of blocks. Each block is either allocated or free.
> The list of free blocks comes and no memory cost, since it is stored in
> free blocks only

How does it know the size of each block? Or is each block always linked 
to the next sequential one?

> Are there other malloc() implementations with such low overhead around?

> P.S.: The malloc() is intended to replace the current one in SDCC, and
> thus is intended to work well for SDCC's target architectures - 8-bit
> with no alignment restrictions, typically 128B to 64KB of RAM; the XDATA
> is defined as a named address space for sometarget architectures (8051
> and related).

If this is to replace a normal malloc() and thus have to support 
conventional malloc/free calls of someone else's code, then your hands 
are tied somewhat.

Because one idea would be to use an allocation scheme that does not 
store sizes. Then there can be zero overhead (not per allocated block, 
although free blocks can store whatever links and extra info you want).

This requires that the user program needs to also give the size to the 
free function, and so needs to remember it. Most of the time however, 
this will already be stored or already known (eg. the length of an array 
or buffer, or the size of a struct).

With a total memory of 64KB or less, it might be worth using such as 
scheme in user-code, in additional to conventional malloc/free. Then the 
overheads of the latter become less significant.

(Note that if it's more efficient to round up requested sizes, that will 
still work with my proposal: the allocator and free function will both 
do the same rounding. But of course this is also wasteful.)

Other schemes can be considered in user-code where, for example, you 
know memory will never be freed: just a one-time allocation done at the 
start. Such blocks don't need links or sizes. Or where you know there 
will be large numbers of allocations and deallocations all of the same 
size.)

-- 
Bartc

[toc] | [prev] | [next] | [standalone]

#72132

On 06.10.2015 14:47, Bartc wrote:
> On 05/10/2015 13:09, Philipp Klaus Krause wrote:
> 
>> But I didn't find something on
>> making memory management cheaper in terms of overhead.
>>
>> So I came up with the following idea, which seems quite natural to me,
>> but I haven't seen it anywhere else. It only stores a single pointer per
>> allocated block, and has thus quite low overhead.
> 
>> It uses a linked list of blocks. Each block is either allocated or free.
>> The list of free blocks comes and no memory cost, since it is stored in
>> free blocks only
> 
> How does it know the size of each block? Or is each block always linked
> to the next sequential one?

Yes. Each one is linked to the next one. That is the one pointer stored
in every block, and the only overhead.

> 
>> Are there other malloc() implementations with such low overhead around?
> 
>> P.S.: The malloc() is intended to replace the current one in SDCC, and
>> thus is intended to work well for SDCC's target architectures - 8-bit
>> with no alignment restrictions, typically 128B to 64KB of RAM; the XDATA
>> is defined as a named address space for sometarget architectures (8051
>> and related).
> 
> If this is to replace a normal malloc() and thus have to support
> conventional malloc/free calls of someone else's code, then your hands
> are tied somewhat.
> 
> […]
> 

It is supposed to replace the memory management that SDCC currently
provides.

Philipp

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.c

csiph-web