search

dart-lang / sdk

The Dart SDK, including the VM, JS and Wasm compilers, analysis, core libraries, and more.
https://dart.dev
BSD 3-Clause "New" or "Revised" License
10.31k stars 1.59k forks source link

Dart should support more compression schemes #41048

Open jensjoha opened 4 years ago

jensjoha commented 4 years ago

Dart supports gzip out of the box (e.g. GZIP.encoder), and it is for instance used in flutter to speedup the transfer to device (https://github.com/flutter/flutter/blob/9666f697fb241db3d7aeb9bd9bf2b965e9c916e8/packages/flutter_tools/lib/src/devfs.dart#L50).

I've experimented with disabling it in flutter, and checking the compression level of a (big, 13.5 MB) partial dill file. I found the following (sending it to an emulator).

As-is (i.e. with gzip compression) it takes ~475 ms to send it to the device.

Disabling compression yields (here I ran it 5 times)

[ +272 ms] DevFS: Sync finished
[ +226 ms] DevFS: Sync finished
[ +244 ms] DevFS: Sync finished
[ +169 ms] DevFS: Sync finished
[ +285 ms] DevFS: Sync finished

so we have a transfer speed of between 47 and 80 MB/s (between 12.5 ms and 21 ms per MB) (on emulator, on a real device, e.g. connected via wifi or usb2, that could certainly be slower).

I also timed the compression and the input size and output size:

Total uncompressed: 14157664
Total compressed: 4219340 (in 477 ms)

Total uncompressed: 14157704
Total compressed: 4219420 (in 480 ms)

Total uncompressed: 14157624
Total compressed: 4219445 (in 460 ms)

Total uncompressed: 14157624
Total compressed: 4219445 (in 472 ms)

Total uncompressed: 14157704
Total compressed: 4219420 (in 460 ms)

Total uncompressed: 14157664
Total compressed: 4219340 (in 467 ms)

(notice that the sizes aren't all exactly the same as I did this by performing an edit in the program). The compression ratio ~0.298 (i.e. good) and the compression speed: ~30MB/s (i.e. slow).

Assuming that we can transfer a block while compression the next one and that compressing the first block and decompressing the last block it negligible time-wise, the time is going to be something like max(compression time, transfer time, decompression time).

For the 13.5 MB dill used in this test: Assuming transfer of about 50 MB/s, for uncompressed data, this gives us max(0, 13.5/50, 0) = 0.27 seconds.

Assuming transfer of about 50 MB/s and compression rate of 0.298 and compression speed of 30MB/s, (lets assume decompression is free) this gives us max(13.5/30, 13.5*0.298/50, 0) = 0.45 seconds.

This seems consistent with the numbers from above.

Now lets imagine other compression schemes and different transfer speeds.

Running lzbench on it to get an idea of other compression schemes available gives

$ ./lzbench the.dill 
lzbench 1.8 (64-bit Linux)   Assembled by P.Skibinski
Compressor name         Compress. Decompress. Compr. size  Ratio Filename
memcpy                  10051 MB/s 10648 MB/s    14157664 100.00 the.dill
density 0.14.2 -1        1282 MB/s  1929 MB/s     9288692  65.61 the.dill
density 0.14.2 -2         712 MB/s  1218 MB/s     7557722  53.38 the.dill
density 0.14.2 -3         368 MB/s   401 MB/s     6760712  47.75 the.dill
fastlz 0.1 -1             359 MB/s   684 MB/s     6461009  45.64 the.dill
fastlz 0.1 -2             361 MB/s   680 MB/s     6181122  43.66 the.dill
lizard 1.0 -10            559 MB/s  2687 MB/s     6320058  44.64 the.dill
lizard 1.0 -11            363 MB/s  2570 MB/s     5965981  42.14 the.dill
lizard 1.0 -12            167 MB/s  2689 MB/s     5467744  38.62 the.dill
lizard 1.0 -13            109 MB/s  2704 MB/s     5337523  37.70 the.dill
lizard 1.0 -14            102 MB/s  2715 MB/s     5260391  37.16 the.dill
lz4 1.9.2                 663 MB/s  4308 MB/s     6300842  44.50 the.dill
lz4fast 1.9.2 -3          746 MB/s  4428 MB/s     6764004  47.78 the.dill
lz4fast 1.9.2 -17        1125 MB/s  4890 MB/s     8787036  62.07 the.dill
lzf 3.6 -0                382 MB/s   740 MB/s     6655648  47.01 the.dill
lzf 3.6 -1                386 MB/s   762 MB/s     6361802  44.94 the.dill
lzfse 2017-03-08           62 MB/s   811 MB/s     4227491  29.86 the.dill
lzjb 2010                 328 MB/s   391 MB/s     7849259  55.44 the.dill
lzo1b 2.10 -1             252 MB/s   719 MB/s     6079356  42.94 the.dill
lzo1c 2.10 -1             278 MB/s   746 MB/s     6241321  44.08 the.dill
lzo1f 2.10 -1             261 MB/s   678 MB/s     6168674  43.57 the.dill
lzo1x 2.10 -1             587 MB/s   743 MB/s     6264339  44.25 the.dill
lzo1y 2.10 -1             589 MB/s   734 MB/s     6233224  44.03 the.dill
lzrw 15-Jul-1991 -1       306 MB/s   610 MB/s     6949480  49.09 the.dill
lzrw 15-Jul-1991 -3       342 MB/s   643 MB/s     6405875  45.25 the.dill
lzrw 15-Jul-1991 -4       351 MB/s   585 MB/s     6204239  43.82 the.dill
lzrw 15-Jul-1991 -5       166 MB/s   609 MB/s     5705646  40.30 the.dill
lzsse4fast 2019-04-18     292 MB/s  3811 MB/s     5746848  40.59 the.dill
lzsse8fast 2019-04-18     283 MB/s  3901 MB/s     5742520  40.56 the.dill
lzvn 2017-03-08            76 MB/s  1065 MB/s     4829278  34.11 the.dill
pithy 2011-12-24 -0       594 MB/s  1994 MB/s     6355593  44.89 the.dill
pithy 2011-12-24 -3       568 MB/s  1931 MB/s     6017942  42.51 the.dill
pithy 2011-12-24 -6       545 MB/s  2044 MB/s     5788847  40.89 the.dill
pithy 2011-12-24 -9       469 MB/s  2018 MB/s     5648935  39.90 the.dill
quicklz 1.5.0 -1          522 MB/s   727 MB/s     5740553  40.55 the.dill
quicklz 1.5.0 -2          277 MB/s   715 MB/s     5259971  37.15 the.dill
shrinker 0.1              380 MB/s  1594 MB/s     5737880  40.53 the.dill
snappy 2019-09-30         493 MB/s  1542 MB/s     6369801  44.99 the.dill
tornado 0.6a -1           402 MB/s   491 MB/s     6494793  45.87 the.dill
tornado 0.6a -2           327 MB/s   476 MB/s     5559364  39.27 the.dill
tornado 0.6a -3           221 MB/s   317 MB/s     4468013  31.56 the.dill
zstd 1.4.3 -1             458 MB/s  1244 MB/s     4558421  32.20 the.dill
zstd 1.4.3 -2             404 MB/s  1184 MB/s     4388838  31.00 the.dill
zstd 1.4.3 -3             260 MB/s  1166 MB/s     4203005  29.69 the.dill
zstd 1.4.3 -4             215 MB/s  1138 MB/s     4180803  29.53 the.dill
zstd 1.4.3 -5             125 MB/s  1104 MB/s     4079499  28.81 the.dill
done... (cIters=1 dIters=1 cTime=1.0 dTime=2.0 chunkSize=1706MB cSpeed=0MB)

Caveats: This was run on the partial dill file which contains lots of text and will compress differently than for instance images would. In general I would assume that images (and other resources) does not compress very well as they are already compressed and that this would thus give a good indicator of real-world-performance for this use-case. This could be wrong though. In the below I also assume that all compression schemes can operate in a "streaming" fashion so the discussed formula (max(compression time, transfer time, decompression time)) holds.

Using the calculation from above, with a transfer speed of 50MB/s it gives me this (I've semi-arbitrarily removed most compression schemes here):

Compressor name Compress. Ratio Time
zstd 1.4.3 -4 215 29.53 0.079731
zstd 1.4.3 -3 260 29.69 0.080163
zstd 1.4.3 -2 404 31 0.0837
zstd 1.4.3 -5 125 28.81 0.108
lz4 1.9.2 663 44.5 0.12015
snappy 2019-09-30 493 44.99 0.121473
memcpy (aka uncompresed) 10051 100 0.27
gzip in dart 30 29.8 0.45

Conclusions: At this transfer speed, doing gzip is the worst thing you can do. Also, for this input, zstd compresses better than gzip and does so a lot faster, so will always be better (under the maybe naive assumptions in this text). Using zstd 1.4.3 -4 instead of gzip would make the transfer more than 5 times faster. Using snappy 2019-09-30 would make it more than 3 times faster.

Lets try with 30MB/s (I expect this to be somewhat realistic via USB2):

Compressor name Compress. Ratio Time
zstd 1.4.3 -5 125 28.81 0.129645
zstd 1.4.3 -4 215 29.53 0.132885
zstd 1.4.3 -3 260 29.69 0.133605
zstd 1.4.3 -2 404 31 0.1395
lz4 1.9.2 663 44.5 0.20025
snappy 2019-09-30 493 44.99 0.202455
memcpy (aka uncompresed) 10051 100 0.45
gzip in dart 30 29.8 0.45

Basically the same conclusion as before. Using zstd 1.4.3 -5 (or -4) instead of gzip would make the transfer more than 3 times faster. snappy 2019-09-30 more than 2 times faster.

Lets try with 5MB/s (I expect this to be somewhat realistic via semi-bad wifi):

Compressor name Compress. Ratio Time
zstd 1.4.3 -5 125 28.81 0.77787
zstd 1.4.3 -4 215 29.53 0.79731
zstd 1.4.3 -3 260 29.69 0.80163
gzip in dart 30 29.8 0.8046
zstd 1.4.3 -2 404 31 0.837
lz4 1.9.2 663 44.5 1.2015
snappy 2019-09-30 493 44.99 1.21473
memcpy (aka uncompresed) 10051 100 2.7

Here gzip gives value for the money compared to not going any compression at all, but zstd is still faster.

Generally I would assume that a developer uses a phone connected via usb (or an emulator) in which case picking another compressor would speed things up a good deal, so: Can we make Dart support more compression schemes, please?

/cc @mraleph @a-siva @aam

jensjoha commented 4 years ago

Update: Here are tables with using gzip in dart with a compression level of 1 instead, which makes the issue "less pressing".

Transfer speed of 50MB/s:

Compressor name Compress. Ratio Time
zstd 1.4.3 -4 215 29.53 0.079731
zstd 1.4.3 -3 260 29.69 0.080163
zstd 1.4.3 -2 404 31 0.0837
zstd 1.4.3 -5 125 28.81 0.108
gzip -1 in dart 112.5 33.95 0.12
lz4 1.9.2 663 44.5 0.12015
snappy 2019-09-30 493 44.99 0.121473
memcpy (aka uncompresed) 10051 100 0.27
gzip in dart 30 29.8 0.45

Transfer speed of 30MB/s:

Compressor name Compress. Ratio Time
zstd 1.4.3 -5 125 28.81 0.129645
zstd 1.4.3 -4 215 29.53 0.132885
zstd 1.4.3 -3 260 29.69 0.133605
zstd 1.4.3 -2 404 31 0.1395
gzip -1 in dart 112.5 33.95 0.152775
lz4 1.9.2 663 44.5 0.20025
snappy 2019-09-30 493 44.99 0.202455
memcpy (aka uncompresed) 10051 100 0.45
gzip in dart 30 29.8 0.45

Transfer speed of 5MB/s:

Compressor name Compress. Ratio Time
zstd 1.4.3 -5 125 28.81 0.77787
zstd 1.4.3 -4 215 29.53 0.79731
zstd 1.4.3 -3 260 29.69 0.80163
gzip in dart 30 29.8 0.8046
zstd 1.4.3 -2 404 31 0.837
gzip -1 in dart 112.5 33.95 0.91665
lz4 1.9.2 663 44.5 1.2015
snappy 2019-09-30 493 44.99 1.21473
memcpy (aka uncompresed) 10051 100 2.7

I'll probably try to patch up flutter and the vm and test that out to get more "real world numbers".

rmacnak-google commented 3 years ago

zstd might be a good one to add. It's been registered as a possible content-encoding for HTTP, and Chrome might implement it. If we add it to dart:io, it would at least find use by HttpClient.

Reprevise commented 1 year ago

Seems like Chrome is going ahead with zstd, and Dart should totally add it. I've opened an issue (#53906) for Brotli as well. Both would find use in HttpClient.

parlough commented 1 year ago

It would be nice to support more compression algorithms and zstd and Brotli seem to both be good choices.

There is the concern that it would increase the binary size of apps not insignificantly, particularly due to their dictionary sizes. However, standardized Brotli support would allow Flutter apps to use WOFF2 fonts, which might make up for some of the increased size?