code review 145020043: fmt: Improved printing performance for integers.

fmt: Improved printing performance for integers.

Related to issue 3463. The special casing for base10
and base2^n is copied from strconv.Itoa().

Of course this is code duplication which should be avoided
but neither fmt nor strconv expose a usable interface to
use the integer format routine of the other package. Itoa
cannot use fmt.Sprint because there is no format string for
generic bases, fmt cannot use strconv.Itoa because Itoa
does not offer uppercase digits (ABCDEF..).

Performance stats for the following program:

package main

import "fmt"
import "runtime/pprof"
import "os"
import "bufio"

func main() {
	f, _ := os.Create("print_buf.prof")
	pprof.StartCPUProfile(f)
	defer pprof.StopCPUProfile()

	b := bufio.NewWriter(os.Stdout)
	for i := 0; i < 1<<25; i++ {
		fmt.Fprintln(b, i)
	}
}

=========== Old =============================

	User time (seconds): 26.69
	System time (seconds): 5.31
	Percent of CPU this job got: 138%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:23.04

=========== New =============================

	User time (seconds): 14.84
	System time (seconds): 2.77
	Percent of CPU this job got: 141%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:12.43

[Leonhard Holz, 2014-09-17 13:02:52]

Hello golang-codereviews@googlegroups.com,

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

[bradfitz, 2014-09-17 18:42:45]

Instead of code duplication, you should investigate moving any necessary shared
code to a new internal package.

See
https://docs.google.com/a/golang.org/document/d/1e8kOo3r51b2BWtTs_1uADIA5djfX...

[Leonhard Holz, 2014-09-17 20:48:30]

On 2014/09/17 18:42:45, bradfitz wrote:
> Instead of code duplication, you should investigate moving any necessary
shared
> code to a new internal package.
> 
> See
>
https://docs.google.com/a/golang.org/document/d/1e8kOo3r51b2BWtTs_1uADIA5djfX...

