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 `float`

and `double`

values, with a few hacks, we can write a wrapper API that takes pointers, or more usefully, Objective-C objects.

Our `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 `-init`

and `+new`

initializers have been marked as unavailable. All indices and dimensions are also `NSInteger`

s so they import to Swift as `Int`

s for best impedance matching.

Now let’s move to the implementation. Our underlying storage will be a `sparse_matrix_double`

:

Since `double`

s 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 `NSInteger`

to `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 `double`

s 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 `end`

and `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 `nil`

.

Our `-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 `0`

since `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.

This `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 `double`

s, 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.