subject:"\[Xenomai\-git\] Philippe Gerum \: cobalt\/heap\: rebase on HEAPMEM algorithm"

[Xenomai-git] Philippe Gerum : cobalt/heap: rebase on HEAPMEM algorithm

2018-05-21 Thread git repository hosting

Module: xenomai-3
Branch: next
Commit: 10606d3ab266b3ffd077cc06db3c96d620d70612
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=10606d3ab266b3ffd077cc06db3c96d620d70612

Author: Philippe Gerum 
Date:   Sun May 13 19:00:50 2018 +0200

cobalt/heap: rebase on HEAPMEM algorithm

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   3232768  0  0  8  6
   1024k   3232768  0  0  7  2   +shuffle +realloc
   1024k   1665536  0  0  7  2   +realloc
   1024k   1665536  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   1665536  0  0  6  7   +shuffle +realloc
   1024k   3232768  0  0  8  6
512k   3216384  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   2432768  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
   1024k3k 292  1  1  1  8   +shuffle
256k  174 1024  1  1  1  6   +shuffle
   1024k   2432768  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

---

 include/cobalt/kernel/heap.h |  168 
 kernel/cobalt/Kconfig|7 +
 kernel/cobalt/heap.c |  978 +-
 3 files changed, 663 insertions(+), 490 deletions(-)

diff --git a/include/cobalt/kernel/heap.h b/include/cobalt/kernel/heap.h
index d89f25d..8a1c6f6 100644
--- a/include/cobalt/kernel/heap.h
+++ b/include/cobalt/kernel/heap.h
@@ -20,6 +20,7 @@
 #define _COBALT_KERNEL_HEAP_H
 
 #include 
+#include 
 #include 
 #include 
 #include 
@@ -28,66 +29,66 @@
 /**
  * @addtogroup cobalt_core_heap
  * @{
- *
- * @par Implementation constraints
- *
- * - Minimum page size is 2 ** XNHEAP_MINLOG2 (must be large enough to
- * hold a pointer).
- *
- * - Maximum page size is 2 ** XNHEAP_MAXLOG2.
- *
- * - Requested block size is rounded up to XNHEAP_MINLOG2.
- *
- * - Requested block size larger than 2 times the XNHEAP_PAGESZ is
- * rounded up to the next page boundary and obtained from the free
- * page list. So we need a bucket for each power of two between
- * XNHEAP_MINLOG2 and XNHEAP_MAXLOG2 inclusive, plus one to honor
- * requests ranging from the maximum page size to twice this size.
  */
-#define XNHEAP_PAGESZPAGE_SIZE
-#define XNHEAP_MINLOG23
-#define XNHEAP_MAXLOG222   /* Holds pagemap.bcount blocks */
-#define XNHEAP_MINALLOCSZ (1 << XNHEAP_MINLOG2)
-#define XNHEAP_MINALIGNSZ (1 << 4) /* i.e. 16 bytes */
-#define

[Xenomai-git] Philippe Gerum : cobalt/heap: rebase on HEAPMEM algorithm

2018-05-20 Thread git repository hosting

Module: xenomai-3
Branch: next
Commit: 0446cc545543100016491a71d7e2fc87082e6575
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=0446cc545543100016491a71d7e2fc87082e6575

Author: Philippe Gerum 
Date:   Sun May 13 19:00:50 2018 +0200

cobalt/heap: rebase on HEAPMEM algorithm

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   3232768  0  0  8  6
   1024k   3232768  0  0  7  2   +shuffle +realloc
   1024k   1665536  0  0  7  2   +realloc
   1024k   1665536  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   1665536  0  0  6  7   +shuffle +realloc
   1024k   3232768  0  0  8  6
512k   3216384  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   2432768  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
   1024k3k 292  1  1  1  8   +shuffle
256k  174 1024  1  1  1  6   +shuffle
   1024k   2432768  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

