<div dir="ltr"><div>Hey,</div><div><br></div><div>Background</div><div>----------------</div><div>I built a hash table in C:  <a href="https://github.com/Peaker/small_hash">https://github.com/Peaker/small_hash</a></div><div>
<br></div><div>According to a few simple benchmarks (mainly, 10 million insertions), my C hash table is much faster than any Haskell data structure I tried (e.g: 8 times faster than IntMap).</div><div>You can run the C benchmark (in small_hash) via: &quot;make &amp;&amp; ./benchmark 10000000&quot;.</div>
<div><br></div><div>The other benchmarks are at: <a href="https://github.com/Peaker/hashtable_benchmarks">https://github.com/Peaker/hashtable_benchmarks</a></div><div><div>Benchmarks results on my hardware: <a href="http://hpaste.org/81902">http://hpaste.org/81902</a></div>
</div><div><br></div><div>I was hoping to get that fast mapping goodness to Haskell, by building an FFI to it:</div><div><a href="https://github.com/Peaker/small_hash_hs">https://github.com/Peaker/small_hash_hs</a></div><div>
<br></div><div>In order to do FFI bindings to a C data structure, that can contain arbitrary Haskell values, I must create a lot of StablePtrs (for each Haskell value stored in the C hash table).</div><div><br></div><div>
Problem 1:</div><div>-------------</div><div>Disappointingly, the FFI bindings were dozens of times slower(!) than the C code.</div><div><br></div><div>When using +RTS -H200M the speed is about 10 times slower(!) than the C code.</div>
<div>oprofile shows that the culprit is the Stable Ptr code.</div><div><br></div><div>Digging in, I found that stable ptrs and stable names shared a table, despite having quite different characteristics:</div><div> * Stable Names aren&#39;t considered roots by GC, ptrs are.</div>
<div> * Making two stable ptrs for the same Haskell value doesn&#39;t really require them to unify -- so there&#39;s no need for the hash table or the &quot;refs&quot; counter for stable ptrs.</div><div><br></div><div>My Changes:</div>
<div>-----------------</div><div>I split the Stable Names into their own table (which allowed removing the &quot;refs&quot; field from them).</div><div>Stable Ptrs no longer use a hash table to unify, don&#39;t need &quot;refs&quot;, or &quot;sn_obj&quot;, or &quot;old&quot;.</div>
<div><br></div><div>This made Stable Ptrs cost just 1 C ptr in the table and really cheap to create/destroy.</div><div><div><br></div><div>The commits are here:</div><div><a href="https://github.com/Peaker/ghc/commits/master">https://github.com/Peaker/ghc/commits/master</a></div>
</div><div><br></div><div><div>They are not polished (I didn&#39;t thoroughly review myself yet, didn&#39;t run the test suite, fix out-of-date comments involved) and not ready for integration yet.</div></div><div><br></div>
<div>Result:</div><div>---------</div><div>The hash table benchmark via the FFI is now only ~2 times slower than the C data structure and much faster than any other mapping structure for that particular benchmark (10 million insertions of identity integers, sequentially). A lot of the cost here is due to fine-grained allocation, as the C code does bulk allocation. I shall improve this benchmark later, and I believe it will tighten the gap some more.</div>
<div><br></div><div>Problem 2:</div><div>--------------</div><div><a href="http://hackage.haskell.org/trac/ghc/ticket/7670">http://hackage.haskell.org/trac/ghc/ticket/7670</a></div><div><br></div><div>Every minor GC iterates a whole lot of stable ptrs. This means that with the default heap size, runtime is about 8 times longer (than with a 200M heap size).</div>
<div><br></div><div>To avoid this, I&#39;d like to split the stable ptrs table into generations.</div><div><br></div><div>To do this, I need to know which of the pointed objects were promoted and to what generation, so I can promote my stable ptrs accordingly.</div>
<div>It seems like the correct time to do this is in the updateStablePtrTable (now named &quot;updateStableTables&quot;)</div><div><br></div><div>This is the part I need help with.</div><div>How do I know if an object was promoted to a higher generation when I traverse the objects?</div>
<div><div><br></div><div>Thanks! </div><div dir="ltr">Eyal</div><div dir="ltr"><br></div>
</div></div>