compress/flate: size optimization of final deflate block (btype 0 -> btype 1)

[ivantsepp]

Similar to #40830 and #39095, I was curious why golang's deflate output didn't match PHP's gzdeflate. I found that the implementation will always add a final empty block of type 0 (uncompressed).

go/src/compress/flate/deflate.go

Lines 639 to 645 in 0c14000

	if d.w.writeStoredHeader(0, true); d.w.err != nil {
	return d.w.err
	}
	d.w.flush()
	if d.w.err != nil {
	return d.w.err
	}

I feel like this could be optimized to save some bytes in the output. For example, one approach could be to use a final empty block of type 1 (fixed huffman coding) instead.

The empty block of type 0 ends in 0x0000FFFF for the length 0 while the empty block of type 1 ends in 0x00, the fixed code for EOB marker. This means we could save 3 or 4 bytes on the output.

Here's a diff to demonstrate that approach:

diff --git a/src/compress/flate/deflate.go b/src/compress/flate/deflate.go
index 6697f3a791..3b995e9f45 100644
--- a/src/compress/flate/deflate.go
+++ b/src/compress/flate/deflate.go
@@ -636,9 +636,10 @@ func (d *compressor) close() error {
        if d.err != nil {
                return d.err
        }
-       if d.w.writeStoredHeader(0, true); d.w.err != nil {
+       if d.w.writeFixedHeader(true); d.w.err != nil {
                return d.w.err
        }
+       d.w.writeCode(fixedLiteralEncoding.codes[endBlockMarker])
        d.w.flush()
        if d.w.err != nil {
                return d.w.err
diff --git a/src/compress/flate/deflate_test.go b/src/compress/flate/deflate_test.go
index 3610c7bf87..d117dba774 100644
--- a/src/compress/flate/deflate_test.go
+++ b/src/compress/flate/deflate_test.go
@@ -35,24 +35,24 @@ type reverseBitsTest struct {
 }

 var deflateTests = []*deflateTest{
-       {[]byte{}, 0, []byte{1, 0, 0, 255, 255}},
-       {[]byte{0x11}, -1, []byte{18, 4, 4, 0, 0, 255, 255}},
-       {[]byte{0x11}, DefaultCompression, []byte{18, 4, 4, 0, 0, 255, 255}},
-       {[]byte{0x11}, 4, []byte{18, 4, 4, 0, 0, 255, 255}},
+       {[]byte{}, 0, []byte{3, 0}},
+       {[]byte{0x11}, -1, []byte{18, 4, 12, 0}},
+       {[]byte{0x11}, DefaultCompression, []byte{18, 4, 12, 0}},
+       {[]byte{0x11}, 4, []byte{18, 4, 12, 0}},

-       {[]byte{0x11}, 0, []byte{0, 1, 0, 254, 255, 17, 1, 0, 0, 255, 255}},
-       {[]byte{0x11, 0x12}, 0, []byte{0, 2, 0, 253, 255, 17, 18, 1, 0, 0, 255, 255}},
+       {[]byte{0x11}, 0, []byte{0, 1, 0, 254, 255, 17, 3, 0}},
+       {[]byte{0x11, 0x12}, 0, []byte{0, 2, 0, 253, 255, 17, 18, 3, 0}},
        {[]byte{0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11}, 0,
-               []byte{0, 8, 0, 247, 255, 17, 17, 17, 17, 17, 17, 17, 17, 1, 0, 0, 255, 255},
+               []byte{0, 8, 0, 247, 255, 17, 17, 17, 17, 17, 17, 17, 17, 3, 0},
        },
-       {[]byte{}, 2, []byte{1, 0, 0, 255, 255}},
-       {[]byte{0x11}, 2, []byte{18, 4, 4, 0, 0, 255, 255}},
-       {[]byte{0x11, 0x12}, 2, []byte{18, 20, 2, 4, 0, 0, 255, 255}},
-       {[]byte{0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11}, 2, []byte{18, 132, 2, 64, 0, 0, 0, 255, 255}},
-       {[]byte{}, 9, []byte{1, 0, 0, 255, 255}},
-       {[]byte{0x11}, 9, []byte{18, 4, 4, 0, 0, 255, 255}},
-       {[]byte{0x11, 0x12}, 9, []byte{18, 20, 2, 4, 0, 0, 255, 255}},
-       {[]byte{0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11}, 9, []byte{18, 132, 2, 64, 0, 0, 0, 255, 255}},
+       {[]byte{}, 2, []byte{3, 0}},
+       {[]byte{0x11}, 2, []byte{18, 4, 12, 0}},
+       {[]byte{0x11, 0x12}, 2, []byte{18, 20, 2, 12, 0}},
+       {[]byte{0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11}, 2, []byte{18, 132, 2, 192, 0}},
+       {[]byte{}, 9, []byte{3, 0}},
+       {[]byte{0x11}, 9, []byte{18, 4, 12, 0}},
+       {[]byte{0x11, 0x12}, 9, []byte{18, 20, 2, 12, 0}},
+       {[]byte{0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11, 0x11}, 9, []byte{18, 132, 2, 192, 0}},
 }

 var deflateInflateTests = []*deflateInflateTest{
diff --git a/src/compress/zlib/example_test.go b/src/compress/zlib/example_test.go
index 70408895ff..beabde6d05 100644
--- a/src/compress/zlib/example_test.go
+++ b/src/compress/zlib/example_test.go
@@ -19,12 +19,12 @@ func ExampleNewWriter() {
        w.Write([]byte("hello, world\n"))
        w.Close()
        fmt.Println(b.Bytes())
-       // Output: [120 156 202 72 205 201 201 215 81 40 207 47 202 73 225 2 4 0 0 255 255 33 231 4 147]
+       // Output: [120 156 202 72 205 201 201 215 81 40 207 47 202 73 225 2 12 0 33 231 4 147]
 }

 func ExampleNewReader() {
        buff := []byte{120, 156, 202, 72, 205, 201, 201, 215, 81, 40, 207,
-               47, 202, 73, 225, 2, 4, 0, 0, 255, 255, 33, 231, 4, 147}
+               47, 202, 73, 225, 2, 12, 0, 33, 231, 4, 147}
        b := bytes.NewReader(buff)

        r, err := zlib.NewReader(b)

So my question is: why do we need to output a final empty block of type 0? Is it reasonable to swap that out for a final empty block of type 1 (and if so, should I take that diff and make a PR?). I wasn't completely sure if this implementation detail was intentional or not. I do see notes around flushing (such as https://www.bolet.org/~pornin/deflate-flush.html) - but flushing is only to get guarantee byte alignment for streaming right? Is it needed when ending the deflate stream?

Ideally, the best approach would be to mark the last block as final instead of having to output an empty block. I would be interested in tackling this approach if folks agree!

[ivantsepp]

apologies, I accidentally hit the submit button too early. created the issue without flushing out my thoughts. reopening!

[gabyhelp]

Related Issues

• compress/flate: Close is not idempotent #27741 (closed)
• compress/flate: read data with partial flush #68130
• compress/gzip: unable to reproduce the same gzip/DEFLATE compressed output as Python/Rust #40830 (closed)

Related Code Changes

• compress/flate: improve inflate speed by reading more bits at a time
• compress/flate: replace "Best Speed" with specialized version
• compress/flate: level 1 (best speed) match across blocks
• compress/flate: make compression level 0 consistent
• compress/flate: replace "Best Speed" with specialized version
• compress/flate: make Reader.Read return io.EOF eagerly
• compress/flate: make Reader.Read return io.EOF eagerly

_{(Emoji vote if this was helpful or unhelpful; more detailed feedback welcome in this discussion.)}

[dmitshur]

CC @dsnet, @mdempsky.