code review 12521043: encoding/binary: Reduce memory allocations and add fast...

encoding/binary: Reduce memory allocations and add fast paths for slices

Also added a new test and a few benchmarks for different basic slice types.

Fixes issue 2634

benchmark                         old ns/op    new ns/op    delta
BenchmarkReadSlice1000Int8s           35700         3328  -90.68%
BenchmarkReadSlice1000Uint8s          34159          110  -99.68%
BenchmarkReadSlice1000Int16s          46197        14607  -68.38%
BenchmarkReadSlice1000Uint16s         44314        14693  -66.84%
BenchmarkReadSlice1000Int32s          49191        19269  -60.83%
BenchmarkReadSlice1000Uint32s         47523        18213  -61.68%
BenchmarkReadSlice1000Int64s          61243        29637  -51.61%
BenchmarkReadSlice1000Uint64s         57205        27828  -51.35%
BenchmarkWriteSlice1000Int8s          40406         2217  -94.51%
BenchmarkWriteSlice1000Uint8s         40316           99  -99.75%
BenchmarkWriteSlice1000Int16s         51168        11912  -76.72%
BenchmarkWriteSlice1000Uint16s        49556        11840  -76.11%
BenchmarkWriteSlice1000Int32s         54567        15955  -70.76%
BenchmarkWriteSlice1000Uint32s        51732        15800  -69.46%
BenchmarkWriteSlice1000Int64s         67872        24318  -64.17%
BenchmarkWriteSlice1000Uint64s        61171        23469  -61.63%

benchmark                          old MB/s     new MB/s  speedup
BenchmarkReadSlice1000Int8s           28.01       300.41   10.73x
BenchmarkReadSlice1000Uint8s          29.27      9051.21  309.23x
BenchmarkReadSlice1000Int16s          43.29       136.92    3.16x
BenchmarkReadSlice1000Uint16s         45.13       136.11    3.02x
BenchmarkReadSlice1000Int32s          81.31       207.58    2.55x
BenchmarkReadSlice1000Uint32s         84.17       219.61    2.61x
BenchmarkReadSlice1000Int64s         130.63       269.93    2.07x
BenchmarkReadSlice1000Uint64s        139.85       287.48    2.06x
BenchmarkWriteSlice1000Int8s          24.75       451.01   18.22x
BenchmarkWriteSlice1000Uint8s         24.80     10104.20  407.43x
BenchmarkWriteSlice1000Int16s         39.09       167.89    4.29x
BenchmarkWriteSlice1000Uint16s        40.36       168.91    4.19x
BenchmarkWriteSlice1000Int32s         73.30       250.70    3.42x
BenchmarkWriteSlice1000Uint32s        77.32       253.16    3.27x
BenchmarkWriteSlice1000Int64s        117.87       328.97    2.79x
BenchmarkWriteSlice1000Uint64s       130.78       340.87    2.61x

benchmark                        old allocs   new allocs    delta
BenchmarkReadSlice1000Int8s               2            1  -50.00%
BenchmarkReadSlice1000Uint8s              2            1  -50.00%
BenchmarkReadSlice1000Int16s              2            1  -50.00%
BenchmarkReadSlice1000Uint16s             2            1  -50.00%
BenchmarkReadSlice1000Int32s              2            1  -50.00%
BenchmarkReadSlice1000Uint32s             2            1  -50.00%
BenchmarkReadSlice1000Int64s              2            1  -50.00%
BenchmarkReadSlice1000Uint64s             2            1  -50.00%
BenchmarkWriteSlice1000Int8s              3            1  -66.67%
BenchmarkWriteSlice1000Uint8s             3            1  -66.67%
BenchmarkWriteSlice1000Int16s             3            1  -66.67%
BenchmarkWriteSlice1000Uint16s            3            1  -66.67%
BenchmarkWriteSlice1000Int32s             3            1  -66.67%
BenchmarkWriteSlice1000Uint32s            3            1  -66.67%
BenchmarkWriteSlice1000Int64s             3            1  -66.67%
BenchmarkWriteSlice1000Uint64s            3            1  -66.67%

benchmark                         old bytes    new bytes    delta
BenchmarkReadSlice1000Int8s            1072            8  -99.25%
BenchmarkReadSlice1000Uint8s           1072            8  -99.25%
BenchmarkReadSlice1000Int16s           2096            8  -99.62%
BenchmarkReadSlice1000Uint16s          2096            8  -99.62%
BenchmarkReadSlice1000Int32s           4144            8  -99.81%
BenchmarkReadSlice1000Uint32s          4144            8  -99.81%
BenchmarkReadSlice1000Int64s           8240            8  -99.90%
BenchmarkReadSlice1000Uint64s          8240            8  -99.90%
BenchmarkWriteSlice1000Int8s           1080            8  -99.26%
BenchmarkWriteSlice1000Uint8s          1080            8  -99.26%
BenchmarkWriteSlice1000Int16s          2104            8  -99.62%
BenchmarkWriteSlice1000Uint16s         2104            8  -99.62%
BenchmarkWriteSlice1000Int32s          4152            8  -99.81%
BenchmarkWriteSlice1000Uint32s         4152            8  -99.81%
BenchmarkWriteSlice1000Int64s          8248            8  -99.90%
BenchmarkWriteSlice1000Uint64s         8248            8  -99.90%

