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

Groups > comp.lang.c > #71967

Cheap malloc()

Show all headers | View raw

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

Back to comp.lang.c | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

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

csiph-web