---

 include/cobalt/kernel/heap.h |  168 
 kernel/cobalt/Kconfig|7 +
 kernel/cobalt/heap.c |  979 +-
 3 files changed, 662 insertions(+), 492 deletions(-)

diff --git a/include/cobalt/kernel/heap.h b/include/cobalt/kernel/heap.h
index d89f25d..8a1c6f6 100644
--- a/include/cobalt/kernel/heap.h
+++ b/include/cobalt/kernel/heap.h
@@ -20,6 +20,7 @@
 #define _COBALT_KERNEL_HEAP_H
 
 #include 
+#include 
 #include 
 #include 
 #include 
@@ -28,66 +29,66 @@
 /**
  * @addtogroup cobalt_core_heap
  * @{
- *
- * @par Implementation constraints
- *
- * - Minimum page size is 2 ** XNHEAP_MINLOG2 (must be large enough to
- * hold a pointer).
- *
- * - Maximum page size is 2 ** XNHEAP_MAXLOG2.
- *
- * - Requested block size is rounded up to XNHEAP_MINLOG2.
- *
- * - Requested block size larger than 2 times the XNHEAP_PAGESZ is
- * rounded up to the next page boundary and obtained from the free
- * page list. So we need a bucket for each power of two between
- * XNHEAP_MINLOG2 and XNHEAP_MAXLOG2 inclusive, plus one to honor
- * requests ranging from the maximum page size to twice this size.
  */
-#define XNHEAP_PAGESZPAGE_SIZE
-#define XNHEAP_MINLOG23
-#define XNHEAP_MAXLOG222   /* Holds pagemap.bcount blocks */
-#define XNHEAP_MINALLOCSZ (1 << XNHEAP_MINLOG2)
-#define XNHEAP_MINALIGNSZ (1 << 4) /* i.e. 16 bytes */
-#define

[Xenomai-git] Philippe Gerum : cobalt/heap: rebase on HEAPMEM algorithm

2018-05-16 Thread git repository hosting

Module: xenomai-3
Branch: wip/heapmem
Commit: edde4308feb872e4885ff50329c2c9beb56757f4
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=edde4308feb872e4885ff50329c2c9beb56757f4

Author: Philippe Gerum 
Date:   Sun May 13 19:00:50 2018 +0200

cobalt/heap: rebase on HEAPMEM algorithm

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   3232768  0  0  8  6
   1024k   3232768  0  0  7  2   +shuffle +realloc
   1024k   1665536  0  0  7  2   +realloc
   1024k   1665536  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   1665536  0  0  6  7   +shuffle +realloc
   1024k   3232768  0  0  8  6
512k   3216384  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   2432768  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
   1024k3k 292  1  1  1  8   +shuffle
256k  174 1024  1  1  1  6   +shuffle
   1024k   2432768  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

---

 include/cobalt/kernel/heap.h |  168 
 kernel/cobalt/Kconfig|7 +
 kernel/cobalt/heap.c |  979 +-
 3 files changed, 662 insertions(+), 492 deletions(-)

diff --git a/include/cobalt/kernel/heap.h b/include/cobalt/kernel/heap.h
index d89f25d..4f95c80 100644
--- a/include/cobalt/kernel/heap.h
+++ b/include/cobalt/kernel/heap.h
@@ -20,6 +20,7 @@
 #define _COBALT_KERNEL_HEAP_H
 
 #include 
+#include 
 #include 
 #include 
 #include 
@@ -28,66 +29,66 @@
 /**
  * @addtogroup cobalt_core_heap
  * @{
- *
- * @par Implementation constraints
- *
- * - Minimum page size is 2 ** XNHEAP_MINLOG2 (must be large enough to
- * hold a pointer).
- *
- * - Maximum page size is 2 ** XNHEAP_MAXLOG2.
- *
- * - Requested block size is rounded up to XNHEAP_MINLOG2.
- *
- * - Requested block size larger than 2 times the XNHEAP_PAGESZ is
- * rounded up to the next page boundary and obtained from the free
- * page list. So we need a bucket for each power of two between
- * XNHEAP_MINLOG2 and XNHEAP_MAXLOG2 inclusive, plus one to honor
- * requests ranging from the maximum page size to twice this size.
  */
