summaryrefslogtreecommitdiff
path: root/src/lib/eo/eo_ptr_indirection.c
diff options
context:
space:
mode:
authorJérémy Zurcher <jeremy@asynk.ch>2013-05-05 15:08:55 +0200
committerJérémy Zurcher <jeremy@asynk.ch>2013-05-05 15:18:01 +0200
commit94b6dff74c70d8e06d2cf7a16deb174e28b40935 (patch)
tree014d6d54dd38b2ee5f78b3ad8e9acb491912f5ab /src/lib/eo/eo_ptr_indirection.c
parent10aafd711d2b019df0154c7627a52c650a006244 (diff)
eo ptr ind: speed up by caching last used table
- keep a reference to the last used table and it's indexes - use this table prior to normal search through table arrays
Diffstat (limited to 'src/lib/eo/eo_ptr_indirection.c')
-rw-r--r--src/lib/eo/eo_ptr_indirection.c134
1 files changed, 95 insertions, 39 deletions
diff --git a/src/lib/eo/eo_ptr_indirection.c b/src/lib/eo/eo_ptr_indirection.c
index ddb7a78..9ee90b5 100644
--- a/src/lib/eo/eo_ptr_indirection.c
+++ b/src/lib/eo/eo_ptr_indirection.c
@@ -43,17 +43,20 @@
43 * - a flag indicating if the entry is active 43 * - a flag indicating if the entry is active
44 * - a generation assigned to the object 44 * - a generation assigned to the object
45 * - an index 'next_in_queue' used to chain the entries in the queue 45 * - an index 'next_in_queue' used to chain the entries in the queue
46 *
46 * When an entry is searched into a table, we first use one of the entries that 47 * When an entry is searched into a table, we first use one of the entries that
47 * has never been used. If there is none, we try to pop from the queue. 48 * has never been used. If there is none, we try to pop from the queue.
49 * Assigning all the entries of a table before trying to reuse them from
50 * the fifo ensures that we are not going to soon recycle a released entry,
51 * thus minimize the risks of an aggressive del() then use() on a single entry.
48 * If a such entry doesn't exist, we pass to the next table. 52 * If a such entry doesn't exist, we pass to the next table.
49 * When an entry is found, we reserve it to the object pointer and create 53 * When an entry is found, we reserve it to the object pointer and create
50 * the id with the table id, the intermediate table id, the entry and a 54 * the id with the table id, the intermediate table id, the entry and a
51 * generation. 55 * generation.
56 * The indexes and a reference to the last table which served an entry is kept
57 * and is reused prior to the others untill it is full.
52 * When an object is freed, the entry into the table is released by appending 58 * When an object is freed, the entry into the table is released by appending
53 * it to the queue. 59 * it to the queue.
54 * Assigning all the entries of a table before trying to reuse them from
55 * the fifo ensures that we are not going to soon recycle a released entry,
56 * thus minimize the risks of an aggressive del() then use() on a single entry.
57 */ 60 */
58 61
59#if SIZEOF_UINTPTR_T == 4 62#if SIZEOF_UINTPTR_T == 4
@@ -178,8 +181,22 @@ typedef struct
178 Table_Index queue_tail; 181 Table_Index queue_tail;
179} _Eo_Ids_Table; 182} _Eo_Ids_Table;
180 183
184/* Table Info */
185typedef struct
186{
187 /* Table pointer */
188 _Eo_Ids_Table *table;
189 /* Top table index */
190 Table_Index table_id;
191 /* Intermediate table index */
192 Table_Index int_table_id;
193} _Eo_Table_Info;
194
181/* Tables handling pointers indirection */ 195/* Tables handling pointers indirection */
182_Eo_Ids_Table **_eo_ids_tables[MAX_IDS_TABLES] = { NULL }; 196static _Eo_Ids_Table **_eo_ids_tables[MAX_IDS_TABLES] = { NULL };
197
198/* Current table used for following allocations */
199static _Eo_Table_Info current_table = { NULL, 0, 0 };
183 200
184/* Next generation to use when assigning a new entry to a Eo pointer */ 201/* Next generation to use when assigning a new entry to a Eo pointer */
185Generation_Counter _eo_generation_counter; 202Generation_Counter _eo_generation_counter;
@@ -228,66 +245,104 @@ _eo_obj_pointer_get(const Eo_Id obj_id)
228#endif 245#endif
229} 246}
230 247
231Eo_Id 248static inline _Eo_Id_Entry *
232_eo_id_allocate(const _Eo *obj) 249get_available_entry(_Eo_Ids_Table *table)
233{ 250{
234#ifdef HAVE_EO_ID
235 _Eo_Ids_Table *table;
236 _Eo_Id_Entry *entry = NULL; 251 _Eo_Id_Entry *entry = NULL;
252
253 if (table->start != MAX_IDS_PER_TABLE)
254 {
255 /* Serve never used entries first */
256 entry = &(table->entries[table->start]);
257 table->start++;
258 }
259 else if (table->queue_head != -1)
260 {
261 /* Pop an unused entry from the queue */
262 entry = &(table->entries[table->queue_head]);
263 if (entry->next_in_queue == -1)
264 table->queue_head = table->queue_tail = -1;
265 else
266 table->queue_head = entry->next_in_queue;
267 }
268
269 return entry;
270}
271
272static inline _Eo_Id_Entry *
273search_tables()
274{
275 _Eo_Ids_Table *table;
276 _Eo_Id_Entry *entry;
277
237 for (Table_Index table_id = 1; table_id < MAX_IDS_TABLES; table_id++) 278 for (Table_Index table_id = 1; table_id < MAX_IDS_TABLES; table_id++)
238 { 279 {
239 if (!_eo_ids_tables[table_id]) 280 if (!_eo_ids_tables[table_id])
240 { 281 {
241 /* We allocate a new intermediate table */ 282 /* Allocate a new intermediate table */
242 _eo_ids_tables[table_id] = _eo_id_mem_calloc(MAX_IDS_INTER_TABLES, sizeof(_Eo_Ids_Table*)); 283 _eo_ids_tables[table_id] = _eo_id_mem_calloc(MAX_IDS_INTER_TABLES, sizeof(_Eo_Ids_Table*));
243 } 284 }
285
244 for (Table_Index int_table_id = 0; int_table_id < MAX_IDS_INTER_TABLES; int_table_id++) 286 for (Table_Index int_table_id = 0; int_table_id < MAX_IDS_INTER_TABLES; int_table_id++)
245 { 287 {
246 table = ID_TABLE; 288 table = ID_TABLE;
289
247 if (!table) 290 if (!table)
248 { 291 {
249 /* We allocate a new table */ 292 /* Allocate a new table and reserve the first entry */
250 table = _eo_id_mem_calloc(1, sizeof(_Eo_Ids_Table)); 293 table = _eo_id_mem_calloc(1, sizeof(_Eo_Ids_Table));
251 table->start = 1; 294 table->start = 1;
252 table->queue_head = table->queue_tail = -1; 295 table->queue_head = table->queue_tail = -1;
253 ID_TABLE = table; 296 ID_TABLE = table;
254 /* We select directly the first entry of the new table */
255 entry = &(table->entries[0]); 297 entry = &(table->entries[0]);
256 } 298 }
257 else if (table->start < MAX_IDS_PER_TABLE)
258 {
259 /* We use an empty entries in the table */
260 entry = &(table->entries[table->start]);
261 table->start++;
262 }
263 else if (table->queue_head != -1)
264 {
265 /* We pop an unused entry from the queue */
266 entry = &(table->entries[table->queue_head]);
267 if (entry->next_in_queue == -1)
268 table->queue_head = table->queue_tail = -1;
269 else
270 table->queue_head = entry->next_in_queue;
271 }
272 else 299 else
273 { 300 {
274 /* Table is full of actives entries */ 301 entry = get_available_entry(table);
275 continue;
276 } 302 }
277 303
278 assert(entry); 304 if (entry)
279 /* An entry was found - need to find the entry id and fill it */ 305 {
280 entry->ptr = (_Eo *)obj; 306 /* Store table info into current table */
281 entry->active = 1; 307 current_table.table = table;
282 entry->generation = _eo_generation_counter; 308 current_table.table_id = table_id;
283 _eo_generation_counter++; 309 current_table.int_table_id = int_table_id;
284 _eo_generation_counter %= MAX_GENERATIONS; 310 return entry;
285 return EO_COMPOSE_ID(table_id, int_table_id, 311 }
286 (entry - table->entries),
287 entry->generation);
288 } 312 }
289 } 313 }
290 return 0; 314
315 ERR("no more available entries to store eo objects");
316 current_table.table = NULL;
317 return NULL;
318}
319
320Eo_Id
321_eo_id_allocate(const _Eo *obj)
322{
323#ifdef HAVE_EO_ID
324 _Eo_Id_Entry *entry = NULL;
325
326 if (current_table.table)
327 entry = get_available_entry(current_table.table);
328
329 if (!entry)
330 {
331 entry = search_tables();
332 if (!entry)
333 return 0;
334 }
335
336 /* An entry was found - fill it */
337 entry->ptr = (_Eo *)obj;
338 entry->active = 1;
339 entry->generation = _eo_generation_counter;
340 _eo_generation_counter++;
341 _eo_generation_counter %= MAX_GENERATIONS;
342 return EO_COMPOSE_ID(current_table.table_id,
343 current_table.int_table_id,
344 (entry - current_table.table->entries),
345 entry->generation);
291#else 346#else
292 return (Eo_Id)obj; 347 return (Eo_Id)obj;
293#endif 348#endif
@@ -350,6 +405,7 @@ _eo_free_ids_tables()
350 } 405 }
351 _eo_ids_tables[table_id] = NULL; 406 _eo_ids_tables[table_id] = NULL;
352 } 407 }
408 current_table.table = NULL;
353} 409}
354 410
355#ifdef EFL_DEBUG 411#ifdef EFL_DEBUG