Parallelize ld.lld --compress-debug-sections=zstd

[MaskRay]

[ELF] Parallelize --compress-debug-sections=zlib parallelized --compress-debug-sections=zlib with an approach like a simplified pigz. ld.lld recently got zstd support (see https://maskray.me/blog/2022-09-09-zstd-compressed-debug-sections for context). I have a pending patch to parallelize --compress-debug-sections=zstd with zstd API: https://reviews.llvm.org/D133679

@Cyan4973 @terrelln it will be great to have your input on how to use the parallel zstd API :)

A test program (see z.cc in D133679's comment) using ZSTD_CCtx_setParameter(cctx, ZSTD_c_nbWorkers, th) + ZSTD_compressStream2 appears slower than the zstd cli (compiled from the same build). I do not know whether the additional performance gap is due to zstd cli's reading thread (which is difficult to leverage in the linker) or other feature I have missed.

zstd/contrib/pzstd appears to use an approach similar to pigz and https://reviews.llvm.org/D117853 . Does the approach leverage parallelism more than the ZSTD_c_nbWorkers API?

[OfekShochat]

Im not sure, that file hasnt changed since 2017, and ZSTD_compressStream2 was released on May 27, 2021 (https://zstd.docsforge.com/dev/api/ZSTD_compressStream2/)

[Cyan4973]

The method to trigger zstd multi-threaded compression seems correct to me.

But what is measured is time ./z (...).
Now, it's also a matter of what happens within z.cc.

[OfekShochat]

it does the typical stuff which I think is done also in zstdcli.c. it does load dynamic libraries, though from the benchmarks sys time is virtually the same I think

[Cyan4973]

I just tested z.cc, and confirm its poor performance level :

time ./z ~/dev/bench/enwik9 tmp.zst 1
./z ~/dev/bench/enwik9 tmp.zst 1  8.87s user 0.22s system 103% cpu 8.815 total
time ./z ~/dev/bench/enwik9 tmp.zst 2
./z ~/dev/bench/enwik9 tmp.zst 2  8.86s user 0.22s system 127% cpu 7.121 total
time ./z ~/dev/bench/enwik9 tmp.zst 4
./z ~/dev/bench/enwik9 tmp.zst 4  8.91s user 0.21s system 144% cpu 6.298 total

In contrast, the following modification y.c scales as expected :

time ./y ~/dev/bench/enwik9 tmp.zst 1
./y ~/dev/bench/enwik9 tmp.zst 1  3.55s user 0.34s system 100% cpu 3.879 total
time ./y ~/dev/bench/enwik9 tmp.zst 2
./y ~/dev/bench/enwik9 tmp.zst 2  3.56s user 0.32s system 214% cpu 1.807 total
time ./y ~/dev/bench/enwik9 tmp.zst 4
./y ~/dev/bench/enwik9 tmp.zst 4  3.63s user 0.34s system 416% cpu 0.953 total

y.c source code :

#include <stdio.h>   // fopen
#include <stdlib.h>  // malloc
#include <assert.h>
#include <zstd.h>

#define KB  *(1<<10)
#define BUF_SIZE (128 KB)

int main(int argc, char *argv[])
{
    assert(argc >= 3);
    FILE* const fin = fopen(argv[1], "rb");
    assert(fin != NULL);
    void* const inBuff = malloc(BUF_SIZE);
    assert(inBuff != NULL);

    FILE* const fout = fopen(argv[2], "wb");
    assert(fout != NULL);
    void* const outBuff = malloc(BUF_SIZE);
    assert(outBuff != NULL);

    int th = 0;
    if (argc > 3) th = atoi(argv[3]);

    ZSTD_CCtx* const cctx = ZSTD_createCCtx();
    assert(cctx != NULL);

    if (ZSTD_isError(ZSTD_CCtx_setParameter(cctx, ZSTD_c_nbWorkers, th))) return 2;

    do {
        size_t const r = fread(inBuff, 1, BUF_SIZE, fin);
        if (r==0) break;

        ZSTD_inBuffer zib = {inBuff, r, 0};
        while(zib.pos < zib.size) {
            ZSTD_outBuffer zob = {outBuff, BUF_SIZE, 0};
            size_t const more = ZSTD_compressStream2(cctx, &zob, &zib, ZSTD_e_continue);
            assert(!ZSTD_isError(more));
            size_t const w = fwrite(outBuff, 1, zob.pos, fout);
            assert(w == zob.pos);
        }
    } while(1);
    // no more input

    size_t more = 1;
    while (more) {
        ZSTD_inBuffer zib = {inBuff, 0, 0};
        ZSTD_outBuffer zob = {outBuff, BUF_SIZE, 0};
        more = ZSTD_compressStream2(cctx, &zob, &zib, ZSTD_e_end);
        assert(!ZSTD_isError(more));
        size_t const w = fwrite(outBuff, 1, zob.pos, fout);
        assert(w == zob.pos);
    }

    ZSTD_freeCCtx(cctx);
    free(outBuff);
    fclose(fout);
    free(inBuff);
    fclose(fin);
}

If I were to guess, delegating I/O to mmap is likely a source of troubles.

[OfekShochat]

Interesting, so the sys time with time says nothing. Are you saying the modification should work as expected with the modifications on the differential review?

[Cyan4973]

The library seems to scale appropriately.
The only action is to pass an argument ZSTD_c_nbWorkers, as implemented in https://reviews.llvm.org/D133679.
So yes, I would expect https://reviews.llvm.org/D133679 to produce the wanted speed boost.

[OfekShochat]

Thanks! I would consider this solved

[MaskRay]

Thanks! In z.cc, I deliberately use a std::vector to emulate the lld patch since avoiding a copy is difficult. The linker needs to know the output section size and there are multiple debug sections.

If I change z.cc to use fopen+fwrite, I get a similar performance with y.cc and the degree of ZSTD_c_nbWorkers parallelism is perfect. So the slowdown is due to the copy which takes nearly 400ms for my case (irrelevant to the number of threads).

Is there any suggestion for ZSTD_inBuffer and ZSTD_outBuffer sizes? contrib/pzstd appears to use 4 times the window size. For level=3 that is 4<<21=8MiB.

[Cyan4973]

Is there any suggestion for ZSTD_inBuffer and ZSTD_outBuffer sizes?

You can use ZSTD_CStreamInSize() and ZSTD_CStreamOutSize() to get recommended sizes for input and output buffers respectively :
https://github.com/facebook/zstd/blob/v1.5.2/lib/zstd.h#L719

These are soft recommendations. Streaming interface will work with any buffer size, really.
When providing buffer sizes equal or larger to recommendation, the streaming algorithm will be able to save a few memcpy() here and there, but memcpy() is generally fast enough that the expected outcome is only a "small" optimization.

[MaskRay]

Implemented in fa74144

Thanks for the ZSTD_CStreamInSize suggestion! Actually zstd examples/streaming_compression.c has an example.