Data Structure

CSR (Compressed Sparse Row) comes up constantly in graph computation and storage optimization. It first appeared in a 1977 Yale University report, the Yale Sparse Matrix Package, which is why it’s sometimes called the Yale format. It was designed to store and process sparse matrices efficiently. What a Sparse Matrix Is A sparse matrix is one where most of the entries are zero. You run into them across nearly every corner of modern computing: scientific computing, graph theory, machine learning. Real-world data, once you cast it as a matrix, almost always ends up looking like this. Take a social network: even with a million users, any given person typically has around 500 friends. Representing that directly as a matrix would require something on the order of 10^12 entries, roughly 7.3 petabytes. Storage cost balloons far beyond the actual information the matrix carries. ...

This post is my own write-up of Rust hash iteration+reinsertion and the related Rust issue/PR, written the way I understood them. The original is the authoritative source, so check it directly for the exact details. I want to walk through an interesting bug that showed up in Rust’s HashMap. The code looks completely ordinary, yet under the right conditions, an operation that should be O(n) blows up to O(n²). Reproducing the Bug Look at the code below. It inserts values 1 through 5,000,000 into a first hash map (one, that’s T1), then iterates over one and reinserts every value into a second hash map (two, that’s T2). Nothing fancy. ...