delta/go-git.git/src/compress/flate, branch dev.debug

compress/flate: use math/bits.Reverse8/16 instead of local implementation

2017-03-01T00:15:32+00:00

No measurable impact on performance (specifically, no degradation).
Reverse is used in Huffman en/de-coding. For completeness, here are
all the speed-related benchmark results:

name                             old time/op    new time/op    delta
Decode/Digits/Huffman/1e4-8         181µs ± 0%     178µs ± 1%   ~             (p=0.100 n=3+3)
Decode/Digits/Huffman/1e5-8        1.60ms ± 3%    1.56ms ± 3%   ~             (p=0.400 n=3+3)
Decode/Digits/Huffman/1e6-8        15.7ms ± 1%    15.3ms ± 3%   ~             (p=0.700 n=3+3)
Decode/Digits/Speed/1e4-8           179µs ± 0%     180µs ± 0%   ~             (p=0.200 n=3+3)
Decode/Digits/Speed/1e5-8          1.68ms ± 0%    1.66ms ± 3%   ~             (p=0.700 n=3+3)
Decode/Digits/Speed/1e6-8          16.6ms ± 2%    16.6ms ± 5%   ~             (p=0.700 n=3+3)
Decode/Digits/Default/1e4-8         179µs ± 1%     178µs ± 1%   ~             (p=0.700 n=3+3)
Decode/Digits/Default/1e5-8        1.62ms ± 3%    1.62ms ± 4%   ~             (p=1.000 n=3+3)
Decode/Digits/Default/1e6-8        16.0ms ± 2%    16.0ms ± 3%   ~             (p=1.000 n=3+3)
Decode/Digits/Compression/1e4-8     179µs ± 1%     179µs ± 0%   ~             (p=0.200 n=3+3)
Decode/Digits/Compression/1e5-8    1.62ms ± 2%    1.62ms ± 3%   ~             (p=1.000 n=3+3)
Decode/Digits/Compression/1e6-8    16.1ms ± 3%    16.0ms ± 3%   ~             (p=1.000 n=3+3)
Decode/Twain/Huffman/1e4-8          205µs ± 2%     207µs ± 1%   ~             (p=1.000 n=3+3)
Decode/Twain/Huffman/1e5-8         1.77ms ± 2%    1.77ms ± 4%   ~             (p=0.700 n=3+3)
Decode/Twain/Huffman/1e6-8         17.4ms ± 2%    17.4ms ± 3%   ~             (p=1.000 n=3+3)
Decode/Twain/Speed/1e4-8            186µs ± 1%     186µs ± 1%   ~             (p=0.400 n=3+3)
Decode/Twain/Speed/1e5-8           1.53ms ± 2%    1.52ms ± 0%   ~             (p=0.700 n=3+3)
Decode/Twain/Speed/1e6-8           14.9ms ± 1%    14.8ms ± 1%   ~             (p=1.000 n=3+3)
Decode/Twain/Default/1e4-8          176µs ± 1%     174µs ± 0%   ~             (p=0.200 n=3+3)
Decode/Twain/Default/1e5-8         1.30ms ± 2%    1.31ms ± 1%   ~             (p=0.700 n=3+3)
Decode/Twain/Default/1e6-8         12.6ms ± 3%    12.5ms ± 0%   ~             (p=0.700 n=3+3)
Decode/Twain/Compression/1e4-8      177µs ± 0%     174µs ± 1%   ~             (p=0.100 n=3+3)
Decode/Twain/Compression/1e5-8     1.30ms ± 1%    1.31ms ± 0%   ~             (p=0.700 n=3+3)
Decode/Twain/Compression/1e6-8     12.5ms ± 1%    12.5ms ± 1%   ~             (p=1.000 n=3+3)
Encode/Digits/Huffman/1e4-8        47.4µs ± 1%    46.5µs ± 0%   ~             (p=0.100 n=3+3)
Encode/Digits/Huffman/1e5-8         453µs ± 2%     446µs ± 1%   ~             (p=0.700 n=3+3)
Encode/Digits/Huffman/1e6-8        4.44ms ± 3%    4.39ms ± 0%   ~             (p=1.000 n=3+3)
Encode/Digits/Speed/1e4-8           190µs ± 4%     185µs ± 0%   ~             (p=0.100 n=3+3)
Encode/Digits/Speed/1e5-8          1.78ms ± 5%    1.75ms ± 1%   ~             (p=1.000 n=3+3)
Encode/Digits/Speed/1e6-8          17.9ms ± 7%    17.3ms ± 1%   ~             (p=0.400 n=3+3)
Encode/Digits/Default/1e4-8         366µs ± 1%     361µs ± 0%   ~             (p=0.200 n=3+3)
Encode/Digits/Default/1e5-8        5.58ms ± 5%    5.44ms ± 1%   ~             (p=0.400 n=3+3)
Encode/Digits/Default/1e6-8        59.0ms ± 3%    58.2ms ± 1%   ~             (p=0.700 n=3+3)
Encode/Digits/Compression/1e4-8     369µs ± 3%     362µs ± 0%   ~             (p=0.100 n=3+3)
Encode/Digits/Compression/1e5-8    5.50ms ± 2%    5.47ms ± 1%   ~             (p=1.000 n=3+3)
Encode/Digits/Compression/1e6-8    59.4ms ± 2%    58.5ms ± 1%   ~             (p=0.400 n=3+3)
Encode/Twain/Huffman/1e4-8         64.4µs ± 3%    64.7µs ± 1%   ~             (p=0.700 n=3+3)
Encode/Twain/Huffman/1e5-8          526µs ± 1%     526µs ± 2%   ~             (p=1.000 n=3+3)
Encode/Twain/Huffman/1e6-8         5.18ms ± 2%    5.17ms ± 1%   ~             (p=0.700 n=3+3)
Encode/Twain/Speed/1e4-8            206µs ± 1%     204µs ± 0%   ~             (p=0.100 n=3+3)
Encode/Twain/Speed/1e5-8           1.73ms ± 2%    1.70ms ± 0%   ~             (p=0.100 n=3+3)
Encode/Twain/Speed/1e6-8           16.7ms ± 0%    16.7ms ± 1%   ~             (p=1.000 n=3+3)
Encode/Twain/Default/1e4-8          423µs ± 3%     418µs ± 1%   ~             (p=1.000 n=3+3)
Encode/Twain/Default/1e5-8         6.34ms ± 4%    6.23ms ± 0%   ~             (p=1.000 n=3+3)
Encode/Twain/Default/1e6-8         68.0ms ± 3%    67.5ms ± 0%   ~             (p=0.700 n=3+3)
Encode/Twain/Compression/1e4-8      435µs ± 3%     424µs ± 0%   ~             (p=0.700 n=3+3)
Encode/Twain/Compression/1e5-8     7.01ms ± 1%    6.92ms ± 0%   ~             (p=0.100 n=3+3)
Encode/Twain/Compression/1e6-8     77.1ms ± 4%    75.5ms ± 1%   ~             (p=0.400 n=3+3)

