From: "Юрий Соколов" <funny.falcon@...>
Date: 2015-08-13T00:28:29+03:00
Subject: [ruby-core:70357] Re: [Ruby trunk - Feature #11420] [Open] Introduce ID key table into MRI

--047d7b450b1060ac8a051d23e652
Content-Type: text/plain; charset=UTF-8

First btw is:

struct entry {
   uint32 hash, next, prev, forw;
   st_data_t key, value;
 } entries[capa];
uint32 bins[numbins];
#=>
 bins   : [ ... ]
 entries: [[hash1, next, prev, forw, key1, val1], ...]

Second btw (php7-like) is (as you correctly assumed):

struct entry {
   uint hash, next;
   st_data_t key, value;
 } entries[capa];
uint32 bins[numbins];
#=>
 bins   : [ ... ]
 entries: [[hash1, next, key1, val1], ...]

I think, incremental compaction can fix worst case of php7-like hash
(longliving continiously mutated huge hash), so i'll try to implement it.

> struct hash_id_table {
>     int capa;
>     int num;
>     int used;
>     item_t *items;
> };
> Can we eliminate `used'? If we can remove it, table size will be 16B.
> I understand used and num is not same (used counts delete empty,
> collited entries), but `used' is used only for extension. How about to
> use num for this purpose? Sorry if I misunderstood.

With presence of deletions, 'used' is neccessary for most of
open-addressing algorithms.

Two algos which don't need 'used' are "Coockoo Hashing" and "Robin-Hood
with backshifting". Coockoo limits number of possible slots for an element,
and Robin-Hood do more job on deletion (in case of collisions). Both will
do much more job on insertion than simple openaddressing.

Coalesce chained hash could be also made without free_pos with searching
for free position like with open-adressing. It will increase insertion time
a bit, but otherwise, it is ok. Should I implement it?

With regards,
Sokolov Yura aka funny_falcon

--047d7b450b1060ac8a051d23e652
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<p dir=3D"ltr">First btw is:</p>
<p dir=3D"ltr">struct entry {<br>
=C2=A0 =C2=A0uint32 hash, next, prev, forw;<br>
=C2=A0=C2=A0 st_data_t key, value;<br>
=C2=A0} entries[capa];<br>
uint32 bins[numbins];<br>
#=3D&gt;<br>
=C2=A0bins=C2=A0 =C2=A0: [ ... ]<br>
=C2=A0entries: [[hash1, next, prev, forw, key1, val1], ...]</p>
<p dir=3D"ltr">Second btw (php7-like) is (as you correctly assumed):</p>
<p dir=3D"ltr">struct entry {<br>
=C2=A0 =C2=A0uint hash, next;<br>
=C2=A0=C2=A0 st_data_t key, value;<br>
=C2=A0} entries[capa];<br>
uint32 bins[numbins];<br>
#=3D&gt;<br>
=C2=A0bins=C2=A0 =C2=A0: [ ... ]<br>
=C2=A0entries: [[hash1, next, key1, val1], ...]</p>
<p dir=3D"ltr">I think, incremental compaction can fix worst case of php7-l=
ike hash (longliving continiously mutated huge hash), so i&#39;ll try to im=
plement it.</p>
<p dir=3D"ltr">&gt; struct hash_id_table {<br>
&gt; =C2=A0 =C2=A0 int capa;<br>
&gt; =C2=A0 =C2=A0 int num;<br>
&gt; =C2=A0 =C2=A0 int used;<br>
&gt; =C2=A0 =C2=A0 item_t *items;<br>
&gt; };<br>
&gt; Can we eliminate `used&#39;? If we can remove it, table size will be 1=
6B.<br>
&gt; I understand used and num is not same (used counts delete empty,<br>
&gt; collited entries), but `used&#39; is used only for extension. How abou=
t to<br>
&gt; use num for this purpose? Sorry if I misunderstood.</p>
<p dir=3D"ltr">With presence of deletions, &#39;used&#39; is neccessary for=
 most of open-addressing algorithms.</p>
<p dir=3D"ltr">Two algos which don&#39;t need &#39;used&#39; are &quot;Cooc=
koo Hashing&quot; and &quot;Robin-Hood with backshifting&quot;. Coockoo lim=
its number of possible slots for an element, and Robin-Hood do more job on =
deletion (in case of collisions). Both will do much more job on insertion t=
han simple openaddressing.</p>
<p dir=3D"ltr">Coalesce chained hash could be also made without free_pos wi=
th searching for free position like with open-adressing. It will increase i=
nsertion time a bit, but otherwise, it is ok. Should I implement it?</p>
<p dir=3D"ltr">With regards,<br>
Sokolov Yura aka funny_falcon</p>

--047d7b450b1060ac8a051d23e652--