Inaccuracy in setBlock which implies time inefficient performance.

[VelislavKarastoychev]

Hello, everyone. My name is Velislav and I am developing a mathematical library in typescript. As good practice I use the numericjs for efficiency and output comparison with my own library (https://github.com/VelislavKarastoychev/euriklis-mathematics) and I found that in the method setBlock the else statement is omitted which costs ten times worst time efficiency of the method. The correct version has to be:

numeric.setBlock = function setBlock(x,from,to,B) {
    var s = numeric.dim(x);
    function foo(x,y,k) {
        var i,a = from[k], n = to[k]-a+1;
        // do not make zero test every time,
        // because the for / while loops has a special
        // flag which tests every time for the zero condition.
        if(k === s.length-1) { for(i=n;i--;) { x[i+a] = y[i]; } }
        else for(i=n;i--;) { foo(x[i+a],y[i],k+1); }
    }
    foo(x,B,0);
    return x;
}

In my library I apply the so called Duffs device (its binary and not the octal version) and strongly recommend the following form:

numeric.setBlock = function setBlock(x,from,to,B) {
    var s = numeric.dim(x);
    function foo(x,y,k) {
        var i,a = from[k], n = to[k]-a+1;
        if(k === s.length-1) { 
           for(i=n;i-- > 1;) { x[i+a] = y[i--]; }
            if (i === 0) x[i + a]  = y[i]; 
        } else for(i=n;i--;) { foo(x[i+a],y[i],k+1); }
    }
    foo(x,B,0);
    return x;
}

It's seems that this inaccuracy is provoked from the implementation of the getBlock method. In the getBlock method for the case when k === s.length - 1 is used return and in this situation there is no need for the usage of the else statement. But in setBlock the absence of the else decreases significantly the performance for large matrices.

A similar issue for inefficient implementation exists in the method getBlock. My recommendations for the implementation of the getBlock are:

numeric.getBlock = function getBlock(x,from,to) {
    var s = numeric.dim(x);
    function foo(x,k) {
        var i,a = from[k], n = to[k]-a+1, ret = Array(n);
        if(k === s.length-1) {
            for(i=n;i--;) { ret[i] = x[i+a]; }
            return ret;
        }
        for(i=n;i--;) { ret[i] = foo(x[i+a],k+1); }
        return ret;
    }
    return foo(x,0);
}

instead of the original

numeric.getBlock = function getBlock(x,from,to) {
    var s = numeric.dim(x);
    function foo(x,k) {
        var i,a = from[k], n = to[k]-a, ret = Array(n);
        if(k === s.length-1) {
            for(i=n;i>=0;i--) { ret[i] = x[i+a]; }
            return ret;
        }
        for(i=n;i>=0;i--) { ret[i] = foo(x[i+a],k+1); }
        return ret;
    }
    return foo(x,0);
}

In this situation we just stop to make zero test conditions for every step of the for loop (in every programming language in the while/for/forEach loops exists a flag which checks automatically if the counter is reached the zero value, so by using decreasing operator, we may avoid the zero testing condition).

This very small change speeds up the performance of the method more than 5 times:

after the fixing of the numeric code:

It has to be noticed that the original implementation of the numeric.getBlock method has a mistake, namely the length of the array has to be n + 1 instead of n or more concretely:

numeric.getBlock = function getBlock(x,from,to) {
    var s = numeric.dim(x);
    function foo(x,k) {
        var i,a = from[k], n = to[k]-a, ret = Array(n + 1);
        if(k === s.length-1) {
            for(i=n;i>=0;i--) { ret[i] = x[i+a]; }
            return ret;
        }
        for(i=n;i>=0;i--) { ret[i] = foo(x[i+a],k+1); }
        return ret;
    }
    return foo(x,0);
}

This error is not observable because in JavaScript the Array is a generic array and its length may be changed dynamically but if we want to work with TypedArrays, then this code will produce incorrect result.