Re: C is too old? opinions?

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

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.

The idea I was proposing was that you always simply take the first
item in the bucket, regardless of whether or not it is the best fit
out of the all the items in the bucket. You are taking from a bucket
which by definition only contains blocks that are big enough, so any
item from the bucket is sufficient, if wasteful. I say wasteful
because there can be cases when it gives you a block nearly 4 times
as big as necessary. For example, if you want a block of size 9, you
can't take from the 8 to 15 bucket, because it might contain some
8s. So you take the first item from the 16 to 31 bucket, which might
be as large as 31. Basically, when asking for blocks of size 2^n+1
(where n is an integer), you might be given a block as large as
2^(n+2)-1. And in the limit, that means quadruple memory usage,
in the worst case.

On the other hand, maybe a nice balanced tree structure would work
better. I guess I was just trying to say that there *are* solutions
to this problem and prove it by giving an example of a workable, if
not particularly frugal, algorithm.

(Actually, it might be very workable if you use more buckets but
still spread out the buckets evenly on a logarithmic scale. You
should be able to get the memory wastage down arbitrarily low.)

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.

Yeah, the size of memory seems to be a big one. Even the cleverest
implementation I can think of can't cope with an arbitrarily large
amount of memory. (That is, unless you have infinite memory, in
which case allocation becomes trivially easy, but that isn't a very
common architecture...)

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

Yeah, and static allocation has another advantage: it eliminates
all the error-handling needed for memory allocation failures. I
have been known to use static allocation for this reason sometimes...

- Logan
.

Relevant Pages

  • Re: Suggestions for my mallocator
    ... allocation system is actually quite difficult. ... recover all of memory correctly. ... suitable bucket, and there is no need to search the list of bucket ... the vast majority of scenarios where the memory is being pushed this ...
    (comp.lang.c)
  • Re: list allocator
    ... was wondering about the default allocation strategie. ... The number of copies depends on the container. ... and inserts/deletes are not guaranteed to affect elements at ... Each bucket is typically a fixed-size allocation - when a bucket gets full, ...
    (microsoft.public.vc.stl)
  • 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: Proposed addition of malloc_size_np()
    ... On Sat, 25 Mar 2006, Jason Evans wrote: ... bucket that the memory was allocated from... ... If you malloc, and malloc_size_npreturns 32 for that allocation, then you can treat it as a 32-byte allocation. ...
    (freebsd-arch)
  • Re: Attempt to rollback WMP11 to WMP10 failed
    ... That'd be real real useful. ... I tried to run WMP11, and checked for any events at the same time...only the ... The memory could not be read. ... There is no bucket number; or perhaps I'm looking in the worng place for that? ...
    (microsoft.public.windowsmedia.player)