name                             old speed      new speed      delta
Decode/Digits/Huffman/1e4-8      55.2MB/s ± 0%  56.2MB/s ± 1%   ~             (p=0.100 n=3+3)
Decode/Digits/Huffman/1e5-8      62.4MB/s ± 3%  64.1MB/s ± 3%   ~             (p=0.400 n=3+3)
Decode/Digits/Huffman/1e6-8      63.8MB/s ± 1%  65.3MB/s ± 3%   ~             (p=0.700 n=3+3)
Decode/Digits/Speed/1e4-8        55.8MB/s ± 0%  55.4MB/s ± 0%   ~             (p=0.200 n=3+3)
Decode/Digits/Speed/1e5-8        59.6MB/s ± 0%  60.3MB/s ± 3%   ~             (p=0.700 n=3+3)
Decode/Digits/Speed/1e6-8        60.1MB/s ± 2%  60.3MB/s ± 4%   ~             (p=0.700 n=3+3)
Decode/Digits/Default/1e4-8      55.8MB/s ± 1%  56.1MB/s ± 1%   ~             (p=0.700 n=3+3)
Decode/Digits/Default/1e5-8      61.8MB/s ± 3%  61.7MB/s ± 4%   ~             (p=1.000 n=3+3)
Decode/Digits/Default/1e6-8      62.4MB/s ± 2%  62.4MB/s ± 3%   ~             (p=1.000 n=3+3)
Decode/Digits/Compression/1e4-8  55.7MB/s ± 1%  56.0MB/s ± 0%   ~             (p=0.300 n=3+3)
Decode/Digits/Compression/1e5-8  61.7MB/s ± 2%  61.9MB/s ± 3%   ~             (p=1.000 n=3+3)
Decode/Digits/Compression/1e6-8  62.2MB/s ± 3%  62.6MB/s ± 3%   ~             (p=1.000 n=3+3)
Decode/Twain/Huffman/1e4-8       48.8MB/s ± 2%  48.4MB/s ± 1%   ~             (p=1.000 n=3+3)
Decode/Twain/Huffman/1e5-8       56.4MB/s ± 2%  56.6MB/s ± 4%   ~             (p=0.700 n=3+3)
Decode/Twain/Huffman/1e6-8       57.6MB/s ± 2%  57.5MB/s ± 3%   ~             (p=1.000 n=3+3)
Decode/Twain/Speed/1e4-8         53.7MB/s ± 1%  53.9MB/s ± 1%   ~             (p=0.400 n=3+3)
Decode/Twain/Speed/1e5-8         65.5MB/s ± 2%  65.6MB/s ± 0%   ~             (p=0.700 n=3+3)
Decode/Twain/Speed/1e6-8         66.9MB/s ± 1%  67.4MB/s ± 1%   ~             (p=1.000 n=3+3)
Decode/Twain/Default/1e4-8       56.9MB/s ± 1%  57.3MB/s ± 0%   ~             (p=0.200 n=3+3)
Decode/Twain/Default/1e5-8       77.2MB/s ± 2%  76.6MB/s ± 1%   ~             (p=0.700 n=3+3)
Decode/Twain/Default/1e6-8       79.3MB/s ± 3%  80.0MB/s ± 0%   ~             (p=0.700 n=3+3)
Decode/Twain/Compression/1e4-8   56.4MB/s ± 0%  57.5MB/s ± 1%   ~             (p=0.100 n=3+3)
Decode/Twain/Compression/1e5-8   76.8MB/s ± 1%  76.5MB/s ± 0%   ~             (p=0.700 n=3+3)
Decode/Twain/Compression/1e6-8   80.1MB/s ± 1%  79.8MB/s ± 1%   ~             (p=1.000 n=3+3)
Encode/Digits/Huffman/1e4-8       211MB/s ± 1%   215MB/s ± 0%   ~             (p=0.100 n=3+3)
Encode/Digits/Huffman/1e5-8       221MB/s ± 2%   224MB/s ± 1%   ~             (p=0.700 n=3+3)
Encode/Digits/Huffman/1e6-8       225MB/s ± 3%   228MB/s ± 0%   ~             (p=1.000 n=3+3)
Encode/Digits/Speed/1e4-8        52.8MB/s ± 4%  54.1MB/s ± 0%   ~             (p=0.100 n=3+3)
Encode/Digits/Speed/1e5-8        56.2MB/s ± 5%  57.0MB/s ± 1%   ~             (p=1.000 n=3+3)
Encode/Digits/Speed/1e6-8        56.0MB/s ± 6%  57.7MB/s ± 1%   ~             (p=0.400 n=3+3)
Encode/Digits/Default/1e4-8      27.3MB/s ± 1%  27.7MB/s ± 0%   ~             (p=0.200 n=3+3)
Encode/Digits/Default/1e5-8      17.9MB/s ± 4%  18.4MB/s ± 1%   ~             (p=0.400 n=3+3)
Encode/Digits/Default/1e6-8      17.0MB/s ± 3%  17.2MB/s ± 1%   ~             (p=0.500 n=3+3)
Encode/Digits/Compression/1e4-8  27.1MB/s ± 3%  27.6MB/s ± 0%   ~             (p=0.100 n=3+3)
Encode/Digits/Compression/1e5-8  18.2MB/s ± 2%  18.3MB/s ± 1%   ~             (p=1.000 n=3+3)
Encode/Digits/Compression/1e6-8  16.9MB/s ± 2%  17.1MB/s ± 1%   ~             (p=0.400 n=3+3)
Encode/Twain/Huffman/1e4-8        155MB/s ± 3%   155MB/s ± 1%   ~             (p=0.700 n=3+3)
Encode/Twain/Huffman/1e5-8        190MB/s ± 1%   190MB/s ± 2%   ~             (p=1.000 n=3+3)
Encode/Twain/Huffman/1e6-8        193MB/s ± 2%   193MB/s ± 1%   ~             (p=0.700 n=3+3)
Encode/Twain/Speed/1e4-8         48.5MB/s ± 1%  49.1MB/s ± 0%   ~             (p=0.100 n=3+3)
Encode/Twain/Speed/1e5-8         57.7MB/s ± 2%  59.0MB/s ± 0%   ~             (p=0.100 n=3+3)
Encode/Twain/Speed/1e6-8         59.7MB/s ± 0%  59.7MB/s ± 1%   ~             (p=1.000 n=3+3)
Encode/Twain/Default/1e4-8       23.6MB/s ± 3%  23.9MB/s ± 1%   ~             (p=1.000 n=3+3)
Encode/Twain/Default/1e5-8       15.8MB/s ± 4%  16.1MB/s ± 0%   ~             (p=1.000 n=3+3)
Encode/Twain/Default/1e6-8       14.7MB/s ± 3%  14.8MB/s ± 0%   ~             (p=0.700 n=3+3)
Encode/Twain/Compression/1e4-8   23.0MB/s ± 3%  23.6MB/s ± 0%   ~             (p=0.700 n=3+3)
Encode/Twain/Compression/1e5-8   14.3MB/s ± 1%  14.5MB/s ± 0%   ~             (p=0.100 n=3+3)
Encode/Twain/Compression/1e6-8   13.0MB/s ± 4%  13.2MB/s ± 1%   ~             (p=0.400 n=3+3)

