Re: C is too old? opinions?

Rob Thorpe wrote:
Dynamic memory allocation has many of the same problems as GC for
real-time.

Lets say malloc and free work by keeping a single linked list of free
space.
That means that in the worst case one of malloc or free must walk the
whole list to find space. The list could be very long, making the
worst case bad and dependent on the size of memory.

To make it better you could use a malloc with several buckets for
different sizes of allocation, this is like a chaining hash map. Each
bucket has a free list for that size of allocation. Then the worst
case is the length of one of these bucket lists. But this has problems
too. Imagine if all the allocations are in the smallest bucket, the
problem then reduces to the "single linked list" method of malloc/free.

Seems like there's an easy enough solution to this. Just break it up
into buckets, where each bucket has blocks sized from one power of 2
to the next. If the minimum allocation size is 8 bytes, the first
bucket has blocks sized 8 through 15 in it, the second has blocks
sized 16 through 31, the third has 32 through 63, and so on. And
don't worry about ordering the lists of things in the buckets.
Just put them in there at random.

Then when it's time to do an allocation, grab something out of a bucket
that is guaranteed to give you a block big enough. For example, if
someone asks for a chunk of size 15, then even if there might be some
15-sized chunks in the 8 to 15 bucket, ignore that and grab something
from the 16 to 23 bucket.

The nice thing about this is that it's O(1). Or at least O(log M)
where M is the total size of the memory in the system[1].

The bad thing about this is that it's fairly wasteful with memory.
The exact amount it wastes in the worst case is hard to determine.
It's certain 1/2 and it might be as high as 3/4, actually...

Of course, this idea doesn't solve the problem of reassembling the
pieces you have to fragment when adjacent pieces are freed...

- Logan

[1] If someone asks for a chunk of size 16 and the 16 to 31 bucket
is empty, you probably want to try the 32 to 63 bucket, then
the 64 to 127 bucket, and so on. You can take the leftovers
and put them in a smaller bucket.
.

Relevant Pages

  • Re: C is too old? opinions?
    ... Lets say malloc and free work by keeping a single linked list of free ... bucket has a free list for that size of allocation. ... don't worry about ordering the lists of things in the buckets. ... Its easy to do one thing with the set data structure in bounded time, ...
    (comp.programming)
  • Re: Why are tuples immutable?
    ... No it is not because that would imply that keys with the same hash ... and the dictionary bucket. ... All you need is that the lists that are used as a key remain stable. ... > Except that the hash value will change when the list mutates, ...
    (comp.lang.python)
  • Re: What does "koh-kghu call " mean?
    ... irrespective of the size of specification of the PL/SQL collection type? ... Bucket 0 size=44 ... In the SGA management, there are 255 lists, of which the ... first 200 or so are each for a very specific chunk size ...
    (comp.databases.oracle.server)
  • Re: Thou shalt have no other gods before the ANSI C standard
    ... but the most common is probably "hash chaining" ... where each "bucket" of the array is a list, ... One of the primary goals is to avoid collisions as much as possible, ... resulting in 4 very long lists to fall down on lookups. ...
    (sci.crypt)
  • Re: Improving memory consumption in the container library
    ... so the malloc overhead is 1/1000, ... imagine means significant savings compared to using malloc on large numbers of small blocks ... And why I try to stay clear of mallocwhich, I understand, might use 16 or 32 bytes of extra overhead per allocation. ... For smaller lists, 1 or 2 calls to free will be necessary. ...
    (comp.lang.c)