<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p>Indeed I misunderstood. As you already suspected this wouldn't
work for Int# (or other unboxed types) sadly as the GC would
assume these to be pointers which no doubt would lead to segfaults
or worse.<br>
<br>
Rereading your initial mail I can say the runtime currently
doesn't support such a heap object.<br>
If I understand you correctly what you would like is basically a
something like:<br>
<font face="monospace"><br>
Con n </font><font face="monospace"><font face="monospace">P
I# </font></font><font face="monospace"><font
face="monospace"><font face="monospace">P I# </font></font></font><font
face="monospace"><font face="monospace"><font face="monospace"><font
face="monospace">P I# ...</font></font></font> <br>
\/ </font><font face="monospace">\/</font><font
face="monospace"> </font><font face="monospace"><font
face="monospace">\/</font> <br>
Pair1 Pair2 Pair3 ...<br>
</font></p>
<p><font face="monospace">Where n gives the number of pairs.<br>
</font></p>
<p>I can see how it might be feasible to add a heap object like this
to GHC but I'm unsure if it would be worth the complexity as it's
layout diverges quite a bit from what GHC usually expects.<br>
<br>
The other option would be to expose to users a way to have an
object that consist of a given number of words and a bitmap which
indicates to the GHC which fields are pointers. This is more or
less<br>
the representation that's already used to deal with stack frames
iirc so that might not be as far fetched as it seems at first.<br>
It might even be possible to implement some sort of prototype for
this using hand written Cmm. <br>
<br>
But there are not any plans to implement anything like this as far
as I know. <br>
<br>
</p>
<div class="moz-cite-prefix">Am 02/08/2022 um 20:51 schrieb Jaro
Reinders:<br>
</div>
<blockquote type="cite"
cite="mid:77955754-cb22-b273-88cb-ddc1ceb7306b@gmail.com">
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<p>It seems you have misunderstood me. I want to store *unboxed*
Int#s inside the array, not just some unlifted types. Surely in
the case of unboxed integers the unsafeCoerce# function can make
the garbage collector crash as they might be interpreted as
arbitrary pointers.</p>
<p>Cheers,</p>
<p>Jaro<br>
</p>
<div class="moz-cite-prefix">On 02/08/2022 20:24, Andreas
Klebinger wrote:<br>
</div>
<blockquote type="cite"
cite="mid:fef30d8b-47b5-e4ca-6937-52c6c498696a@gmx.at">
<meta http-equiv="Content-Type" content="text/html;
charset=UTF-8">
<p>I think it's possible to do this *today* using unsafeCoerce#.</p>
<p>I was able to come up with this basic example below. In
practice one would at the very least want to abstract away the
gnarly stuff inside a<br>
library. But since it sounds like you want to be the one to
write a library that shouldn't be a problem.</p>
<div style="color: #d4d4d4;background-color: #1e1e1e;font-family: Consolas, 'Courier New', monospace;font-weight: normal;font-size: 14px;line-height: 19px;white-space: pre;"><div><span style="color: #569cd6;">{-# LANGUAGE MagicHash #-}</span></div><div><span style="color: #569cd6;">{-# LANGUAGE UnboxedTuples #-}</span></div><div><span style="color: #569cd6;">{-# LANGUAGE UnliftedDatatypes #-}</span></div>
<div><span style="color: #569cd6;">module</span><span style="color: #d4d4d4;"> </span><span style="color: #4ec9b0;">Main</span><span style="color: #d4d4d4;"> </span><span style="color: #569cd6;">where</span></div>
<div><span style="color: #569cd6;">import</span><span style="color: #d4d4d4;"> </span><span style="color: #4ec9b0;">GHC.Exts</span></div><div><span style="color: #569cd6;">import</span><span style="color: #d4d4d4;"> </span><span style="color: #4ec9b0;">GHC.IO</span></div><div><span style="color: #569cd6;">import</span><span style="color: #d4d4d4;"> </span><span style="color: #4ec9b0;">Unsafe.Coerce</span></div><div><span style="color: #569cd6;">import</span><span style="color: #d4d4d4;"> </span><span style="color: #4ec9b0;">Data.Kind</span></div>
<div><span style="color: #569cd6;">data</span><span style="color: #d4d4d4;"> </span><span style="color: #569cd6;">SA</span><span style="color: #d4d4d4;"> = SA (</span><span style="color: #569cd6;">SmallMutableArray</span><span style="color: #d4d4d4;"># </span><span style="color: #569cd6;">RealWorld</span><span style="color: #d4d4d4;"> </span><span style="color: #569cd6;">Any</span><span style="color: #d4d4d4;">)</span></div>
<div><span style="color: #dcdcaa;">mkArray</span><span style="color: #d4d4d4;"> :: </span><span style="color: #569cd6;">Int</span><span style="color: #d4d4d4;"> -> </span><span style="color: #9cdcfe;">a</span><span style="color: #d4d4d4;"> -> </span><span style="color: #569cd6;">IO</span><span style="color: #d4d4d4;"> (</span><span style="color: #569cd6;">SA</span><span style="color: #d4d4d4;">)</span></div><div><span style="color: #d4d4d4;">mkArray (I# n) initial = IO $ \s -></span></div><div><span style="color: #d4d4d4;"> </span><span style="color: #c586c0;">case</span><span style="color: #d4d4d4;"> unsafeCoerce# (newSmallArray# n initial s) </span><span style="color: #c586c0;">of</span></div><div><span style="color: #d4d4d4;"> (# s', arr #) -> (# s', SA arr #)</span></div>
<div><span style="color: #dcdcaa;">readLifted</span><span style="color: #d4d4d4;"> :: </span><span style="color: #569cd6;">SA</span><span style="color: #d4d4d4;"> -> </span><span style="color: #569cd6;">Int</span><span style="color: #d4d4d4;"> -> </span><span style="color: #569cd6;">IO</span><span style="color: #d4d4d4;"> </span><span style="color: #9cdcfe;">a</span></div><div><span style="color: #d4d4d4;">readLifted (SA arr) (I# i) = IO (\s -></span></div><div><span style="color: #d4d4d4;"> unsafeCoerce# (readSmallArray# arr i s)</span></div><div><span style="color: #d4d4d4;"> )</span></div>
<div><span style="color: #569cd6;">data</span><span style="color: #d4d4d4;"> </span><span style="color: #569cd6;">UWrap</span><span style="color: #d4d4d4;"> (</span><span style="color: #9cdcfe;">a</span><span style="color: #d4d4d4;"> :: </span><span style="color: #569cd6;">UnliftedType</span><span style="color: #d4d4d4;">) = UWrap </span><span style="color: #9cdcfe;">a</span></div><div><span style="color: #6a9955;">-- UWrap is just here because we can't return unlifted types in IO</span></div><div><span style="color: #6a9955;">-- If you don't need your result in IO you can eliminate this indirection.</span></div><div><span style="color: #dcdcaa;">readUnlifted</span><span style="color: #d4d4d4;"> :: </span><span style="color: #569cd6;">forall</span><span style="color: #d4d4d4;"> </span><span style="color: #9cdcfe;">a</span><span style="color: #d4d4d4;">. </span><span style="color: #569cd6;">SA</span><span style="color: #d4d4d4;"> -> </span><span style="color: #569cd6;">Int</span><span style="color: #d4d4d4;"> -> </span><span style="color: #569cd6;">IO</span><span style="color: #d4d4d4;"> (</span><span style="color: #569cd6;">UWrap</span><span style="color: #d4d4d4;"> </span><span style="color: #9cdcfe;">a</span><span style="color: #d4d4d4;">)</span></div><div><span style="color: #d4d4d4;">readUnlifted (SA arr) (I# i) = IO (\s -></span></div><div><span style="color: #d4d4d4;"> </span><span style="color: #c586c0;">case</span><span style="color: #d4d4d4;"> unsafeCoerce# (readSmallArray# arr i s) </span><span style="color: #c586c0;">of</span></div><div><span style="color: #d4d4d4;"> (# s', a :: </span><span style="color: #9cdcfe;">a</span><span style="color: #d4d4d4;"> #) -> (# s', UWrap a #)</span></div><div><span style="color: #d4d4d4;"> )</span></div>
<div><span style="color: #dcdcaa;">writeLifted</span><span style="color: #d4d4d4;"> :: </span><span style="color: #9cdcfe;">a</span><span style="color: #d4d4d4;"> -> </span><span style="color: #569cd6;">Int</span><span style="color: #d4d4d4;"> -> </span><span style="color: #569cd6;">SA</span><span style="color: #d4d4d4;"> -> </span><span style="color: #569cd6;">IO</span><span style="color: #d4d4d4;"> ()</span></div><div><span style="color: #d4d4d4;">writeLifted x (I# i) (SA arr) = IO $ \s -></span></div><div><span style="color: #d4d4d4;"> </span><span style="color: #c586c0;">case</span><span style="color: #d4d4d4;"> writeSmallArray# (unsafeCoerce# arr) i x s </span><span style="color: #c586c0;">of</span></div><div><span style="color: #d4d4d4;"> s -> (# s, </span><span style="color: #569cd6;">()</span><span style="color: #d4d4d4;"> #)</span></div>
<div><span style="color: #dcdcaa;">writeUnlifted</span><span style="color: #d4d4d4;"> :: (</span><span style="color: #9cdcfe;">a</span><span style="color: #d4d4d4;"> :: </span><span style="color: #569cd6;">UnliftedType</span><span style="color: #d4d4d4;">) -> </span><span style="color: #569cd6;">Int</span><span style="color: #d4d4d4;"> -> </span><span style="color: #569cd6;">SA</span><span style="color: #d4d4d4;"> -> </span><span style="color: #569cd6;">IO</span><span style="color: #d4d4d4;"> ()</span></div><div><span style="color: #d4d4d4;">writeUnlifted x (I# i) (SA arr) = IO $ \s -></span></div><div><span style="color: #d4d4d4;"> </span><span style="color: #c586c0;">case</span><span style="color: #d4d4d4;"> writeSmallArray# arr i (unsafeCoerce# x) s </span><span style="color: #c586c0;">of</span></div><div><span style="color: #d4d4d4;"> s -> (# s, </span><span style="color: #569cd6;">()</span><span style="color: #d4d4d4;"> #)</span></div>
<div><span style="color: #569cd6;">type</span><span style="color: #d4d4d4;"> </span><span style="color: #569cd6;">UB</span><span style="color: #d4d4d4;"> :: </span><span style="color: #569cd6;">UnliftedType</span></div><div><span style="color: #569cd6;">data</span><span style="color: #d4d4d4;"> </span><span style="color: #569cd6;">UB</span><span style="color: #d4d4d4;"> = UT | UF</span></div>
<div><span style="color: #dcdcaa;">showU</span><span style="color: #d4d4d4;"> :: </span><span style="color: #569cd6;">UWrap</span><span style="color: #d4d4d4;"> </span><span style="color: #569cd6;">UB</span><span style="color: #d4d4d4;"> -> </span><span style="color: #569cd6;">String</span></div><div><span style="color: #d4d4d4;">showU (UWrap UT) = </span><span style="color: #ce9178;">"UT"</span></div><div><span style="color: #d4d4d4;">showU (UWrap UF) = </span><span style="color: #ce9178;">"UF"</span></div>
<div><span style="color: #dcdcaa;">main</span><span style="color: #d4d4d4;"> :: </span><span style="color: #569cd6;">IO</span><span style="color: #d4d4d4;"> ()</span></div><div><span style="color: #d4d4d4;">main = </span><span style="color: #c586c0;">do</span></div><div><span style="color: #d4d4d4;"> arr <- mkArray </span><span style="color: #b5cea8;">4</span><span style="color: #d4d4d4;"> </span><span style="color: #569cd6;">()</span></div><div><span style="color: #d4d4d4;"> writeLifted True </span><span style="color: #b5cea8;">0</span><span style="color: #d4d4d4;"> arr</span></div><div><span style="color: #d4d4d4;"> writeLifted False </span><span style="color: #b5cea8;">1</span><span style="color: #d4d4d4;"> arr</span></div><div><span style="color: #d4d4d4;"> writeUnlifted UT </span><span style="color: #b5cea8;">2</span><span style="color: #d4d4d4;"> arr</span></div><div><span style="color: #d4d4d4;"> writeUnlifted UT </span><span style="color: #b5cea8;">3</span><span style="color: #d4d4d4;"> arr</span></div>
<div><span style="color: #d4d4d4;"> (readLifted arr </span><span style="color: #b5cea8;">0</span><span style="color: #d4d4d4;"> :: </span><span style="color: #569cd6;">IO</span><span style="color: #d4d4d4;"> </span><span style="color: #569cd6;">Bool</span><span style="color: #d4d4d4;">) >>= print</span></div><div><span style="color: #d4d4d4;"> (readLifted arr </span><span style="color: #b5cea8;">1</span><span style="color: #d4d4d4;"> :: </span><span style="color: #569cd6;">IO</span><span style="color: #d4d4d4;"> </span><span style="color: #569cd6;">Bool</span><span style="color: #d4d4d4;">) >>= print</span></div><div><span style="color: #d4d4d4;"> (readUnlifted arr </span><span style="color: #b5cea8;">2</span><span style="color: #d4d4d4;"> :: </span><span style="color: #569cd6;">IO</span><span style="color: #d4d4d4;"> (</span><span style="color: #569cd6;">UWrap</span><span style="color: #d4d4d4;"> </span><span style="color: #569cd6;">UB</span><span style="color: #d4d4d4;">)) >>= (putStrLn . showU)</span></div><div><span style="color: #d4d4d4;"> (readUnlifted arr </span><span style="color: #b5cea8;">3</span><span style="color: #d4d4d4;"> :: </span><span style="color: #569cd6;">IO</span><span style="color: #d4d4d4;"> (</span><span style="color: #569cd6;">UWrap</span><span style="color: #d4d4d4;"> </span><span style="color: #569cd6;">UB</span><span style="color: #d4d4d4;">)) >>= (putStrLn . showU)</span></div>
<div><span style="color: #d4d4d4;"> return </span><span style="color: #569cd6;">()</span></div></div>
<p>Cheers</p>
<p>Andreas<br>
</p>
<div class="moz-cite-prefix">Am 02/08/2022 um 17:32 schrieb J.
Reinders:<br>
</div>
<blockquote type="cite"
cite="mid:864C4634-6BA6-49FF-8FC8-873FDC4E9254@gmail.com">
<blockquote type="cite">
<pre class="moz-quote-pre" wrap="">Could you use `StablePtr` for the keys?
</pre>
</blockquote>
<pre class="moz-quote-pre" wrap="">That might be an option, but I have no idea how performant stable pointers are and manual management is obviously not ideal.
</pre>
<blockquote type="cite">
<pre class="moz-quote-pre" wrap="">How does the cost of computing object hashes and comparing colliding
objects compare with the potential cache miss cost of using boxed
integers or a separate array? Would such an "optimisation" be worth
the effort?
</pre>
</blockquote>
<pre class="moz-quote-pre" wrap="">Literature on hash tables suggests that cache misses were a very important factor in running time (in 2001): <a class="moz-txt-link-freetext" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.4189" moz-do-not-send="true">https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.4189</a>
I don’t know whether it has become less or more important now, but I have been told there haven’t been that many advances in memory latency.
_______________________________________________
ghc-devs mailing list
<a class="moz-txt-link-abbreviated moz-txt-link-freetext" href="mailto:ghc-devs@haskell.org" moz-do-not-send="true">ghc-devs@haskell.org</a>
<a class="moz-txt-link-freetext" href="http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs" moz-do-not-send="true">http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs</a>
</pre>
</blockquote>
</blockquote>
</blockquote>
</body>
</html>