Less is More: The Sparse Matrix Hackathon

A bitmap-indexed sparse representation for a text/word-frequency matrix, written in C.

The assignment gives you a 10 × 100 integer matrix (4,000 bytes) holding word frequencies for ten sentences, where most cells are zero, and asks for a representation that stores only the useful values. The suggested routes are coordinate triples (row, col, value) or a linked list of nodes.

I went with neither. This uses a bitmap plus a packed value array, which for this matrix comes out smaller than both — 102 bytes, a 39× reduction — and the reason it wins is worth more than the number itself.

---

The idea

Split the matrix into two questions that are usually answered together:

1. Is there a value here? → one bit per cell, in a bitmap.
2. What is it? → the non-zero values, packed back to back with nothing between them.

The bitmap answers question 1 for every cell at a cost of one bit each. The value array — I called it the vault in the code — holds only the numbers that actually exist, in row-major order, with no indices attached.

The trick is that you don't need to store indices. To read cell (r, c):

pos = r * wordCount + c

bitmap[pos] == 0  ->  the answer is 0, stop
bitmap[pos] == 1  ->  count the 1s before pos; that count is the
                      index into the vault

Counting the set bits before a position is the rank operation from succinct data structures. It's what lets the vault stay index-free: a value's position in the packed array is fully determined by how many non-zeros precede it.

A worked example on a 2 × 4 matrix:

matrix   3 0 0 1        bitmap   1 0 0 1 0 1 0 0
         0 2 0 0        vault    3 1 2

get(1,1) -> pos = 1*4+1 = 5; bit is 1; set bits before pos 5 are at
            0 and 3, so rank = 2 -> vault[2] = 2   ✓
get(0,2) -> pos = 2; bit is 0 -> return 0 without touching the vault   ✓

---

Why not coordinate triples or a linked list

Both suggested methods store the address of every value alongside the value. That's the expensive part, and it's what the bitmap avoids.

For this matrix — 10 rows, 33 unique words, 60 non-zero entries:

Representation	Bytes	Notes
Dense int[10][100] (the baseline)	4,000	what the starter code uses
Dense, trimmed to int[10][33]	1,320	still stores every zero
Linked list, {int, int, int, ptr} nodes	1,440	24 B/node on 64-bit — worse than dense
COO triples as int	720	12 B per non-zero
COO triples packed into unsigned char	180	3 B per non-zero
CSR (row pointers + column indices)	142	22 + 60 + 60
Bitmap + packed vault	102	42 + 60

The linked-list row is the one worth pausing on. It's a method the assignment suggests, and on a matrix this size it uses more memory than storing every zero — because each node carries an 8-byte pointer plus padding to hold a single 1-byte frequency. Dynamic growth is a real advantage, but it isn't free, and at this density the pointer overhead swamps the savings.

When does the bitmap win? It costs R*C/8 + nnz bytes; byte-packed COO costs 3*nnz. The bitmap is smaller whenever

R*C/8 + nnz  <  3*nnz     ⟺     density > 1/16 ≈ 6.25%

This matrix sits at 60/330 = 18.2% density, comfortably past the crossover. The direction of that inequality matters more than the specific number: bitmaps win on moderately sparse data and lose on extremely sparse data, where the bitmap degenerates into a mostly-empty array of zero bits and explicit coordinates become cheaper. A word-frequency matrix over ten short sentences is only mildly sparse, which is exactly the regime this representation suits.

---

Results

Original size     : 4000 bytes
Bitmap            :   42 bytes
Vault (values)    :   60 bytes   (0 waste)
Total memory used :  102 bytes

39× smaller, with every cell still reconstructible. The printed matrix is identical to the dense version.

Vocabulary: 33 unique words across 10 sentences; 60 of the 330 cells are non-zero.

---

Build and run

gcc main.c sparse_utils.c -o sparse_matrix_demo
./sparse_matrix_demo

Adding sentences to the lines array in sparse_utils.c works as before — wordCount, the bitmap and the vault all resize on the next run.

---

Files

main.c           display logic + memory accounting
sparse_utils.c   tokenizing, vocabulary building, compression, lookup
sparse_utils.h   shared declarations and the SET_BIT / GET_BIT macros

Three memory decisions inside sparse_utils.c:

• The dense grid is built first in a calloc'd temporary buffer, because the vocabulary size isn't known until the text has been parsed.
• The vault is malloc'd to exactly nonZeroCount bytes after counting — no over-allocation, no growth doubling.
• The 4,000-byte temporary is free'd as soon as compression finishes, so the steady-state footprint is the 102 bytes above.

That last point needs a caveat: 102 bytes is the steady state, not the peak. During construction the program briefly holds the temporary dense grid, so peak usage is about 4.1 KB. Removing it would mean tokenizing in two passes — one to fix the vocabulary, one to fill the structure directly — which is the obvious next improvement.

---

Scalability, and the one thing that doesn't scale

Space scales well. At fixed density the total is R*C/8 + nnz bytes, which stays a small constant factor above the count of real values however large the matrix gets.

Lookup does not. getSparseValue computes rank by scanning every bit from position 0, so one lookup is O(R×C) and printing the whole matrix is O((R×C)²). At 330 cells that's invisible. At 10,000 × 10,000 it would be fatal.

The standard fix is a rank directory: precompute the running total of set bits at the start of every block of, say, 8 bytes, and keep those counts in a small array. A lookup then reads one precomputed count and popcounts a handful of bytes — O(1) instead of O(n) — for roughly 12% extra space. That turns this from a representation that is merely compact into one that is compact and fast, and it's where I'd take this next.

Two other limits worth stating:

• Frequencies live in unsigned char, so a word appearing more than 255 times in one sentence would overflow. Fine here — the maximum is 3 — but it's an assumption, not a guarantee.
• Tokenization splits on spaces only. No punctuation handling, no case folding, so Data and data would become separate columns.

---

What I took from this

The interesting part wasn't compressing the matrix. It was noticing that "where are the values" and "what are the values" are two different questions with two different best answers. Once they're separated, the addressing information — normally two-thirds of the cost in a COO representation — collapses to one bit per cell, and the values themselves need no addressing at all.

The other lesson: the intuitive answer isn't automatically the efficient one. A linked list feels like the memory-saving choice, because nothing is allocated until it's needed. Measured against the dense baseline it loses, and it loses to a pointer whose only job is to say where the next node lives.