From: "Юрий Соколов" <funny.falcon@...>
Date: 2014-03-23T10:37:57+04:00
Subject: [ruby-core:61643] Re: hash function for global method cache

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

Fixing hash function is much simpler. Unordered hash with open addressing
could be much faster and have size not bigger than any binary tree
(simplified specialized khash). Hope that inline hash will fix logarithmic
search time is ridiculous.
I could be wrong in any sentence. Time will show.
22.03.2014 7:20 =D0=CF=CC=D8=DA=CF=D7=C1=D4=C5=CC=D8 "Eric Wong" <normalper=
son@yhbt.net> =CE=C1=D0=C9=D3=C1=CC:

> =E0=D2=C9=CA =F3=CF=CB=CF=CC=CF=D7 <funny.falcon@gmail.com> wrote:
> > what's the profit from using binary tree in place of hash?
>
> Mainly: not caring about the quality of hash function :)
>
> Also: no extra allocation/resizing for buckets (but existing allocations
> get 1 pointer bigger than my ihash implementation).  Splay tree has
> self-optimizing behavior may also be good for us (but hurts CoW).
>
>
> Fwiw, I also played with critbit trees (with container_of), but could
> not figure out how to do non-recursive traversal nor conditional
> unlink/delete while traversing :<
>

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

<p dir=3D"ltr">Fixing hash function is much simpler. Unordered hash with op=
en addressing could be much faster and have size not bigger than any binary=
 tree (simplified specialized khash). Hope that inline hash will fix logari=
thmic search time is ridiculous.<br>

I could be wrong in any sentence. Time will show. </p>
<div class=3D"gmail_quote">22.03.2014 7:20 =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">
=E0=D2=C9=CA =F3=CF=CB=CF=CC=CF=D7 &lt;<a href=3D"mailto:funny.falcon@gmail=
.com">funny.falcon@gmail.com</a>&gt; wrote:<br>
&gt; what&#39;s the profit from using binary tree in place of hash?<br>
<br>
Mainly: not caring about the quality of hash function :)<br>
<br>
Also: no extra allocation/resizing for buckets (but existing allocations<br=
>
get 1 pointer bigger than my ihash implementation). =9ASplay tree has<br>
self-optimizing behavior may also be good for us (but hurts CoW).<br>
<br>
<br>
Fwiw, I also played with critbit trees (with container_of), but could<br>
not figure out how to do non-recursive traversal nor conditional<br>
unlink/delete while traversing :&lt;<br>
</blockquote></div>

--001a1135effe0540f204f5405c60--