I understand. So src/fmt/format.go could be moved to src/internal/fmt and so
used by src/fmt/print.go and src/strconv/*. But for me this looks like a larger
issue as the floating point methods have to be refactored too and there are more
instances of itoa mentioned in the paper.

So my proposal is to stick with the duplicated code for issue 3463 and open up a
new issue for refactoring number formating into an internal package. I can work
on it then.

[bradfitz, 2014-09-17 20:49:46]

Well, it's too late for Go 1.4 anyway, so you have plenty of time to do it
properly.


On Wed, Sep 17, 2014 at 4:48 PM, <leonhard.holz@googlemail.com> wrote:

> On 2014/09/17 18:42:45, bradfitz wrote:
>
>> Instead of code duplication, you should investigate moving any
>>
> necessary shared
>
>> code to a new internal package.
>>
>
>  See
>>
>
> https://docs.google.com/a/golang.org/document/d/1e8kOo3r51b2BWtTs_
> 1uADIA5djfXhPT36s6eHVRIvaU/edit
>
> I understand. So src/fmt/format.go could be moved to src/internal/fmt
> and so used by src/fmt/print.go and src/strconv/*. But for me this looks
> like a larger issue as the floating point methods have to be refactored
> too and there are more instances of itoa mentioned in the paper.
>
> So my proposal is to stick with the duplicated code for issue 3463 and
> open up a new issue for refactoring number formating into an internal
> package. I can work on it then.
>
> https://codereview.appspot.com/145020043/
>

[Leonhard Holz, 2014-09-18 05:42:43]

Can you give me some hints where the other itoa methods are?

On 2014/09/17 20:49:46, bradfitz wrote:
> Well, it's too late for Go 1.4 anyway, so you have plenty of time to do it
> properly.
> 
> 
> On Wed, Sep 17, 2014 at 4:48 PM, <mailto:leonhard.holz@googlemail.com> wrote:
> 
> > On 2014/09/17 18:42:45, bradfitz wrote:
> >
> >> Instead of code duplication, you should investigate moving any
> >>
> > necessary shared
> >
> >> code to a new internal package.
> >>
> >
> >  See
> >>
> >
> > https://docs.google.com/a/golang.org/document/d/1e8kOo3r51b2BWtTs_
> > 1uADIA5djfXhPT36s6eHVRIvaU/edit
> >
> > I understand. So src/fmt/format.go could be moved to src/internal/fmt
> > and so used by src/fmt/print.go and src/strconv/*. But for me this looks
> > like a larger issue as the floating point methods have to be refactored
> > too and there are more instances of itoa mentioned in the paper.
> >
> > So my proposal is to stick with the duplicated code for issue 3463 and
> > open up a new issue for refactoring number formating into an internal
> > package. I can work on it then.
> >
> > https://codereview.appspot.com/145020043/
> >

[bradfitz, 2014-09-19 03:26:28]

The tree is closed for changes like this for 3 months.  Please open a bug
if you want to make sure it's not forgotten. Otherwise bring this up again
in 3 months, after Go 1.4 is out.


On Wed, Sep 17, 2014 at 9:02 AM, <leonhard.holz@googlemail.com> wrote:

> Reviewers: golang-codereviews,
>
> Message:
> Hello golang-codereviews@googlegroups.com,
>
> I'd like you to review this change to
> https://code.google.com/p/go
>
>
> Description:
> fmt: Improved printing performance for integers.
>
> Related to issue 3463. The special casing for base10
> and base2^n is copied from strconv.Itoa().
>
> Of course this is code duplication which should be avoided
> but neither fmt nor strconv expose a usable interface to
> use the integer format routine of the other package. Itoa
> cannot use fmt.Sprint because there is no format string for
> generic bases, fmt cannot use strconv.Itoa because Itoa
> does not offer uppercase digits (ABCDEF..).
>
> Performance stats for the following program:
>
> package main
>
> import "fmt"
> import "runtime/pprof"
> import "os"
> import "bufio"
>
> func main() {
>         f, _ := os.Create("print_buf.prof")
>         pprof.StartCPUProfile(f)
>         defer pprof.StopCPUProfile()
>
>         b := bufio.NewWriter(os.Stdout)
>         for i := 0; i < 1<<25; i++ {
>                 fmt.Fprintln(b, i)
>         }
> }
>
> =========== Old =============================
>
>         User time (seconds): 26.69
>         System time (seconds): 5.31
>         Percent of CPU this job got: 138%
>         Elapsed (wall clock) time (h:mm:ss or m:ss): 0:23.04
>
> =========== New =============================
>
>         User time (seconds): 14.84
>         System time (seconds): 2.77
>         Percent of CPU this job got: 141%
>         Elapsed (wall clock) time (h:mm:ss or m:ss): 0:12.43
>
>
> Please review this at https://codereview.appspot.com/145020043/
>
> Affected files (+50, -5 lines):
>   M src/fmt/format.go
>
>
> Index: src/fmt/format.go
> ===================================================================
> --- a/src/fmt/format.go
> +++ b/src/fmt/format.go
> @@ -22,6 +22,8 @@
>  const (
>         signed   = true
>         unsigned = false
> +       digits01 = "012345678901234567890123456789
> 0123456789012345678901234567890123456789012345678901234567890123456789"
> +       digits10 = "000000000011111111112222222222
> 3333333333444444444455555555556666666666777777777788888888889999999999"
>  )
>
>  var padZeroBytes = make([]byte, nByte)
> @@ -154,6 +156,13 @@
>         }
>  }
>
> +var shifts = [16 + 1]uint{
> +       1 << 1: 1,
> +       1 << 2: 2,
> +       1 << 3: 3,
> +       1 << 4: 4,
> +}
> +
>  // integer; interprets prec but not wid.  Once formatted, result is sent
> to pad()
>  // and then flags are cleared.
>  func (f *fmt) integer(a int64, base uint64, signedness bool, digits
> string) {
> @@ -199,13 +208,49 @@
>         // block but it's not worth the duplication, so ua has 64 bits.
>         i := len(buf)
>         ua := uint64(a)
> -       for ua >= base {
> -               i--
> -               buf[i] = digits[ua%base]
> -               ua /= base
> +
> +       // convert bits
> +       if base == 10 {
> +               // common case: use constants for / and % because
> +               // the compiler can optimize it into a multiply+shift,
> +               // and unroll loop
> +               for ua >= 100 {
> +                       i -= 2
> +                       q := ua / 100
> +                       j := uintptr(ua - q*100)
> +                       buf[i+1] = digits01[j]
> +                       buf[i+0] = digits10[j]
> +                       ua = q
> +               }
> +               if ua >= 10 {
> +                       i--
> +                       q := ua / 10
> +                       buf[i] = digits[uintptr(ua-q*10)]
> +                       ua = q
> +               }
> +
> +       } else if s := shifts[base]; s > 0 {
> +               // base is power of 2: use shifts and masks instead of /
> and %
> +               m := uintptr(base) - 1 // == 1<<s - 1
> +               for ua >= base {
> +                       i--
> +                       buf[i] = digits[uintptr(ua)&m]
> +                       ua >>= s
> +               }
> +
> +       } else {
> +               // general case
> +               for ua >= base {
> +                       i--
> +                       buf[i] = digits[uintptr(ua%base)]
> +                       ua /= base
> +               }
>         }
> +
> +       // ua < base
>         i--
> -       buf[i] = digits[ua]
> +       buf[i] = digits[uintptr(ua)]
> +
>         for i > 0 && prec > len(buf)-i {
>                 i--
>                 buf[i] = '0'
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "golang-codereviews" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-codereviews+unsubscribe@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>

[bradfitz, 2014-09-29 19:29:55]

R=close

Addressed recently by r@ in
https://code.google.com/p/go/source/detail?r=f0cbfc3381c4

changeset:   21260:f0cbfc3381c4
user:        Rob Pike <r@golang.org>
date:        Mon Sep 22 11:58:15 2014 -0700
summary:     fmt: make printing of ints 25-35% faster