Efficient workspace: type or immutable?


#1

A recent thread on the Julia users’ newsgroup about SparseMatrixCSC made me realize that my code may have a hidden inefficiency. My code has the following structure. A key computational routine is GAssemble, similar to finite element matrix assembly. It repeatedly invokes another function, say EAssemble, for individual element assembly. EAssemble uses dozens of small matrices/vectors of small fixed size (size fixed at run time, not compile time.) So I created a composite type called WorkSpace, and the initializer for a WorkSpace allocates all the dozens of small arrays and matrices. GAssemble invokes this initializer for the workspace once, and then it passes the workspace to EAssemble many times inside a loop.

Question: Should WorkSpace be an immutable composite (immutable) or an ordinary composite (type)?

Argument in favor of ordinary composite: the header information for all of the dozens of small matrices and vectors does not have to be copied over each time EAssemble is invoked.

Argument in favor of immutable composite: I just learned from the recent discussion that if typeof(ws)==WorkSpace, and Workspace is an ordinary (mutable) composite type, then a reference to a matrix element like ws.a[i,j] inside a tight loop needs multiple dereferencing at run-time because the compiler apparently can’t tell that ws.a didn’t change since the last loop iteration. (In which version of Julia??)

Suggestions would be appreciated!

– Steve Vavasis


#2

I would normally use a mutable type for something like this. The main use for immutable is when you potentially have zillions of instances of a type, in which case immutable makes it much cheaper to store in arrays and other data structures. In contrast, mutable types are much easier to work with for types with lots of fields that you might need to update individually.

Any efficiency concerns about accessing ws.a[i,j] in a tight loop can be alleviated just by assigning to a temporary variable a = ws.a[i,j] outside the loop.


#3

Whether composite or not, immutable types are easier to reason about (whether for humans or compilers) and less error prone. In many cases, that’s more important than performance. Performance-wise, immutable scales much better in parallel execution. Personally, when I don’t have a good reason to go with mutable type, I default to immutable. In some cases, breaking a type in two to form a hybrid may be the best way. In any case, if performance is a worry, nothing beats benchmarking the various alternatives.