Writing efficient code with LALOLib

This page provides a list of guidelines to write efficient code with LALOLib.

Use javascript code instead of LALOLab scripts
Use typed objects
Use typed functions
Access elements of a vector or matrix directly
Use pointer-like references
Do not think in you are in Matlab: loops are not so bad!
Spare the garbage collector: do not create many objects unnecessarily
Write optimizers-friendly javascript code

Use javascript code instead of LALOLab scripts

Consider a LALOLab script and its equivalent javascript translation (jsscript), then

lab.exec(jsscript)

will always be slightly faster than

lab.do(script)

Javascript code for any LALOLab script can be easily obtained by clicking the "Javascript code" button in LALOLab. Then, the following guidelines can be applied to further optimize the code.

Use typed objects

If your page creates matrices and vectors, then it should create them with the LALOLib functions

zeros(m,n), ones(m,n), rand(m,n)...

which will enforce a particular object structure on them for faster subsequent computations.

You can also build matrices with Arrays of Arrays and call

A = mat(anArrayOfArrays, true)

to convert them to LALOLib matrices, but this will be slower and will use more memory.

Use typed functions

The general purpose functions listed below are fine to use once in a while, but consume time to determine how to perform the operation depending on the type of the arguments. Therefore, it is always faster (and highly recommended inside loops) to use dedicated typed functions as detailed below.

General purpose function	Type of argument a	Type/value of argument b	Equivalent typed function
add(a,b)	number	vector	addScalarVector(a,b)
	vector	number	addScalarVector(b,a)
	number	matrix	addScalarMatrix(a,b)
	matrix	number	addScalarMatrix(b,a)
	vector	vector	addVectors(a,b)
	matrix	matrix	addMatrices(a,b)
sub(a,b)	number	vector	subScalarVector(a,b)
	vector	number	subVectorScalar(a,b)
	number	matrix	subScalarMatrix(a,b)
	matrix	number	subMatrixScalar(a,b)
	vector	vector	subVectors(a,b)
	matrix	matrix	subMatrices(a,b)
minus(a)	number		-a
	vector		minusVector(a)
	matrix		minusMatrix(a)
mul(a,b)	number	vector	mulScalarVector(a,b)
	number	matrix	mulScalarMatrix(a,b)
	vector	vector	dot(a,b)
	matrix	vector	mulMatrixVector(a,b)
	matrix	matrix	mulMatrixMatrix(a,b)
entrywisemul(a,b)	vector	vector	entrywisemulVector(a,b)
	matrix	matrix	entrywisemulMatrix(a,b)
entrywisediv(a,b)	vector	number	divVectorScalar(a,b)
	number	vector	divScalarVector(a,b)
	matrix	number	divMatrixScalar(a,b)
	number	matrix	divScalarMatrix(a,b)
	vector	vector	divVectors(a,b)
	matrix	matrix	divMatrices(a,b)
outerprod(a,b)	vector	vector	outerprodVectors(a,b)
sum(a,b)	vector	undefined or b=1	sumVector(a)
	matrix	undefined	sumMatrix(a)
	matrix	b=1	sumMatrixRows(a)
	matrix	b=2	sumMatrixCols(a)
prod(a,b)	vector	undefined or b=1	prodVector(a)
	matrix	undefined	prodMatrix(a)
	matrix	b=1	prodMatrixRows(a)
	matrix	b=2	prodMatrixCols(a)
min(a,b)	vector		minVector(a)
(or max)	matrix		minMatrix(a)
	vector	number	minVectorScalar(a,b)
	number	vector	minVectorScalar(b,a)
	vector	vector	minVectorVector(b,a)
	matrix	b=1	minMatrixRows(a)
	matrix	b=2	minMatrixCols(a)
	matrix	number	minMatrixScalar(a,b)
	number	matrix	minMatrixScalar(b,a)
	number	matrix	minMatrixMatrix(a,b)
transpose(a)	vector		transposeVector(a)
	matrix		transposeMatrix(a)
get(a)	vector		vectorCopy(a)
	matrix		matrixCopy(a)
get(a,b)	vector	number	a[b]
	vector	vector/Array	getSubVector(a,b)
get(a,b,c)	matrix	b: number, c=[]	getRows(a,[b])
	matrix	b: vector/Array, c=[]	getRows(a,b)
	matrix	b=[], c: number	getCols(a,[c])
	matrix	b=[], c: vector/Array	getCols(a,c)
	matrix	b: vector/Array, c: vector/Array	getSubMatrix(a,b,c)
randn(), randn(1), randn(1,1)			randnScalar()
Math functions	number		e.g., Math.exp(a)
e.g., exp(a)...	vector		e.g., expVector(a)
	matrix		e.g., expMatrix(a)

Access elements of a vector or matrix directly

The size of a vector x can be directly accessed as

x.length     // vector dimension

Then, the element x_i can be accessed with

x[i]

The size of a matrix A can be directly accessed as

A.length  // number of rows
A.m       // number of rows (= A.length)
A.n       // number of columns

Then, the element A_ij can be accessed with

