Re: fragmentation

On May 28, 4:04 am, drop...@xxxxxxxxx wrote:
Hi.
I'm writting my own memory management functions.
While playing with different options, I feel necessity of
fragmentation counting algorithm.
For example, 1 is allocated block and 0 is not.
This is 0% fragmentation: 11111100000
This is 100% fragmentation: 101010101010
How can I build algorithm which will count this coefficient?

You are looking for a heurisitic indicator, so there is no single
answer.

Richard Heathfield gave a useful one. The fraction of block-block
boundaries that separate free and allocated space (minus one) with
respect to total number of block-block boundaries. This is allocator-
centric, since it uses only blocks in its computation, igoring that
allocations are usually multiple blocks.

So give the name _segment_ to any set of blocks allocated by a call of
the allocator.

Then another useful metric is the number of segment boundaries that
touch free space (minus one) divided by the total number of segment
boundaries. This tells you how successful the allocator has been in
matching requests to the size of available "holes."

Another possibility is the number of free blocks that are smaller than
the median (or mean or mode or whatever makes sense) size allocated
segment divided by the total number of free blocks. This is an
indicator of "wasted" space, i.e. the space likely to be in segments
too smal to be useful.

Yet another is the number of blocks (or segments) that would have to
be moved by a given compaction algorithm to obtain fully contiguous
allocation divided by the total number of blocks(or segments)
allocated. This is an indicator of future computing power needed to
fix the fragmentation.

You get the idea. Pick what best suits your needs for information
about how well the allocator is performing.

.

Relevant Pages

  • Re: Profiling tools/how to discover hot-spots in my code?
    ... so the real hotspots will show up independent of the disk access patterns. ... Program hotspots are caused by poor algorithm design. ... the internal performance counters in the allocator. ...
    (microsoft.public.vc.mfc)
  • transforming single-threaded allocators...
    ... I have developed a non-blocking algorithm that allows one to transform an inherently single-threaded memory allocator into a scaleable multi-threaded allocator. ... Okay, here is an initial proof of concept, I have transformed the Windows Heap object created with the HEAP_NO_SERIALIZE flag. ...
    (comp.programming.threads)
  • Re: [PATCH 1/1] network memory allocator.
    ... Rate of fragmentation can be found in some userspace ... With existing allocator it never happens by deisgn. ... I'm not understanding, if you have a page A with two packets, a and b; ... round up to nearest order page alloc per object; SLAB is build to avoid ...
    (Linux-Kernel)
  • Re: [PATCH 1/1] network memory allocator.
    ... Each socket has it's limit, so if allocator got enough memory, blocked ... round up to nearest order page alloc per object; SLAB is build to avoid ... So the actual internal fragmentation of the current kmalloc/SLAB ... Network stack uses kmalloc. ...
    (Linux-Kernel)
  • Re: Dedicated lock-free group
    ... that allocator design is NOTHING NEW. ... source package with build documentation and the article as the accompanying ... That's because you failed to present your invention in a usable and easily ... You ignore the inventor of the algorithm, and try to help somebody who might ...
    (comp.programming.threads)