Epoch-based queries, Non-threadsafe and threadsafe APIs#43
Merged
Conversation
Merged
remove container/list
Merged
Cache bidir
Epoch-based queries for OneToMany calls
Thread-safe pool for calling SP
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
This is summary PR of #44, #45, #46 and #47
cpu profile:
go test -run=^$ -bench=^BenchmarkStaticCaseShortestPath$ -cpuprofile=cpu_query_new.prof -benchtime=10s go tool pprof -text cpu_query_new.profmem profile:
go test -run=^$ -bench=^BenchmarkStaticCaseShortestPath$ -memprofile=mem_query_new.prof -benchtime=10s go tool pprof -text mem_query_new.profResults:
CPU
Showing nodes accounting for 61.73s, 94.35% of 65.43s total Dropped 245 nodes (cum <= 0.33s) flat flat% sum% cum cum% 15.55s 23.77% 23.77% 41.53s 63.47% runtime.scanobject 7.12s 10.88% 34.65% 8.40s 12.84% runtime.findObject 6.93s 10.59% 45.24% 6.93s 10.59% runtime.(*mspan).base (inline) 5.10s 7.79% 53.03% 8.40s 12.84% github.com/LdDl/ch.(*Graph).directionalSearch 4.19s 6.40% 59.44% 8.57s 13.10% github.com/LdDl/ch.(*Graph).initShortestPath 3.61s 5.52% 64.95% 3.63s 5.55% runtime.(*gcBits).bitp (inline) 3.04s 4.65% 69.60% 3.07s 4.69% runtime.(*mspan).heapBitsSmallForAddr 3s 4.59% 74.19% 3s 4.59% runtime.memclrNoHeapPointers 2.40s 3.67% 77.85% 3.08s 4.71% github.com/LdDl/ch.(*Graph).shortestPathsWithMaxCost 1.23s 1.88% 79.73% 13.13s 20.07% runtime.greyobject 0.77s 1.18% 80.91% 0.77s 1.18% runtime.arenaIndex (inline) 0.76s 1.16% 82.07% 1.77s 2.71% container/heap.down 0.71s 1.09% 83.16% 41.33s 63.17% runtime.gcDrain 0.64s 0.98% 84.14% 0.65s 0.99% runtime.mapaccess2_fast64 0.61s 0.93% 85.07% 0.88s 1.34% runtime.pageIndexOf (inline) 0.57s 0.87% 85.94% 0.70s 1.07% runtime.spanOf (inline) 0.50s 0.76% 86.70% 0.53s 0.81% runtime.mapaccess1_fast64 0.49s 0.75% 87.45% 0.53s 0.81% runtime.typePointers.next 0.48s 0.73% 88.19% 0.48s 0.73% runtime.typePointers.nextFast (inline) 0.44s 0.67% 88.86% 0.44s 0.67% runtime.(*mspan).divideByElemSize (inline) 0.41s 0.63% 89.48% 0.41s 0.63% github.com/LdDl/ch.vertexDistHeap.Less 0.34s 0.52% 90.00% 5.33s 8.15% runtime.mallocgc 0.33s 0.5% 90.51% 0.33s 0.5% runtime.markBits.isMarked (inline) 0.30s 0.46% 90.97% 3.39s 5.18% runtime.(*mspan).typePointersOfUnchecked 0.30s 0.46% 91.43% 1.08s 1.65% runtime.sweepone 0.27s 0.41% 91.84% 1.63s 2.49% github.com/LdDl/ch.(*Graph).ComputePath 0.22s 0.34% 92.17% 0.49s 0.75% runtime.(*sweepLocked).sweep 0.22s 0.34% 92.51% 0.64s 0.98% runtime.mapassign_fast64 0.21s 0.32% 92.83% 0.41s 0.63% github.com/LdDl/ch.distanceHeap.down 0.17s 0.26% 93.09% 0.70s 1.07% runtime.wbBufFlush1 0.14s 0.21% 93.31% 0.51s 0.78% runtime.spanOfUnchecked (inline) 0.13s 0.2% 93.50% 0.77s 1.18% github.com/LdDl/ch.vertexDistHeap.Swap 0.08s 0.12% 93.63% 10.13s 15.48% github.com/LdDl/ch.(*Graph).shortestPathCore 0.07s 0.11% 93.73% 2.06s 3.15% container/heap.Pop 0.05s 0.076% 93.81% 3.68s 5.62% runtime.(*mspan).markBitsForIndex (inline) 0.05s 0.076% 93.89% 1.21s 1.85% runtime.deductAssistCredit 0.05s 0.076% 93.96% 0.68s 1.04% runtime.newobject 0.04s 0.061% 94.02% 0.73s 1.12% gcWriteBarrier 0.04s 0.061% 94.09% 0.39s 0.6% runtime.growslice 0.03s 0.046% 94.13% 0.44s 0.67% container/heap.Push 0.03s 0.046% 94.18% 0.46s 0.7% github.com/LdDl/ch.(*distanceHeap).Pop 0.02s 0.031% 94.21% 0.46s 0.7% runtime.(*mspan).objIndex (inline) 0.02s 0.031% 94.24% 1.15s 1.76% runtime.gcDrainN 0.02s 0.031% 94.27% 43.71s 66.80% runtime.systemstack 0.02s 0.031% 94.30% 0.72s 1.10% runtime.wbBufFlush.func1 0.01s 0.015% 94.31% 3.35s 5.12% github.com/LdDl/ch.(*Graph).contractNode 0.01s 0.015% 94.33% 3.29s 5.03% github.com/LdDl/ch.(*Graph).processIncidentEdges 0.01s 0.015% 94.35% 4.36s 6.66% runtime.makeslice 0 0% 94.35% 3.71s 5.67% github.com/LdDl/ch.(*Graph).PrepareContractionHierarchies 0 0% 94.35% 3.68s 5.62% github.com/LdDl/ch.(*Graph).Preprocess 0 0% 94.35% 18.72s 28.61% github.com/LdDl/ch.(*Graph).ShortestPath 0 0% 94.35% 18.71s 28.60% github.com/LdDl/ch.(*Graph).shortestPath 0 0% 94.35% 3.95s 6.04% github.com/LdDl/ch.BenchmarkStaticCaseShortestPath 0 0% 94.35% 18.72s 28.61% github.com/LdDl/ch.BenchmarkStaticCaseShortestPath.func1 0 0% 94.35% 1.07s 1.64% runtime.bgsweep 0 0% 94.35% 1.16s 1.77% runtime.gcAssistAlloc 0 0% 94.35% 1.15s 1.76% runtime.gcAssistAlloc.func1 0 0% 94.35% 1.15s 1.76% runtime.gcAssistAlloc1 0 0% 94.35% 41.40s 63.27% runtime.gcBgMarkWorker 0 0% 94.35% 41.33s 63.17% runtime.gcBgMarkWorker.func2 0 0% 94.35% 20.58s 31.45% runtime.gcDrainMarkWorkerDedicated (inline) 0 0% 94.35% 20.75s 31.71% runtime.gcDrainMarkWorkerIdle (inline) 0 0% 94.35% 2.87s 4.39% runtime.memclrNoHeapPointersChunked 0 0% 94.35% 0.72s 1.10% runtime.wbBufFlush 0 0% 94.35% 18.72s 28.61% testing.(*B).launch 0 0% 94.35% 3.96s 6.05% testing.(*B).run1.func1 0 0% 94.35% 22.68s 34.66% testing.(*B).runNMemory:
Showing nodes accounting for 63553.36MB, 98.84% of 64300.56MB total Dropped 33 nodes (cum <= 321.50MB) flat flat% sum% cum cum% 62775.68MB 97.63% 97.63% 62775.68MB 97.63% github.com/LdDl/ch.(*Graph).initShortestPath 773.19MB 1.20% 98.83% 901.85MB 1.40% github.com/LdDl/ch.(*Graph).directionalSearch 2.50MB 0.0039% 98.83% 1109.39MB 1.73% github.com/LdDl/ch.(*Graph).shortestPathCore 2MB 0.0031% 98.84% 63887.07MB 99.36% github.com/LdDl/ch.(*Graph).shortestPath 0 0% 98.84% 63887.07MB 99.36% github.com/LdDl/ch.(*Graph).ShortestPath 0 0% 98.84% 412.33MB 0.64% github.com/LdDl/ch.BenchmarkStaticCaseShortestPath 0 0% 98.84% 63887.07MB 99.36% github.com/LdDl/ch.BenchmarkStaticCaseShortestPath.func1 0 0% 98.84% 63885.04MB 99.35% testing.(*B).launch 0 0% 98.84% 414.36MB 0.64% testing.(*B).run1.func1 0 0% 98.84% 64299.40MB 100% testing.(*B).runNCPU:
Showing nodes accounting for 19.14s, 93.78% of 20.41s total Dropped 110 nodes (cum <= 0.10s) flat flat% sum% cum cum% 7.22s 35.37% 35.37% 12.78s 62.62% github.com/LdDl/ch.(*Graph).directionalSearch 2.07s 10.14% 45.52% 2.58s 12.64% github.com/LdDl/ch.(*Graph).shortestPathsWithMaxCost 1.71s 8.38% 53.90% 2.52s 12.35% container/heap.down 0.77s 3.77% 57.67% 2.55s 12.49% runtime.scanobject 0.73s 3.58% 61.24% 0.73s 3.58% github.com/LdDl/ch.vertexDistHeap.Less 0.57s 2.79% 64.04% 0.66s 3.23% runtime.findObject 0.56s 2.74% 66.78% 0.56s 2.74% runtime.(*mspan).base (inline) 0.56s 2.74% 69.52% 1.59s 7.79% runtime.mapassign_fast64 0.52s 2.55% 72.07% 0.57s 2.79% runtime.mapaccess2_fast64 0.51s 2.50% 74.57% 1.23s 6.03% runtime.mallocgc 0.50s 2.45% 77.02% 0.65s 3.18% runtime.mapaccess1_fast64 0.38s 1.86% 78.88% 0.49s 2.40% container/heap.up 0.33s 1.62% 80.50% 1.54s 7.55% github.com/LdDl/ch.(*Graph).ComputePath 0.29s 1.42% 81.92% 0.47s 2.30% runtime.evacuate_fast64 0.25s 1.22% 83.15% 0.25s 1.22% runtime.(*mspan).heapBitsSmallForAddr 0.25s 1.22% 84.37% 0.25s 1.22% runtime.memhash64 0.20s 0.98% 85.35% 0.20s 0.98% runtime.memclrNoHeapPointers 0.17s 0.83% 86.18% 2.76s 13.52% container/heap.Pop 0.17s 0.83% 87.02% 0.17s 0.83% runtime.add (inline) 0.16s 0.78% 87.80% 0.24s 1.18% github.com/LdDl/ch.distanceHeap.down 0.16s 0.78% 88.58% 0.16s 0.78% runtime.(*gcBits).bitp (inline) 0.15s 0.73% 89.32% 0.15s 0.73% runtime.nextFreeFast (inline) 0.13s 0.64% 89.96% 0.13s 0.64% github.com/LdDl/ch.distanceHeap.Less (inline) 0.10s 0.49% 90.45% 14.42s 70.65% github.com/LdDl/ch.(*Graph).shortestPathCore 0.08s 0.39% 90.84% 0.84s 4.12% runtime.greyobject 0.08s 0.39% 91.23% 0.79s 3.87% runtime.newobject (partial-inline) 0.07s 0.34% 91.57% 0.11s 0.54% github.com/LdDl/ch.(*Vertex).bidirectedEdges (inline) 0.06s 0.29% 91.87% 0.16s 0.78% github.com/LdDl/ch.(*vertexDistHeap).Push 0.04s 0.2% 92.06% 0.31s 1.52% github.com/LdDl/ch.(*distanceHeap).Pop 0.04s 0.2% 92.26% 0.20s 0.98% github.com/LdDl/ch.(*distanceHeap).Push (inline) 0.04s 0.2% 92.45% 0.15s 0.73% github.com/LdDl/ch.vertexDistHeap.Swap 0.04s 0.2% 92.65% 0.13s 0.64% runtime.(*sweepLocked).sweep 0.04s 0.2% 92.85% 0.18s 0.88% runtime.sweepone 0.03s 0.15% 92.99% 2.60s 12.74% runtime.gcDrain 0.03s 0.15% 93.14% 0.32s 1.57% runtime.growslice 0.02s 0.098% 93.24% 0.67s 3.28% container/heap.Push 0.02s 0.098% 93.34% 2.73s 13.38% github.com/LdDl/ch.(*Graph).processIncidentEdges 0.02s 0.098% 93.43% 0.27s 1.32% runtime.(*mspan).typePointersOfUnchecked 0.02s 0.098% 93.53% 0.12s 0.59% runtime.wbBufFlush1 0.01s 0.049% 93.58% 0.12s 0.59% github.com/LdDl/ch.(*Vertex).computeImportance 0.01s 0.049% 93.63% 0.19s 0.93% runtime.(*mcache).refill 0.01s 0.049% 93.68% 0.11s 0.54% runtime.(*mheap).allocSpan 0.01s 0.049% 93.73% 0.48s 2.35% runtime.growWork_fast64 0.01s 0.049% 93.78% 0.21s 1.03% runtime.makeBucketArray 0 0% 93.78% 0.12s 0.59% gcWriteBarrier 0 0% 93.78% 3.01s 14.75% github.com/LdDl/ch.(*Graph).PrepareContractionHierarchies 0 0% 93.78% 2.98s 14.60% github.com/LdDl/ch.(*Graph).Preprocess 0 0% 93.78% 14.43s 70.70% github.com/LdDl/ch.(*Graph).ShortestPath 0 0% 93.78% 2.76s 13.52% github.com/LdDl/ch.(*Graph).contractNode 0 0% 93.78% 0.11s 0.54% github.com/LdDl/ch.(*Graph).createOrUpdateShortcut 0 0% 93.78% 0.11s 0.54% github.com/LdDl/ch.(*Graph).insertShortcuts (inline) 0 0% 93.78% 14.43s 70.70% github.com/LdDl/ch.(*Graph).shortestPath 0 0% 93.78% 3.18s 15.58% github.com/LdDl/ch.BenchmarkStaticCaseShortestPath 0 0% 93.78% 14.43s 70.70% github.com/LdDl/ch.BenchmarkStaticCaseShortestPath.func1 0 0% 93.78% 0.17s 0.83% github.com/LdDl/ch.graphFromCSV 0 0% 93.78% 0.19s 0.93% runtime.(*mcache).nextFree 0 0% 93.78% 0.13s 0.64% runtime.(*mcentral).cacheSpan 0 0% 93.78% 0.12s 0.59% runtime.(*mcentral).grow 0 0% 93.78% 0.11s 0.54% runtime.(*mheap).alloc 0 0% 93.78% 0.11s 0.54% runtime.(*mheap).alloc.func1 0 0% 93.78% 0.16s 0.78% runtime.(*mspan).markBitsForIndex (inline) 0 0% 93.78% 0.18s 0.88% runtime.bgsweep 0 0% 93.78% 2.60s 12.74% runtime.gcBgMarkWorker 0 0% 93.78% 2.60s 12.74% runtime.gcBgMarkWorker.func2 0 0% 93.78% 1.36s 6.66% runtime.gcDrainMarkWorkerDedicated (inline) 0 0% 93.78% 1.24s 6.08% runtime.gcDrainMarkWorkerIdle (inline) 0 0% 93.78% 0.21s 1.03% runtime.hashGrow 0 0% 93.78% 0.11s 0.54% runtime.makeslice 0 0% 93.78% 0.20s 0.98% runtime.newarray 0 0% 93.78% 2.90s 14.21% runtime.systemstack 0 0% 93.78% 0.12s 0.59% runtime.wbBufFlush 0 0% 93.78% 0.12s 0.59% runtime.wbBufFlush.func1 0 0% 93.78% 14.43s 70.70% testing.(*B).launch 0 0% 93.78% 3.18s 15.58% testing.(*B).run1.func1 0 0% 93.78% 17.61s 86.28% testing.(*B).runNMemory:
Showing nodes accounting for 3638.56MB, 97.62% of 3727.10MB total Dropped 10 nodes (cum <= 18.64MB) flat flat% sum% cum cum% 2212.88MB 59.37% 59.37% 2534.27MB 68.00% github.com/LdDl/ch.(*Graph).directionalSearch 741.54MB 19.90% 79.27% 741.54MB 19.90% github.com/LdDl/ch.(*Graph).ComputePath 322.89MB 8.66% 87.93% 322.89MB 8.66% github.com/LdDl/ch.(*vertexDistHeap).Push 139.74MB 3.75% 91.68% 139.74MB 3.75% github.com/LdDl/ch.(*Graph).CreateVertex 131.14MB 3.52% 95.20% 131.14MB 3.52% github.com/LdDl/ch.(*distanceHeap).Push (inline) 47.86MB 1.28% 96.48% 86.37MB 2.32% github.com/LdDl/ch.(*Graph).createOrUpdateShortcut 21.01MB 0.56% 97.05% 238.52MB 6.40% github.com/LdDl/ch.(*Graph).processIncidentEdges 20.01MB 0.54% 97.58% 20.01MB 0.54% github.com/LdDl/ch.(*Vertex).addOutIncidentEdge (inline) 1.50MB 0.04% 97.62% 3293.35MB 88.36% github.com/LdDl/ch.(*Graph).shortestPath 0 0% 97.62% 332.88MB 8.93% container/heap.Push 0 0% 97.62% 264.01MB 7.08% github.com/LdDl/ch.(*Graph).PrepareContractionHierarchies 0 0% 97.62% 254.02MB 6.82% github.com/LdDl/ch.(*Graph).Preprocess 0 0% 97.62% 3293.35MB 88.36% github.com/LdDl/ch.(*Graph).ShortestPath 0 0% 97.62% 238.52MB 6.40% github.com/LdDl/ch.(*Graph).contractNode 0 0% 97.62% 86.37MB 2.32% github.com/LdDl/ch.(*Graph).insertShortcuts (inline) 0 0% 97.62% 3275.81MB 87.89% github.com/LdDl/ch.(*Graph).shortestPathCore 0 0% 97.62% 131.14MB 3.52% github.com/LdDl/ch.(*Graph).shortestPathsWithMaxCost 0 0% 97.62% 433.75MB 11.64% github.com/LdDl/ch.BenchmarkStaticCaseShortestPath 0 0% 97.62% 3293.35MB 88.36% github.com/LdDl/ch.BenchmarkStaticCaseShortestPath.func1 0 0% 97.62% 169.74MB 4.55% github.com/LdDl/ch.graphFromCSV 0 0% 97.62% 3290.31MB 88.28% testing.(*B).launch 0 0% 97.62% 436.80MB 11.72% testing.(*B).run1.func1 0 0% 97.62% 3727.10MB 100% testing.(*B).runN