A.val[i*A.n + j]

Use pointer-like references

To access matrix rows

Consider scanning the rows of matrix X inside a loop as

for(i = 0; i < X.length; i++) {
	Xi = getRows(X, [i]);
	... work with Xi ... 
}

With a call to get (or getRows) the rows are copied into Xi. But if work on Xi only involves reading its entries, this can be made faster by using X.row(i) as

for(i = 0; i < X.length; i++) {
	Xi = X.row(i);
	... work with Xi ... 
}

which provides a pointer-like reference to the ith row of X without copying the data. However, remember that in this case any modification to Xi also applies to X.

To access a contiguous subset of entries in a vector

Consider the code which extracts the first n entries of a vector x as

u = getSubVector(x, range(0, n) );    // equivalent to u = get(x, range(0, n) )

by copying these entries into u. If the work with u only involves reading its entries, then we can instead get a pointer-like reference to the subvector as

u = x.subarray(0, n);

without copying the data.

Do not think you are in Matlab: loops are not so bad!

With LALOLib, there is no obvious need for loop hunting and vectorization.

For instance, in Matlab,

x = (a(2:N) - a(1:N-1)) .* b

is typically faster than

for i=1:N-1
	x(i) = (a(i+1) - a(i)) * b(i)
end

But with LALOLib,

for (i=0; i < N-1; i++) {
	x[i] = (a[i+1] - a[i]) * b[i] ;
}

is probably as fast as

x = entrywisemulVectors( subVectors( a.subarray(1,N), a.subarray(0,N-1) ) , b);

which is faster than

x = entrywisemulVectors( subVectors( getSubVectors(a, range(1,N)), getSubVectors(a, range(0,N-1)) ), b);

The reason is that linear algebra functions like subVectors end up being implemented as javascript loops in the flavor of the one above.

However, using the LALOLib functions can still be faster in some cases where the loop does not get optimized by the browser for one of the reasons detailed at the bottom of this page.

Spare the garbage collector: do not create many objects unnecessarily

Memory cannot be explicitly freed in Javascript, which instead relies on an uncontroled garbage collector. This garbage collector periodically scans all variables and objects to detects the ones that can be destroyed. The more objects (or variables) you create, the longer the scans take, and eventually even the smallest computations can become very slow.

A typical example of this occurs when you create an m-x-n matrix with many rows as an Array of Arrays instead of using zeros(m,n):

A = new Array(m);
for ( i=0; i < m; i++)
	A[i] = new Array(n); 	// or new Float64Array(n) or zeros(n)

In this example, m+1 objects are created versus a single one when using A = zeros(m,n).

Another common mistake is to create global variables for temporary use. Any variable used temporarily in a function should be a local one in order to be freed from memory when the function returns. Remember that in javascript, local variables are declared with the keyword var. Undeclared variables are always global.

Use in-place (saxpy/gaxpy) operations

All basic linear algebra functions in LALOLib create a new Vector/Matrix to store their result, which makes them easy to use and matlab-like. However, inside a loop this can generate a lot of unnecessary memory allocations for temporary variables.

Consider for instance the following iterations of y = y + a x with vectors x, y and scalar a:

for (i=0; i < n; i++) {
    y = addVectors(y, mulScalarVector(a, x));
}

At every iteration, a new vector is created to store the result of mulScalarVector and another one for the result of addVectors. Furthermore, these two get collected as garbage in the next iteration. Instead, it is more efficient to use the in-place operation for y = y + a x (saxpy):

for (i=0; i < n; i++) {
    saxpy(a, x, y);
}

Similarly, the gaxpy function provides the in-place operation for computing y = y + A x with vectors x, y and a Matrix A as gaxpy(A,x,y).

Copy vectors or matrices content only

Consider a loop in which a vector y is initialized to x before doing some work:

for (i=0; i < n; i++) {
    y = vectorCopy(x);
    ... work on y ... 
}

The vectorCopy function actually creates an new Object at each iteration, which becomes garbage at the next one. A more efficient approach is to create a single vector before the loop and only copy the content of x into y:

y = zeros(x.length);
for (i=0; i < n; i++) {
    y.set(x);    // or vectorCopyInto(x,y)
    ... work on y ... 
}

For matrices, the content of X can be copied into Y without additional memory allocations with

Y.val.set(X.val);

Write compiler-friendly javascript code

A number of constructs should be avoided in order not to prevent code optimization performed by the compiler embedded in the browser: use the following checklist.

Write (and use) typed functions with arguments and returning value of fixed typed:
if an argument to a function can be of different types, the function will probably not be optimized. If you need to write such a function, defer all significant computations to subfunctions dedicated to the various types.
Write small (typed) functions for computational intensive subtasks: these will probably be better optimized.
Write loops over Arrays with explicit indexing instead of for (i in a) {...}.
Do not modify the structure of objects:
Adding fields to a matrix object (like for instance A.singularvalues = svd(A) ) changes the internal type of the matrix and makes functions of that matrix execute with non-optimized code.
Do not use try... catch statements.