util: implement zstd compression engine Now that zstd is vendored and being built (in some configurations), we can implement a compression engine for zstd! The zstd engine is a little different from existing engines. Because it may not always be present, we have to defer load the module in case importing it fails. We facilitate this via a cached property that holds a reference to the module or None. The "available" method is implemented to reflect reality. The zstd engine declares its ability to handle bundles using the "zstd" human name and the "ZS" internal name. The latter was chosen because internal names are 2 characters (by only convention I think) and "ZS" seems reasonable. The engine, like others, supports specifying the compression level. However, there are no consumers of this API that yet pass in that argument. I have plans to change that, so stay tuned. Since all we need to do to support bundle generation with a new compression engine is implement and register the compression engine, bundle generation with zstd "just works!" Tests demonstrating this have been added. How does performance of zstd for bundle generation compare? On the mozilla-unified repo, `hg bundle --all -t <engine>-v2` yields the following on my i7-6700K on Linux: engine CPU time bundle size vs orig size throughput none 97.0s 4,054,405,584 100.0% 41.8 MB/s bzip2 (l=9) 393.6s 975,343,098 24.0% 10.3 MB/s gzip (l=6) 184.0s 1,140,533,074 28.1% 22.0 MB/s zstd (l=1) 108.2s 1,119,434,718 27.6% 37.5 MB/s zstd (l=2) 111.3s 1,078,328,002 26.6% 36.4 MB/s zstd (l=3) 113.7s 1,011,823,727 25.0% 35.7 MB/s zstd (l=4) 116.0s 1,008,965,888 24.9% 35.0 MB/s zstd (l=5) 121.0s 977,203,148 24.1% 33.5 MB/s zstd (l=6) 131.7s 927,360,198 22.9% 30.8 MB/s zstd (l=7) 139.0s 912,808,505 22.5% 29.2 MB/s zstd (l=12) 198.1s 854,527,714 21.1% 20.5 MB/s zstd (l=18) 681.6s 789,750,690 19.5% 5.9 MB/s On compression, zstd for bundle generation delivers: * better compression than gzip with significantly less CPU utilization * better than bzip2 compression ratios while still being significantly faster than gzip * ability to aggressively tune compression level to achieve significantly smaller bundles That last point is important. With clone bundles, a server can pre-generate a bundle file, upload it to a static file server, and redirect clients to transparently download it during clone. The server could choose to produce a zstd bundle with the highest compression settings possible. This would take a very long time - a magnitude longer than a typical zstd bundle generation - but the result would be hundreds of megabytes smaller! For the clone volume we do at Mozilla, this could translate to petabytes of bandwidth savings per year and faster clones (due to smaller transfer size). I don't have detailed numbers to report on decompression. However, zstd decompression is fast: >1 GB/s output throughput on this machine, even through the Python bindings. And it can do that regardless of the compression level of the input. By the time you have enough data to worry about overhead of decompression, you have plenty of other things to worry about performance wise. zstd is wins all around. I can't wait to implement support for it on the wire protocol and in revlogs.

     1

     2

  $ cat << EOF >> $HGRCPATH

     3

  > [format]

     4

  > usegeneraldelta=yes

     5

  > EOF

     6

     7

bundle w/o type option

     8

     9

  $ hg init t1

    10

  $ hg init t2

    11

  $ cd t1

    12

  $ echo blablablablabla > file.txt

    13

  $ hg ci -Ama

    14

  adding file.txt

    15

  $ hg log | grep summary

    16

  summary:     a

    17

  $ hg bundle ../b1 ../t2

    18

  searching for changes

    19

  1 changesets found

    20

    21

  $ cd ../t2

    22

  $ hg pull ../b1

    23

  pulling from ../b1

    24

  requesting all changes

    25

  adding changesets

    26

  adding manifests

    27

  adding file changes

    28

  added 1 changesets with 1 changes to 1 files

    29

  (run 'hg update' to get a working copy)

    30

  $ hg up

    31

  1 files updated, 0 files merged, 0 files removed, 0 files unresolved

    32

  $ hg log | grep summary

    33

  summary:     a

    34

  $ cd ..

    35

    36

