From 28c80f91221ae2639f4573046d8621a2a4d18cda Mon Sep 17 00:00:00 2001 From: Tom Hacohen Date: Mon, 15 Aug 2016 17:11:13 +0100 Subject: [PATCH] Efl object: implement CoW for the function vtables This commit implements a sort of CoW for the vtables. The vtables are usually just linked to and refcounted. When we need to change them we allocate new ones and copy them over so we can write to them. I wrote some code to measure the effectiveness of this change. When running elementary_test (and immediately exiting) I saw that out of the total number of vtable chains (561) that were needed by the classes in the EFL, 79 (14.08%) were reused. Considering that I had to add refcounting (unsigned short, but let's consider it's the size of a word because of alignment), I would calculate the saving as such (in bytes): Number of items in a chain (refcounted block): 32 32 bit: sizeof(chain_node) = 8 Mem wasted on refcounting: 561 * 4 = 2244 Mem saved because of sharing: 79 * (32 * 8) = 20224 Total save: 17980 bytes 64 bit: sizeof(chain_node) = 16 Mem wasted on refcounting: 561 * 8 = 4488 Mem saved because of sharing: 79 * (32 * 16) = 40448 Total save: 35960 bytes Wow, we use a lot of memory in Eo classes, I'm sure we can save even more if we put our hearts into it (change the shareable units to be smaller to increase the chance of sharing). This is internal and doesn't affect API/ABI so we can change this even further with time. This also improves efl_object_override(). This should now be quite memory efficient (don't abuse, but it's not a big hogg as it was), so feel free to abuse that one and rely on it in API. @feature --- src/lib/eo/eo.c | 114 ++++++++++++++++++++++++++++++++++++------------ src/lib/eo/eo_private.h | 14 +++++- 2 files changed, 98 insertions(+), 30 deletions(-) diff --git a/src/lib/eo/eo.c b/src/lib/eo/eo.c index 9104a9e..0f530b4 100644 --- a/src/lib/eo/eo.c +++ b/src/lib/eo/eo.c @@ -41,12 +41,6 @@ static inline void _efl_data_xunref_internal(_Eo_Object *obj, void *data, const /* Start of Dich */ -/* How we search and store the implementations in classes. */ -#define DICH_CHAIN_LAST_BITS 5 -#define DICH_CHAIN_LAST_SIZE (1 << DICH_CHAIN_LAST_BITS) -#define DICH_CHAIN1(x) ((x) >> DICH_CHAIN_LAST_BITS) -#define DICH_CHAIN_LAST(x) ((x) & ((1 << DICH_CHAIN_LAST_BITS) - 1)) - /* We are substracting the mask here instead of "AND"ing because it's a hot path, * it should be a valid class at this point, and this lets the compiler do 1 @@ -58,11 +52,86 @@ static inline void _efl_data_xunref_internal(_Eo_Object *obj, void *data, const }) static inline void +_vtable_chain2_unref(Dich_Chain2 *chain) +{ + if (--(chain->refcount) == 0) + { + free(chain); + } +} + +static inline void _vtable_chain_alloc(Dich_Chain1 *chain1) { - if (!chain1->funcs) + chain1->chain2 = calloc(1, sizeof(*(chain1->chain2))); + chain1->chain2->refcount = 1; +} + +static inline void _vtable_chain_write_prepare(Dich_Chain1 *dst); + +static inline void +_vtable_chain_merge(Dich_Chain1 *dst, const Dich_Chain1 *src) +{ + Eina_Bool writeable = EINA_FALSE; + size_t j; + const op_type_funcs *sf = src->chain2->funcs; + op_type_funcs *df = dst->chain2->funcs; + + if (df == sf) { - chain1->funcs = calloc(DICH_CHAIN_LAST_SIZE, sizeof(*(chain1->funcs))); + /* Skip if the chain is the same. */ + return; + } + + for (j = 0 ; j < DICH_CHAIN_LAST_SIZE ; j++, df++, sf++) + { + if (sf->func && memcmp(df, sf, sizeof(*df))) + { + if (!writeable) + { + _vtable_chain_write_prepare(dst); + df = dst->chain2->funcs + j; + } + + memcpy(df, sf, sizeof(*df)); + } + } +} + +static inline void +_vtable_chain_write_prepare(Dich_Chain1 *dst) +{ + if (!dst->chain2) + { + _vtable_chain_alloc(dst); + return; + } + else if (dst->chain2->refcount == 1) + { + /* We own it, no need to duplicate */ + return; + } + + Dich_Chain1 old; + old.chain2 = dst->chain2; + + _vtable_chain_alloc(dst); + _vtable_chain_merge(dst, &old); + + _vtable_chain2_unref(old.chain2); +} + +static inline void +_vtable_chain_copy_ref(Dich_Chain1 *dst, const Dich_Chain1 *src) +{ + if (dst->chain2) + { + _vtable_chain_merge(dst, src); + } + else + { + dst->chain2 = src->chain2; + dst->chain2->refcount++; } } @@ -74,21 +143,9 @@ _vtable_copy_all(Eo_Vtable *dst, const Eo_Vtable *src) Dich_Chain1 *dc1 = dst->chain; for (i = 0 ; i < src->size ; i++, sc1++, dc1++) { - if (sc1->funcs) + if (sc1->chain2) { - size_t j; - - _vtable_chain_alloc(dc1); - - const op_type_funcs *sf = sc1->funcs; - op_type_funcs *df = dc1->funcs; - for (j = 0 ; j < DICH_CHAIN_LAST_SIZE ; j++, df++, sf++) - { - if (sf->func) - { - memcpy(df, sf, sizeof(*df)); - } - } + _vtable_chain_copy_ref(dc1, sc1); } } } @@ -100,9 +157,9 @@ _vtable_func_get(const Eo_Vtable *vtable, Efl_Object_Op op) if (EINA_UNLIKELY(idx1 >= vtable->size)) return NULL; Dich_Chain1 *chain1 = &vtable->chain[idx1]; - if (EINA_UNLIKELY(!chain1->funcs)) + if (EINA_UNLIKELY(!chain1->chain2)) return NULL; - return &chain1->funcs[DICH_CHAIN_LAST(op)]; + return &chain1->chain2->funcs[DICH_CHAIN_LAST(op)]; } /* XXX: Only used for a debug message below. Doesn't matter that it's slow. */ @@ -135,8 +192,8 @@ _vtable_func_set(Eo_Vtable *vtable, const _Efl_Class *klass, Efl_Object_Op op, e op_type_funcs *fsrc; size_t idx1 = DICH_CHAIN1(op); Dich_Chain1 *chain1 = &vtable->chain[idx1]; - _vtable_chain_alloc(chain1); - fsrc = &chain1->funcs[DICH_CHAIN_LAST(op)]; + _vtable_chain_write_prepare(chain1); + fsrc = &chain1->chain2->funcs[DICH_CHAIN_LAST(op)]; if (fsrc->src == klass) { const _Efl_Class *op_kls = _eo_op_class_get(op); @@ -159,8 +216,8 @@ _vtable_func_clean_all(Eo_Vtable *vtable) for (i = 0 ; i < vtable->size ; i++, chain1++) { - if (chain1->funcs) - free(chain1->funcs); + if (chain1->chain2) + _vtable_chain2_unref(chain1->chain2); } free(vtable->chain); vtable->chain = NULL; @@ -1849,4 +1906,3 @@ efl_manual_free(Eo *obj_id) return EINA_TRUE; } - diff --git a/src/lib/eo/eo_private.h b/src/lib/eo/eo_private.h index 37ee7c7..4096145 100644 --- a/src/lib/eo/eo_private.h +++ b/src/lib/eo/eo_private.h @@ -123,6 +123,12 @@ struct _Eo_Object Eina_Bool manual_free:1; }; +/* How we search and store the implementations in classes. */ +#define DICH_CHAIN_LAST_BITS 5 +#define DICH_CHAIN_LAST_SIZE (1 << DICH_CHAIN_LAST_BITS) +#define DICH_CHAIN1(x) ((x) >> DICH_CHAIN_LAST_BITS) +#define DICH_CHAIN_LAST(x) ((x) & ((1 << DICH_CHAIN_LAST_BITS) - 1)) + /* FIXME: Change the type to something generic that makes sense for eo */ typedef void (*eo_op_func_type)(Eo *, void *class_data, va_list *list); @@ -132,9 +138,15 @@ typedef struct const _Efl_Class *src; } op_type_funcs; +typedef struct _Dich_Chain2 +{ + op_type_funcs funcs[DICH_CHAIN_LAST_SIZE]; + unsigned short refcount; +} Dich_Chain2; + struct _Dich_Chain1 { - op_type_funcs *funcs; + Dich_Chain2 *chain2; }; typedef struct -- 2.7.4