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

Groups > comp.lang.c > #72133

Re: Cheap malloc()

Show all headers | View raw

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

Back to comp.lang.c | Previous | Next — Previous in thread | 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