Monday, June 18, 2012

Matrix Support

The Octave Language

An interesting feature of the Octave language is that matrices are treated as values, not references. For example, the following code
A = [1 2 3];
B = A;
A(1) = 100;
disp (B(1));
will display the value 1, not 100. Matrices are also passed by value in function calls.

Interpreter Implementation

Octave currently uses a really cool system to minimize the number of times matrices. It combines Copy on Write (COW) with reference counting to reduce the number of copies.

The idea is to delay copies until a matrix is mutated. Then the copy is only made if the reference count is greater than one. Take the previous example,
A = [1 2 3];
B = A; # No copy
A(1) = 100; # Copy, as both A and B refer to [1 2 3]
This algorithm has two nice properties. First, it is simple. Second, copies are only made when required.


I plan on using the same algorithm in JIT. This decision means that every assignment of the form
A(idx) = x; # Where idx and x are scalar
requires a check to see if a copy is required. This actually is not such a big issue, because we already require a check to ensure the index is legal. In order to speed up the normal case, we can directly inline the condition check.

Which leads us to the pseudo code for the inlined function.
if (isint (idx) && idx >= 1 && i < nelem (A) && count (A) == 1)
  A(idx) = x;
  A = handle_odd_assign (A, idx, x);
Hopefully, this will allow the normal case to be quick, but still provide a correct implementation for more complicated cases.

No comments:

Post a Comment