[ruby-core:61631] Re: hash function for global method cache

what's the profit from using binary tree in place of hash?
20.03.2014 11:12 ミマフリレマラチヤナフリ "Eric Wong" <[e-mail]> ホチミノモチフ:

> SASADA Koichi <[e-mail]> wrote:
> > (2014/03/18 8:03), Eric Wong wrote:
> > > Global method cache is power-of-two-sized; so it should have a good
> hash
> > > function.  In vm_method.c:
> >
> > FYI (maybe you know): funny_fulcon proposed to replace global cache by
> > per-class cache.
> > https://bugs.ruby-lang.org/issues/9262
>
> Yes, that issue is for growing global cache, though.  It seems per-class
> cache idea is dead for now.
>
> Long term hope is to get rid of the global cache and only use inline
> cache.
>
> ihash[1] with hash-based IDs[2] should be faster than the current st.c +
> incrementing IDs.  However my primary goal of ihash was memory saving,
> but speed should happen because of reduced indirection.
>
> I will also try RB tree (steal rb.h from jemalloc) or splay tree
> (*BSD sys/tree.h) for method tables/constants.  id/symbol table
> might be too big for a binary search tree.
>
>
> [1] - https://bugs.ruby-lang.org/issues/9614
>       git://80x24.org/ruby.git ihash5
>
> [2] - not implemented, yet, probably not going to touch parse.y
>       until Symbol GC patch is merged.
>