Int vs Int32 or StaticTuple vs SIMD

[RtyLiu]

I have seen a language comparison and did not like it (Mojo behind Julia) :).
https://github.com/attractivechaos/plb2
There is the following code for NQueens problem:

fn nq_solve(n: Int) -> Int:
    var a = StaticTuple[32, Int](-1)
    var l = StaticTuple[32, Int](0)
    var c = StaticTuple[32, Int](0)
    var r = StaticTuple[32, Int](0)
    for i in range(0, n):
        a[i] = -1
        l[i], c[i], r[i] = 0, 0, 0
    var m = 0
    let y0 = (1<<n) - 1
    var k = 0
    while k >= 0:
        let y = (l[k] | c[k] | r[k]) & y0;
        if (y ^ y0) >> (a[k] + 1):
            var i = a[k] + 1
            while i < n:
                if (y & 1<<i) == 0: break
                i += 1
            if k < n - 1:
                let z = 1<<i
                a[k] = i
                k += 1
                l[k] = (l[k-1]|z)<<1
                c[k] = c[k-1]|z
                r[k] = (r[k-1]|z)>>1
            else:
                m += 1
                k -= 1
        else:
            a[k] = -1
            k -= 1
    return m

I have made a small change:

fn nq_solve(n: Int) -> Int:
    var a = SIMD[DType.int32, 32](-1)
    var l = SIMD[DType.int32, 32](0)
    var c = SIMD[DType.int32, 32](0)
    var r = SIMD[DType.int32, 32](0)
    
    var m = 0
    let y0: Int32 = (1<<n) - 1
    var k  = 0
    while k >= 0:
        let y: Int32 = (l[k] | c[k] | r[k]) & y0;
        if (y ^ y0) >> (a[k] + 1) != 0:
            var i: Int32 = a[k] + 1
            while i < n:
                if (y & 1<<i) == 0: break
                i += 1
            if k < n - 1:
                let z = 1<<i
                a[k] = i
                k += 1
                l[k] = (l[k-1]|z)<<1
                c[k] = c[k-1]|z
                r[k] = (r[k-1]|z)>>1
            else:
                m += 1
                k -= 1
        else:
            a[k] = -1
            k -= 1
    return m

then benchmark it (16 queens):

fn main():
    @parameter
    fn test_fn():
        _ = nq_solve(16)

    let report = benchmark.run[test_fn]()
    report.print()    

Original:

---------------------
Benchmark Report (s)
---------------------
Mean: 15.854452617750001
Total: 63.417810471000003
Iters: 4
Warmup Mean: 7.8996361224999996
Warmup Total: 15.799272244999999
Warmup Iters: 2
Fastest Mean: 15.854452617750001
Slowest Mean: 15.854452617750001

Changed:

Mean: 9.3444570822500008
Total: 37.377828329000003
Iters: 4
Warmup Mean: 18.5477321145
Warmup Total: 37.095464229000001
Warmup Iters: 2
Fastest Mean: 9.3444570822500008
Slowest Mean: 9.3444570822500008

1. Did I benchmarket it right :)
2. Where the speed come from Int32 vs Int or SIMD used as array vs StaticTuple
3. May be you see the diff if (y ^ y0) >> (a[k] + 1): vs if (y ^ y0) >> (a[k] + 1) != 0:
   Start this and see why:

fn main():
    var x = 64
    var y: Int32=64
    var z: Int32=0
    if x:
        print("x",x)
    if y:
        print("y",y)
    else:
        print("What?  64 is false?")
    if z:
        print("0 is true?",z)

[soraros]

"0 is true?"

You are hitting #1623 again.

[RtyLiu]

Yes, thanks. The question is what is the difference in internal implementation between Int and Int32? Is there a speed penalty of using Int?

[soraros]

You could try Int32/Int64 with tuple and int64 with SIMD vector to test your theories.

[RtyLiu]

Yep.
$ mojo nqueen.mojo
Mean: 15.870783995249999

$ mojo nqueen_Int32_tuple.mojo
Mean: 14.127117193749999

$ mojo nqueen_SIMD.mojo
Mean: 9.2833659874999999

[soraros]

The modified version actually runs at least two times slower for me.

[RtyLiu]

Sure? Do you have GPU?