From 994318eebe032447f9457a77fe446b5978480cd7 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=A9my=20Zurcher?= Date: Sun, 28 Apr 2013 00:43:23 +0200 Subject: [PATCH] eo_ptr_ind: pack ptr, active flag and generation all together use of an array of the below struct instead of 3 separate arrays leads to better cache performance and smaller memory usage typedef struct { _Eo *ptr; unsigned int active : 1; unsigned int generation : BITS_FOR_GENERATION_COUNTER; } _Eo_Id_Entry; --- src/lib/eo/eo_ptr_indirection.c | 111 ++++++++++++++++++++-------------------- 1 file changed, 56 insertions(+), 55 deletions(-) diff --git a/src/lib/eo/eo_ptr_indirection.c b/src/lib/eo/eo_ptr_indirection.c index ce2fc6e..32e3781 100644 --- a/src/lib/eo/eo_ptr_indirection.c +++ b/src/lib/eo/eo_ptr_indirection.c @@ -32,9 +32,10 @@ * occur when accessing with the old id. * * Each table is composed of: - * - pointers to the objects - * - generations assigned to the objects - * - a boolean table indicating if an entry is active + * - entries composed of + * - a pointer to the object + * - a flag indicating if the entry is active + * - a generation assigned to the object * - an index 'start' indicating which entry is the next one to use. * - a queue that will help us to store the unused entries. It stores only the * entries that have been used at least one time. The entries that have @@ -112,7 +113,7 @@ _eo_id_mem_alloc(size_t size) return (void *)(((unsigned char *)ptr) + MEM_HEADER_SIZE); #else return malloc(size); -#endif +#endif } static void * @@ -142,15 +143,22 @@ _eo_id_mem_free(void *ptr) #endif } +/* Entry */ +typedef struct +{ + /* Pointer to the object */ + _Eo *ptr; + /* Active flag */ + unsigned int active : 1; + /* Generation */ + unsigned int generation : BITS_FOR_GENERATION_COUNTER; +} _Eo_Id_Entry; + /* Table */ typedef struct { - /* Pointers of objects stored in table */ - _Eo *ptrs[MAX_IDS_PER_TABLE]; - /* Generations */ - Table_Index generation[MAX_IDS_PER_TABLE]; - /* Active flags */ - char active[MAX_IDS_PER_TABLE >> 3]; + /* Entries of the table holding real pointers and generations */ + _Eo_Id_Entry entries[MAX_IDS_PER_TABLE]; /* Queue to handle free entries */ Eina_Trash *queue; /* Indicates where start the "never used" entries */ @@ -163,20 +171,6 @@ _Eo_Ids_Table **_eo_ids_tables[MAX_IDS_TABLES] = { NULL }; /* Next generation to use when assigning a new entry to a Eo pointer */ Table_Index _eo_generation_counter; -/* Internal macro for active flag manipulation */ -#define _ENTRY_ACTIVE_DO_OP(table, id_in_table, op) \ - (table)->active[(id_in_table) >> 3] op (1 << ((id_in_table) % 8)) - -/* Macro that indicates if an entry is active */ -#define IS_ENTRY_ACTIVE(table, id_in_table) \ - (_ENTRY_ACTIVE_DO_OP(table, id_in_table, &)) -/* Macro that activates an entry */ -#define ACTIVATE_ENTRY(table, id_in_table) \ - _ENTRY_ACTIVE_DO_OP(table, id_in_table, |=) -/* Macro that de-activates an entry */ -#define DEACTIVATE_ENTRY(table, id_in_table) \ - _ENTRY_ACTIVE_DO_OP(table, id_in_table, &=~) - /* Macro used to compose an Eo id */ #define EO_COMPOSE_ID(TABLE, INTER_TABLE, ENTRY, GENERATION) \ (Eo_Id)(((TABLE & (MAX_IDS_TABLES - 1)) << SHIFT_FOR_IDS_TABLE) | \ @@ -198,14 +192,18 @@ _Eo * _eo_obj_pointer_get(const Eo_Id obj_id) { #ifdef HAVE_EO_ID + _Eo_Id_Entry *entry; Table_Index table_id, int_table_id, entry_id, generation; EO_DECOMPOSE_ID((Table_Index) obj_id, table_id, int_table_id, entry_id, generation); /* Checking the validity of the entry */ - if (_eo_ids_tables[table_id] && ID_TABLE && IS_ENTRY_ACTIVE(ID_TABLE, entry_id) && - ID_TABLE->generation[entry_id] == generation) - return ID_TABLE->ptrs[entry_id]; + if (_eo_ids_tables[table_id] && ID_TABLE) + { + entry = &(ID_TABLE->entries[entry_id]); + if (entry && entry->active && (entry->generation == generation)) + return entry->ptr; + } ERR("obj_id %p is not pointing to a valid object. Maybe it has already been freed.", (void *)obj_id); @@ -220,7 +218,7 @@ Eo_Id _eo_id_allocate(const _Eo *obj) { #ifdef HAVE_EO_ID - Eo_Id ret = 0; + _Eo_Id_Entry *entry = NULL; for (Table_Index table_id = 1; table_id < MAX_IDS_TABLES; table_id++) { if (!_eo_ids_tables[table_id]) @@ -230,44 +228,43 @@ _eo_id_allocate(const _Eo *obj) } for (Table_Index int_table_id = 0; int_table_id < MAX_IDS_INTER_TABLES; int_table_id++) { - _Eo **ptr; if (!ID_TABLE) { /* We allocate a new intermediate table */ ID_TABLE = _eo_id_mem_calloc(1, sizeof(_Eo_Ids_Table)); eina_trash_init(&(ID_TABLE->queue)); /* We select directly the first entry of the new table */ - ptr = &(ID_TABLE->ptrs[0]); + entry = &(ID_TABLE->entries[0]); ID_TABLE->start = 1; } else { /* We try to pop from the queue an unused entry */ - ptr = (_Eo **)eina_trash_pop(&(ID_TABLE->queue)); + entry = (_Eo_Id_Entry *)eina_trash_pop(&(ID_TABLE->queue)); } - if (!ptr && ID_TABLE->start < MAX_IDS_PER_TABLE) + if (!entry && ID_TABLE->start < MAX_IDS_PER_TABLE) { /* No more unused entries in the trash but still empty entries in the table */ - ptr = &(ID_TABLE->ptrs[ID_TABLE->start]); + entry = &(ID_TABLE->entries[ID_TABLE->start]); ID_TABLE->start++; } - if (ptr) + if (entry) { /* An entry was found - need to find the entry id and fill it */ - Table_Index id = ptr - ID_TABLE->ptrs; - ID_TABLE->generation[id] = _eo_generation_counter; - ACTIVATE_ENTRY(ID_TABLE, id); - *ptr = (_Eo *)obj; - ret = EO_COMPOSE_ID(table_id, int_table_id, id, _eo_generation_counter); + entry->ptr = (_Eo *)obj; + entry->active = 1; + entry->generation = _eo_generation_counter; _eo_generation_counter++; _eo_generation_counter %= MAX_GENERATIONS; - return ret; + return EO_COMPOSE_ID(table_id, int_table_id, + (entry - ID_TABLE->entries), + entry->generation); } } } - return ret; + return 0; #else return (Eo_Id)obj; #endif @@ -277,22 +274,24 @@ void _eo_id_release(const Eo_Id obj_id) { #ifdef HAVE_EO_ID + _Eo_Id_Entry *entry; Table_Index table_id, int_table_id, entry_id, generation; EO_DECOMPOSE_ID((Table_Index) obj_id, table_id, int_table_id, entry_id, generation); /* Checking the validity of the entry */ - if (!_eo_ids_tables[table_id]) goto error; - if (!ID_TABLE) goto error; - if (ID_TABLE->generation[entry_id] != generation) goto error; - - /* Disable the entry */ - DEACTIVATE_ENTRY(ID_TABLE, entry_id); - /* Push the entry into the queue */ - eina_trash_push(&(ID_TABLE->queue), &(ID_TABLE->ptrs[entry_id])); - - return; + if (_eo_ids_tables[table_id] && ID_TABLE) + { + entry = &(ID_TABLE->entries[entry_id]); + if (entry && entry->active && (entry->generation == generation)) + { + /* Disable the entry */ + entry->active = 0; + /* Push the entry into the queue */ + eina_trash_push(&(ID_TABLE->queue), entry); + return; + } + } -error: ERR("obj_id %p is not pointing to a valid object. Maybe it has already been freed.", (void *)obj_id); #else (void) obj_id; @@ -323,6 +322,7 @@ _eo_free_ids_tables() void _eo_print() { + _Eo_Id_Entry *entry; unsigned long obj_number = 0; for (Table_Index table_id = 0; table_id < MAX_IDS_TABLES; table_id++) { @@ -334,12 +334,13 @@ _eo_print() { for (Table_Index entry_id = 0; entry_id < MAX_IDS_PER_TABLE; entry_id++) { - if (IS_ENTRY_ACTIVE(ID_TABLE, entry_id)) + entry = &(ID_TABLE->entries[entry_id]); + if (entry->active) { printf("%ld: %p -> (%p, %p, %p, %p)\n", obj_number++, - ID_TABLE->ptrs[entry_id], + entry->ptr, (void *)table_id, (void *)int_table_id, (void *)entry_id, - (void *)ID_TABLE->generation[entry_id]); + (void *)entry->generation); } } } -- 2.7.4