[Hierro, 2013-08-06 10:24:39]

Hello golang-dev@googlegroups.com,

I'd like you to review this change to
https://code.google.com/p/go

[r, 2013-08-06 10:46:00]

This is too complicated and pulls in too much. All that's required is a few more
cases in the big switch in Write.

https://codereview.appspot.com/12521043/diff/6001/src/pkg/encoding/binary/bin...
File src/pkg/encoding/binary/binary.go (right):

https://codereview.appspot.com/12521043/diff/6001/src/pkg/encoding/binary/bin...
src/pkg/encoding/binary/binary.go:316: if r := recover(); r != nil {
don't do this

https://codereview.appspot.com/12521043/diff/6001/src/pkg/encoding/binary/bin...
src/pkg/encoding/binary/binary.go:435: // Fast path for common slice types
You don't need reflection to do these cases. You've changed more than is
necessary and sped it up less than is possible.

[Hierro, 2013-08-06 11:57:29]

On 2013/08/06 10:46:00, r wrote:
> This is too complicated and pulls in too much. All that's required is a few
more
> cases in the big switch in Write.
> 
>
https://codereview.appspot.com/12521043/diff/6001/src/pkg/encoding/binary/bin...
> File src/pkg/encoding/binary/binary.go (right):
> 
>
https://codereview.appspot.com/12521043/diff/6001/src/pkg/encoding/binary/bin...
> src/pkg/encoding/binary/binary.go:316: if r := recover(); r != nil {
> don't do this

encoding/json does exactly the same and it saves a lot of if err != nil checks.

> 
>
https://codereview.appspot.com/12521043/diff/6001/src/pkg/encoding/binary/bin...
> src/pkg/encoding/binary/binary.go:435: // Fast path for common slice types
> You don't need reflection to do these cases. You've changed more than is
> necessary and sped it up less than is possible.

That requires one of the following:

1 - Always initialize the encoder/decoder, which is not required for basic types
(degrades performance for basic types)
2 - Copy and paste the line for initializing the encoder/decoder in every type
switch case for slices (ugly and prone to errors).

I had already tested option #2 and, guess what? It's slower than this patch.
Probably because of the way Go handles switches (disassembling the code and
finding exactly why is left as an exercise for the reader). Left is this CL,
right is the code you suggest:

benchmark                        old ns/op    new ns/op    delta
BenchmarkWriteSlice1000Int32s        25962        27278   +5.07%

benchmark                         old MB/s     new MB/s  speedup
BenchmarkWriteSlice1000Int32s       154.07       146.63    0.95x

benchmark                       old allocs   new allocs    delta
BenchmarkWriteSlice1000Int32s            4            3  -25.00%

benchmark                        old bytes    new bytes    delta
BenchmarkWriteSlice1000Int32s          140          105  -25.00%

One could argue that saving 35 bytes per run is worth the 5% performance
penalty, but I don't think that's the case. Note that I didn't include error
checking in this test, so the final version would be even slower. Furthermore,
this CL will also speed up any struct which contains slices, while the code you
suggest won't.

Regards,
Alberto

P.S.: Your suggested patch follows, I've omitted error checking in the big
switch in Write() for slices, so the final version would be even slower:

fiam@ubuntu:~/go/src/pkg/encoding/binary$ cat r.diff 
diff -r ab644299d124 src/pkg/encoding/binary/binary.go
--- a/src/pkg/encoding/binary/binary.go	Mon Aug 05 15:46:06 2013 -0700
+++ b/src/pkg/encoding/binary/binary.go	Tue Aug 06 13:44:30 2013 +0200
@@ -20,6 +20,7 @@
 	"io"
 	"math"
 	"reflect"
+	"runtime"
 )
 
 // A ByteOrder specifies how to convert byte sequences into
@@ -167,14 +168,10 @@
 	default:
 		return errors.New("binary.Read: invalid type " + d.Type().String())
 	}
-	size, err := dataSize(v)
-	if err != nil {
+	if _, err := dataSize(v); err != nil {
 		return errors.New("binary.Read: " + err.Error())
 	}
-	d := &decoder{order: order, buf: make([]byte, size)}
-	if _, err := io.ReadFull(r, d.buf); err != nil {
-		return err
-	}
+	d := decoder{coder: coder{order: order}, reader: r}
 	d.value(v)
 	return nil
 }
