• Philippe Gerum's avatar
    cobalt/heap: rebase on HEAPMEM algorithm · 4b2408b8
    Philippe Gerum authored
    Address the issue mentioned in [1] regarding the core (xnheap)
    allocator, using a variant of the McKusick scheme significantly
    improving the performance figures.
    
    As a by-product of this overhaul, the core allocator can now manage
    heaps up to (4GB - PAGE_SIZE).
    
    The performance report log obtained by testing on imx6qp
    is as follows:
    
    == memcheck started
         seq_heap_size=2048k
         random_alloc_rounds=1024
         pattern_heap_size=128k
         pattern_check_rounds=128
    
    [SEQUENTIAL ALLOC->FREE, ^2 BLOCK SIZES] ON 'xnheap'
    
    HEAPSZ	test heap size
    BLOCKSZ	tested block size
    NRBLKS	number of blocks allocatable in heap
    AVG-A	average time to allocate block (us)
    AVG-F	average time to free block (us)
    MAX-A	max time to allocate block (us)
    MAX-F	max time to free block (us)
    FLAGS	+shuffle: randomized free
        	+realloc: measure after initial alloc/free pass (hot heap)
    
    sorted by: max alloc time
      HEAPSZ  BLOCKSZ   NRBLKS  AVG-A  AVG-F  MAX-A  MAX-F   FLAGS
       1024k       32    32768      0      0      8      6
       1024k       32    32768      0      0      7      2   +shuffle +realloc
       1024k       16    65536      0      0      7      2   +realloc
       1024k       16    65536      0      0      6      7   +shuffle +realloc
      ... (364 results following) ...
    
    sorted by: max free time
      HEAPSZ  BLOCKSZ   NRBLKS  AVG-A  AVG-F  MAX-A  MAX-F   FLAGS
       1024k      128     8192      0      1      2      8
       1024k       16    65536      0      0      6      7   +shuffle +realloc
       1024k       32    32768      0      0      8      6
        512k       32    16384      0      0      5      6   +realloc
      ... (364 results following) ...
    
    overall:
      worst alloc time: 8 (us)
      worst free time: 8 (us)
      average of max. alloc times: 1 (us)
      average of max. free times: 2 (us)
      average alloc time: 1 (us)
      average free time: 1 (us)
    
    [SEQUENTIAL ALLOC->FREE, RANDOM BLOCK SIZES] ON 'xnheap'
    
    HEAPSZ	test heap size
    BLOCKSZ	tested block size
    NRBLKS	number of blocks allocatable in heap
    AVG-A	average time to allocate block (us)
    AVG-F	average time to free block (us)
    MAX-A	max time to allocate block (us)
    MAX-F	max time to free block (us)
    FLAGS	+shuffle: randomized free
        	+realloc: measure after initial alloc/free pass (hot heap)
    
    sorted by: max alloc time
      HEAPSZ  BLOCKSZ   NRBLKS  AVG-A  AVG-F  MAX-A  MAX-F   FLAGS
        512k       17k      28      1      1      8      2   +shuffle
        512k       45k      11      1      1      7      2
       1024k       24    32768      0      0      7      6   +shuffle
        128k      820      128      1      1      6      2   +shuffle
      ... (32764 results following) ...
    
    sorted by: max free time
      HEAPSZ  BLOCKSZ   NRBLKS  AVG-A  AVG-F  MAX-A  MAX-F   FLAGS
       1024k        3k     292      1      1      1      8   +shuffle
        256k      174     1024      1      1      1      6   +shuffle
       1024k       24    32768      0      0      7      6   +shuffle
         32k       12k       2      2      3      1      5
      ... (32764 results following) ...
    
    overall:
      worst alloc time: 8 (us)
      worst free time: 8 (us)
      average of max. alloc times: 1 (us)
      average of max. free times: 1 (us)
      average alloc time: 1 (us)
      average free time: 1 (us)
    
    [1] http://www.xenomai.org/pipermail/xenomai/2018-April/038883.html
    4b2408b8
heap.c 21.3 KB