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:
#import <Foundation/Foundation.h>
NS_ASSUME_NONNULL_BEGIN
@interface SparseMatrix : NSObject
- (instancetype)init NS_UNAVAILABLE;
+ (instancetype)new NS_UNAVAILABLE;
- (instancetype)initWithRows:(NSInteger)rows columns:(NSInteger)columns NS_DESIGNATED_INITIALIZER;
- (void)setObject:(id)object atRow:(NSInteger)row column:(NSInteger)column;
- (nullable id)objectAtRow:(NSInteger)row column:(NSInteger)column;
- (void)removeObjectAtRow:(NSInteger)row column:(NSInteger)column;
@end
NS_ASSUME_NONNULL_ENDSince 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 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 sparse_matrix_double:
@implementation SparseMatrix {
sparse_matrix_double _matrix;
}Since 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:
_Static_assert(sizeof(void *) <= sizeof(double), "Our pointers will be truncated");Our initializer is fairly straightforward; we simply end up calling sparse_matrix_create_double to allocate the underlying sparse matrix:
- (instancetype)initWithRows:(NSInteger)rows columns:(NSInteger)columns
{
if (rows == 0 || columns == 0) {
@throw [NSException exceptionWithName:NSInvalidArgumentException reason:@"A sparse matrix must have at least one entry" userInfo:nil];
}
if (!(self = [super init])) {
return nil;
}
_matrix = sparse_matrix_create_double((sparse_dimension)rows, (sparse_dimension)columns);
return self;
}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:
_Static_assert(sizeof(NSInteger) <= sizeof(sparse_dimension), "Our sizes will be truncated");We might as well do this for the sparse_index type we’ll use later as well:
_Static_assert(sizeof(NSInteger) <= sizeof(sparse_index), "Our indices will be truncated");Next, let’s implement our -setObject:... method. This one’s a one-liner:
- (void)setObject:(id)object atRow:(NSInteger)row column:(NSInteger)column
{
sparse_insert_entry_double(_matrix, (double)((uint64_t)[object retain]), (sparse_index)row, (sparse_index)column);
}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:
- (id)objectAtRow:(NSInteger)row column:(NSInteger)column
{
double value = 0;
sparse_index end = 0;
sparse_index index = 0;
sparse_extract_sparse_row_double(_matrix, (sparse_index)row, (sparse_index)column, &end, 1, &value, &index);
return [[(id)((uint64_t)value) retain] autorelease];
}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:
- (void)removeObjectAtRow:(NSInteger)row column:(NSInteger)column
{
// Doesn't use -objectAtRow... for retrieval to avoid autorelease.
double value = 0;
sparse_index end = 0;
sparse_index index = 0;
sparse_extract_sparse_row_double(_matrix, (sparse_index)row, (sparse_index)column, &end, 1, &value, &index);
[(id)((uint64_t)value) release];
sparse_insert_entry_double(_matrix, 0, (sparse_index)row, (sparse_index)column);
}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.
- (void)dealloc
{
const NSInteger rows = (NSInteger)sparse_get_matrix_number_of_rows(_matrix);
const sparse_dimension columns = sparse_get_matrix_number_of_columns(_matrix);
double *const columnSpace = malloc(columns * sizeof(double));
sparse_index *const indices = malloc(columns * sizeof(sparse_index));
for (NSInteger row = 0; row < rows; row++) {
if (sparse_get_matrix_nonzero_count_for_row(_matrix, row) > 0) {
sparse_index columnEnd = 0;
sparse_extract_sparse_row_double(_matrix, row, 0, &columnEnd, columns, columnSpace, indices);
for (NSInteger column = 0; column < columns; column++) {
[(id)((uint64_t)columnSpace[column]) release];
}
}
}
free(columnSpace);
free(indices);
sparse_matrix_destroy(_matrix);
[super dealloc];
}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 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:
#if defined(__LP64__) && __LP64__
#define sparse_pointer_storage double
#define sparse_pointer_storage_int uint64_t
#define sparse_pointer_matrix sparse_matrix_double
#define sparse_pointer_matrix_create sparse_matrix_create_double
#define sparse_pointer_matrix_insert sparse_insert_entry_double
#define sparse_pointer_matrix_extract sparse_extract_sparse_row_double
#else
#define sparse_pointer_storage float
#define sparse_pointer_storage_int uint32_t
#define sparse_pointer_matrix sparse_matrix_float
#define sparse_pointer_matrix_create sparse_matrix_create_float
#define sparse_pointer_matrix_insert sparse_insert_entry_float
#define sparse_pointer_matrix_extract sparse_extract_sparse_row_float
#endifNow 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.