test bundle types

    37

    38

  $ testbundle() {

    39

  >   echo % test bundle type $1

    40

  >   hg init t$1

    41

  >   cd t1

    42

  >   hg bundle -t $1 ../b$1 ../t$1

    43

  >   f -q -B6 -D ../b$1; echo

    44

  >   cd ../t$1

    45

  >   hg debugbundle ../b$1

    46

  >   hg debugbundle --spec ../b$1

    47

  >   echo

    48

  >   cd ..

    49

  > }

    50

    51

  $ for t in "None" "bzip2" "gzip" "none-v2" "v2" "v1" "gzip-v1"; do

    52

  >   testbundle $t

    53

  > done

    54

  % test bundle type None

    55

  searching for changes

    56

  1 changesets found

    57

  HG20\x00\x00 (esc)

    58

  Stream params: {}

    59

  changegroup -- "sortdict([('version', '02'), ('nbchanges', '1')])"

    60

      c35a0f9217e65d1fdb90c936ffa7dbe679f83ddf

    61

  none-v2

    62

    63

  % test bundle type bzip2

    64

  searching for changes

    65

  1 changesets found

    66

  HG20\x00\x00 (esc)

    67

  Stream params: sortdict([('Compression', 'BZ')])

    68

  changegroup -- "sortdict([('version', '02'), ('nbchanges', '1')])"

    69

      c35a0f9217e65d1fdb90c936ffa7dbe679f83ddf

    70

  bzip2-v2

    71

    72

  % test bundle type gzip

    73

  searching for changes

    74

  1 changesets found

    75

  HG20\x00\x00 (esc)

    76

  Stream params: sortdict([('Compression', 'GZ')])

    77

  changegroup -- "sortdict([('version', '02'), ('nbchanges', '1')])"

    78

      c35a0f9217e65d1fdb90c936ffa7dbe679f83ddf

    79

  gzip-v2

    80

    81

  % test bundle type none-v2

    82

  searching for changes

    83

  1 changesets found

    84

  HG20\x00\x00 (esc)

    85

  Stream params: {}

    86

  changegroup -- "sortdict([('version', '02'), ('nbchanges', '1')])"

    87

      c35a0f9217e65d1fdb90c936ffa7dbe679f83ddf

    88

  none-v2

    89

    90

  % test bundle type v2

    91

  searching for changes

    92

  1 changesets found

    93

  HG20\x00\x00 (esc)

    94

  Stream params: sortdict([('Compression', 'BZ')])

    95

  changegroup -- "sortdict([('version', '02'), ('nbchanges', '1')])"

    96

      c35a0f9217e65d1fdb90c936ffa7dbe679f83ddf

    97

  bzip2-v2

    98

    99

  % test bundle type v1

   100

  searching for changes

   101

  1 changesets found

   102

  HG10BZ

   103

  c35a0f9217e65d1fdb90c936ffa7dbe679f83ddf

   104

  bzip2-v1

   105

   106

  % test bundle type gzip-v1

   107

  searching for changes

   108

  1 changesets found

   109

  HG10GZ

   110

  c35a0f9217e65d1fdb90c936ffa7dbe679f83ddf

   111

  gzip-v1

   112

   113

#if zstd

   114

   115

  $ for t in "zstd" "zstd-v2"; do

   116

  >   testbundle $t

   117

  > done

   118

  % test bundle type zstd

   119

  searching for changes

   120

  1 changesets found

   121

  HG20\x00\x00 (esc)

   122

  Stream params: sortdict([('Compression', 'ZS')])

   123

  changegroup -- "sortdict([('version', '02'), ('nbchanges', '1')])"

   124

      c35a0f9217e65d1fdb90c936ffa7dbe679f83ddf

   125

  zstd-v2

   126

   127

  % test bundle type zstd-v2

   128

  searching for changes

   129

  1 changesets found

   130

  HG20\x00\x00 (esc)

   131

  Stream params: sortdict([('Compression', 'ZS')])

   132

  changegroup -- "sortdict([('version', '02'), ('nbchanges', '1')])"

   133

      c35a0f9217e65d1fdb90c936ffa7dbe679f83ddf

   134

  zstd-v2

   135

   136

#else

   137

   138

zstd is a valid engine but isn't available

   139

   140

  $ hg -R t1 bundle -a -t zstd irrelevant.hg

   141

  abort: compression engine zstd could not be loaded

   142

  [255]

   143

   144

#endif

   145

   146

test garbage file

   147

   148

  $ echo garbage > bgarbage

   149

  $ hg init tgarbage

   150

  $ cd tgarbage

   151

  $ hg pull ../bgarbage

   152

  pulling from ../bgarbage

   153

  abort: ../bgarbage: not a Mercurial bundle

   154

  [255]

   155

  $ cd ..

   156

   157

test invalid bundle type

   158

   159

  $ cd t1

   160

  $ hg bundle -a -t garbage ../bgarbage

   161

  abort: garbage is not a recognized bundle specification

   162

  (see 'hg help bundle' for supported values for --type)

   163

  [255]

   164

  $ cd ..