zstd experimentations

Sun Sep 4 00:57:53 EDT 2016

The C extension is now working with Python 2.6 and 2.7. I've also fixed
some obvious memory leaks.

The "zstd" bookmark on my repo at
https://hg.mozilla.org/users/gszorc_mozilla.com/hg is now using the new
module.

The tipmost commit at the time I'm writing this contains a very hacky
`debugzstd` command for "benchmarking" various compression configurations.
It's worth noting that for most revlog data sets I've thrown at it, zstd
has better compression ratios than zlib level 6 (the default) at level 1
(or 3 at the worst) while performing compression several times faster.

Here are some (very unscientific since n=1) examples. Basically, the
uncompressed revlog entries from the changelog and manifest were compressed
via different formats. This kinda/sorta resembles what a server would do
when creating a changegroup.

changelog raw delta chunks on the hg repo:

zlib 6; Time: 0.4s; Speed: 27.5MB/s; Ratio: 0.38; Input: 10317988; Output:
3940156
Level 1; Time: 0.1s; Speed: 193.5MB/s; Ratio: 0.41; Input: 10317988;
Output: 4277954
Level 2; Time: 0.1s; Speed: 154.5MB/s; Ratio: 0.38; Input: 10317988;
Output: 3949151
Level 3; Time: 0.1s; Speed: 123.2MB/s; Ratio: 0.36; Input: 10317988;
Output: 3763515
Level 4; Time: 0.1s; Speed: 110.6MB/s; Ratio: 0.36; Input: 10317988;
Output: 3723455
Level 5; Time: 0.1s; Speed: 84.5MB/s; Ratio: 0.36; Input: 10317988; Output:
3703418
Level 6; Time: 0.2s; Speed: 66.9MB/s; Ratio: 0.35; Input: 10317988; Output:
3607777
Level 7; Time: 0.2s; Speed: 50.3MB/s; Ratio: 0.34; Input: 10317988; Output:
3549991
Level 8; Time: 0.3s; Speed: 35.4MB/s; Ratio: 0.34; Input: 10317988; Output:
3486817
Level 9; Time: 0.4s; Speed: 26.2MB/s; Ratio: 0.33; Input: 10317988; Output:
3446649
Level 10; Time: 0.5s; Speed: 22.6MB/s; Ratio: 0.33; Input: 10317988;
Output: 3432997
Level 11; Time: 0.5s; Speed: 21.6MB/s; Ratio: 0.33; Input: 10317988;
Output: 3414896
Level 12; Time: 0.6s; Speed: 16.0MB/s; Ratio: 0.33; Input: 10317988;
Output: 3389109
Level 13; Time: 0.9s; Speed: 12.1MB/s; Ratio: 0.33; Input: 10317988;
Output: 3366366
Level 14; Time: 1.4s; Speed: 7.6MB/s; Ratio: 0.32; Input: 10317988; Output:
3342622
Level 15; Time: 1.5s; Speed: 6.9MB/s; Ratio: 0.32; Input: 10317988; Output:
3301345
Level 16; Time: 1.8s; Speed: 5.9MB/s; Ratio: 0.32; Input: 10317988; Output:
3269435
Level 17; Time: 2.1s; Speed: 5.0MB/s; Ratio: 0.30; Input: 10317988; Output:
3126585
Level 18; Time: 2.9s; Speed: 3.6MB/s; Ratio: 0.30; Input: 10317988; Output:
3064639
Level 19; Time: 3.9s; Speed: 2.7MB/s; Ratio: 0.29; Input: 10317988; Output:
3011868
Level 20; Time: 4.0s; Speed: 2.6MB/s; Ratio: 0.29; Input: 10317988; Output:
3005903
Level 21; Time: 4.2s; Speed: 2.5MB/s; Ratio: 0.29; Input: 10317988; Output:
3002320
Level 22; Time: 4.4s; Speed: 2.3MB/s; Ratio: 0.29; Input: 10317988; Output:
2999782

manifest raw delta chunks on the hg repo:

