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

Groups > comp.lang.c > #72129

Re: Cheap malloc()

Show all headers | View raw

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

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