-#define XNHEAP_PAGESZPAGE_SIZE
-#define XNHEAP_MINLOG23
-#define XNHEAP_MAXLOG222   /* Holds pagemap.bcount blocks */
-#define XNHEAP_MINALLOCSZ (1 << XNHEAP_MINLOG2)
-#define XNHEAP_MINALIGNSZ (1 << 4) /* i.e. 16 bytes */

[Xenomai-git] Philippe Gerum : cobalt/heap: rebase on HEAPMEM algorithm

2018-05-15 Thread git repository hosting

Module: xenomai-3
Branch: wip/heapmem
Commit: 55b21ebe8a44f75f74c0a3a9e885fd3096d8327c
URL:
http://git.xenomai.org/?p=xenomai-3.git;a=commit;h=55b21ebe8a44f75f74c0a3a9e885fd3096d8327c

Author: Philippe Gerum 
Date:   Sun May 13 19:00:50 2018 +0200

cobalt/heap: rebase on HEAPMEM algorithm

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   3232768  0  0  8  6
   1024k   3232768  0  0  7  2   +shuffle +realloc
   1024k   1665536  0  0  7  2   +realloc
   1024k   1665536  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   1665536  0  0  6  7   +shuffle +realloc
   1024k   3232768  0  0  8  6
512k   3216384  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   2432768  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
   1024k3k 292  1  1  1  8   +shuffle
256k  174 1024  1  1  1  6   +shuffle
   1024k   2432768  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

---

 include/cobalt/kernel/heap.h |  168 
 kernel/cobalt/Kconfig|7 +
 kernel/cobalt/heap.c |  979 +-
 3 files changed, 662 insertions(+), 492 deletions(-)

diff --git a/include/cobalt/kernel/heap.h b/include/cobalt/kernel/heap.h
index d89f25d..4f95c80 100644
--- a/include/cobalt/kernel/heap.h
+++ b/include/cobalt/kernel/heap.h
@@ -20,6 +20,7 @@
 #define _COBALT_KERNEL_HEAP_H
 
 #include 
+#include 
 #include 
 #include 
 #include 
@@ -28,66 +29,66 @@
 /**
  * @addtogroup cobalt_core_heap
  * @{
- *
- * @par Implementation constraints
- *
- * - Minimum page size is 2 ** XNHEAP_MINLOG2 (must be large enough to
- * hold a pointer).
- *
- * - Maximum page size is 2 ** XNHEAP_MAXLOG2.
- *
- * - Requested block size is rounded up to XNHEAP_MINLOG2.
- *
- * - Requested block size larger than 2 times the XNHEAP_PAGESZ is
- * rounded up to the next page boundary and obtained from the free
- * page list. So we need a bucket for each power of two between
- * XNHEAP_MINLOG2 and XNHEAP_MAXLOG2 inclusive, plus one to honor
- * requests ranging from the maximum page size to twice this size.
  */
-#define XNHEAP_PAGESZPAGE_SIZE
-#define XNHEAP_MINLOG23
-#define XNHEAP_MAXLOG222   /* Holds pagemap.bcount blocks */
-#define XNHEAP_MINALLOCSZ (1 << XNHEAP_MINLOG2)
-#define XNHEAP_MINALIGNSZ (1 << 4) /* i.e. 16 bytes */

[Xenomai-git] Philippe Gerum : cobalt/heap: rebase on HEAPMEM algorithm

[Xenomai-git] Philippe Gerum : cobalt/heap: rebase on HEAPMEM algorithm

[Xenomai-git] Philippe Gerum : cobalt/heap: rebase on HEAPMEM algorithm

[Xenomai-git] Philippe Gerum : cobalt/heap: rebase on HEAPMEM algorithm

4 matches

Site Navigation

Mail list logo

Footer information