A WebGPU implementation of recursive Datalog queries. Semi-naive evaluation runs to a fixed point entirely in compute shaders, over sorted arrays rather than a hash index, with the host outside the iteration loop.
Artifact for Terascale Query Processing in the Browser: Rethinking GPU Acceleration.
Datasets are listed in the public/data folder. A .bin file is a flat
little-endian Uint32Array of [src, dst, src, dst, ...], and the filename
carries the edge count, so data_88234.bin holds 88,234 edges. The .txt files
beside them are the same graphs as whitespace-separated pairs.
The 12 transitive-closure graphs and the 4 same-generation graphs are included.
The triangle-counting inputs are large SNAP graphs and are not, so
src/app-triangle.ts will not run until you fetch them from
https://snap.stanford.edu/data/ and convert them to the format above.
The complete benchmark runs on an NVIDIA RTX 3060 Laptop GPU with 6 GB of
memory. Partial benchmarks run on smaller GPUs, but some datasets will abort
during buffer allocation. Two graphs shipped in public/data are outside the
benchmark suite for this reason, data_51971 and data_103689, whose peak
intermediate relation exceeds what 6 GB holds.
A Chromium-based browser with WebGPU and the subgroups feature. The
set-operation kernels use subgroup ballot and shuffle, and src/app.ts exits
with an error if the adapter does not expose it.
chrome://flags -> Unsafe WebGPU Support -> Enabled
timestamp-query is optional. Without it the per-stage GPU breakdown is empty
and end-to-end timing still works.
Node 18 or later, for the build and for the WebAssembly baselines.
npm install
Transitive closure is the running example throughout the paper. Build and run instructions are provided below.
npm run serve
src/app.ts reads its dataset list from the query string, and its built-in
default is a graph that is not shipped here, so pass one.
http://localhost:8080/?datasets=data_7035,data_21693,data_23874,data_26013,data_39994,data_48232,data_49152,data_88234,data_119666,data_121544,data_196575,data_223001
The page is only a host for the compute pipeline, which runs to completion on load and logs to the console. Each dataset gets 10 warmup and 100 timed runs. On the machine above the 12-dataset suite reports
| Dataset | Iters | Final full size | E2E (ms) | σ |
|-------------|------:|----------------:|---------:|------:|
| data_7035 | 64 | 146,120 | 42.004 | 2.002 |
| data_26013 | 20 | 21,402,960 | 181.494 | 3.268 |
| data_49152 | 188 | 78,557,912 | 1182.753 |13.061 |
| data_119666 | 426 | 5,022,084 | 328.263 | 6.177 |
| data_223001 | 287 | 80,498,014 | 1446.111 | 4.251 |
Final full size is the closure size, and it is identical across all 100 runs
of every dataset.
webpack.config.js has a single entry. Point it at another driver and rebuild.
The other two carry their own hard-coded dataset lists.
entry: "./src/app.ts" transitive closure, 12 graphs
entry: "./src/app-sg.ts" same generation, 4 graphs
entry: "./src/app-triangle.ts" triangle counting, 8 SNAP graphs
One build runs several join strategies back to back within a single page load, with every other stage held fixed, so nothing but the URL differs between arms.
http://localhost:8080/?lookup=binsearch,mnmg,gpulog&datasets=data_7035,data_88234
binsearch lower_bound on lex-sorted E, then scan until the key changes.
The production path.
mnmg one hash slot per tuple, probe stops only at an empty slot,
prefix-sum output placement, no atomics
gpulog one index entry per distinct key over sorted E, prefix-sum
placement
hash hash probe with the same slab reservation the production path
uses
The two ports are faithful to the published designs and are given two advantages the originals do not have. Their two prefix-sum passes are fused into one decoupled-lookback pass, and neither is charged for the host readback the original performs after counting.
Three engines run under Node against the same inputs.
node sqljs_bench.js [tc|sg|both] [dataset] [warmup] [timed]
node duckdb_bench.js [tc|sg|both] [dataset] [warmup] [timed]
node ascent_bench.js [tc|sg|both] [dataset]
ascent-bench/ is the Rust crate behind the third. Its compiled WebAssembly is
committed under ascent-bench/pkg/, so no Rust toolchain is needed to run it.
Rebuilding needs wasm-pack.
The CUDA baselines and Souffle are not part of this repository.
The flags at the top of src/app.ts select the pipeline. The committed values
are the ones the paper reports.
USE_SETOPS true sorted Full with set difference and
disjoint merge, in place of a hash
membership test. Requires subgroups.
USE_BINSEARCH_JOIN true index nested-loop join, in place of a
hash table over E
USE_FUSED_DEDUP_SETDIFF true one kernel for deduplication and set
difference, in place of three
BATCH_SIZE_MAX 30 iterations per command buffer, shrunk
adaptively near the fixed point
WARMUP_RUNS / TIMED_RUNS 10/100 per dataset
Capacity constants in the same block fix every buffer size at startup, which is what lets the fixpoint loop run without allocating.
One fixpoint iteration, recorded into a command encoder. Every dispatch is indirect, and no size crosses back to the host.
// count and join args, derived on the GPU from the previous delta's size
argsWriter.recordSimpleArgs(encoder, bufferDeltaSize, countJoinArgsBuf);
const countPass = encoder.beginComputePass(timer.beginPass('count'));
countPass.setPipeline(join.countPipeline);
countPass.setBindGroup(0, countBGs[s]);
countPass.dispatchWorkgroupsIndirect(countJoinArgsBuf, 0);
countPass.end();
const joinPass = encoder.beginComputePass(timer.beginPass('join'));
joinPass.setPipeline(join.joinPipeline);
joinPass.setBindGroup(0, joinBGs[s]);
joinPass.dispatchWorkgroupsIndirect(countJoinArgsBuf, 0);
joinPass.end();
// sort args from the candidate count the count pass just wrote
argsWriter.recordSortArgs(encoder, bufferCount,
splitArgsBuf, histoArgsBuf, scatterArgsBuf,
sortBuffersNewT.uniformBuffer);
recordGPULexSortIndirectInPlace(encoder, sorter, sortBuffersNewT,
histoArgsBuf, scatterArgsBuf, timer, 'sort');
// deduplicate and subtract Full in one pass
fusedDedupSetDiff.record(encoder,
sortBuffersNewT.values, sortBuffersNewT.keys, bufferNewTSize,
bufferFullSortedKeys[fs], bufferFullSortedValues[fs], bufferFullSortedSize[fs],
bufferDeltaPair_keys[1 - s], bufferDeltaPair_values[1 - s], bufferNewDeltaSize,
timer, 'dedup+split+setDifference');
// Full and the new delta are disjoint by construction, so a merge suffices
mergeDisjoint.record(encoder,
bufferFullSortedKeys[fs], bufferFullSortedValues[fs], bufferFullSortedSize[fs],
bufferDeltaPair_keys[1 - s], bufferDeltaPair_values[1 - s], bufferNewDeltaSize,
bufferFullSortedKeys[fsNext], bufferFullSortedValues[fsNext], bufferFullSortedSize[fsNext],
timer, 'mergeDisjoint');
// the next iteration's input size, device to device
encoder.copyBufferToBuffer(bufferNewDeltaSize, 0, bufferDeltaSize, 0, 4);Thirty of these are recorded into one command buffer before a single submit. The host reads one value per batch, whether the delta has become empty.