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

Groups > comp.lang.c > #72145

Re: Cheap malloc()

Show all headers | View raw

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

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