Repository: gonum/gonum
Pull request #1587 (2021-03-16 23:09:25)

graph/flow: improve consistency of coverage reports
Please take a look.

The background to this is that we regularly see graph/flow/control_flow\*.go files, and occasionally optimize/listsearch.go, in the codecov reports as having changed. This is due to algorithmic randomness that shows up in those files. In the case of graph/flow it is due to map iteration order. So the approach is just to increase the number of times the tests are run to decrease the probability of having a test ensemble that does not hit possible lines at least once.

This PR does not address the effect that we see in optimize/listsearch.go, but I'm unable to see how that comes in. I suspect it's from concurrency racing in the algorithm, but it's low enough frequency that I don't see it when I repeatedly run coverage tests. I'll look again if it continues to be a problem.

<!--
Checklist:

- API changes have been discussed
- code is goformated correctly (goimports)
- packages with generated code have had code generation run
- tests pass locally
- linked to relevant issues

Please make sure your commit message summary line and pull request
title match the Go convention; a one-line summary of the change,
prefixed by the primary affected package that should complete the
sentence, "This change modifies Gonum to _____."
-->


codecov-io: # [Codecov](https://codecov.io/gh/gonum/gonum/pull/1587?src=pr&el=h1) Report
> Merging [#1587](https://codecov.io/gh/gonum/gonum/pull/1587?src=pr&el=desc) (e616dfe) into [master](https://codecov.io/gh/gonum/gonum/commit/a6ddba7f8db212e57ac2164ec4592a502d00b5cf?el=desc) (a6ddba7) will **not change** coverage.
> The diff coverage is `n/a`.

> :exclamation: Current head e616dfe differs from pull request most recent head 3eb9cb6. Consider uploading reports for the commit 3eb9cb6 to get more accurate results
[![Impacted file tree graph](https://codecov.io/gh/gonum/gonum/pull/1587/graphs/tree.svg?width=650&height=150&src=pr&token=B7qHnqSPNL)](https://codecov.io/gh/gonum/gonum/pull/1587?src=pr&el=tree)

```diff
@@           Coverage Diff           @@
##           master    #1587   +/-   ##
=======================================
  Coverage   72.70%   72.70%           
=======================================
  Files         481      481           
  Lines       57968    57968           
=======================================
  Hits        42145    42145           
  Misses      13426    13426           
  Partials     2397     2397           
```



------

[Continue to review full report at Codecov](https://codecov.io/gh/gonum/gonum/pull/1587?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/gonum/gonum/pull/1587?src=pr&el=footer). Last update [a6ddba7...3eb9cb6](https://codecov.io/gh/gonum/gonum/pull/1587?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

kortschak: *ping*

Patch:
diff --git a/AUTHORS b/AUTHORS
index a8b1d7e2..2befdaeb 100644
--- a/AUTHORS
+++ b/AUTHORS
@@ -54,7 +54,7 @@ Jonas Schulze <jonas.schulze@ovgu.de>
 Jonathan J Lawlor <jonathan.lawlor@gmail.com>
 Jonathan Reiter <jonreiter@gmail.com>
 Jonathan Schroeder <jd.schroeder@gmail.com>
-Joost van Amersfoort <hi@joo.st>
+Joost van Amersfoort <git@joo.st>
 Joseph Watson <jtwatson@linux-consulting.us>
 Josh Wilson <josh.craig.wilson@gmail.com>
 Julien Roland <juroland@gmail.com>
diff --git a/CONTRIBUTORS b/CONTRIBUTORS
index c62b5da2..5be7e420 100644
--- a/CONTRIBUTORS
+++ b/CONTRIBUTORS
@@ -62,7 +62,7 @@ Jonas Schulze <jonas.schulze@ovgu.de>
 Jonathan J Lawlor <jonathan.lawlor@gmail.com>
 Jonathan Reiter <jonreiter@gmail.com>
 Jonathan Schroeder <jd.schroeder@gmail.com>
-Joost van Amersfoort <hi@joo.st>
+Joost van Amersfoort <git@joo.st>
 Joseph Watson <jtwatson@linux-consulting.us>
 Josh Wilson <josh.craig.wilson@gmail.com>
 Julien Roland <juroland@gmail.com>
diff --git a/graph/traverse/traverse.go b/graph/traverse/traverse.go
index 125b1611..2a4efb66 100644
--- a/graph/traverse/traverse.go
+++ b/graph/traverse/traverse.go
@@ -160,32 +160,27 @@ func (d *DepthFirst) Walk(g Graph, from graph.Node, until func(graph.Node) bool)
 		d.visited = make(set.Int64s)
 	}
 	d.stack.Push(from)
-	if d.Visit != nil && !d.visited.Has(from.ID()) {
-		d.Visit(from)
-	}
-	d.visited.Add(from.ID())
-
-	for d.stack.Len() > 0 {
-		t := d.stack.Pop()
-		if until != nil && until(t) {
-			return t
+	for d.stack.Len() != 0 {
+		u := d.stack.Pop()
+		uid := u.ID()
+		if d.visited.Has(uid) {
+			continue
 		}
-		tid := t.ID()
-		to := g.From(tid)
+		d.visited.Add(uid)
+		if d.Visit != nil {
+			d.Visit(u)
+		}
+		if until != nil && until(u) {
+			return u
+		}
+		to := g.From(uid)
 		for to.Next() {
-			n := to.Node()
-			nid := n.ID()
-			if d.Traverse != nil && !d.Traverse(g.Edge(tid, nid)) {
+			v := to.Node()
+			vid := v.ID()
+			if d.Traverse != nil && !d.Traverse(g.Edge(uid, vid)) {
 				continue
 			}
-			if d.visited.Has(nid) {
-				continue
-			}
-			if d.Visit != nil {
-				d.Visit(n)
-			}
-			d.visited.Add(nid)
-			d.stack.Push(n)
+			d.stack.Push(v)
 		}
 	}
 
diff --git a/internal/asm/f32/stubs_amd64.go b/internal/asm/f32/stubs_amd64.go
index 276377d5..1b3b70c0 100644
--- a/internal/asm/f32/stubs_amd64.go
+++ b/internal/asm/f32/stubs_amd64.go
@@ -66,3 +66,11 @@ func DotUnitary(x, y []float32) (sum float32)
 //  }
 //  return sum
 func DotInc(x, y []float32, n, incX, incY, ix, iy uintptr) (sum float32)
+
+// Sum is
+//  var sum float32
+//  for _, v := range x {
+// 		sum += v
+//  }
+//  return sum
+func Sum(x []float32) float32
diff --git a/internal/asm/f32/stubs_noasm.go b/internal/asm/f32/stubs_noasm.go
index e8571953..17ab71f6 100644
--- a/internal/asm/f32/stubs_noasm.go
+++ b/internal/asm/f32/stubs_noasm.go
@@ -111,3 +111,17 @@ func DdotInc(x, y []float32, n, incX, incY, ix, iy uintptr) (sum float64) {
 	}
 	return
 }
+
+// Sum is
+//  var sum float32
+//  for _, v := range x {
+//  	sum += v
+//  }
+//  return sum
+func Sum(x []float32) float32 {
+	var sum float32
+	for _, v := range x {
+		sum += v
+	}
+	return sum
+}
diff --git a/internal/asm/f32/sum_amd64.s b/internal/asm/f32/sum_amd64.s
new file mode 100644
index 00000000..42e96361
--- /dev/null
+++ b/internal/asm/f32/sum_amd64.s
@@ -0,0 +1,100 @@
+// Copyright ©2021 The Gonum Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+// +build !noasm,!gccgo,!safe
+
+#include "textflag.h"
+
+#define X_PTR SI
+#define IDX AX
+#define LEN CX
+#define TAIL BX
+#define SUM X0
+#define SUM_1 X1
+#define SUM_2 X2
+#define SUM_3 X3
+
+// func Sum(x []float32) float32
+TEXT ·Sum(SB), NOSPLIT, $0
+	MOVQ x_base+0(FP), X_PTR // X_PTR = &x
+	MOVQ x_len+8(FP), LEN    // LEN = len(x)
+	XORQ IDX, IDX            // i = 0
+	PXOR SUM, SUM            // p_sum_i = 0
+	CMPQ LEN, $0             // if LEN == 0 { return 0 }
+	JE   sum_end
+
+	PXOR SUM_1, SUM_1
+	PXOR SUM_2, SUM_2
+	PXOR SUM_3, SUM_3
+
+	MOVQ X_PTR, TAIL // Check memory alignment
+	ANDQ $15, TAIL   // TAIL = &x % 16
+	JZ   no_trim     // if TAIL == 0 { goto no_trim }
+	SUBQ $16, TAIL   // TAIL -= 16
+
+sum_align: // Align on 16-byte boundary do {
+	ADDSS (X_PTR)(IDX*4), SUM // SUM += x[0]
+	INCQ  IDX                 // i++
+	DECQ  LEN                 // LEN--
+	JZ    sum_end             // if LEN == 0 { return }
+	ADDQ  $4, TAIL            // TAIL += 4
+	JNZ   sum_align           // } while TAIL < 0
+
+no_trim:
+	MOVQ LEN, TAIL
+	SHRQ $4, LEN   // LEN = floor( n / 16 )
+	JZ   sum_tail8 // if LEN == 0 { goto sum_tail8 }
+
+
+sum_loop: // sum 16x wide do {
+	ADDPS (X_PTR)(IDX*4), SUM     // sum_i += x[i:i+4]
+	ADDPS 16(X_PTR)(IDX*4), SUM_1
+	ADDPS 32(X_PTR)(IDX*4), SUM_2
+	ADDPS 48(X_PTR)(IDX*4), SUM_3
+
+	ADDQ  $16, IDX                // i += 16
+	DECQ  LEN
+	JNZ   sum_loop                // } while --LEN > 0
+
+sum_tail8:
+	ADDPS SUM_3, SUM
+	ADDPS SUM_2, SUM_1
+
+	TESTQ $8, TAIL
+	JZ    sum_tail4
+
+	ADDPS (X_PTR)(IDX*4), SUM // sum_i += x[i:i+4]
+	ADDPS 16(X_PTR)(IDX*4), SUM_1
+	ADDQ  $8, IDX
+
+sum_tail4:
+	ADDPS SUM_1, SUM
+
+	TESTQ $4, TAIL
+	JZ    sum_tail2
+
+	ADDPS (X_PTR)(IDX*4), SUM // sum_i += x[i:i+4]
+	ADDQ  $4, IDX
+
+sum_tail2:
+	HADDPS SUM, SUM            // sum_i[:2] += sum_i[2:4]
+
+	TESTQ $2, TAIL
+	JZ    sum_tail1
+
+	MOVSD (X_PTR)(IDX*4), SUM_1 // reuse SUM_1
+	ADDPS SUM_1, SUM            // sum_i += x[i:i+2]
+	ADDQ  $2, IDX
+
+sum_tail1:
+	HADDPS SUM, SUM // sum_i[0] += sum_i[1]
+
+	TESTQ $1, TAIL
+	JZ    sum_end
+
+	ADDSS (X_PTR)(IDX*4), SUM
+
+sum_end: // return sum
+	MOVSS SUM, ret+24(FP)
+	RET


Test patch:
diff --git a/graph/flow/control_flow_test.go b/graph/flow/control_flow_test.go
index d053ea66..3abd211a 100644
--- a/graph/flow/control_flow_test.go
+++ b/graph/flow/control_flow_test.go
@@ -132,53 +132,60 @@ func (n char) ID() int64      { return int64(n) }
 func (n char) String() string { return string(n) }
 
 func TestDominators(t *testing.T) {
-	for _, test := range dominatorsTests {
-		g := simple.NewDirectedGraph()
-		for _, e := range test.edges {
-			g.SetEdge(e)
-		}
-
-		for _, alg := range []struct {
-			name string
-			fn   func(graph.Node, graph.Directed) DominatorTree
-		}{
-			{"Dominators", Dominators},
-			{"DominatorsSLT", DominatorsSLT},
-		} {
-			got := alg.fn(test.n, g)
-
-			if !reflect.DeepEqual(got.Root(), test.want.root) {
-				t.Errorf("unexpected dominator tree root from %s: got:%v want:%v",
-					alg.name, got.root, test.want.root)
+	// The dominator functions are non-deterministic due
+	// to map iteration ordering, so repeat the tests to
+	// ensure consistent coverage. The value of 100 was
+	// chosen empirically to have no observed reduction
+	// in coverage in several hundred runs of go test -cover.
+	for i := 0; i < 100; i++ {
+		for _, test := range dominatorsTests {
+			g := simple.NewDirectedGraph()
+			for _, e := range test.edges {
+				g.SetEdge(e)
 			}
 
-			if !reflect.DeepEqual(got.dominatorOf, test.want.dominatorOf) {
-				t.Errorf("unexpected dominator tree from %s: got:%v want:%v",
-					alg.name, got.dominatorOf, test.want.dominatorOf)
-			}
+			for _, alg := range []struct {
+				name string
+				fn   func(graph.Node, graph.Directed) DominatorTree
+			}{
+				{"Dominators", Dominators},
+				{"DominatorsSLT", DominatorsSLT},
+			} {
+				got := alg.fn(test.n, g)
+
+				if !reflect.DeepEqual(got.Root(), test.want.root) {
+					t.Errorf("unexpected dominator tree root from %s: got:%v want:%v",
+						alg.name, got.root, test.want.root)
+				}
 
-			for q, want := range test.want.dominatorOf {
-				node := got.DominatorOf(q)
-				if node != want {
-					t.Errorf("unexpected dominator tree result from %s dominated of %v: got:%v want:%v",
-						alg.name, q, node, want)
+				if !reflect.DeepEqual(got.dominatorOf, test.want.dominatorOf) {
+					t.Errorf("unexpected dominator tree from %s: got:%v want:%v",
+						alg.name, got.dominatorOf, test.want.dominatorOf)
 				}
-			}
 
-			for _, nodes := range got.dominatedBy {
-				sort.Sort(ordered.ByID(nodes))
-			}
+				for q, want := range test.want.dominatorOf {
+					node := got.DominatorOf(q)
+					if node != want {
+						t.Errorf("unexpected dominator tree result from %s dominated of %v: got:%v want:%v",
+							alg.name, q, node, want)
+					}
+				}
 
-			if !reflect.DeepEqual(got.dominatedBy, test.want.dominatedBy) {
-				t.Errorf("unexpected dominator tree from %s: got:%v want:%v",
-					alg.name, got.dominatedBy, test.want.dominatedBy)
-			}
+				for _, nodes := range got.dominatedBy {
+					sort.Sort(ordered.ByID(nodes))
+				}
+
+				if !reflect.DeepEqual(got.dominatedBy, test.want.dominatedBy) {
+					t.Errorf("unexpected dominator tree from %s: got:%v want:%v",
+						alg.name, got.dominatedBy, test.want.dominatedBy)
+				}
 
-			for q, want := range test.want.dominatedBy {
-				nodes := got.DominatedBy(q)
-				if !reflect.DeepEqual(nodes, want) {
-					t.Errorf("unexpected dominator tree result from %s dominated by %v: got:%v want:%v",
-						alg.name, q, nodes, want)
+				for q, want := range test.want.dominatedBy {
+					nodes := got.DominatedBy(q)
+					if !reflect.DeepEqual(nodes, want) {
+						t.Errorf("unexpected dominator tree result from %s dominated by %v: got:%v want:%v",
+							alg.name, q, nodes, want)
+					}
 				}
 			}
 		}
diff --git a/graph/traverse/traverse_test.go b/graph/traverse/traverse_test.go
index 135e98b4..7d08fc25 100644
--- a/graph/traverse/traverse_test.go
+++ b/graph/traverse/traverse_test.go
@@ -8,6 +8,7 @@ import (
 	"fmt"
 	"reflect"
 	"sort"
+	"strings"
 	"testing"
 
 	"gonum.org/v1/gonum/graph"
@@ -55,6 +56,16 @@ var (
 		4: nil,
 		5: nil,
 	}
+
+	// g1595 is the graph shown in https://github.com/gonum/gonum/issues/1595 with the addition
+	// of an unconnected 0 node (due to limitations of intset).
+	g1595 = []intset{
+		0: nil,
+		1: linksTo(2, 4),
+		2: linksTo(3),
+		3: nil,
+		4: nil,
+	}
 )
 
 var breadthFirstTests = []struct {
@@ -158,13 +169,13 @@ func TestBreadthFirst(t *testing.T) {
 			return false
 		})
 		if !test.final[final] {
-			t.Errorf("unexepected final node for test %d:\ngot:  %v\nwant: %v", i, final, test.final)
+			t.Errorf("unexpected final node for test %d:\ngot:  %v\nwant: %v", i, final, test.final)
 		}
 		for _, l := range got {
 			sort.Sort(ordered.Int64s(l))
 		}
 		if !reflect.DeepEqual(got, test.want) {
-			t.Errorf("unexepected BFS level structure for test %d:\ngot:  %v\nwant: %v", i, got, test.want)
+			t.Errorf("unexpected BFS level structure for test %d:\ngot:  %v\nwant: %v", i, got, test.want)
 		}
 	}
 }
@@ -175,13 +186,22 @@ var depthFirstTests = []struct {
 	edge  func(graph.Edge) bool
 	until func(graph.Node) bool
 	final map[graph.Node]bool
-	want  []int64
+	want  [][]int64
 }{
 	{
 		g:     wpBronKerboschGraph,
 		from:  simple.Node(1),
 		final: map[graph.Node]bool{nil: true},
-		want:  []int64{0, 1, 2, 3, 4, 5},
+		want: [][]int64{
+			{1, 0, 4, 3, 5, 2},
+			{1, 0, 4, 3, 2, 5},
+			{1, 2, 3, 4, 0, 5},
+			{1, 2, 3, 5, 4, 0},
+			{1, 4, 0, 3, 5, 2},
+			{1, 4, 0, 3, 2, 5},
+			{1, 4, 3, 2, 5, 0},
+			{1, 4, 3, 5, 2, 0},
+		},
 	},
 	{
 		g: wpBronKerboschGraph,
@@ -191,7 +211,12 @@ var depthFirstTests = []struct {
 		},
 		from:  simple.Node(1),
 		final: map[graph.Node]bool{nil: true},
-		want:  []int64{0, 1, 2, 3, 4},
+		want: [][]int64{
+			{1, 0, 4, 3, 2},
+			{1, 2, 3, 4, 0},
+			{1, 4, 0, 3, 2},
+			{1, 4, 3, 2, 0},
+		},
 	},
 	{
 		g:     wpBronKerboschGraph,
@@ -203,19 +228,26 @@ var depthFirstTests = []struct {
 		g:     batageljZaversnikGraph,
 		from:  simple.Node(0),
 		final: map[graph.Node]bool{nil: true},
-		want:  []int64{0},
+		want:  [][]int64{{0}},
 	},
 	{
 		g:     batageljZaversnikGraph,
 		from:  simple.Node(3),
 		final: map[graph.Node]bool{nil: true},
-		want:  []int64{1, 2, 3, 4, 5},
+		want: [][]int64{
+			{3, 1, 2, 4, 5},
+			{3, 4, 2, 1, 5},
+			{3, 4, 5, 2, 1},
+		},
 	},
 	{
-		g:     batageljZaversnikGraph,
-		from:  simple.Node(13),
+		g:     g1595,
+		from:  simple.Node(1),
 		final: map[graph.Node]bool{nil: true},
-		want:  []int64{6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20},
+		want: [][]int64{
+			{1, 4, 2, 3},
+			{1, 2, 3, 4},
+		},
 	},
 }
 
@@ -243,11 +275,21 @@ func TestDepthFirst(t *testing.T) {
 			return false
 		})
 		if !test.final[final] {
-			t.Errorf("unexepected final node for test %d:\ngot:  %v\nwant: %v", i, final, test.final)
+			t.Errorf("unexpected final node for test %d:\ngot:  %v\nwant: %v", i, final, test.final)
 		}
-		sort.Sort(ordered.Int64s(got))
-		if test.want != nil && !reflect.DeepEqual(got, test.want) {
-			t.Errorf("unexepected DFS traversed nodes for test %d:\ngot:  %v\nwant: %v", i, got, test.want)
+		var ok bool
+		for _, want := range test.want {
+			if reflect.DeepEqual(got, want) {
+				ok = true
+				break
+			}
+		}
+		if test.want != nil && !ok {
+			var wanted strings.Builder
+			for _, w := range test.want {
+				fmt.Fprintf(&wanted, "     %v\n", w)
+			}
+			t.Errorf("unexpected DFS traversed nodes for test %d:\ngot: %v\nwant one of:\n%s", i, got, &wanted)
 		}
 	}
 }
diff --git a/internal/asm/f32/stubs_test.go b/internal/asm/f32/stubs_test.go
index 18990fc5..6aae9835 100644
--- a/internal/asm/f32/stubs_test.go
+++ b/internal/asm/f32/stubs_test.go
@@ -150,3 +150,65 @@ func TestAxpyIncTo(t *testing.T) {
 		checkValidIncGuard(t, v.dst, 0, int(v.incDst), gdLn)
 	}
 }
+
+func TestSum(t *testing.T) {
+	var srcGd float32 = -1
+	for j, v := range []struct {
+		src    []float32
+		expect float32
+	}{
+		{
+			src:    []float32{},
+			expect: 0,
+		},
+		{
+			src:    []float32{1},
+			expect: 1,
+		},
+		{
+			src:    []float32{nan},
+			expect: nan,
+		},
+		{
+			src:    []float32{1, 2, 3},
+			expect: 6,
+		},
+		{
+			src:    []float32{1, -4, 3},
+			expect: 0,
+		},
+		{
+			src:    []float32{1, 2, 3, 4},
+			expect: 10,
+		},
+		{
+			src:    []float32{1, 1, nan, 1, 1},
+			expect: nan,
+		},
+		{
+			src:    []float32{inf, 4, nan, -inf, 9},
+			expect: nan,
+		},
+		{
+			src:    []float32{1, 1, 1, 1, 9, 1, 1, 1, 2, 1, 1, 1, 1, 1, 5, 1},
+			expect: 29,
+		},
+		{
+			src:    []float32{1, 1, 1, 1, 9, 1, 1, 1, 2, 1, 1, 1, 1, 1, 5, 11, 1, 1, 1, 9, 1, 1, 1, 2, 1, 1, 1, 1, 1, 5, 1},
+			expect: 67,
+		},
+	} {
+		for _, i := range [4]int{0, 1, 2, 3} {
+			gdLn := 4 + j%4 + i
+			gsrc := guardVector(v.src, srcGd, gdLn)
+			src := gsrc[gdLn : len(gsrc)-gdLn]
+			ret := Sum(src)
+			if !same(ret, v.expect) {
+				t.Errorf("Test %d Sum error Got: %v Expected: %v", j, ret, v.expect)
+			}
+			if !isValidGuard(gsrc, srcGd, gdLn) {
+				t.Errorf("Test %d Guard violated in src vector %v %v", j, gsrc[:gdLn], gsrc[len(gsrc)-gdLn:])
+			}
+		}
+	}
+}