Experiments and implementations · Intermediate

Compare storage for the same graph

Verify identical neighbors before comparing byte matrices and32-bit CSR payload, object sizes and process-wide RSS.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Store one graph in two representations
  2. Predict logical bytes first
  3. Fix generation and measurement scope
  4. Check every row before reporting memory
  5. Interpret only what was measured
  6. Distinguish construction peak from retained representation
  7. Exercise: calculate a changed-density case
  8. Ask Logeia about this articleCheck your understanding

Store one graph in two representations

A graph's vertex count alone does not decide its best representation. Build directed graphs on two hundred vertices and store each as a byte-per-cell adjacency matrix and compressed sparse rows. Exclude self loops and duplicate edges. CSR uses thirty-two-bit offsets and destination indices. Before comparing storage, assert that every row exposes exactly the same neighbors in both forms.

Equal information is essential. If one representation also stores weights or reverse edges, its memory cost describes a different task. This experiment uses unweighted directed edges. An undirected extension needs an explicit policy for storing both directions. Distinguish mathematical edge count, stored entries and allocated bytes. Comparing labels such as matrix and list without those contracts can make an apparently precise memory result meaningless.

Predict logical bytes first

With V equal to two hundred, the matrix contains forty thousand bytes. CSR has V plus one offsets and E destinations, giving four times (V plus one plus E) bytes with thirty-two-bit entries. There are 39,800 possible nonself directed edges. At one percent density, E is 398 and predicted CSR payload is 2,396 bytes. At ten percent, 3,980 edges require 16,724 bytes.

At fifty percent, 19,900 edges require 80,404 CSR bytes, exceeding the byte matrix. The break-even depends on actual element types. A bit-packed matrix would have a different payload again. The experiment's byte-per-cell choice is explicit, not a claim that all adjacency matrices use that representation. Predict from stored arrays before measuring runtime objects so the numerical comparison has a clear basis.

DensityEdgesByte matrix32-bit CSR
1%39840,000 B2,396 B
10%3,98040,000 B16,724 B
50%19,90040,000 B80,404 B

Fix generation and measurement scope

Save the code as graph.py and run it with Python on Linux using only the standard library. Seed seven chooses a fixed number of distinct candidate edges for each density, then sorts them for row construction. Assert that the integer array item size is four bytes. If another runtime has a different width, revise the type or prediction rather than silently comparing against the old formula.

The candidate-edge and chosen-edge lists also consume memory. Consequently the reported process peak RSS is not the isolated cost of either graph representation. This example compares logical payload and object sizes while demonstrating their difference from a process-wide measure. A strict standalone RSS comparison would need separate processes and a defined baseline; do not subtract these mixed-process figures and label the result per-representation memory.

Check every row before reporting memory

The matrix sets position i times V plus j. CSR appends a row's destinations and then records the next offset. Row i spans offsets[i] through offsets[i plus one], excluding the end. An empty row uses equal adjacent offsets. There must be V plus one offsets so the final row also has an explicit end; the last offset equals the total stored destinations.

Assert neighbor equality for all two hundred rows before printing capacity numbers. A smaller representation that dropped edges has not solved the same problem. Output vertex and edge counts, logical payload, sys.getsizeof object sizes and process peak RSS as separately named fields. Identify exactly which fields correspond to the prediction formula. This prevents several incompatible meanings of memory from being presented as one interchangeable measurement.

python
import array,random,resource,sys
n=200;rng=random.Random(7)
for fraction in [0.01,0.1,0.5]:
    pairs=[(i,j) for i in range(n) for j in range(n) if i!=j];edges=sorted(rng.sample(pairs,int(len(pairs)*fraction)))
    matrix=bytearray(n*n);offsets=array.array('I',[0]);columns=array.array('I');cursor=0
    assert offsets.itemsize==columns.itemsize==4
    for i in range(n):
        while cursor<len(edges) and edges[cursor][0]==i:
            j=edges[cursor][1];matrix[i*n+j]=1;columns.append(j);cursor+=1
        offsets.append(len(columns))
    for i in range(n):assert [j for j in range(n) if matrix[i*n+j]]==list(columns[offsets[i]:offsets[i+1]])
    logical_csr=4*(n+1+len(edges));logical_matrix=n*n
    assert logical_csr==offsets.itemsize*len(offsets)+columns.itemsize*len(columns)
    print('vertices=',n,'edges=',len(edges),'matrix_bytes=',logical_matrix,'csr_bytes=',logical_csr,'objects_bytes=',sys.getsizeof(matrix),sys.getsizeof(offsets)+sys.getsizeof(columns),'process_peak_rss_KiB=',resource.getrusage(resource.RUSAGE_SELF).ru_maxrss)
print('same directed graph, no self loops or duplicate edges; all rows matched')

Interpret only what was measured

Logical predictions should match array lengths and element widths. sys.getsizeof additionally includes object management and allocation slack, so it can exceed payload bytes. Peak RSS depends on construction history and reports the whole process. The code labels Linux ru_maxrss in KiB; other operating systems may use another unit. Preserve OS and Python version with results.

The experiment does not time neighbor iteration or single-edge membership queries. Matrix indexing and CSR neighbor traversal support different operation patterns, but their actual latency was not measured by comparing byte counts. Cache effects and Python loop overhead are additional factors. Restrict conclusions to measured storage, then design a separate timing workload with identical queries and verified answers if performance is the next question.

For a representation-specific RSS comparison, launch separate processes with identical preparation and measurement boundaries. The single-process observation here cannot isolate either representation's incremental resident memory.

Distinguish construction peak from retained representation

This generator enumerates every possible edge before sampling, so temporary construction memory is quadratic even when retained CSR payload is linear in V plus E. A very large sparse-graph experiment should stream generation or consume an existing edge list instead. The completed representation's space bound does not automatically describe its builder's peak usage.

Preserve semantic graph equality when changing generation. Sorting and deduplication add their own temporary work. Separate reading input, constructing, retaining and querying the representation. Comparing whole-process RSS with only the final CSR formula and calling the difference waste confuses measurement boundaries.

For a rerun, keep Python version, array width and graph contracts explicit. If a result changes, first decide whether logical payload changed or whether object overhead and process-wide state changed. That classification makes the observed numbers useful rather than treating every memory field as an interchangeable implementation score.

Exercise: calculate a changed-density case

For V equal to one hundred and E equal to five hundred with the same types, the matrix payload is ten thousand bytes and CSR is four times 601, or 2,404 bytes. At three thousand edges, CSR becomes 12,404 bytes and exceeds the matrix. Solve the break-even from the formulas, then choose densities on both sides for an additional run.

A bit-packed hundred-by-hundred matrix has 1,250 logical bytes before management overhead, but changes access operations and tail handling. Do not reuse earlier object-size or speed claims after changing representation. The example creates no network or database resources; retain only source and reported results as needed. Explain input contracts, semantic equality, predicted storage and measurement scope together rather than selecting one attractive byte count.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 5

Prepare for AI systems · STEP 2

Choose a learning path