[self-interest] Bignum performance

[Russell Allen]

David might have other ideas, but I suspect what is happening is that Self isn't cheating enough.

Multiply two bigInts in Self and the maths primitives are still at the smallInt level, with lots of Self level code to chop the bigInts into smallInts and then reassemble them.

Look at the code to multiply a bigInt by another and you soon end up with stuff like:

mulDigits: digits1 And: digits2 = ( | carryIdx <- 0. carryM <- 0. dsize1 <- 0. dsize2 <- 0. res |
    dsize1: digits1 size.
    dsize2: digits2 size.
    carryIdx: dsize2 - cByteSize.
    res: (digitsRep copySize: dsize1 + dsize2 FillingWith: 0).
    0 upTo: dsize1 By: cByteSize Do: [
        |:idx1. carryA <- 0. | 
        carryM: (mulOne: (in: digits1 At: idx1)
                Digits: digits2
          ResultStream: [|:x. :idx2. idx <- 0. y <- 0. c <- 0. | 
            idx: idx1 + idx2.
            idx2 = carryIdx ifTrue: [
                "Last digit in 'digits2' so use left over carry
                 from last round."
                c: carryM.
            ].
            y: c + x + (in: res At: idx) + carryA.
            base <= y ifTrue: [carryA: 1. y: y - base] 
                       False: [carryA: 0].
            in: res At: idx Put: y.
        ]).
        carryM: carryM + carryA.
    ].
    "Finish off with carry."
    assert: [0 = (mostSignificantDigit: res)].
    in: res At: res size - cByteSize Put: carryM.
    res)

I'm not surprised the JIT can't get us there!

Presumably we need specific bignum primitives to call as soon as the original small integer gets promoted to a larger one.

Russell

On 14/09/2013, at 11:49 PM, Chris Double <chris.double at double.co.nz> wrote:

> Bignum performance in Self seems to be quite slow. Executing 1000
> factorial on my laptop gives the following:
> 
> [ 1000 factorial ] time
> => 2228
> 
> On similar JIT'd languages that support bignums I get subsecond
> results. Implementing similar to factorial to use '+' instead of '*' to
> ensure that no bignums are created I get:
> 
> [ 1000 foo ] time
> => 0
> 
> Where 'foo' is a method on 'traits integer':
> 
> <= 1 ifTrue: 1 False: [ + predecessor foo ]
> 
> Has anyone got ideas on what the performance hit might be caused by?
> 
> Chris.
> -- 
> http://www.bluishcoder.co.nz
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.selflanguage.org/pipermail/self-interest/attachments/20130915/6a17d1fa/attachment.html>