RE: Functions and memory usage

[RLake@...]

> What we do is managing small allocations(smaller than 513
> bytes) and big allocations in a different way.
> for every allocation size between 1 and 512 bytes we allocate
> a 4K page where we will store only object of a certain size;
> for example 1 page with only 4 bytes chunks 1 page with only
> 32 bytes page.we round the allocations size to multiple of 4.
> for all chunk bigger than 512 bytes, we allocate it with a
> normal general pourpose allocator using a "best fit" algorithm.
> we "waste" 200/300k of memory every 100Mb allocated.
> With this solution we have an allocator that is almost CPU
> free for small alloc/free and relatively fast for big alloc/free
> because the number of chunk managed by the "best fit" are not so many.

If I'm not mistaken, this is a very similar algorithm to the one used by
dlmalloc. Have you compared your performance and fragmentation with it?
dlmalloc is a very mature and fast allocator.

This strategy works well if there are only a few sizes of blocks allocated,
and if deallocation-time is correlated with allocation-time. These are both
reasonable assumptions in many applications. However it is very easy to
come up with pathological cases.

An example of a pathological case is something like the following:

do
  local a = {}
  b = {}
  for i = 1, big_number do
    a[i] = {}
    b[i] = {}
  end
end

a, being local to the outermost do, will disappear at the end of it. b,
being global, won't. However, the allocations for the elements of a and b
were interleaved, so when a is garbage collected, it is going to leave 50%
fragmentation.

Most people would avoid code like that, but it comes up sometimes in
computations which memoise a lot of temporary values; it is not always easy
to notice that it is happening. Of course, no non-compacting garbage
collector is likely to help you with that sort of thing.

There is some evidence that first-fit is less likely to fragment than
best-fit, by the way. I believe that dlmalloc is almost-first-fit, but
don't quote me on that.