Re: C is too old? opinions?

Logan Shaw wrote:
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.

What you describe is very similar to malloc in early versions of BSD.
Remember that each bucket must be connected to some sort of set data
structure. Describing the set of memory blocks. You must work out how
to pick an item from that set data structure in bounded time. That
isn't a simple thing to do. Lists can't do it and neither can chaining
hashes. But chaining hashes can be made to have more reasonable
behaviour.

Its easy to do one thing with the set data structure in bounded time,
ie insert or remove, but hard to do both in bounded time.

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

Yes, BSD malloc used to waste amounts of memory of this order on a few
types of load.

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.

Yes, and that can be done in bounded time. You can know what the
bounded time is if you know how many buckets you have.

What you need to know is plenty of limits, the size of memory, the
largest block that a program can request from malloc etc. With those
its not too hard.

As some earlier poster mentioned not bothering and only using static
allocation in real-time parts of code can be a simple option.

.

Relevant Pages

  • Re: C is too old? opinions?
    ... Lets say malloc and free work by keeping a single linked list of free ... different sizes of allocation, this is like a chaining hash map. ... bucket has a free list for that size of allocation. ... don't worry about ordering the lists of things in the buckets. ...
    (comp.programming)
  • Re: vasam
    ... // Set the size for long lists in records #2 and #3 only! ... Here is the sequel of my previous post "Variable array sizes as members" ... I was given some advice on how to use malloc and realloc in oder to achieve ...
    (microsoft.public.vc.language)
  • 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: Problem with a linked list
    ... If malloc() returns a null pointer, ... You just compare the tail iterator against NULL ... and is a single parameter the can be efficiently returned or passed as ... This should be more conducive to learning how linked lists ...
    (comp.lang.c)
  • Re: malloc/free question
    ... I'd like to be able to malloc a block of memory, ... For example, malloc 100 ... Use realloc. ... seriously consider using two lists. ...
    (comp.lang.c)