Mercurial > gemma
changeset 5682:33499bd1b829 sr-v2
Sort indices in spatial index.
author | Sascha L. Teichmann <sascha.teichmann@intevation.de> |
---|---|
date | Sun, 11 Feb 2024 21:26:22 +0100 |
parents | c09d55e9f098 |
children | 31973f6f5cca |
files | pkg/mesh/meshserialize_v2.go pkg/mesh/strtree.go |
diffstat | 2 files changed, 39 insertions(+), 16 deletions(-) [+] |
line wrap: on
line diff
--- a/pkg/mesh/meshserialize_v2.go Sun Feb 11 18:44:03 2024 +0100 +++ b/pkg/mesh/meshserialize_v2.go Sun Feb 11 21:26:22 2024 +0100 @@ -16,6 +16,7 @@ func (s *STRTree) optimizeForSerializationV2() { s.removeUnusedTriangles() // TODO: Implement me! + s.sortIndices() } // removeUnusedTriangles removes all triangles from the
--- a/pkg/mesh/strtree.go Sun Feb 11 18:44:03 2024 +0100 +++ b/pkg/mesh/strtree.go Sun Feb 11 21:26:22 2024 +0100 @@ -14,8 +14,9 @@ package mesh import ( + "cmp" "math" - "sort" + "slices" ) // STRTreeDefaultEntries is the default number of children per node and leaf. @@ -265,10 +266,10 @@ } func (s *STRTree) build(items []int32) int32 { - sort.Slice(items, func(i, j int) bool { - ti := s.tin.Triangles[items[i]] - tj := s.tin.Triangles[items[j]] - return s.tin.Vertices[ti[0]].X < s.tin.Vertices[tj[0]].X + slices.SortFunc(items, func(i, j int32) int { + ti := s.tin.Triangles[i] + tj := s.tin.Triangles[j] + return cmp.Compare(s.tin.Vertices[ti[0]].X, s.tin.Vertices[tj[0]].X) }) P := int(math.Ceil(float64(len(items)) / float64(s.Entries))) @@ -278,10 +279,10 @@ leaves := s.strJoin( slices, S, - func(i, j int32) bool { + func(i, j int32) int { ti := s.tin.Triangles[i] tj := s.tin.Triangles[j] - return s.tin.Vertices[ti[0]].Y < s.tin.Vertices[tj[0]].Y + return cmp.Compare(s.tin.Vertices[ti[0]].Y, s.tin.Vertices[tj[0]].Y) }, s.allocLeaf, ) @@ -295,8 +296,8 @@ return s.allocNode(items) } - sort.Slice(items, func(i, j int) bool { - return s.bbox(items[i]).X1 < s.bbox(items[j]).X1 + slices.SortFunc(items, func(i, j int32) int { + return cmp.Compare(s.bbox(i).X1, s.bbox(j).X1) }) P := int(math.Ceil(float64(len(items)) / float64(s.Entries))) @@ -306,7 +307,7 @@ nodes := s.strJoin( slices, S, - func(i, j int32) bool { return s.bbox(i).Y1 < s.bbox(j).Y1 }, + func(i, j int32) int { return cmp.Compare(s.bbox(i).Y1, s.bbox(j).Y1) }, s.allocNode, ) @@ -337,16 +338,14 @@ } func (s *STRTree) strJoin( - slices [][]int32, S int, - less func(int32, int32) bool, + slics [][]int32, S int, + cmp func(int32, int32) int, alloc func([]int32) int32, ) []int32 { nodes := make([]int32, 0, S*S) - for _, slice := range slices { - sort.Slice(slice, func(i, j int) bool { - return less(slice[i], slice[j]) - }) + for _, slice := range slics { + slices.SortFunc(slice, cmp) for len(slice) > 0 { var n int @@ -426,3 +425,26 @@ } } } + +// sortIndices sorts the indices in the inner nodes and leaves of the tree. +// This helps if the index array is delta encoded in serialization. +// It also may help reduding CPU cache line misses during usage because +// redirects are ordered closer together. +func (s *STRTree) sortIndices() { + stack := []int32{s.index[0]} + for len(stack) > 0 { + top := stack[len(stack)-1] + stack = stack[:len(stack)-1] + if top > 0 { // node + n := s.index[top+1] + children := s.index[top+2 : top+2+n] + stack = append(stack, children...) + slices.Sort(children) + } else { // leaf + top = -top - 1 + n := s.index[top+1] + triangles := s.index[top+2 : top+2+n] + slices.Sort(triangles) + } + } +}