Skip to content

G
go
Switch branch/tag
  1. 08 Sep, 2017 5 commits
    • Josh Bleecher Snyder's avatar
      math/rand: make Perm match Shuffle · caae0917
      Josh Bleecher Snyder authored 
      Perm and Shuffle are fundamentally doing the same work.
This change makes Perm's algorithm match Shuffle's.
In addition to allowing developers to switch more
easily between the two methods, it affords a nice speed-up:

name      old time/op  new time/op  delta
Perm3-8   75.7ns ± 1%  51.8ns ± 1%  -31.59%  (p=0.000 n=9+8)
Perm30-8   610ns ± 1%   405ns ± 1%  -33.67%  (p=0.000 n=9+9)

This change alters the output from Perm,
given the same Source and seed.
This is a change from Go 1.0 behavior.
This necessitates updating the regression test.

This also changes the number of calls made to the Source
during Perm, which changes the output of the math/rand examples.

This also slightly perturbs the output of Perm,
nudging it out of the range currently accepted by TestUniformFactorial.
However, it is complete unclear that the helpers relied on
by TestUniformFactorial are correct. That is #21211.
This change updates checkSimilarDistribution to respect
closeEnough for standard deviations, which makes the test pass.
The whole situation is muddy; see #21211 for details.

There is an alternative implementation of Perm
that avoids initializing m, which is more similar
to the existing implementation, plus some optimizations:

func (r *Rand) Perm(n int) []int {
	m := make([]int, n)
	max31 := n
	if n > 1<<31-1-1 {
		max31 = 1<<31 - 1 - 1
	}
	i := 1
	for ; i < max31; i++ {
		j := r.int31n(int32(i + 1))
		m[i] = m[j]
		m[j] = i
	}
	for ; i < n; i++ {
		j := r.Int63n(int64(i + 1))
		m[i] = m[j]
		m[j] = i
	}
	return m
}

This is a tiny bit faster than the implementation
actually used in this change:

name      old time/op  new time/op  delta
Perm3-8   51.8ns ± 1%  50.3ns ± 1%  -2.83%  (p=0.000 n=8+9)
Perm30-8   405ns ± 1%   394ns ± 1%  -2.66%  (p=0.000 n=9+8)

However, 3% in performance doesn't seem worth
having the two algorithms diverge,
nor the reduced readability of this alternative.

Updates #16213.

Change-Id: I11a7441ff8837ee9c241b4c88f7aa905348be781
Reviewed-on: https://go-review.googlesource.com/55972
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: default avatarRob Pike <r@golang.org>
      caae0917
    • Josh Bleecher Snyder's avatar
      math/rand: add Shuffle · a2dfe5d2
      Josh Bleecher Snyder authored 
      Shuffle uses the Fisher-Yates algorithm.

Since this is new API, it affords us the opportunity
to use a much faster Int31n implementation that mostly avoids division.
As a result, BenchmarkPerm30ViaShuffle is
about 30% faster than BenchmarkPerm30,
despite requiring a separate initialization loop
and using function calls to swap elements.

Fixes #20480
Updates #16213
Updates #21211

Change-Id: Ib8956c4bebed9d84f193eb98282ec16ee7c2b2d5
Reviewed-on: https://go-review.googlesource.com/51891
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: default avatarIan Lance Taylor <iant@golang.org>
      a2dfe5d2
    • Cholerae Hu's avatar
      time: don't match '---' month in time.Parse · 32e117d9
      Cholerae Hu authored 
      The existing implementation will panic when month in date string is '---'.

Fixed #21113

Change-Id: I8058ae7a4102e882f8b7e9c65d80936b563265e4
Reviewed-on: https://go-review.googlesource.com/51010
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: default avatarIan Lance Taylor <iant@golang.org>
      32e117d9
    • Mayank Kumar's avatar
      path: add path.Dir example with trailing slash · a323656b
      Mayank Kumar authored 
      Change-Id: I143203a9dcf9a4da0e53a3aab6e370244b849296
Reviewed-on: https://go-review.googlesource.com/62270
Run-TryBot: Ian Lance Taylor <iant@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: default avatarIan Lance Taylor <iant@golang.org>
      a323656b
    • Kunpei Sakai's avatar
      net/http: make ServeMux preserve query string during redirects · ab401077
      Kunpei Sakai authored 
      Ensure that the implicitly created redirect
for
  "/route"
after
  "/route/"
has been registered doesn't lose the query string information.
A previous attempt (https://golang.org/cl/43779) changed http.Redirect, however, that change broke direct calls to http.Redirect.
To avoid that problem, this change touches ServeMux.Handler only.

Fixes #17841

Change-Id: I303c1b1824615304ae68147e254bb41b0ea339be
Reviewed-on: https://go-review.googlesource.com/61210
Run-TryBot: Emmanuel Odeke <emm.odeke@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: default avatarTom Bergan <tombergan@google.com>
Reviewed-by: default avatarEmmanuel Odeke <emm.odeke@gmail.com>
      ab401077
  3. 07 Sep, 2017 5 commits
  5. 06 Sep, 2017 13 commits
  7. 05 Sep, 2017 7 commits
  9. 04 Sep, 2017 1 commit
  11. 03 Sep, 2017 4 commits
  13. 02 Sep, 2017 2 commits
    • Mark Pulford's avatar
      math: Add Round function (ties away from zero) · 03c3bb5f
      Mark Pulford authored 
      This function avoids subtle faults found in many ad-hoc implementations,
and is simple enough to be inlined by the compiler.

Fixes #20100

Change-Id: Ib320254e9b1f1f798c6ef906b116f63bc29e8d08
Reviewed-on: https://go-review.googlesource.com/43652Reviewed-by: default avatarRobert Griesemer <gri@golang.org>
      03c3bb5f
    • Keith Randall's avatar
      runtime: fix hashmap load factor computation · dbe3522c
      Keith Randall authored 
      overLoadFactor wasn't really doing what it says it does.
It was reporting overOrEqualToLoadFactor.  That's actually what we
want when adding an entry to a map, but it isn't what we want when
constructing a map in the first place.

The impetus for this change is that if you make a map with a hint
of exactly 8 (which happens, for example, with the unitMap in
time/format.go), we allocate 2 buckets for it instead of 1.

Instead, make overLoadFactor really report when it is > the max
allowed load factor, not >=.  Adjust the callers who want to ensure
that the map is no more than the max load factor after an insertion
by adding a +1 to the current (pre-addition) size.

Change-Id: Ie8d85344800a9a870036b637b1031ddd9e4b93f9
Reviewed-on: https://go-review.googlesource.com/61053
Run-TryBot: Keith Randall <khr@golang.org>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: default avatarMartin Möhrmann <moehrmann@google.com>
      dbe3522c
  15. 01 Sep, 2017 3 commits
GitLab Nexedi Edition | About GitLab | About Nexedi | 沪ICP备2021021310号-2 | 沪ICP备2021021310号-7