COST
COST copied to clipboard
Single-threaded graph computation in Rust
COST
COST is an acronym for the "Configuration that Outperforms a Single Thread", indicating the hardware resources required by a distributed system before it begins to outperform a single-threaded implementation. This repository contains the single-threaded implementations providing the baseline performance.
Specifically, this repository contains single-threaded implementations of three graph algorithms, PageRank, label propagation, and union-find, supporting performance measurements taken on two graphs, twitter_rv and uk_2007_05. The code is intended to be instructive, rather than a meaningful replacement for a graph-processing system.
Instructions
The project consists of several independent binaries and a supporting library. The src/bin/
directory has one file for each binary, each of which can be executed by typing
cargo run --release --bin <binary_name> -- <arguments>
All binaries take at least one argument, and can be run with zero arguments to present their usage (and any warnings about files that may be overwritten as a result of executing the binary).
Introducing graph data
The most common first binary to use is to_vertex
, which creates a binary representation of data presented as a textual list of pairs of vertex identifiers (one per line). You should be able to type:
% cargo run --release --bin to_vertex
Finished release [optimized] target(s) in 0.0 secs
Running `target/release/to_vertex`
Usage: to_vertex <source> <prefix>
NOTE: <prefix>.nodes and <prefix>.edges will be overwritten.
%
If you acquire some excellent graph data, you could for example type
% cargo run --release --bin to_vertex -- my_graph.txt my_graph
which will create files my_graph.nodes
and my_graph.edges
. These files will generally be smaller than the textual representation, though the .nodes
file will use space proportional to the largest vertex identifier.
Once you have ingressed some graph data, you can also re-arrange the data according to a Hilbert curve, which is an excellent bit of mathematics you can search for and read about if you so care.
% cargo run --release --bin to_hilbert -- my_graph
will produce my_graph.upper
and my_graph.lower
for pre-existing my_graph.nodes
and my_graph.edges
. The Hilbert representation can be even a bit tighter, and often has improved performance for several of the algorithms.
Graph algorithms
There are three algorithms here: pagerank, label propagation, and union find. Each has their own binary, and each expects you to supply three arguments: the "mode", which is one of vertex
, hilbert
, and compressed
, the graph filename prefix, and a number greater than the largest vertex identifier (a size for per-vertex state allocation). If you don't know the last number, the stats
binary can help you out by scanning the graph for you.
For example,
% cargo run --release --bin union_find -- hilbert ./friendster 66000000
Finished release [optimized] target(s) in 0.0 secs
Running `target/release/union_find hilbert ./friendster 66000000`
65608365 non-roots found
%
which reports the number of nodes in the graph minus the number of connected components.
Notes
There is a companion COST repository managed by Microsoft Research, including the state of the project several months ago. This may be helpful if you are interested in the corresponding C# implementations. The repository also contains Naiad implementations that were done more recently. I am no longer affiliated with Microsoft and cannot commit to the repository (nor, historically, do they accept pull requests), and must apologize for the sorry state I left the code in. It may be cleaned up in the future (either by me, or other more industrious souls), given the right incentives.