Re: GObject extension propose (GContainer)

[Tim Janik <timj imendio com>]

On Sat, 17 Jun 2006, Tristan Van Berkom wrote:

> Alan M. Evans wrote:
> [...]
>
> > > the lookup penalties are negligible.
> > > type node/class lookups and is_a checks are O(1);
> > > interface class lookups and conforms_to checks are O(ld(N)), where
> > > N is the number of interfaces a type node conforms to.
> >
> > Your assertion that the penalties are negligable is not really supported
> > by your response, unless the constant is also known for both orders.
> From my swift glance at gtype.c, it seems that in the case of
> an interface, the implementing interface is searched on that class's
> list of implementing interfaces... so when classes implement
> hundreds of interfaces it might be a performance hit.

no there won't be a performance hit.

that's because gtype.c uses a binary search for the
lookups (as indicated in my last email by the O(ld(N)) complexity).
the function used for frequent interface lookups is:

gpointer g_type_interface_peek (gpointer instance_class,
                                GType    iface_type);
and in a nutshell, it does:
{
  TypeNode *node = lookup_type_node_I (class->g_type);	       // O(1)
  TypeNode *iface = lookup_type_node_I (iface_type);	       // O(1)
  IFaceEntry *entry = type_lookup_iface_entry_L (node, iface); // O(ld(N))
  return entry->vtable;
}

take a look at gtype.c and type_lookup_iface_entry_L() to confirm.
using a binary lookup in type_lookup_iface_entry_L() means, lookups in terms
of number of interfaces and node visits during the search relate like this:

       interfaces-per-node  |  visits-per-lookup
                   1        |        1.0
                   2        |        2.0
                   3        |        2.6
                   4        |        3.0
                   5        |        3.3
                   6        |        3.6
                   8        |        4.0
                  16        |        5.0
                  32        |        6.0
                  64        |        7.0
                 128        |        8.0
                 256        |        9.0
                 512        |       10.0
                1024        |       11.0
               65536        |       17.0
              262144        |       19.0
             1048576        |       21.0
            67108864        |       27.0
           268435456        |       29.0
          2147483648        |       32.0

that is, for all practical purposes, interface lookups are negligible even
for many thausands of interfaces implemented per node.

and now, please show me the OO system that gets into the hundreds at least...

> Cheers,
>                                     -Tristan

---
ciaoTJ