zlib 6; Time: 1.1s; Speed: 41.3MB/s; Ratio: 0.34; Input: 46865097; Output:
16070541
Level 1; Time: 0.1s; Speed: 677.7MB/s; Ratio: 0.10; Input: 46865097;
Output: 4647782
Level 2; Time: 0.1s; Speed: 566.5MB/s; Ratio: 0.09; Input: 46865097;
Output: 4198007
Level 3; Time: 0.1s; Speed: 504.2MB/s; Ratio: 0.07; Input: 46865097;
Output: 3420796
Level 4; Time: 0.1s; Speed: 508.8MB/s; Ratio: 0.07; Input: 46865097;
Output: 3444775
Level 5; Time: 0.2s; Speed: 291.5MB/s; Ratio: 0.06; Input: 46865097;
Output: 2831290
Level 6; Time: 0.2s; Speed: 262.8MB/s; Ratio: 0.06; Input: 46865097;
Output: 2756099
Level 7; Time: 0.2s; Speed: 239.1MB/s; Ratio: 0.06; Input: 46865097;
Output: 2719771
Level 8; Time: 0.2s; Speed: 201.5MB/s; Ratio: 0.06; Input: 46865097;
Output: 2672378
Level 9; Time: 0.4s; Speed: 133.0MB/s; Ratio: 0.06; Input: 46865097;
Output: 2657551
Level 10; Time: 0.4s; Speed: 120.7MB/s; Ratio: 0.06; Input: 46865097;
Output: 2649282
Level 11; Time: 0.4s; Speed: 113.7MB/s; Ratio: 0.06; Input: 46865097;
Output: 2620218
Level 12; Time: 0.5s; Speed: 91.0MB/s; Ratio: 0.06; Input: 46865097;
Output: 2608377
Level 13; Time: 0.6s; Speed: 79.4MB/s; Ratio: 0.06; Input: 46865097;
Output: 2604652
Level 14; Time: 0.8s; Speed: 61.7MB/s; Ratio: 0.06; Input: 46865097;
Output: 2594825
Level 15; Time: 2.2s; Speed: 21.4MB/s; Ratio: 0.06; Input: 46865097;
Output: 2611654
Level 16; Time: 2.4s; Speed: 19.6MB/s; Ratio: 0.06; Input: 46865097;
Output: 2587735
Level 17; Time: 2.4s; Speed: 19.2MB/s; Ratio: 0.05; Input: 46865097;
Output: 2383974
Level 18; Time: 2.9s; Speed: 16.0MB/s; Ratio: 0.05; Input: 46865097;
Output: 2354903
Level 19; Time: 4.6s; Speed: 10.1MB/s; Ratio: 0.05; Input: 46865097;
Output: 2456306
Level 20; Time: 6.2s; Speed: 7.5MB/s; Ratio: 0.05; Input: 46865097; Output:
2445997
Level 21; Time: 10.2s; Speed: 4.6MB/s; Ratio: 0.05; Input: 46865097;
Output: 2422624
Level 22; Time: 15.7s; Speed: 3.0MB/s; Ratio: 0.05; Input: 46865097;
Output: 2415681

changelog raw delta chunks on the mozilla-unified repo:

