From d83f1dc56f2f576df3243e8fb1642ac36faa1f55 Mon Sep 17 00:00:00 2001 From: cedric Date: Tue, 1 Feb 2011 18:10:03 +0000 Subject: [PATCH] * eina: improve speed and scalability a lot. git-svn-id: svn+ssh://svn.enlightenment.org/var/svn/e/trunk/eina@56637 7cbeb6ba-43b4-40fd-8cce-4c39aea84d33 --- ChangeLog | 6 +- src/include/eina_rbtree.h | 6 + src/modules/mp/chained_pool/eina_chained_mempool.c | 121 ++++++++++++++------- src/tests/eina_bench_array.c | 8 +- 4 files changed, 97 insertions(+), 44 deletions(-) diff --git a/ChangeLog b/ChangeLog index 304e652..cad2484 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,4 +1,8 @@ 2011-01-29 Carsten Haitzler (The Rasterman) 1.0.0 release - + +2011-02-01 Cedric Bail + + * Improve scalability and raw speed of Chained Mempool. + diff --git a/src/include/eina_rbtree.h b/src/include/eina_rbtree.h index 7617236..a4b46c2 100644 --- a/src/include/eina_rbtree.h +++ b/src/include/eina_rbtree.h @@ -96,6 +96,12 @@ struct _Eina_Rbtree #define EINA_RBTREE_GET(Rbtree) & ((Rbtree)->__rbtree) /** + * @def EINA_RBTREE_CONTAINER_GET + * find back the container of an red black tree. + */ +#define EINA_RBTREE_CONTAINER_GET(Ptr, Type) ((Type *)((char *)Ptr - offsetof(Type, __rbtree))) + +/** * @typedef Eina_Rbtree_Cmp_Node_Cb * Function used compare two nodes and see which direction to navigate. */ diff --git a/src/modules/mp/chained_pool/eina_chained_mempool.c b/src/modules/mp/chained_pool/eina_chained_mempool.c index df9fe85..727a049 100644 --- a/src/modules/mp/chained_pool/eina_chained_mempool.c +++ b/src/modules/mp/chained_pool/eina_chained_mempool.c @@ -42,6 +42,7 @@ #include "eina_module.h" #include "eina_mempool.h" #include "eina_trash.h" +#include "eina_rbtree.h" #include "eina_private.h" @@ -64,6 +65,7 @@ typedef struct _Chained_Mempool Chained_Mempool; struct _Chained_Mempool { Eina_Inlist *first; + Eina_Rbtree *root; const char *name; int item_alloc; int pool_size; @@ -86,6 +88,7 @@ typedef struct _Chained_Pool Chained_Pool; struct _Chained_Pool { EINA_INLIST; + EINA_RBTREE; Eina_Trash *base; int usage; @@ -93,6 +96,24 @@ struct _Chained_Pool unsigned char *limit; }; +static inline Eina_Rbtree_Direction +_eina_chained_mp_pool_cmp(const Eina_Rbtree *left, const Eina_Rbtree *right, __UNUSED__ void *data) +{ + if (left < right) return EINA_RBTREE_LEFT; + return EINA_RBTREE_RIGHT; +} + +static inline int +_eina_chained_mp_pool_key_cmp(const Eina_Rbtree *node, const void *key, + __UNUSED__ int length, __UNUSED__ void *data) +{ + const Chained_Pool *r = EINA_RBTREE_CONTAINER_GET(node, const Chained_Pool); + + if (key > (void *) r->limit) return 1; + if (key < (void *) r) return -1; + return 0; +} + static inline Chained_Pool * _eina_chained_mp_pool_new(Chained_Mempool *pool) { @@ -151,16 +172,12 @@ eina_chained_mempool_malloc(void *data, __UNUSED__ unsigned int size) #endif #endif - // look 4 pool from 2nd bucket on - EINA_INLIST_FOREACH(pool->first, p) - { - // base is not NULL - has a free slot - if (p->base || p->last) - { - pool->first = eina_inlist_demote(pool->first, EINA_INLIST_GET(p)); - break; - } - } + // Either we have some free space in the first one, or there is no free space. + p = EINA_INLIST_CONTAINER_GET(pool->first, Chained_Pool); + + // base is not NULL - has a free slot + if (p && !p->base && !p->last) + p = NULL; // we have reached the end of the list - no free pools if (!p) @@ -182,6 +199,8 @@ eina_chained_mempool_malloc(void *data, __UNUSED__ unsigned int size) } pool->first = eina_inlist_prepend(pool->first, EINA_INLIST_GET(p)); + pool->root = eina_rbtree_inline_insert(pool->root, EINA_RBTREE_GET(p), + _eina_chained_mp_pool_cmp, NULL); } if (p->last) @@ -229,6 +248,7 @@ static void eina_chained_mempool_free(void *data, void *ptr) { Chained_Mempool *pool = data; + Eina_Rbtree *r; Chained_Pool *p; void *pmem; @@ -249,36 +269,52 @@ eina_chained_mempool_free(void *data, void *ptr) #endif #endif - EINA_INLIST_FOREACH(pool->first, p) - { - // Could the pointer be inside that pool - if ((unsigned char*) ptr < p->limit) - { - // pool mem base - pmem = (void *)(((unsigned char *)p) + sizeof(Chained_Pool)); - // is it in pool mem? - if (ptr >= pmem) - { - // freed node points to prev free node - eina_trash_push(&p->base, ptr); - // next free node is now the one we freed - p->usage--; - pool->usage--; - if (p->usage == 0) - { - // free bucket - pool->first = eina_inlist_remove(pool->first, EINA_INLIST_GET(p)); - _eina_chained_mp_pool_free(p); - } - else - // move to front - pool->first = eina_inlist_promote(pool->first, EINA_INLIST_GET(p)); - - break; - } - } - } + // searching for the right mempool + r = eina_rbtree_inline_lookup(pool->root, ptr, 0, _eina_chained_mp_pool_key_cmp, NULL); + + // related mempool not found + if (!r) + { +#ifdef DEBUG + INF("%p is not the property of %p Chained_Mempool", ptr, pool); +#endif + goto on_error; + } + + p = EINA_RBTREE_CONTAINER_GET(r, Chained_Pool); + + // pool mem base + pmem = (void *)(((unsigned char *)p) + sizeof(Chained_Pool)); + + // is it in pool mem? + if (ptr < pmem) + { +#ifdef DEBUG + INF("%p is inside the private part of %p pool from %p Chained_Mempool (could be the sign of a buffer underrun).", ptr, p, pool); +#endif + goto on_error; + } + + // freed node points to prev free node + eina_trash_push(&p->base, ptr); + // next free node is now the one we freed + p->usage--; + pool->usage--; + if (p->usage == 0) + { + // free bucket + pool->first = eina_inlist_remove(pool->first, EINA_INLIST_GET(p)); + pool->root = eina_rbtree_inline_remove(pool->root, EINA_RBTREE_GET(p), + _eina_chained_mp_pool_cmp, NULL); + _eina_chained_mp_pool_free(p); + } + else + { + // move to front + pool->first = eina_inlist_promote(pool->first, EINA_INLIST_GET(p)); + } + on_error: #ifndef NVALGRIND if (ptr) { @@ -371,9 +407,16 @@ eina_chained_mempool_shutdown(void *data) #endif mp->first = eina_inlist_remove(mp->first, mp->first); + mp->root = eina_rbtree_inline_remove(mp->root, EINA_RBTREE_GET(p), + _eina_chained_mp_pool_cmp, NULL); _eina_chained_mp_pool_free(p); } +#ifdef DEBUG + if (mp->root) + INF("Bad news, list of pool and rbtree are out of sync for %p !", mp); +#endif + #ifndef NVALGRIND VALGRIND_DESTROY_MEMPOOL(mp); #endif diff --git a/src/tests/eina_bench_array.c b/src/tests/eina_bench_array.c index 2e32e98..425eddd 100644 --- a/src/tests/eina_bench_array.c +++ b/src/tests/eina_bench_array.c @@ -691,9 +691,9 @@ void eina_bench_array(Eina_Benchmark *bench) EINA_BENCHMARK( eina_bench_evas_list_4evas_render), 200, 4000, 100); - /* eina_benchmark_register(bench, "ecore", */ - /* EINA_BENCHMARK( */ - /* eina_bench_ecore_list_4evas_render), 200, */ - /* 1000, 100); */ + eina_benchmark_register(bench, "ecore", + EINA_BENCHMARK( + eina_bench_ecore_list_4evas_render), 200, + 500, 100); } -- 2.7.4