| Documentation | Build Status | Try It Online! |
|---|---|---|
 |
Finch is a adaptable Julia-to-Julia compiler for loop nests over sparse or structured multidimensional arrays. In addition to supporting sparse arrays, Finch can also handle custom operators and fill values other than zero, runs of repeated values, or even special structures such as clustered nonzeros or triangular patterns.
Finch allows you to write for-loops as if they are dense, but compile them to be
sparse! The compiler takes care of applying rules like x * 0 => 0 and the like
to avoid redundant computation. Finch also supports if-statements and custom
user types and functions. Users can add rewrite rules to inform the compiler
about any special user-defined properties or optimizations. You can even modify
indexing expressions to express sparse convolution, or to describe windows into
structured arrays.
As an example, here's a program which calculates the minimum, maximum, sum, and variance of a sparse vector, reading the vector only once, and only reading nonzero values:
using Finch
X = @fiber(sl(e(0.0)), fsprand((10,), 0.5))
x = Scalar(0.0)
x_min = Scalar(Inf)
x_max = Scalar(-Inf)
x_sum = Scalar(0.0)
x_var = Scalar(0.0)
@finch begin
for i = _
x .= 0
x[] = X[i]
x_min[] <<min>>= x[]
x_max[] <<max>>= x[]
x_sum[] += x[]
x_var[] += x[] * x[]
end
end;You can see what kind of code Finch generates using @finch_code
@finch_code begin
for i = _
x .= 0
x[] = X[i]
x_min[] <<min>>= x[]
x_max[] <<max>>= x[]
x_sum[] += x[]
x_var[] += x[] * x[]
end
endquote
X_lvl = (ex.body.bodies[2]).rhs.tns.tns.lvl
X_lvl_2 = X_lvl.lvl
x_min = (ex.body.bodies[3]).lhs.tns.tns
x_min_val = x_min.val
x_max = (ex.body.bodies[4]).lhs.tns.tns
x_max_val = x_max.val
x_sum = (ex.body.bodies[5]).lhs.tns.tns
x_sum_val = x_sum.val
x_var = (ex.body.bodies[6]).lhs.tns.tns
x_var_val = x_var.val
X_lvl_q = X_lvl.ptr[1]
X_lvl_q_stop = X_lvl.ptr[1 + 1]
if X_lvl_q < X_lvl_q_stop
X_lvl_i1 = X_lvl.idx[X_lvl_q_stop - 1]
else
X_lvl_i1 = 0
end
i = 1
phase_stop = min(X_lvl_i1, X_lvl.shape)
if phase_stop >= 1
i = 1
if X_lvl.idx[X_lvl_q] < 1
X_lvl_q = scansearch(X_lvl.idx, 1, X_lvl_q, X_lvl_q_stop - 1)
end
while i <= phase_stop
X_lvl_i = X_lvl.idx[X_lvl_q]
phase_stop_2 = min(phase_stop, X_lvl_i)
if X_lvl_i == phase_stop_2
cond = 0 < -i + phase_stop_2
if cond
x_max_val = max(0.0, x_max_val)
x_min_val = min(0.0, x_min_val)
end
X_lvl_2_val_2 = X_lvl_2.val[X_lvl_q]
x_min_val = min(x_min_val, X_lvl_2_val_2)
x_max_val = max(x_max_val, X_lvl_2_val_2)
x_sum_val = X_lvl_2_val_2 + x_sum_val
x_var_val = X_lvl_2_val_2 * X_lvl_2_val_2 + x_var_val
X_lvl_q += 1
else
x_max_val = max(0.0, x_max_val)
x_min_val = min(0.0, x_min_val)
end
i = phase_stop_2 + 1
end
i = phase_stop + 1
end
if X_lvl.shape >= i
cond_2 = 0 < X_lvl.shape + 1 + -i
if cond_2
x_max_val = max(0.0, x_max_val)
x_min_val = min(0.0, x_min_val)
end
end
(x_var = (Scalar){0.0, Float64}(x_var_val), x_sum = (Scalar){0.0, Float64}(x_sum_val), x_max = (Scalar){-Inf, Float64}(x_max_val), x_min = (Scalar){Inf, Float64}(x_min_val))
end
Array formats in Finch are described recursively mode by mode. Semantically, an
array in Finch can be understood as a tree, where each level in the tree
corresponds to a dimension and each edge corresponds to an index. For example,
@fiber(d(sl(e(0.0)))) constructs a Float64 CSC-format sparse matrix, and
@fiber(sl(sl(e(0.0)))) constructs a DCSC-format hypersparse matrix. As another
example, here's a column-major sparse matrix-vector multiply:
x = @fiber(d(e(0.0)), rand(42));
A = @fiber(d(sl(e(0.0))), fsprand((42, 42), 0.1));
y = @fiber(d(e(0.0)));
@finch begin
y .= 0
for j=_, i=_
y[i] += A[i, j] * x[j]
end
end;At it's heart, Finch is powered by a new domain specific language for coiteration, breaking structured iterators into control flow units we call Looplets. Looplets are lowered progressively with several stages for rewriting and simplification.
The technologies enabling Finch are described in our manuscript.
At the Julia REPL, install the latest stable version by running:
julia> using Pkg; Pkg.add("Finch")