zlib 6; Time: 4.3s; Speed: 43.6MB/s; Ratio: 0.27; Input: 186973077; Output:
49813643
Level 1; Time: 0.6s; Speed: 299.4MB/s; Ratio: 0.26; Input: 186973077;
Output: 48886045
Level 2; Time: 0.8s; Speed: 242.0MB/s; Ratio: 0.24; Input: 186973077;
Output: 44548226
Level 3; Time: 1.0s; Speed: 180.7MB/s; Ratio: 0.22; Input: 186973077;
Output: 41270743
Level 4; Time: 1.0s; Speed: 188.2MB/s; Ratio: 0.22; Input: 186973077;
Output: 40884311
Level 5; Time: 1.4s; Speed: 133.8MB/s; Ratio: 0.22; Input: 186973077;
Output: 40363804
Level 6; Time: 1.6s; Speed: 114.7MB/s; Ratio: 0.21; Input: 186973077;
Output: 38376645
Level 7; Time: 2.0s; Speed: 94.5MB/s; Ratio: 0.20; Input: 186973077;
Output: 37580770
Level 8; Time: 2.6s; Speed: 72.3MB/s; Ratio: 0.20; Input: 186973077;
Output: 36542917
Level 9; Time: 3.4s; Speed: 55.2MB/s; Ratio: 0.19; Input: 186973077;
Output: 35784615
Level 10; Time: 3.6s; Speed: 52.0MB/s; Ratio: 0.19; Input: 186973077;
Output: 35762714
Level 11; Time: 4.5s; Speed: 41.4MB/s; Ratio: 0.19; Input: 186973077;
Output: 34993427
Level 12; Time: 5.7s; Speed: 32.8MB/s; Ratio: 0.19; Input: 186973077;
Output: 34675491
Level 13; Time: 7.5s; Speed: 24.8MB/s; Ratio: 0.18; Input: 186973077;
Output: 34179005
Level 14; Time: 10.9s; Speed: 17.1MB/s; Ratio: 0.18; Input: 186973077;
Output: 33889445
Level 15; Time: 18.3s; Speed: 10.2MB/s; Ratio: 0.18; Input: 186973077;
Output: 33776317
Level 16; Time: 21.4s; Speed: 8.7MB/s; Ratio: 0.18; Input: 186973077;
Output: 32939701
Level 17; Time: 23.3s; Speed: 8.0MB/s; Ratio: 0.17; Input: 186973077;
Output: 32037493
Level 18; Time: 32.0s; Speed: 5.8MB/s; Ratio: 0.16; Input: 186973077;
Output: 30392784
Level 19; Time: 44.7s; Speed: 4.2MB/s; Ratio: 0.16; Input: 186973077;
Output: 29697484
Level 20; Time: 66.1s; Speed: 2.8MB/s; Ratio: 0.15; Input: 186973077;
Output: 28033006
Level 21; Time: 97.9s; Speed: 1.9MB/s; Ratio: 0.15; Input: 186973077;
Output: 27352393
Level 22; Time: 111.7s; Speed: 1.7MB/s; Ratio: 0.14; Input: 186973077;
Output: 27084000

manifest raw delta chunks on the mozilla-unified repo:

zlib 6; Time: 13.3s; Speed: 41.2MB/s; Ratio: 0.37; Input: 548522238;
Output: 200730288
Level 1; Time: 1.9s; Speed: 281.5MB/s; Ratio: 0.34; Input: 548522238;
Output: 187273109
Level 2; Time: 2.5s; Speed: 216.5MB/s; Ratio: 0.33; Input: 548522238;
Output: 180865804
Level 3; Time: 3.9s; Speed: 142.1MB/s; Ratio: 0.33; Input: 548522238;
Output: 182441417
Level 4; Time: 4.3s; Speed: 126.7MB/s; Ratio: 0.34; Input: 548522238;
Output: 185236126
Level 5; Time: 5.5s; Speed: 99.8MB/s; Ratio: 0.33; Input: 548522238;
Output: 181287658
Level 6; Time: 6.6s; Speed: 82.6MB/s; Ratio: 0.32; Input: 548522238;
Output: 175609442
Level 7; Time: 8.5s; Speed: 64.5MB/s; Ratio: 0.32; Input: 548522238;
Output: 174398004
Level 8; Time: 11.2s; Speed: 49.1MB/s; Ratio: 0.31; Input: 548522238;
Output: 172077381
Level 9; Time: 17.5s; Speed: 31.4MB/s; Ratio: 0.31; Input: 548522238;
Output: 170752760
Level 10; Time: 16.4s; Speed: 33.4MB/s; Ratio: 0.31; Input: 548522238;
Output: 170876255
Level 11; Time: 20.7s; Speed: 26.5MB/s; Ratio: 0.31; Input: 548522238;
Output: 167657180
Level 12; Time: 22.8s; Speed: 24.0MB/s; Ratio: 0.31; Input: 548522238;
Output: 167381137
Level 13; Time: 29.0s; Speed: 18.9MB/s; Ratio: 0.30; Input: 548522238;
Output: 166383934
Level 14; Time: 34.5s; Speed: 15.9MB/s; Ratio: 0.30; Input: 548522238;
Output: 166100586
Level 15; Time: 53.9s; Speed: 10.2MB/s; Ratio: 0.30; Input: 548522238;
Output: 166912474
Level 16; Time: 63.4s; Speed: 8.7MB/s; Ratio: 0.29; Input: 548522238;
Output: 157403141
Level 17; Time: 80.8s; Speed: 6.8MB/s; Ratio: 0.28; Input: 548522238;
Output: 152908629
Level 18; Time: 109.1s; Speed: 5.0MB/s; Ratio: 0.27; Input: 548522238;
Output: 150183444
Level 19; Time: 184.9s; Speed: 3.0MB/s; Ratio: 0.26; Input: 548522238;
Output: 144261854
Level 20; Time: 183.3s; Speed: 3.0MB/s; Ratio: 0.15; Input: 548522238;
Output: 82676648
Level 21; Time: 232.3s; Speed: 2.4MB/s; Ratio: 0.13; Input: 548522238;
Output: 73595576
Level 22; Time: 277.8s; Speed: 2.0MB/s; Ratio: 0.12; Input: 548522238;
Output: 67587632

