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

2 files changed, 98 insertions, 30 deletions

diff --git a/src/lib/eo/eo.c b/src/lib/eo/eo.c
index 9104a9e499..0f530b41d2 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 37ee7c7919..40961459d5 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