changeset 2469:1312953defab octree-diff

Do difference calculation multi-core.
author Sascha L. Teichmann <sascha.teichmann@intevation.de>
date Mon, 25 Feb 2019 23:43:41 +0100
parents 27cc04bbda46
children 5bd3236f2b1f
files cmd/octreediff/main.go
diffstat 1 files changed, 126 insertions(+), 15 deletions(-) [+]
line wrap: on
line diff
--- a/cmd/octreediff/main.go	Mon Feb 25 21:51:39 2019 +0100
+++ b/cmd/octreediff/main.go	Mon Feb 25 23:43:41 2019 +0100
@@ -49,6 +49,74 @@
 	}
 }
 
+func sliceWork(
+	vs []octree.Vertex,
+	fn func([]octree.Vertex, func([]octree.Vertex) []octree.Vertex),
+) []octree.Vertex {
+
+	n := runtime.NumCPU()
+
+	wg := new(sync.WaitGroup)
+
+	slices := make(chan []octree.Vertex)
+	out := make(chan []octree.Vertex)
+
+	pool := make(chan []octree.Vertex, n)
+
+	const pageSize = 2048
+
+	turn := func(p []octree.Vertex) []octree.Vertex {
+		if p != nil {
+			out <- p
+		}
+		select {
+		case p = <-pool:
+		default:
+			p = make([]octree.Vertex, 0, pageSize)
+		}
+		return p
+	}
+
+	for i := 0; i < n; i++ {
+		wg.Add(1)
+		go func() {
+			defer wg.Done()
+			for slice := range slices {
+				fn(slice, turn)
+			}
+		}()
+	}
+	nvs := make([]octree.Vertex, 0, len(vs))
+	done := make(chan struct{})
+	go func() {
+		defer close(done)
+		for ns := range out {
+			nvs = append(nvs, ns...)
+			select {
+			case pool <- ns[:0:pageSize]:
+			default:
+			}
+		}
+	}()
+
+	size := len(vs)/n + 1
+	for len(vs) > 0 {
+		var l int
+		if len(vs) < size {
+			l = len(vs)
+		} else {
+			l = size
+		}
+		slices <- vs[:l]
+		vs = vs[l:]
+	}
+	close(slices)
+	wg.Wait()
+	close(out)
+	<-done
+	return nvs
+}
+
 func process(bottleneck string, firstDate, secondDate time.Time) error {
 	start := time.Now()
 	defer func() { log.Printf("processing took %v\n", time.Since(start)) }()
@@ -132,23 +200,66 @@
 
 		setin := time.Now()
 
-		vf := first.Vertices()
-		nvf := make([]octree.Vertex, 0, len(vf))
-		for i := range vf {
-			v := &vf[i]
-			if z, found := second.Value(v.X, v.Y); found {
-				nvf = append(nvf, octree.Vertex{v.X, v.Y, v.Z - z})
-			}
-		}
+		nvf := sliceWork(
+			first.Vertices(),
+			func(
+				slice []octree.Vertex,
+				turn func([]octree.Vertex) []octree.Vertex,
+			) {
+				p := turn(nil)
+				for i := range slice {
+					v := &slice[i]
+					if z, found := second.Value(v.X, v.Y); found {
+						p = append(p, octree.Vertex{v.X, v.Y, v.Z - z})
+						if len(p) == cap(p) {
+							p = turn(p)
+						}
+					}
+				}
+				if len(p) > 0 {
+					turn(p)
+				}
+			})
 
-		vs := second.Vertices()
-		nsf := make([]octree.Vertex, 0, len(vs))
-		for i := range vs {
-			v := &vs[i]
-			if z, found := first.Value(v.X, v.Y); found {
-				nsf = append(nsf, octree.Vertex{v.X, v.Y, z - v.Z})
+		nsf := sliceWork(
+			second.Vertices(),
+			func(
+				slice []octree.Vertex,
+				turn func([]octree.Vertex) []octree.Vertex,
+			) {
+				p := turn(nil)
+				for i := range slice {
+					v := &slice[i]
+					if z, found := first.Value(v.X, v.Y); found {
+						p = append(p, octree.Vertex{v.X, v.Y, z - v.Z})
+						if len(p) == cap(p) {
+							p = turn(p)
+						}
+					}
+				}
+				if len(p) > 0 {
+					turn(p)
+				}
+			})
+
+		/*
+			vf := first.Vertices()
+			nvf := make([]octree.Vertex, 0, len(vf))
+			for i := range vf {
+				v := &vf[i]
+				if z, found := second.Value(v.X, v.Y); found {
+					nvf = append(nvf, octree.Vertex{v.X, v.Y, v.Z - z})
+				}
 			}
-		}
+			vs := second.Vertices()
+			nsf := make([]octree.Vertex, 0, len(vs))
+			for i := range vs {
+				v := &vs[i]
+				if z, found := first.Value(v.X, v.Y); found {
+					nsf = append(nsf, octree.Vertex{v.X, v.Y, z - v.Z})
+				}
+			}
+		*/
 
 		log.Printf("setting in took %v\n", time.Since(setin))
 		log.Printf("new vertices first: %d\n", len(nvf))