<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi,<div><br></div><div>Indeed, I implemented the quick paths only for byte objects and pointer objects. The reason for this is that I based the implementation on customer benchmarks, and there was a lot of replacements for pointer objects (typically, growing the inner array of OrderedCollection/<wbr>Dictionaries) and byte objects (typically bytestrings concatenation, such as 'a' , 'b' which calls twice this primitive for only a couple characters and is now much faster).</div><div><br></div><div>I wrote the quick path with short copies mind, in which case switching to the C runtime is too expensive. Based on your analysis, for pointer objects it looks good, but for byte objects it gets slower.</div><div><br></div><div>So I see two solutions for the slow down on byte copies:</div><div>1) over a threshold of 1000 elements, fall back to the slang primitive for byte objects</div><div>2) Generate smarter copying machine code (for example with some kind of duff device / unrolled loop / overlapping copies with 1 copy non aligned). If possible nothing requiring to extend the RTL. Note that memcopy in C is written as a per back-end files which is thousands of lines on x86 and we don't want to go anywhere near this complexity, in our case the size of generate machine code also matters and we want to keep it small. We could use pointer size read / writes on byte objects too if we deal with aliasing (if array == replArray just fall back to a slower path).</div><div><br></div><div>Let's look at the naive machine code in Cog's RTL (I could show the actual assembly version if you like it better), in each case the loop does:</div><div>- compare and jumpBelow to see if the copy is finished</div><div>- read one field from repl</div><div>- write the read field in the array</div><div>- increment the 2 registers holding indexes for read/write</div><div>- jump back. </div><div><br></div><div>The copying machine code for byte object is as follow:<br></div><div><br></div><div><div> <font face="monospace, monospace"> instr := cogit CmpR: startReg R: stopReg.</font></div><div><font face="monospace, monospace"><span style="white-space:pre-wrap"> </span>jumpFinished := cogit JumpBelow: 0.</font></div><div><font face="monospace, monospace"><span style="white-space:pre-wrap"> </span>cogit MoveXbr: repStartReg R: replReg R: TempReg.</font></div><div><font face="monospace, monospace"><span style="white-space:pre-wrap"> </span>cogit MoveR: TempReg Xbr: startReg R: arrayReg.</font></div><div><font face="monospace, monospace"><span style="white-space:pre-wrap"> </span>cogit AddCq: 1 R: startReg.</font></div><div><font face="monospace, monospace"><span style="white-space:pre-wrap"> </span>cogit AddCq: 1 R: repStartReg.</font></div><div><font face="monospace, monospace"><span style="white-space:pre-wrap"> </span>cogit Jump: instr.</font></div></div><div><br></div><div>The copying code for pointer object is as follow:</div><div><div><span style="font-family:monospace,monospace;white-space:pre-wrap"> </span><font face="monospace, monospace">instr := cogit CmpR: startReg R: stopReg.</font></div><div><font face="monospace, monospace"><span style="white-space:pre-wrap"> </span>jumpFinished := cogit JumpBelow: 0.</font></div><div><font face="monospace, monospace"><span style="white-space:pre-wrap"> </span>cogit MoveXwr: repStartReg R: replReg R: TempReg.</font></div><div><font face="monospace, monospace"><span style="white-space:pre-wrap"> </span>cogit MoveR: TempReg Xwr: startReg R: arrayReg.</font></div><div><font face="monospace, monospace"><span style="white-space:pre-wrap"> </span>cogit AddCq: 1 R: startReg.</font></div><div><font face="monospace, monospace"><span style="white-space:pre-wrap"> </span>cogit AddCq: 1 R: repStartReg.</font></div><div><font face="monospace, monospace"><span style="white-space:pre-wrap"> </span>cogit Jump: instr.</font></div></div><div><br></div><div>Any idea what we could do smarter, but not too complex, without extending the RTL and without generating let's say more than 20 extra instructions ?</div><div><br></div><div>I think checking for aliasing and using pointer size read/write may be the way to go. Then if performance is not better we just fall back to slang code.</div><div><br></div><div><div><div class="h5">On Mon, Dec 25, 2017 at 10:57 PM, Levente Uzonyi <span dir="ltr"><<a href="mailto:leves@caesar.elte.hu" target="_blank">leves@caesar.elte.hu</a>></span> wrote:</div></div><div class="gmail_extra"><div><div class="h5"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi Clémont,<br>
<br>
I finally found the time to write some benchmarks.<br>
I compared the output of the script below on sqcogspur64linuxht vm 201710061559 and 201712221331 avaiable on bintray.<br>
<br>
result := { ByteArray. DoubleByteArray. WordArray. DoubleWordArray. ByteString. WideString. FloatArray. Array } collect: [ :class |<br>
| collection |<br>
Smalltalk garbageCollect.<br>
collection := class basicNew: 10000.<br>
class -> (#(0 1 2 5 10 20 50 100 200 500 1000 2000 5000 10000) collect: [ :size |<br>
| iterations time overhead |<br>
iterations := (40000000 // (size max: 1) sqrt) floor.<br>
overhead := [ 1 to: iterations do: [ :i | ] ] timeToRun.<br>
time := [ 1 to: iterations do: [ :i |<br>
collection replaceFrom: 1 to: size with: collection startingAt: 1 ] ] timeToRun.<br>
{ size. iterations. time - overhead } ]) ].<br>
<br>
I found that the quick paths are probably only implented for bytes and pointers collections, because there was no significant difference for DoubleByteArray, WordArray, DoubleWordArray, WideString and FloatArray. </blockquote><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
For pointers and bytes collections, there's significant speedup when the copied portion is small. However, somewhere between 50 and 100 copied elements, the copying of bytes collections becomes slower (up to 1.5x @ 100k elements) with the newer VM.<br>
It's interesting that this doesn't happen to pointers classes. Instead of slowdown there's still 1.5x speedup even at 100k elements.<br>
<br>
Levente<div><div class="m_8036511667332271838gmail-h5"><br>
<br>
On Mon, 23 Oct 2017, Clément Bera wrote:<br>
<br>
</div></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div><div class="m_8036511667332271838gmail-h5">
Hi all,<br>
For a long time I was willing to add primitive #replaceFrom:to:with:startingA<wbr>t: in the JIT but did not take time to do it. These days I am showing the JIT to one of my students and as an example of how one would write code in the JIT we implemented this primitive<br>
together, Spur-only. This is part of commit 2273.<br>
<br>
I implemented quick paths for byte objects and array-like objects only. The rationale behind this is that the most common cases I see in Pharo user benchmarks in the profiler is copy of arrays and byteStrings. Typically some application benchmarks would show 3-5% of<br>
time spent in copying small things, and switching from the JIT runtime to C runtime is an important part of the cost.<br>
<br>
First evaluation shows the following speed-ups, but I've just done that quickly in my machine:<br>
<br>
Copy of size 0<br>
Array 2.85x<br>
ByteString 2.7x<br>
Copy of size 1<br>
Array 2.1x<br>
ByteString 2x<br>
Copy of size 3<br>
Array 2x<br>
ByteString 1.9x<br>
Copy of size 8<br>
Array 1.8x<br>
ByteString 1.8x<br>
Copy of size 64<br>
Array 1.1x<br>
ByteString 1.1x<br>
Copy of size 1000<br>
Array 1x<br>
ByteString 1x<br>
<br>
So I would expect some macro benchmarks to get 1 to 3% percent speed-up. Not as much as I expected but it's there.<br>
<br>
Can someone who is good at benchmarks such as Levente have a look and provide us with a better evaluation of the performance difference ?<br>
<br>
Thanks.<br>
<br>
--<br></div></div>
Clément Béra<span class="m_8036511667332271838gmail-"><br>
<a href="https://clementbera.wordpress.com/" rel="noreferrer" target="_blank">https://clementbera.wordpress.<wbr>com/</a><br>
Bâtiment B 40, avenue Halley 59650 Villeneuve d'Ascq<br>
<br>
</span></blockquote>
</blockquote></div><br><br clear="all"><div><br></div></div></div><span class="HOEnZb"><font color="#888888">-- <br></font></span><div class="m_8036511667332271838gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><span class="HOEnZb"><font color="#888888">Clément Béra</font></span><span class=""><div><a href="https://clementbera.wordpress.com/" target="_blank">https://clementbera.wordpress.<wbr>com/</a><br></div><div><span style="color:rgb(34,34,34);font-family:arial,sans-serif;line-height:16px;background-color:rgb(255,255,255)">Bâtiment B 40, avenue Halley 59650 </span><em style="font-weight:bold;font-style:normal;font-family:arial,sans-serif;line-height:16px;background-color:rgb(255,255,255)">Villeneuve d'Ascq</em></div></span></div></div></div></div></div></div></div></div></div>
</div></div></div>
</blockquote></div><br><br clear="all"><div><br></div>
</div></div>