@@ -239,6 +236,54 @@
 	case uint64:
 		bs = b[:8]
 		order.PutUint64(bs, v)
+	case []uint8:
+		e := encoder{coder: coder{order: order}, writer: w}
+		for _, val := range v {
+			e.uint8(val)
+		}
+		return e.err
+	case []int8:
+		e := encoder{coder: coder{order: order}, writer: w}
+		for _, val := range v {
+			e.int8(val)
+		}
+		return e.err
+	case []uint16:
+		e := encoder{coder: coder{order: order}, writer: w}
+		for _, val := range v {
+			e.uint16(val)
+		}
+		return e.err
+	case []int16:
+		e := encoder{coder: coder{order: order}, writer: w}
+		for _, val := range v {
+			e.int16(val)
+		}
+		return e.err
+	case []uint32:
+		e := encoder{coder: coder{order: order}, writer: w}
+		for _, val := range v {
+			e.uint32(val)
+		}
+		return e.err
+	case []int32:
+		e := encoder{coder: coder{order: order}, writer: w}
+		for _, val := range v {
+			e.int32(val)
+		}
+		return e.err
+	case []uint64:
+		e := encoder{coder: coder{order: order}, writer: w}
+		for _, val := range v {
+			e.uint64(val)
+		}
+		return e.err
+	case []int64:
+		e := encoder{coder: coder{order: order}, writer: w}
+		for _, val := range v {
+			e.int64(val)
+		}
+		return e.err
 	}
 	if bs != nil {
 		_, err := w.Write(bs)
@@ -247,15 +292,13 @@
 
 	// Fallback to reflect-based encoding.
 	v := reflect.Indirect(reflect.ValueOf(data))
-	size, err := dataSize(v)
-	if err != nil {
+	if _, err := dataSize(v); err != nil {
 		return errors.New("binary.Write: " + err.Error())
 	}
-	buf := make([]byte, size)
-	e := &encoder{order: order, buf: buf}
+	e := encoder{coder: coder{order: order}, writer: w}
+	defer e.recover()
 	e.value(v)
-	_, err = w.Write(buf)
-	return err
+	return e.err
 }
 
 // Size returns how many bytes Write would generate to encode the value v,
which
@@ -313,54 +356,87 @@
 
 type coder struct {
 	order ByteOrder
-	buf   []byte
+	buf   [8]byte
+	err   error
 }
 
-type decoder coder
-type encoder coder
+func (c *coder) recover() {
+	if r := recover(); r != nil {
+		if _, ok := r.(runtime.Error); ok {
+			panic(r)
+		}
+		c.err = r.(error)
+	}
+}
+
+type decoder struct {
+	coder
+	reader io.Reader
+}
+
+func (d *decoder) read(bs []byte) {
+	if _, err := d.reader.Read(bs); err != nil {
+		panic(err)
+	}
+}
+
+type encoder struct {
+	coder
+	writer io.Writer
+}
+
+func (e *encoder) write(bs []byte) {
+	if _, err := e.writer.Write(bs); err != nil {
+		panic(err)
+	}
+}
 
 func (d *decoder) uint8() uint8 {
-	x := d.buf[0]
-	d.buf = d.buf[1:]
-	return x
+	bs := d.buf[:1]
+	d.read(bs)
+	return bs[0]
 }
 
 func (e *encoder) uint8(x uint8) {
-	e.buf[0] = x
-	e.buf = e.buf[1:]
+	bs := e.buf[:1]
+	bs[0] = x
+	e.write(bs)
 }
 
 func (d *decoder) uint16() uint16 {
-	x := d.order.Uint16(d.buf[0:2])
-	d.buf = d.buf[2:]
-	return x
+	bs := d.buf[:2]
+	d.read(bs)
+	return d.order.Uint16(bs)
 }
 
 func (e *encoder) uint16(x uint16) {
-	e.order.PutUint16(e.buf[0:2], x)
-	e.buf = e.buf[2:]
+	bs := e.buf[:2]
+	e.order.PutUint16(bs, x)
+	e.write(bs)
 }
 
 func (d *decoder) uint32() uint32 {
-	x := d.order.Uint32(d.buf[0:4])
-	d.buf = d.buf[4:]
-	return x
+	bs := d.buf[:4]
+	d.read(bs)
+	return d.order.Uint32(bs)
 }
 
 func (e *encoder) uint32(x uint32) {
-	e.order.PutUint32(e.buf[0:4], x)
-	e.buf = e.buf[4:]
+	bs := e.buf[:4]
+	e.order.PutUint32(bs, x)
+	e.write(bs)
 }
 
 func (d *decoder) uint64() uint64 {
-	x := d.order.Uint64(d.buf[0:8])
-	d.buf = d.buf[8:]
-	return x
+	bs := d.buf[:8]
+	d.read(bs)
+	return d.order.Uint64(bs)
 }
 
 func (e *encoder) uint64(x uint64) {
-	e.order.PutUint64(e.buf[0:8], x)
-	e.buf = e.buf[8:]
+	bs := e.buf[:8]
+	e.order.PutUint64(bs, x)
+	e.write(bs)
 }
 
 func (d *decoder) int8() int8 { return int8(d.uint8()) }
@@ -404,9 +480,45 @@
 		}
 
 	case reflect.Slice:
