Sparse matrices are matrices that are mostly-empty (i.e. most of their entries are zeros). By realizing a matrix is sparse and using a sparse matrix implementation, we can save space and improve performance, especially when working with large dimensions. Rather than allocating a buffer of
rows * columns size, a sparse matrix implementation will proportionally grow in size with the number of non-zero entries in the matrix.
In iOS 9 and macOS 10.11, Apple added API to the Accelerate framework for working with sparse matrices. While Apple’s APIs are designed for working with
double values, with a few hacks, we can write a wrapper API that takes pointers, or more usefully, Objective-C objects.
SparseMatrix wrapper class will have an interface that looks fairly similar to the
NSArray API but takes row/column pairs instead of single indices:
Since our matrices can’t be resized and it’s not useful having a matrix with zero elements, the parameter-less
+new initializers have been marked as unavailable. All indices and dimensions are also
NSIntegers so they import to Swift as
Ints for best impedance matching.
Now let’s move to the implementation. Our underlying storage will be a
doubles are 64-bits in size, they’re sufficient to store any pointer we might pass along. Just to be safe, we can add a static assertion that verifies this:
Our initializer is fairly straightforward; we simply end up calling
sparse_matrix_create_double to allocate the underlying sparse matrix:
Again, we disallow creating empty matrices by throwing an exception if any of the dimensions are
0. Note that it’s safe to cast from a
sparse_dimension since a
sparse_dimension is a
UInt64, however just to be sure we’re not doing a narrowing conversion, we can add a static assertion:
We might as well do this for the
sparse_index type we’ll use later as well:
Next, let’s implement our
-setObject:... method. This one’s a one-liner:
Before adding the object, we retain it, this way our object will not go away as long as it’s in the sparse matrix. We then cast its pointer to a
uint64_t, which is safe because pointers are at most 64-bits, and then we cast to a
double, which is safe because
doubles are also 64-bits in size. Unfortunately, clang doesn’t let us cast directly from a pointer to a
double, but that’s understandable.
As you may have noticed, the call to
-retain implies we’re not using ARC. The reason is that casting from a
uint64_t to a pointer is unsupported since ARC wouldn’t have enough information to reason about the memory management semantics. While our
SparseObjects library itself doesn’t use ARC, it works just fine with any clients that have ARC enabled (including Swift projects).
Now let’s implement the method that will allow us to retrieve our objects:
Here, we simply delegate to
sparse_extract_sparse_row_double to extract values starting at the given row and column. Since we just want the value at the given row/column and no adjacent values, we pass in
1 as the fifth argument. We also don’t use the values returned by reference to
index, but we can’t pass
NULL for those parameters. Next, we cast the
double back to a
uint64_t and then back to a
pointer, which is the inverse of the conversion we did in the previous method. Finally, we return an autoreleased instance of the object.
Note that if the object doesn’t exist,
value will be
0, which gets cast to
nil. Since messaging a
nil object in Objective-C is a no-op, this method just ends up returning
-removeObjectAt... method is quite similar since we have to retrieve the object first in order to send it a
-release message before it gets removed:
Once the object has been released, we simply set a value of
0 at the given row/column.
Finally, we have to consider what happens when the sparse matrix is deallocated. If there are objects stored in it, we have to release them or we’ll have memory leaks.
While the code is a bit long, we simply iterate through all the rows in the matrix, and if a row has non-zero entries, we loop through all of them and send any objects a
-release message. Note, again, that this is a no-op if the entry is
columnSpace[column] ends up getting cast to
nil, and messaging a
nil object is a no-op. Finally, we destroy the underlying matrix and our temporary buffers.
dealloc implementation isn’t the fastest, however it’s the price we pay for lower memory usage overall. One thing you could do is maintain around a separate set of objects that contains just the objects that are currently in the matrix. However, since the point of using sparse matrices is to reduce memory usage, I didn’t do that here.
Speaking of memory usage, there is one more optimization we can make. On 32-bit systems, the implementation above will still end up storing pointers in
doubles, however, 32-bit pointers only require half the storage space. To take this into account, we can conditionally define a set of
sparse_pointer_* APIs that use floating-point Accelerate APIs on 32-bit systems and double-precision Accelerate APIs on 64-bit systems:
Now everywhere you see a
double you’d use a
sparse_pointer_storage, everywhere you see a
sparse_matrix_create_double you’d use a
sparse_pointer_matrix_create, and so on.
The full implementation, complete with unit tests, can be found on GitHub.