<div dir="ltr">Hi All,<div><br></div><div> Clément and I have been looking at primitive performance in the context of string hash. We'll say more about string hash in a later message (and there is nothing to be alarmed about here). But it is worth describing the performance measurements of the various kinds of primitive dispatch in Cog. The following measurements are collected from a 64-bit Squeak trunk image with a 64-bit Cog Spur VM with four different implementations of hashMultiply, three of them primitive. The times are collected on a 2.3 GHz Intel Core i7 MacMini.</div><div><br></div><div>The doit below compares the time taken to go round a loop containing 10 unrolled copies of an operation 10 million times, for a total of 100 million invocations of the operation. The operations are</div><div>- doing nothing</div><div>- sending yourself</div><div>- invoking the SmallInteger>>hashMultiply method</div><div>- invoking a version of hashMultiply written as a normal interpreter primitive (more on this below)</div><div>- invoking a version of hashMultiply written as a C function called from machine code</div>- invoking a version of hashMultiply written as a machine code primitive<div><br></div><div>FYI, hash multiply is</div><div><div>hashMultiply</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>| low |</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>low := self bitAnd: 16383.</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>^(16r260D * low + ((16r260D * (self bitShift: -14) + (16r0065 * low) bitAnd: 16383) * 16384))</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>bitAnd: 16r0FFFFFFF</div><div><br></div><div>and when written as a primitive is</div><div><div>hashMultiply</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>| low |</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>low := self bitAnd: 16383.</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>^(16r260D * low + (16r260D * (self bitShift: -14) + (16r0065 * low) * 16384))</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>bitAnd: 16r0FFFFFFF</div></div><div>because we don't care about the multiply by 16384 overflowing; when written as a primitive it won't overflow into a LargePositiveInteger.</div><div><br></div><div>Here is the doit:</div><div><br></div><div><div><div>| n them |</div><div>n := 10000000.</div><div>them := {</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> [1 to: n do: [:v| v. v. v. v. v. v. v. v. v. v]].
</span>[1 to: n do: [:v| v yourself. v yourself. v yourself. v yourself. v yourself. v yourself. v yourself. v yourself. v yourself. v yourself]].</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>[1 to: n do: [:v| v hashMultiply. v hashMultiply. v hashMultiply. v hashMultiply. v hashMultiply. v hashMultiply. v hashMultiply. v hashMultiply. v hashMultiply. v hashMultiply]].</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>[1 to: n do: [:v| v hashMultiplyInterpreterPrimitive. v hashMultiplyInterpreterPrimitive. v hashMultiplyInterpreterPrimitive. v hashMultiplyInterpreterPrimitive. v hashMultiplyInterpreterPrimitive. v hashMultiplyInterpreterPrimitive. v hashMultiplyInterpreterPrimitive. v hashMultiplyInterpreterPrimitive. v hashMultiplyInterpreterPrimitive. v hashMultiplyInterpreterPrimitive]].</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>[1 to: n do: [:v| v hashMultiplyPrimitive. v hashMultiplyPrimitive. v hashMultiplyPrimitive. v hashMultiplyPrimitive. v hashMultiplyPrimitive. v hashMultiplyPrimitive. v hashMultiplyPrimitive. v hashMultiplyPrimitive. v hashMultiplyPrimitive. v hashMultiplyPrimitive]].</div><div><span class="gmail-Apple-tab-span" style="white-space:pre"> </span>[1 to: n do: [:v| v hashMultiplyNativePrimitive. v hashMultiplyNativePrimitive. v hashMultiplyNativePrimitive. v hashMultiplyNativePrimitive. v hashMultiplyNativePrimitive. v hashMultiplyNativePrimitive. v hashMultiplyNativePrimitive. v hashMultiplyNativePrimitive. v hashMultiplyNativePrimitive. v hashMultiplyNativePrimitive]] }.</div><div>them := them, them.</div><div>them collect: [:b| b timeToRun]</div><div><br></div><div>and the results:</div><div><br></div><div>#(19 235 2321 2453 615 314</div><div> 19 233 2317 2473 614 313)</div></div><div><br></div><div>Writing this as a table we have</div><div>19/19<span style="white-space:pre"> </span><span style="white-space:pre"> null</span></div><div>235/233<span class="gmail-Apple-tab-span" style="white-space:pre"> v yourself (remember divide by 10 to compare against the loop overhead)</span></div><div><span class="gmail-Apple-tab-span" style="white-space:pre">2321/2317 hashMultiply</span></div><div><span class="gmail-Apple-tab-span" style="white-space:pre">2453/2473 </span>hashMultiplyInterpreterPrimitive</div><div>615/614<span style="white-space:pre"> </span>hashMultiplyPrimitive</div><div>314/313<span style="white-space:pre"> </span>hashNativePrimitive</div><div><br></div><div>(the time for) null is the cost of performing the loop arithmetic and the back jump. The JIT eliminates the push and pop of v so the block is effectively empty.</div><div><br></div><div>v yourself is the overhead of sending a message to a SmallInteger, and returning self, plus the loop overhead. So the loop overhead is comparable to the send overhead. Unsurprising; the loop contains an inlined add and an inlined compare.</div><div><br></div><div>hashMultiply is the cost of evaluating hashMultiply in Cog jitted code; i.e. as it exists today in standard Squeak and Pharo images</div><div><br></div><div>hashMultiplyInterpreterPrimitive is the cost of evaluating a primitive version of hashMultiply when written as "normal interpreter primitives". Such primitives are written to take their receiver and arguments from the Smalltalk stack, accessing the stack through the stackPointer global variable, and answering the result by popping the stackPointer and replacing top of stack with the result. When called from a jitted method, the invocation of the interpreter primitive involves<br></div><div>- writing the native stack and frame pointers to the stackPointer and framePointer variables</div><div>- setting the native stack and frame pointers to the C stack (the C stack at the point the interpreter was entered either at start-up or after a callback)</div><div>- calling the C function</div><div>- undoing the stack switch</div><div>- testing primFailCode, the flag that holds the primitive error code and hence indicates a primitive succeeded if 0</div><div><br></div><div>hashMultiplyPrimitive is an experimental implementation of the primitive where it is written as a C function that takes its argument (the receiver) as an argument, and answers its result by returning it, setting primFailCode and answering 0 on failure (because 0 is never a valid object; 0 can be used to flag failure). The primitive is run on the Smalltalk stack, avoiding the stack switch in a normal interpreter primitive invocation. Because the Smalltalk stack is divided into small pages this form can only be used for C functions that will not consume much stack (not recurse, or call a deep call chain, nor do any stack allocation, nor raise an exception, etc).</div><div>When called from a jitted method, the invocation of the C primitive involves<br></div><div>- saving any live caller-saved registers (i.e. the register containing the receiver)</div><div>- marshaling the live registers (in this case only the register containing the receiver) as argument(s) according to the C ABI</div><div>- calling the C function</div><div>- restoring any caller-saved registers</div><div>- testing the C result register and either copying it to the receiver/result register and returning, or falling through to primitive failure code</div><div><br></div><div>hashMultiplyNativePrimitive is the standard fast implementation of a primitive, using the it's inbuilt assembler; i.e. the primitive is written in an executed assembly code from which the it is constructed. Because this is effectively assembly programming we restrict its use to relatively simple performance-critical primitives (SmallInteger, BoxedFloat64 and SmallFloat64 arithmetic and comparison, basicNew, basicNew:, shallowCopy, closure value, perform:[with:with:], #==. #~~, #class, basicAt:, basicAt:put:, basicSize). <br></div><div><br></div><div>As you can see, normal interpreter primitives are woefully slow. The cost is so high that jitted Smalltalk code just beats the primitive, even though the normal Smalltalk code does one more operation and involves five sends (the JIT is clever enough to inline the bitShift: and bitAnd: operations). Alas, most primitives in the VM are written in this style. It has two advantages; first that there exists a large number of existing implementations using this style, and second that the style makes writing primitives that take a variable number of arguments easy (so for example getVMParameters: vmParameterAt: and vmParameterAt:put: are written as one large primitive in the VM code).</div><div><br></div><div>Writing the primitive as a C function that takes its parameters as arguments and answers its result as the function's return value, is much faster. We're therefore interested in using this scheme to reimplement primitives such as replaceFrom:to:with:startingAt: that are performance-critical but too complex to write as native machine code primitives without developing ulcers, loosing whatever hair color one has left, getting psoriasis, etc.</div><div><br></div><div>What's perhaps surprising, but should actually be unsurprising, is that there is still overhead in calling a very simple C function compared to embedding the code to perform the primitive directly in the jitted machine code. It is unsurprising in this case as it shows that the overhead of a send is very similar to the overhead of calling a one-argument C function.</div><div><br></div><div>What's inconvenient about these C function called on the Smalltalk stack style primitives is that currently our C calling marshaling machinery only handles 4 arguments, a limitation that means we don't have to pass arguments on the stack on ARM and WIN64, both of which have a four-integer-register-arguments calling convention, but writing replaceFrom:to:with:startingAt: as a C function requires 5 arguments, because we have to supply the receiver as well. So the C marshalling machinery will have to be extended to pass arguments in both registers and on the stack. Volunteers welcome ;-)</div><div><br></div><div><br></div><div>You may guess where this conversation is going in terms of string hash. But for the moment we can conclude that</div><div>- normal interpreter primitives should not be relied upon for performance-critical primitives</div><div>- the experimental C function called on the Smalltalk stack style primitives look like a good way to write more complex primitives (providing we can invoke them). While they are a little slower than machine code primitives to invoke, the cost will soon be amortized for complex operations.</div><div><br></div><div class="gmail_signature"><div dir="ltr"><div><span style="font-size:small;border-collapse:separate"><div>_,,,^..^,,,_<br></div><div>best, Eliot</div></span></div></div></div>
</div></div></div>