-		l := v.Len()
-		for i := 0; i < l; i++ {
-			d.value(v.Index(i))
+		// Fast path for common slice types
+		switch s := v.Interface().(type) {
+		case []uint8:
+			for i := range s {
+				s[i] = d.uint8()
+			}
+		case []int8:
+			for i := range s {
+				s[i] = d.int8()
+			}
+		case []uint16:
+			for i := range s {
+				s[i] = d.uint16()
+			}
+		case []int16:
+			for i := range s {
+				s[i] = d.int16()
+			}
+		case []uint32:
+			for i := range s {
+				s[i] = d.uint32()
+			}
+		case []int32:
+			for i := range s {
+				s[i] = d.int32()
+			}
+		case []uint64:
+			for i := range s {
+				s[i] = d.uint64()
+			}
+		case []int64:
+			for i := range s {
+				s[i] = d.int64()
+			}
+		default:
+			l := v.Len()
+			for i := 0; i < l; i++ {
+				d.value(v.Index(i))
+			}
 		}
 
 	case reflect.Int8:
@@ -466,9 +578,45 @@
 		}
 
 	case reflect.Slice:
-		l := v.Len()
-		for i := 0; i < l; i++ {
-			e.value(v.Index(i))
+		// Fast path for common slice types
+		switch s := v.Interface().(type) {
+		case []uint8:
+			for _, val := range s {
+				e.uint8(val)
+			}
+		case []int8:
+			for _, val := range s {
+				e.int8(val)
+			}
+		case []uint16:
+			for _, val := range s {
+				e.uint16(val)
+			}
+		case []int16:
+			for _, val := range s {
+				e.int16(val)
+			}
+		case []uint32:
+			for _, val := range s {
+				e.uint32(val)
+			}
+		case []int32:
+			for _, val := range s {
+				e.int32(val)
+			}
+		case []uint64:
+			for _, val := range s {
+				e.uint64(val)
+			}
+		case []int64:
+			for _, val := range s {
+				e.int64(val)
+			}
+		default:
+			l := v.Len()
+			for i := 0; i < l; i++ {
+				e.value(v.Index(i))
+			}
 		}
 
 	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
@@ -519,15 +667,29 @@
 
 func (d *decoder) skip(v reflect.Value) {
 	n, _ := dataSize(v)
-	d.buf = d.buf[n:]
+	b := d.buf[:8]
+	for n >= 8 {
+		d.read(b)
+		n -= 8
+	}
+	if n > 0 {
+		d.read(b[:n])
+	}
 }
 
 func (e *encoder) skip(v reflect.Value) {
 	n, _ := dataSize(v)
-	for i := range e.buf[0:n] {
-		e.buf[i] = 0
+	for ii := 0; ii < 8; ii++ {
+		e.buf[ii] = 0
 	}
-	e.buf = e.buf[n:]
+	b := e.buf[:8]
+	for n >= 8 {
+		e.write(b)
+		n -= 8
+	}
+	if n > 0 {
+		e.write(b[:n])
+	}
 }
 
 // intDestSize returns the size of the integer that ptrType points to,

[r, 2013-08-06 12:13:39]

I think one of us isn't listening. It may be me, but I was expecting to see
Write look like this, to pick one snippet:

We now have

case uint8:
 bs = b[:1]
b[0] = byte(v)


after that something like

 case []uint8:
if len(v) > len(bs) { // This check wouldn't be worth the bother for types
large than 8 bits.
 bs = make([]byte, len(v))
} else {
bs = b[:len(v)]
 }
copy(bs, v)

There is no need for reflection or encoders for slices of basic types. Just
stuff the bits.

-rob

[Hierro, 2013-08-06 14:51:51]

On 2013/08/06 12:13:39, r wrote:
> I think one of us isn't listening. It may be me, but I was expecting to see
> Write look like this, to pick one snippet:
> 
> We now have
> 
> case uint8:
>  bs = b[:1]
> b[0] = byte(v)
> 
> 
> after that something like
> 
>  case []uint8:
> if len(v) > len(bs) { // This check wouldn't be worth the bother for types
> large than 8 bits.
>  bs = make([]byte, len(v))
> } else {
> bs = b[:len(v)]
>  }
> copy(bs, v)
> 
> There is no need for reflection or encoders for slices of basic types. Just
> stuff the bits.
> 
> -rob

That would allocate garbage and run slower than the current patch set. However,
you've just given me an idea to make it even faster. I have to run some errands
right now, but I'll update this CL tonight with a better patch set.

Regards,
Alberto

[Hierro, 2013-08-06 23:28:11]

Hello golang-dev@googlegroups.com, r@golang.org (cc:
golang-dev@googlegroups.com),

Please take another look.

[r, 2013-08-09 06:17:50]

I apologize but your goals for this package seem to be different from ours.
You've doubled the size of the source code, added panics and recovers, even
unrolled loops by hand. This package doesn't deserve that level of attention for
performance. Anyone who *needs* that much performance is better off doing the
byte stuffing themselves, since this package is both severely limited in power
and unable to be performant even in all the cases it does handle.

I have several times suggested a much simpler approach that will make writing
slices significantly faster in a way that seems more in keeping with the modest
goals of this package, but you are clearly not satisfied by that approach.  So
although I appreciate the work you've done, perhaps your code should be
published in a separate open source repository.

I will update the package documentation to make its limitations clearer.

[Hierro, 2013-08-09 10:04:50]

On 2013/08/09 06:17:50, r wrote:
> I apologize but your goals for this package seem to be different from ours.
> You've doubled the size of the source code, added panics and recovers, even
> unrolled loops by hand. This package doesn't deserve that level of attention
for
> performance. Anyone who *needs* that much performance is better off doing the
> byte stuffing themselves, since this package is both severely limited in power
> and unable to be performant even in all the cases it does handle.
> 
> I have several times suggested a much simpler approach that will make writing
> slices significantly faster in a way that seems more in keeping with the
modest
> goals of this package, but you are clearly not satisfied by that approach.  So
> although I appreciate the work you've done, perhaps your code should be
> published in a separate open source repository.
> 
> I will update the package documentation to make its limitations clearer.

I respectfully disagree with that. With a few more optimizations (like writing
ByteOrder methods in assembly), this package would be more than fast enough for
almost everyone. And that's an optimization that most users can't perform
themselves (specially when using App Engine, since AFAIK user code most be pure
Go on GAE, but the standard library can use ASM and unsafe - please correct me
on that if I'm wrong). Also, performance increases are nice for everybody, even
when they don't absolutely need them. If your CPU spends less time in
encoding/binary, you have more time to do other stuff. Of course, performance
improvements usually come with a maintenance cost, because most of the time
you're making the code more complex.  However, I would consider encoding/binary
feature complete so I think making the code a bit more complex to make it more
performant is, at this time, acceptable.

Remember when people used to say that it didn't matter that Python/Ruby web
frameworks were slow because the bottleneck was gonna be the database anyway?
Well, Go has proved all them wrong because websites that migrated their code to
Go have been able to significantly reduce their number of servers (some of us
were already doing that back in the day rewriting the hottest code paths in C
and ASM, but it's nice we don't have do that anymore thanks to Go).

On the other hand, the approach you suggested would be indeed, simpler, but also
completely wrong because it would allocate unnecessary garbage which is going to
be throw again before the function ends.

Anyway, if your stance on performance is that users should rewrite parts of the
standard library when they need fast code, I will close this CL and stop
submitting patches which just increase performance (and, please, close the
issues related to performance with a WONTFIX, so everybody gets the message).

Regards,
Alberto

[Hierro, 2013-08-09 10:16:43]

*** Abandoned ***

[iant, 2013-08-09 13:13:52]

On Fri, Aug 9, 2013 at 3:04 AM,  <alberto.garcia.hierro@gmail.com> wrote:
>
> Anyway, if your stance on performance is that users should rewrite parts
> of the standard library when they need fast code, I will close this CL
> and stop submitting patches which just increase performance (and,
> please, close the issues related to performance with a WONTFIX, so
> everybody gets the message).

I want to point out that Rob was clear that he was talking about a
specific package, binary/encoding, and in particular argued that the
package, by design, can not be as fast as code that does its own byte
stuffing.  Your extension to all performance issues in the standard
library is understandable but erroneous.

Ian

[Hierro, 2013-08-09 16:59:20]

On 2013/08/09 13:13:52, iant wrote:
> On Fri, Aug 9, 2013 at 3:04 AM,  <mailto:alberto.garcia.hierro@gmail.com>
wrote:
> >
> > Anyway, if your stance on performance is that users should rewrite parts
> > of the standard library when they need fast code, I will close this CL
> > and stop submitting patches which just increase performance (and,
> > please, close the issues related to performance with a WONTFIX, so
> > everybody gets the message).
> 
> I want to point out that Rob was clear that he was talking about a
> specific package, binary/encoding, and in particular argued that the
> package, by design, can not be as fast as code that does its own byte
> stuffing.  Your extension to all performance issues in the standard
> library is understandable but erroneous.
> 
> Ian

I wasn't stating that he was talking about the whole standard library, but
rather posing the question. That's why I started the phrase with "if your stance
on performance…".

Regards,
Alberto

[iant, 2013-08-09 17:29:37]

On Fri, Aug 9, 2013 at 9:59 AM,  <alberto.garcia.hierro@gmail.com> wrote:
> On 2013/08/09 13:13:52, iant wrote:
>
>> I want to point out that Rob was clear that he was talking about a
>> specific package, binary/encoding, and in particular argued that the
>> package, by design, can not be as fast as code that does its own byte
>> stuffing.  Your extension to all performance issues in the standard
>> library is understandable but erroneous.
>
>
>> Ian
>
>
> I wasn't stating that he was talking about the whole standard library,
> but rather posing the question. That's why I started the phrase with "if
> your stance on performance…".

My apologies for misunderstanding.

I can't speak for Rob but I don't think most Go developers would agree
with the general notion that "users should rewrite parts of the
standard library when they need fast code."  So if you are asking that
as a question, the answer is no.

Ian

[Hierro, 2013-08-09 18:31:25]

On 2013/08/09 17:29:37, iant wrote:
> On Fri, Aug 9, 2013 at 9:59 AM,  <mailto:alberto.garcia.hierro@gmail.com>
wrote:
> > On 2013/08/09 13:13:52, iant wrote:
> >
> >> I want to point out that Rob was clear that he was talking about a
> >> specific package, binary/encoding, and in particular argued that the
> >> package, by design, can not be as fast as code that does its own byte
> >> stuffing.  Your extension to all performance issues in the standard
> >> library is understandable but erroneous.
> >
> >
> >> Ian
> >
> >
> > I wasn't stating that he was talking about the whole standard library,
> > but rather posing the question. That's why I started the phrase with "if
> > your stance on performance…".
> 
> My apologies for misunderstanding.
> 
> I can't speak for Rob but I don't think most Go developers would agree
> with the general notion that "users should rewrite parts of the
> standard library when they need fast code."  So if you are asking that
> as a question, the answer is no.
> 
> Ian

Thanks for the clarification. Now that I re-read it, maybe the question wasn't
clear enough (English is my third language and I mix things up from time to
time).

Regards,
Alberto

[rsc, 2013-08-09 18:33:55]

Alberto,

You seem singularly focused on performance, willing to go to great lengths
to get a couple percent speedup. What you seem not to appreciate is the
weight we assign to other valid concerns, such as code complexity,
maintainability, and reliability. For those, we are often willing to give
up a few percent or more. Code that is left unchanged is code that is more
likely to be correct, and code that is kept simple is code that will be
easier to adjust later. Rewriting a large amount of code to achieve a
certain speed improvement is almost never better than rewriting a much
smaller amount of code to achieve an only slightly smaller improvement.
Focus on the big savings and the tiny things will take care of themselves.
Your original CL made BenchmarkWriteSlice1000Int32s 2.15x faster. The
smaller, simpler CL that Rob submitted made it 2.14x faster. What's left in
your CL would be another 1.2x if I am reading the numbers correct, and 1.2x
doesn't really pay for such a large change.

Your comparison with Python and Ruby is not really analogous to what's
going on here. Python and Ruby are not just 1.2x or even 2.5x slower than
compiled code.

Russ

[Hierro, 2013-08-10 16:13:14]

On 2013/08/09 18:33:55, rsc wrote:
Hi Russ,

My focus for this package is indeed performance, because I'd really love it to
be fast enough to not need to write my own byte stuffing routines most of time.
Or, at least, leverage encoding/binary to do so. I understand that
maintainability of the code is also a concern, but I don't think the code that I
wrote is inherently more difficult to maintain than it was before. Unrolled
loops are ugly, that's for certain, but I find them an acceptable tradeoff in
this case, mostly because the compiler will never be able to perform those for
me. As for the reliability, my code passes all the tests in encoding/binary and
few more than I added, so I'm pretty confident about its correctness. 

I'd like to clarify that this CL was an initial patch set, which I considered
the bare minimum. I planned to continue improving the performance of the package
with more CLs, as well as cleaning up the code a bit and separating its code
into several better organized files. The reason I didn't wait until I had all
those changes ready is because the other day (on the encoding/json CL) I was
told to submit small changes, not big ones, because is difficult to measure each
individual change if they're presented as a single one.

With this package I took the approach to send a small change first, just to be
told that what I was doing could (wrongly) be done with less code. Although my
initial patch was just 20% faster than Rob's code, it dramatically reduced the
amount of generated garbage. When it comes to bytes allocated, Rob's code is
O(N) while mine is O(1) and uses a very small amount (usually, 8 bytes) per run.
Reducing the pressure on the GC benefits real world applications a lot, but this
was just ignored by Rob.

On the other hand, the code in ByteOrder implementations is less than suboptimal
and, at the same time, probably one of the best candidates to be rewritten in
assembler, because the gc compiler won't generate BSWAP instructions. Having an
optimal ByteOrder implementation is a big win for users, because they can
leverage their performance to write their own specialized byte stuffing routines
for their own types. And there's no way to get that optimal performance without
resorting to assembler, which I wouldn't expect Go users to do.

With that said, I spent a couple more of hours optimizing my fork of
encoding/binary and got pretty good results (at least for my criteria):

benchmark                          old ns/op    new ns/op    delta
BenchmarkReadSlice1000Int8s             2992         2909   -2.77%
BenchmarkReadSlice1000Uint8s            3151           32  -98.98%
BenchmarkReadSlice1000Int16s           19003        10529  -44.59%
BenchmarkReadSlice1000Uint16s          13451        11669  -13.25%
BenchmarkReadSlice1000Int32s           19568        13510  -30.96%
BenchmarkReadSlice1000Uint32s          27385        13323  -51.35%
BenchmarkReadSlice1000Int64s           42735        13343  -68.78%
BenchmarkReadSlice1000Uint64s          31739        13850  -56.36%
BenchmarkWriteSlice1000Int8s            3224         2271  -29.56%
BenchmarkWriteSlice1000Uint8s            108           29  -72.69%
BenchmarkWriteSlice1000Int16s          12866         7950  -38.21%
BenchmarkWriteSlice1000Uint16s         17632         9666  -45.18%
BenchmarkWriteSlice1000Int32s          21643        10436  -51.78%
BenchmarkWriteSlice1000Uint32s         23070        10508  -54.45%
BenchmarkWriteSlice1000Int64s          32699        10520  -67.83%
BenchmarkWriteSlice1000Uint64s         31710        10559  -66.70%
BenchmarkReadStruct                     3569         2035  -42.98%
BenchmarkWriteStruct                    3705         1773  -52.15%
BenchmarkReadStructCustom                879          763  -13.20%
BenchmarkWriteStructCustom               288          217  -24.65%
BenchmarkReadSliceStruct                 726        27079  +3629.89%
BenchmarkReadSliceStructCustom         55581        44792  -19.41%
BenchmarkWriteSliceStructCustom        19856         9226  -53.54%
BenchmarkReadArrayStruct               61334        26983  -56.01%
BenchmarkWriteArrayStruct              64916        13945  -78.52%
BenchmarkReadInts                       1307         1198   -8.34%
BenchmarkWriteInts                      1262         1369   +8.48%
BenchmarkPutBigEndian                     29           12  -58.72%
BenchmarkPutLittleEndian                  27           11  -58.06%
BenchmarkReadBigEndian                    28           12  -58.04%
BenchmarkReadLittleEndian                 28           11  -58.72%

benchmark                           old MB/s     new MB/s  speedup
BenchmarkReadSlice1000Int8s           334.13       343.65    1.03x
BenchmarkReadSlice1000Uint8s          317.36     31297.42   98.62x
BenchmarkReadSlice1000Int16s          105.24       189.94    1.80x
BenchmarkReadSlice1000Uint16s         148.69       171.38    1.15x
BenchmarkReadSlice1000Int32s          204.41       296.06    1.45x
BenchmarkReadSlice1000Uint32s         146.06       300.22    2.06x
BenchmarkReadSlice1000Int64s          187.20       599.52    3.20x
BenchmarkReadSlice1000Uint64s         252.05       577.58    2.29x
BenchmarkWriteSlice1000Int8s          310.16       440.25    1.42x
BenchmarkWriteSlice1000Uint8s        9232.01     33846.01    3.67x
BenchmarkWriteSlice1000Int16s         155.44       251.55    1.62x
BenchmarkWriteSlice1000Uint16s        113.43       206.91    1.82x
BenchmarkWriteSlice1000Int32s         184.81       383.27    2.07x
BenchmarkWriteSlice1000Uint32s        173.38       380.65    2.20x
BenchmarkWriteSlice1000Int64s         244.65       760.44    3.11x
BenchmarkWriteSlice1000Uint64s        252.28       757.62    3.00x
BenchmarkReadStruct                    19.61        34.39    1.75x
BenchmarkWriteStruct                   18.89        39.48    2.09x
BenchmarkReadStructCustom              79.64        91.66    1.15x
BenchmarkWriteStructCustom            242.41       322.56    1.33x
BenchmarkReadSliceStruct                0.00       295.43     infx
BenchmarkReadSliceStructCustom        143.93       178.60    1.24x
BenchmarkWriteSliceStructCustom       402.88       867.11    2.15x
BenchmarkReadArrayStruct              130.43       296.48    2.27x
BenchmarkWriteArrayStruct             123.24       573.66    4.65x
BenchmarkReadInts                      22.94        25.04    1.09x
BenchmarkWriteInts                     23.75        21.91    0.92x

benchmark                          old bytes    new bytes    delta
BenchmarkReadSlice1000Int8s             1032            8  -99.22%
BenchmarkReadSlice1000Uint8s            1032            0  -100.00%
BenchmarkReadSlice1000Int16s            2056            8  -99.61%
BenchmarkReadSlice1000Uint16s           2056            8  -99.61%
BenchmarkReadSlice1000Int32s            4104            8  -99.81%
BenchmarkReadSlice1000Uint32s           4104            8  -99.81%
BenchmarkReadSlice1000Int64s            8200           16  -99.80%
BenchmarkReadSlice1000Uint64s           8200           16  -99.80%
BenchmarkWriteSlice1000Int8s            1032            8  -99.22%
BenchmarkWriteSlice1000Uint8s              8            0  -100.00%
BenchmarkWriteSlice1000Int16s           2056            8  -99.61%
BenchmarkWriteSlice1000Uint16s          2056            8  -99.61%
BenchmarkWriteSlice1000Int32s           4104            8  -99.81%
BenchmarkWriteSlice1000Uint32s          4104            8  -99.81%
BenchmarkWriteSlice1000Int64s           8200           16  -99.80%
BenchmarkWriteSlice1000Uint64s          8200           16  -99.80%
BenchmarkReadStruct                      247           99  -59.92%
BenchmarkWriteStruct                     256           99  -61.33%
BenchmarkReadStructCustom                  8            8    0.00%
BenchmarkWriteStructCustom                 8            8    0.00%
BenchmarkReadSliceStruct                 123          115   -6.50%
BenchmarkReadSliceStructCustom             8            8    0.00%
BenchmarkWriteSliceStructCustom            8            8    0.00%
BenchmarkReadArrayStruct                8248          115  -98.61%
BenchmarkWriteArrayStruct               8256          115  -98.61%
BenchmarkReadInts                         64           64    0.00%
BenchmarkWriteInts                        64           64    0.00%

(old is hg tip, new is my fork. BenchmarkReadSliceStruct shows more time because
it's not supported on current hg tip)

As you can see, there are very significant speed ups and the amount of bytes
allocated has dramatically decreased. In fact, for structs with a low number of
fields, my code beats custom written methods when it comes to reading (because I
wrote the custom methods using io.ReadFull, as I would expect users to do, and
my encoding/binary code uses an optimized version of io.ReadAtLeast). By
rewriting ByteOrder methods in assembler, I was also able to provide optimal
implementations for the byte swapping operations, which increase performance of
custom encode/decode methods.

I added around 1300 lines of code (~500 are new tests and benchmarks). I don't
know if that's worth for you, but for me it certainly is. Now I'm able to use
encoding/binary directly, since the overhead is now only ~2-3x rather than
~8-10x and its memory usage has gone down by ~99%. In fact, I could probably
make that gap in performance smaller by using unsafe, but I'll leave that for
another day.

I just want to clarify that I have no intention to submit this code as CL. In
total, it took me around 5 hours to perform these optimizations, way less time
than I spent arguing about the code that I wrote. That's, unfortunately, a waste
of your and (most importantly to me) my time. In the future I will only submit
CLs which are a PITA to maintain in a fork (e.g. changes to the toolchain or the
runtime).

Regards,
Alberto

[r, 2013-08-10 23:31:56]

Those numbers are impressive.

I am sorry you feel frustrated and especially sorry you feel you
wasted time talking to us. But as contribute.html tries to make clear,
it's better to discuss your design before coding, not once the code is
already written:

"Before undertaking to write something new for the Go project, send
mail to the mailing list to discuss what you plan to do. This gives
everyone a chance to validate the design, helps prevent duplication of
effort, and ensures that the idea fits inside the goals for the
language and tools. It also guarantees that the design is sound before
code is written; the code review tool is not the place for high-level
discussions."

We spent a lot of time at cross-purposes within the code review
process, even as the code was being actively developed. With some
conversation up front, much of that could have been avoided. The
process did let you down, but I feel it could have gone better. The
end result might have been the same, but it would at least have been
more efficient for all concerned.

I say this in the manner of a post-mortem, a lesson for us and for
future contributors.

-rob