Accelerating LargeInteger in Squeak

A quick picture of current implementation:

The LargeIntegers in Squeak are accelerated by using a multi-layer mechanism:

• The first layer is in VM Integer primitives (for example primitive 29 for LargePositiveInteger>>#*). If the Integer parameters fit on 64 bits and so does the result, then they are handled quite fast at this level, especially in COG VM, the most common primitives being directly inlined into JIT.
• The second layer is using the LargeIntegersPlugin (named LargeIntegers) - see Integer>>#* and  #digitMultiply:neg: for example which uses primDigitMultiplyNegative.
• The third layer when above two failed is to fall back to Smalltalk code iterating on 8 bits digits (found at end of Integer>>#digitMultiply:neg: for example)

Currently, the 3rd layer  is not used, because the plugin is integrated internally in every distributed VM.
But it suggests that the LargeIntegersPlugin is also performing operations on 8-bits digits which is quite dated... Most arithmetic units handle at least 32 or 64 bits nowadays.

A new 32-bit implementation:

So what performance could we gain by using 32-bits digits?
To do so, I thought of two options:

• add a new Integer variableWordSubclass: #LargePositiveInteger32, and its Negative32 counterpart, plus a dedicated LargeInteger32Plugin with new primitives
• change the LargeIntegersPlugin to operate on 32-bits digits

The first option is completed by adding byteAt: byteAt:put: and byteLength primitives to preserve a 8-bits digit based fallback code (this is required because fallback must operate on SmallInteger).
The second option would be possible, because the allocated size is always a multiple of 4 bytes, even for Byte Arrays. But it has two drawbacks:

• LargeInteger are necessary for a modern Squeak image to work, so each mistake would cost me a lot of debugging pain, and I would first have to learn how to use the VM simulator...
• It would not be a great option on big-endian machines due to  necessary swapping of each word (unless of course we use native word ordering and cheat for digitAt: and digitAt:put: fallback code).

So I opted for  a new LargeInteger32Plugin solution tested in a 32bits VM. All my operations will be defined using unsigned int, those requiring 64 bits (* + - quo:) will use unsigned long long. Note that 64 bits operations are emulated by gcc which does not use native 64 bits capabilities of ALU in this configuration.

Micro-benchmark results:

So here are the first results on my old 2.26GHz Intel core 2 duo Mac-mini for a hacked COG VM derivated from version 2640. They are presented in term of number of operations executed per second (8bits on left, 32bits on middle, percentage of improvement on right column) for various operands bit lengths.

Number of operations per second in 8-bit vs 32-bit Large Integer Plugin

The main improvement is for *,  around 7x at kilobit is already something. Note the primitive still implements a naïve O(N²) product, we know from other experiments that a simple Karatsuba algorithm programmed at image side already improves things a bit above kilobit length in a COG VM (see optimizing-product-of-prime-powers).

Then come the score of rem: but it is not fair... I cheated to use the same primitive as quo: which in fact computes both quotient and remainder. It is not used in 8-bit version because performing operations with Integer primitives in case of 64 bits or less is much much faster than using the LargeIntegersPlugin. Otherwise, we would have something similar to \\ score, which is already interesting thanks to usage of *...

The improvment of + and - are low, those are only O(N), probably we mainly measure the overhead because internal loops are too simple...

Micro-benchmark source code:

Here are the gory details:

#(100 1000 10000) collect: [:n |
    p1 := 1<<n - 1.
    p2 := p1 sqrtFloor*p1+1.
    q1 := LargePositiveInteger32 digitLength: p1 digitLength.
    1 to: p1 digitLength do: [:i | q1 digitAt: i put: (p1 digitAt: i)].
    q2 := LargePositiveInteger32 digitLength: p2 digitLength.
    1 to: p2 digitLength do: [:i | q2 digitAt: i put: (p2 digitAt: i)].
    n printString , ' bits' -> {
    '+' -> {
        [p1+p2] bench.
        [q1+q2] bench}.
    '-' -> {
        [p2-p1] bench.
        [q2-q1] bench}.
    '*' -> {
        [p1*p2] bench.
        [q1*q2] bench}.
    '//' -> {
        [p2//p1] bench.
        [q2//q1] bench}.
    '\\' -> {
        [p2\\p1] bench.
        [q2\\q1] bench}.
    'quo:' -> {
        [p2 quo: p1] bench.
        [q2 quo: q1] bench}.
    'rem:' -> {
        [p2 rem: p1] bench.
        [q2 rem: q1] bench}.
    'quo: 10' -> {
        [p1 quo: 10] bench.
        [q1 quo: 10] bench}.
    'rem: 10' -> {
        [p1 rem: 10] bench.
        [q1 rem: 10] bench}.
    '<<53' -> {
        [p1 << 53] bench.
        [q1 << 53] bench}.
    '>>35' -> {
        [p2 >> 35] bench.
        [q2 >> 35] bench}.
}].

This benchmark is very naive, because distribution of 1-bit and 0-bit used above is not fair. Since the probability of having a null 8-bit digit is higher than that of having a null 32-bit digit, and since primDigitMultiplyNegative eliminates N loops at each null digits, this is probably unfair for the 8-bit version, but for a first idea of performance, we don't care - only 1 byte out of 256 is null without prior knowledge of distribution.

Basic unit tests:

If results are false, then the benchmark is worth nothing, so I performed some quick sanity tests with involved pairs of Integers.
Since I can't mix the 8-bit and 32-bit Integers (no interest by now), the tests are quite low level.
I disabled logDebuggerStackToFile Preferences, I don't use traditional assert:, and only evaluate from a Workspace, because a Debugger trying to print the 32-bit LargeIntegers may involve such mixed arithmetic and crash the image.
IMO, the Squeak Debugger is much too clever and performs too many message sends on the debuggee...

assert :=
    [p digitLength = q digitLength ifFalse: [self halt: 'different length'].
    1 to: (p digitLength min: q digitLength) do:
        [:i |
        (p digitAt: i) = (q digitAt: i) ifFalse: [self halt: 'different digit at ' , i printString]]].
#(100 1000 10000) do: [:n |
    p1 := 1<<n - 1.
    p2 := p1 sqrtFloor*p1+1.
    q1 := LargePositiveInteger32 digitLength: p1 digitLength.
    1 to: p1 digitLength do: [:i | q1 digitAt: i put: (p1 digitAt: i)].
    q2 := LargePositiveInteger32 digitLength: p2 digitLength.
    1 to: p2 digitLength do: [:i | q2 digitAt: i put: (p2 digitAt: i)]. 
    p := p1. q := q1. assert value.
    p := p2. q := q2. assert value.
    p := p1*3. q := q1*3. assert value.
    p := p1+5. q := q1+5. assert value.
    p := p1-3. q := q1-3. assert value.
    p := p1+p2. q := q1+q2. assert value.
    p := p1-p2. q := q1-q2. assert value.
    p := p2-p1. q := q2-q1. assert value.
    p := p1*p2. q := q1*q2. assert value.
    p := p2<<53. q := q2<<53. assert value.
    p := p2>>35. q := q2>>35. assert value.
    p := p2 quo: p1. q := q2 quo: q1. assert value.
    p := p2 rem: p1. q := q2 rem: q1. assert value.
    p := p2//p1. q := q2//q1. assert value.
    p := p2\\p1. q := q2\\q1. assert value].

Source code and other details:

I went thru complications for either adding my new LargePositive/NegativeInteger32 classes to Smalltalk specialObjectsArray or using addGCRoot: mechanism.
I finally used specialObjectsArray for the bench to be fair.
Note that unlike 8-bit LargeInteger, my 32-bit LargeInteger classes are not compact, but I have no idea of the influence on above micro-benchmark.

The LargePositiveInteger32 and LargeInteger32Plugin code is unpublished yet. I have to clean it up and increase testing before publishing. And I don't really know yet where to publish this stuff. But it will of course be available as MIT.

The volume is also too high for commenting it in this too long post, but this might feed a few more posts if there is any interest...

Meteor contest is published on benchmark games

I arranged to have the visualworks version of meteor contest published on shootout benchmark site.

This version makes Smalltalk only 7x times slower than fastest C++ version as expected, I think this time is taking image startup time into account (with -nogui).

Of course, with inclusion of optimized bit ops which are not native in VW, my stupid rotation algorithm, and some of my costly optimizations, this version of the game is also one of the longest, as long as a C++ program! That does not improve the efficiency/expressiveness score.

I must publicly thank Isaac Gouy again for his patience, since I lazily commited 3 non functional versions before taking the burden to test myself in batch mode. A shame.

Though he clearly made me understand this was becoming upsetting, he did not ban me.

My board initialization did rely on count: which is not a VW native selector.

I have first defined such selector in the 90s, and it's native in Squeak/Pharo, it is now so natural that I forgot it's not an ubiquitous standard yet.

It is provided both by Seaside (via Grease) and Smallapack (via some prereq), and of course, for some reason I had both packages installed in the image I used for testing.

That's a domain where Smalltalk sucks : when you leave your own image cocoon, implicit dependencies are killing... Another one is implicit API vs privacy, unless it's an advantage.

Being different does not necessarily means being better...

Fortunately, there are still enough advantages to compensate this poor feature.

I also accidentally removed a digit from the auto-generated optimized bit tables while trying to manually split too long lines, but saw the bug before it strikes. I generally don't care of line length, replacing tab with spaces to be tab-stop agnostic, or selecting source code output format to chunk...

I also failed to print a space before new line on even rows, and forgot the second new line after second solution. I remember I manually fixed this when I checked solution agreement 2 months ago, after all, those trailing spaces are not significant. Then I forgot...

I also failed to return a new String with ^'' in Tests class>>meteor; it thus returns self, and append an ugly 'Tests' on standard output... One thing I corrected 2 weeks ago in my Squeak version by mimetism with other benchmarks...

Of course, that's something that only happen in batch mode... As an excuse, I said to Isaac that I never launch an image from command line, nor with options, or command arguments, and that to me, it's as weird as booting a kernel with own custom flags, or booting on memtest. You generally never do that until you are forced to. But with Pharo progress on this front, I will soon have no excuse.

I also argued that my images tend to be long lived (several years or decades), because they are comfortably customized, and anything I need is generally pre-installed. To me, reconstructing an image is like re-installing a debian or an ubuntu every few days for sanity reasons, something I'm reluctant to do. I only abandon some overly hacked images where I modified too many kernel methods, and the Pharo ones because the update mechanism sucks compared to Squeak/trunk. It's normal, Pharo put the focus on reconstructing rather than updating as it is perceived as more reliable (and mainstream). Of course, Metacello and Fuel will lower the burden, but I still think it is a burden.

After downloading the tarball, digging thru the makefiles, the shell scripts, and all this mainstream stuff was not at all funny, I knew how to, but I suddenly remembered how good it was to be different finally...