code review 10524044: crypto/sha1: remove an allocation in Sum

crypto/sha1: remove an allocation in Sum
sha1.Sum does two allocations; this CL removes one of them
by placing a small array in the digest that it can use as a
temporary, and by moving the large constant padding array
to a global.

[r, 2013-06-24 23:03:13]

Hello golang-dev@googlegroups.com,

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

[iant, 2013-06-24 23:40:24]

LGTM

[bradfitz, 2013-06-24 23:40:58]

What causes var tmp [64]byte to escape? It's only passed to
(*digest).Write, a concrete type, and block?

Oh, I think we just need to flag block as no-escape in sha1block_amd64.s
and friends.



On Mon, Jun 24, 2013 at 4:03 PM, <r@golang.org> wrote:

> Reviewers: golang-dev1,
>
> Message:
> Hello golang-dev@googlegroups.com,
>
> I'd like you to review this change to
> https://code.google.com/p/go
>
>
> Description:
> crypto/sha1: remove an allocation in Sum
> sha1.Sum does two allocations; this CL removes one of them
> by placing a small array in the digest that it can use as a
> temporary, and by moving the large constant padding array
> to a global.
>
> Please review this at
https://codereview.appspot.**com/10524044/<https://codereview.appspot.com/105...
>
> Affected files:
>   M src/pkg/crypto/sha1/sha1.go
>
>
> Index: src/pkg/crypto/sha1/sha1.go
> ==============================**==============================**=======
> --- a/src/pkg/crypto/sha1/sha1.go
> +++ b/src/pkg/crypto/sha1/sha1.go
> @@ -33,6 +33,7 @@
>  type digest struct {
>         h   [5]uint32
>         x   [chunk]byte
> +       tmp [8]byte
>         nx  int
>         len uint64
>  }
> @@ -87,26 +88,29 @@
>         return
>  }
>
> +// padding is used to fill up to 56 bytes mod 64; it is never modified.
> +var padding = [64]byte{
> +       0: 0x80, // A 1 bit followed by many 0 bits.
> +}
> +
>  func (d0 *digest) Sum(in []byte) []byte {
>         // Make a copy of d0 so that caller can keep writing and summing.
>         d := *d0
>
>         // Padding.  Add a 1 bit and 0 bits until 56 bytes mod 64.
>         len := d.len
> -       var tmp [64]byte
> -       tmp[0] = 0x80
>         if len%64 < 56 {
> -               d.Write(tmp[0 : 56-len%64])
> +               d.Write(padding[0 : 56-len%64])
>         } else {
> -               d.Write(tmp[0 : 64+56-len%64])
> +               d.Write(padding[0 : 64+56-len%64])
>         }
>
>         // Length in bits.
>         len <<= 3
>         for i := uint(0); i < 8; i++ {
> -               tmp[i] = byte(len >> (56 - 8*i))
> +               d.tmp[i] = byte(len >> (56 - 8*i))
>         }
> -       d.Write(tmp[0:8])
> +       d.Write(d.tmp[0:8])
>
>         if d.nx != 0 {
>                 panic("d.nx != 0")
>
>
> --
>
> ---You received this message because you are subscribed to the Google
> Groups "golang-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to
golang-dev+unsubscribe@**googlegroups.com<golang-dev%2Bunsubscribe@googlegrou...
> .
> For more options, visit
https://groups.google.com/**groups/opt_out<https://groups.google.com/groups/o...
> .
>
>
>

[r, 2013-06-24 23:53:05]

I tried that without success, although I may have done it wrong.

-rob

[r, 2013-06-24 23:54:46]

Like this:

//go:noescape

func block(dig *digest, p []byte)

[bradfitz, 2013-06-24 23:56:18]

I was also just trying.

I looked at at a diff of go build -gcflags '-m' -a crypto/sha1 before and
after that annotation, and it does affect whether block's arguments escape,
but it still thinks Write's p []byte escapes to the heap, which I'm not
seeing.

It seems like the escape analysis is too conservative somehow, unless
there's something I'm not seeing.



On Mon, Jun 24, 2013 at 4:52 PM, Rob Pike <r@golang.org> wrote:

> I tried that without success, although I may have done it wrong.
>
> -rob
>

[r, 2013-06-25 00:20:49]

I just did the same experiment with cshapiro watching. Here's what I have:

go build -gcflags=-m
# crypto/sha1
./sha1.go:57: can inline (*digest).Size
./sha1.go:59: can inline (*digest).BlockSize
./sha1.go:40: (*digest).Reset d does not escape
./sha1.go:52: new(digest) escapes to heap
./sha1.go:57: (*digest).Size d does not escape
./sha1.go:59: (*digest).BlockSize d does not escape
./sha1.go:61: leaking param: d
./sha1.go:74: d.x escapes to heap
./sha1.go:61: leaking param: d
./sha1.go:61: (*digest).Write p does not escape
./sha1.go:85: (*digest).Write d.x does not escape
./sha1.go:92: moved to heap: d
./sha1.go:99: d escapes to heap
./sha1.go:101: d escapes to heap
./sha1.go:109: d escapes to heap
./sha1.go:90: leaking param: in to result ~anon1
./sha1.go:90: (*digest).Sum d0 does not escape
./sha1.go:99: (*digest).Sum tmp does not escape
./sha1.go:101: (*digest).Sum tmp does not escape
./sha1.go:109: (*digest).Sum tmp does not escape
./sha1.go:123: (*digest).Sum digest does not escape
./sha1block_decl.go:11: block dig does not escape
./sha1block_decl.go:11: block p does not escape
tubenose=% hg diff .
diff -r f6de76ff41a3 src/pkg/crypto/sha1/sha1block_decl.go
--- a/src/pkg/crypto/sha1/sha1block_decl.go Mon Jun 24 16:53:13 2013 -0700
+++ b/src/pkg/crypto/sha1/sha1block_decl.go Mon Jun 24 17:18:52 2013 -0700
@@ -6,4 +6,6 @@

 package sha1

+//go:noescape
+
 func block(dig *digest, p []byte)
tubenose=%


The two calls to block in Write are each responsible for one of the
two remaining allocations. When I used the pure Go version, the escape
analysis works, so it seems the bug is that the annotation on the
assembler, even though the -m output says it works, isn't working.

-rob

[r, 2013-06-25 00:24:03]

Ha, it's a bug. If you compile sha1block_decl.go BEFORE sha1.go, it
all works. So the decision about the leak calling block is made before
we know whether block is a leaker. It's a compiler bug, and I suspect
one responsible for other leakages.

-rob

[r, 2013-06-25 00:24:25]

*** Abandoned ***

[dave_cheney.net, 2013-06-25 00:27:15]

What a wonderful bug! A workaround would be to create a placeholder
sha1block_arm.s file, then merge sha1block_decl.go into sha1.go. I
can't think of a better more generic solution unless the spec is
changed to say files in a package are compiled in order.

On Tue, Jun 25, 2013 at 10:23 AM, Rob Pike <r@golang.org> wrote:
> Ha, it's a bug. If you compile sha1block_decl.go BEFORE sha1.go, it
> all works. So the decision about the leak calling block is made before
> we know whether block is a leaker. It's a compiler bug, and I suspect
> one responsible for other leakages.
>
> -rob
>
> --
>
> ---
> You received this message because you are subscribed to the Google Groups
"golang-dev" group.
> To unsubscribe from this group and stop receiving emails from it, send an
email to golang-dev+unsubscribe@googlegroups.com.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[r, 2013-06-25 00:28:23]

Issue 5773

[bradfitz, 2013-06-25 00:30:40]

Nice. You saved me some debugging time trying to come up with a minimal
repro. I probably wouldn't have guessed that too soon.  :-)



On Mon, Jun 24, 2013 at 5:28 PM, Rob Pike <r@golang.org> wrote:

> Issue 5773
>