Measured on a "quiet" (no browser running) 2.3 GHz Intel Core i7, running macOS 10.12.3.

See also #19279.

Change-Id: Ice759eb34eb37442b543957447c264e0aadc1fa9
Reviewed-on: https://go-review.googlesource.com/37460
Run-TryBot: Robert Griesemer 
TryBot-Result: Gobot Gobot 
Reviewed-by: Brad Fitzpatrick

compress/flate: avoid large stack growth in fillDeflate

2017-01-12T19:15:57+00:00

Ranging over an array causes the array to be copied over to the
stack, which cause large re-growths. Instead, we should iterate
over slices of the array.

Also, assigning a large struct literal uses the stack even
though the actual fields being populated are small in comparison
to the entirety of the struct (see #18636).

Fixing the stack growth does not alter CPU-time performance much
since the stack-growth and copying was such a tiny portion of the
compression work:

name                         old time/op    new time/op    delta
Encode/Digits/Default/1e4-8     332µs ± 1%     332µs ± 1%   ~     (p=0.796 n=10+10)
Encode/Digits/Default/1e5-8    5.07ms ± 2%    5.05ms ± 1%   ~       (p=0.815 n=9+8)
Encode/Digits/Default/1e6-8    53.7ms ± 1%    53.9ms ± 1%   ~     (p=0.075 n=10+10)
Encode/Twain/Default/1e4-8      380µs ± 1%     380µs ± 1%   ~     (p=0.684 n=10+10)
Encode/Twain/Default/1e5-8     5.79ms ± 2%    5.79ms ± 1%   ~      (p=0.497 n=9+10)
Encode/Twain/Default/1e6-8     61.5ms ± 1%    61.8ms ± 1%   ~     (p=0.247 n=10+10)

name                         old speed      new speed      delta
Encode/Digits/Default/1e4-8  30.1MB/s ± 1%  30.1MB/s ± 1%   ~     (p=0.753 n=10+10)
Encode/Digits/Default/1e5-8  19.7MB/s ± 2%  19.8MB/s ± 1%   ~       (p=0.795 n=9+8)
Encode/Digits/Default/1e6-8  18.6MB/s ± 1%  18.5MB/s ± 1%   ~     (p=0.072 n=10+10)
Encode/Twain/Default/1e4-8   26.3MB/s ± 1%  26.3MB/s ± 1%   ~     (p=0.616 n=10+10)
Encode/Twain/Default/1e5-8   17.3MB/s ± 2%  17.3MB/s ± 1%   ~      (p=0.484 n=9+10)
Encode/Twain/Default/1e6-8   16.3MB/s ± 1%  16.2MB/s ± 1%   ~     (p=0.238 n=10+10)

Updates #18636
Fixes #18625

Change-Id: I471b20339bf675f63dc56d38b3acdd824fe23328
Reviewed-on: https://go-review.googlesource.com/35122
Reviewed-by: Brad Fitzpatrick 
Run-TryBot: Joe Tsai 
TryBot-Result: Gobot Gobot

compress/flate: add examples

2016-11-12T18:42:35+00:00

Updates #16360

Change-Id: I66ff23e0501363f58fe891d5e95806422071f93b
Reviewed-on: https://go-review.googlesource.com/30162
Run-TryBot: Brad Fitzpatrick 
TryBot-Result: Gobot Gobot 
Reviewed-by: Brad Fitzpatrick

all: sprinkle t.Parallel on some slow tests

2016-11-04T16:56:57+00:00

I used the slowtests.go tool as described in
https://golang.org/cl/32684 on packages that stood out.

go test -short std drops from ~56 to ~52 seconds.

This isn't a huge win, but it was mostly an exercise.

Updates #17751

Change-Id: I9f3402e36a038d71e662d06ce2c1d52f6c4b674d
Reviewed-on: https://go-review.googlesource.com/32751
Run-TryBot: Brad Fitzpatrick 
TryBot-Result: Gobot Gobot 
Reviewed-by: Ian Lance Taylor

compress/flate: tighten the BestSpeed max match offset bound.

2016-10-30T22:52:14+00:00

Previously, we were off by one.

Also fix a comment typo.

Change-Id: Ib94d23acc56d5fccd44144f71655481f98803ac8
Reviewed-on: https://go-review.googlesource.com/32149
Reviewed-by: Joe Tsai 
Run-TryBot: Joe Tsai 
TryBot-Result: Gobot Gobot

compress/flate: make compression level 0 consistent

2016-10-27T00:58:30+00:00

Tests for determinism was not working as intended since io.Copybuffer
uses the io.WriterTo if available.

This exposed that level 0 (no compression) changed output
based on the number of writes and buffers given to the
writer.

Previously, Write would emit a new raw block (BTYPE=00) for
every non-empty call to Write.

This CL fixes it such that a raw block is only emitted upon
the following conditions:
 	* A full window is obtained (every 65535 bytes)
 	* Flush is called
 	* Close is called

Change-Id: I807f866d97e2db7820f11febab30a96266a6cbf1
Reviewed-on: https://go-review.googlesource.com/31174
Run-TryBot: Joe Tsai 
TryBot-Result: Gobot Gobot 
Reviewed-by: Joe Tsai

compress/flate: level 1 (best speed) match across blocks

2016-10-27T00:50:06+00:00

This change makes deflate level 1 (best speed) match across
block boundaries. This comes at a small speed penalty,
but improves compression on almost all output.

Sample numbers on various content types:

enwik9:            391052014 ->  382578469 bytes, 77.59 -> 74.28 MB/s
adresser.001:       57269799 ->   47756095 bytes, 287.84 -> 357.86 MB/s
10gb:             5233055166 -> 5198328382 bytes, 105.85 -> 96.99 MB/s
rawstudio-mint14: 3972329211 -> 3927423364 bytes, 100.07 -> 94.22 MB/s
sites:             165556800 ->  163178702 bytes, 72.31 -> 70.15 MB/s
objectfiles:       115962472 ->  111649524 bytes, 132.60 -> 128.05 MB/s
sharnd.out:        200015283 ->  200015283 bytes, 221.50 -> 218.83 MB/s

Change-Id: I62a139e5c06976e803439a4268acede5139b8cfc
Reviewed-on: https://go-review.googlesource.com/31640
Reviewed-by: Joe Tsai 
Reviewed-by: Nigel Tao

compress/flate: use correct table for size estimation

2016-10-17T09:00:41+00:00

The incorrect table was used for estimating output size.
This can give suboptimal selection of entropy encoder in rare cases.

Change-Id: I8b358200f2d1f9a3f9b79a44269d7be704e1d2d9
Reviewed-on: https://go-review.googlesource.com/31172
Reviewed-by: Brad Fitzpatrick 
Run-TryBot: Brad Fitzpatrick 
TryBot-Result: Gobot Gobot

compress/flate: clarify the behavior of Writer.Flush

2016-09-04T03:09:08+00:00

Fixes #16068

Change-Id: I04e80a181c0b7356996f7a1158ea4895ff9e1e39
Reviewed-on: https://go-review.googlesource.com/28477
Run-TryBot: Joe Tsai 
TryBot-Result: Gobot Gobot 
Reviewed-by: Brad Fitzpatrick

compress/flate: always return uncompressed data in the event of error

2016-08-31T01:12:02+00:00

In the event of an unexpected error, we should always flush available
decompressed data to the user.

Fixes #16924

Change-Id: I0bc0824c3201f3149e84e6a26e3dbcba72a1aae5
Reviewed-on: https://go-review.googlesource.com/28216
Run-TryBot: Joe Tsai 
TryBot-Result: Gobot Gobot 
Reviewed-by: Matthew Dempsky