From: "Юрий Соколов" <funny.falcon@...>
Date: 2014-03-22T07:01:16+04:00
Subject: [ruby-core:61631] Re: hash function for global method cache

--001a11c2e2b847f78004f5293712
Content-Type: text/plain; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable

what's the profit from using binary tree in place of hash?
20.03.2014 11:12 =D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 "Eric Wong" <normalpe=
rson@yhbt.net> =CE=C1=D0=C9=D3=C1=CC:

> SASADA Koichi <ko1@atdot.net> 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.
>

--001a11c2e2b847f78004f5293712
Content-Type: text/html; charset=KOI8-R
Content-Transfer-Encoding: quoted-printable

<p dir=3D"ltr">what&#39;s the profit from using binary tree in place of has=
h?</p>
<div class=3D"gmail_quote">20.03.2014 11:12 =D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=
=CC=D8 &quot;Eric Wong&quot; &lt;<a href=3D"mailto:normalperson@yhbt.net">n=
ormalperson@yhbt.net</a>&gt; =CE=C1=D0=C9=D3=C1=CC:<br type=3D"attribution"=
><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1=
px #ccc solid;padding-left:1ex">
SASADA Koichi &lt;<a href=3D"mailto:ko1@atdot.net">ko1@atdot.net</a>&gt; wr=
ote:<br>
&gt; (2014/03/18 8:03), Eric Wong wrote:<br>
&gt; &gt; Global method cache is power-of-two-sized; so it should have a go=
od hash<br>
&gt; &gt; function. =9AIn vm_method.c:<br>
&gt;<br>
&gt; FYI (maybe you know): funny_fulcon proposed to replace global cache by=
<br>
&gt; per-class cache.<br>
&gt; <a href=3D"https://bugs.ruby-lang.org/issues/9262" target=3D"_blank">h=
ttps://bugs.ruby-lang.org/issues/9262</a><br>
<br>
Yes, that issue is for growing global cache, though. =9AIt seems per-class<=
br>
cache idea is dead for now.<br>
<br>
Long term hope is to get rid of the global cache and only use inline<br>
cache.<br>
<br>
ihash[1] with hash-based IDs[2] should be faster than the current st.c +<br=
>
incrementing IDs. =9AHowever my primary goal of ihash was memory saving,<br=
>
but speed should happen because of reduced indirection.<br>
<br>
I will also try RB tree (steal rb.h from jemalloc) or splay tree<br>
(*BSD sys/tree.h) for method tables/constants. =9Aid/symbol table<br>
might be too big for a binary search tree.<br>
<br>
<br>
[1] - <a href=3D"https://bugs.ruby-lang.org/issues/9614" target=3D"_blank">=
https://bugs.ruby-lang.org/issues/9614</a><br>
=9A =9A =9A git://<a href=3D"http://80x24.org/ruby.git" target=3D"_blank">8=
0x24.org/ruby.git</a> ihash5<br>
<br>
[2] - not implemented, yet, probably not going to touch parse.y<br>
=9A =9A =9A until Symbol GC patch is merged.<br>
</blockquote></div>

--001a11c2e2b847f78004f5293712--