facebook / facebook/zstd

Vectorize `blockSize_explicitDelimiter()`

Open
#3,456 0 comments 2 reactions 1 assignee Claimed by @embg View on GitHub
long-term
Dominant language
C
Stars
27.9k
Forks
2.6k
Avg merge
1d 3h
Merged PRs (30d)
8

Description

The function [blockSize_explicitDelimiter()](https://github.com/facebook/zstd/blob/321490cd5b9863433b3d44816d04012874e5ecdb/lib/compress/zstd_compress.c#L6427-L6447) is used to validate that `sum(matchLen) + sum(litLen)` for external sequences adds up to the correct `blockSize`. The hot loop is:
```
while (spos < inSeqsSize) {
end = (inSeqs[spos].offset == 0);
blockSize += inSeqs[spos].litLength + inSeqs[spos].matchLength;
if (end) {
if (inSeqs[spos].matchLength != 0)
return 42; // error
break;
}
spos++;
}
```

Godbolt indicates that clang15 compiles this to a naive scalar loop: https://godbolt.org/z/osjE5KeP6. gcc12 yields a similar result. uiCA gives the naive loop a throughput of 3 cycles/sequence, which seems pretty slow to me: https://bit.ly/401i7ZD.

I think we can do significantly better. For example, this loop could be vectorized by loading one `ZSTD_Sequence` struct into a SSE vector (or two `ZSTD_Sequence` structs into an AVX vector) and performing 2 (or 4) parallel sums. Skylake Xeon can do 2 (load+VPADD)/cycle (according to uops.info), so with multiple accumulators and unrolling we could get up to 4 (or 8) parallel sums. Of course, we'd need to be careful about 32-bit overflow, but even with vectorized overflow checks this solution should be much faster.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.