So, uh, zstandard is 5+x faster for compression at similar or better
compression ratios. For server operators, it's basically free scaling.

On Sat, Sep 3, 2016 at 1:37 PM, Gregory Szorc <gregory.szorc at gmail.com>
wrote:

> https://github.com/indygreg/python-zstandard contains a proper, general
> use C extension. I've implemented most of the C API, including support for
> training and using dictionaries.
>
> It is very alpha. I'm sure there are memory leaks from me not using the
> Python C API properly (this is the first Python C extension I've written).
> I'm sure it will crash. It also only runs on Python 3.5 at the moment. I'll
> backport to 2.6 so we can experiment with this in Mercurial.
>
> If you want a Mercurial clone of the repo, grab it from
> https://hg.mozilla.org/users/gszorc_mozilla.com/python-zstandard.
>
> On Thu, Sep 1, 2016 at 1:49 PM, Bryan O'Sullivan <bos at serpentine.com>
> wrote:
>
>> It would be valuable to target a general-purpose package, if only because
>> the existing Python zstd bindings (somewhere on github) are not good.
>>
>> You're right that zstd is a big win over zlib in every way.
>>
>> On Thu, Sep 1, 2016 at 12:01 AM, Gregory Szorc <gregory.szorc at gmail.com>
>> wrote:
>>
>>> I got caught up in the zstd 1.0 release excitement and started writing a
>>> proper Python C extension for it (one that uses the streaming API and
>>> doesn't use custom framing like the existing python-zstd package does). The
>>> result of what I was able to hack together in a few hours is available at
>>> https://hg.mozilla.org/users/gszorc_mozilla.com/hg/rev/zstd (see the p1
>>> changeset for the C code).
>>>
>>> It compiles, but that's about it. The compress API basically no-ops (I
>>> need to plug in iterator foo). The decompress API segfaults and the API
>>> needs refined. It's also my first time writing a Python C extension, so I'm
>>> sure I'm doing several things wrong. And I know the style doesn't match
>>> Mercurial conventions. I'm not sure if I should strive for tailoring this
>>> to Mercurial's usage or try to release it as a standalone package...
>>>
>>> If anyone wants to take the code and run with it, go for it. I can stamp
>>> another license on the code if someone asks.
>>>
>>> I'd also like to invite a larger discussion around supporting zstd in
>>> the official Mercurial distribution. It seems like an all-around better
>>> compression format than zlib and supporting zstd seems like a relatively
>>> easy way to gain significant performance and size efficiency wins on many
>>> operations.
>>>
>>> _______________________________________________
>>> Mercurial-devel mailing list
>>> Mercurial-devel at mercurial-scm.org
>>> https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.mercurial-scm.org/pipermail/mercurial-devel/attachments/20160903/489a695d/attachment.html>