From 70e31d9ccb656e498a958e6623bc64234414e562 Mon Sep 17 00:00:00 2001 From: Aaron Taylor Date: Sat, 15 May 2021 15:43:01 -0700 Subject: [PATCH] Modified permuteExistingNumbers(), moving the isValidSurrealNumber() check into the symbol-permutation loop. Based on profiling, such a large quantity of invalid numbers was being generated that data operations were sucking up a significant portion of total program runtime. Benchmarking command: time ./ch1-breeding-numbers -generations 13 -silent go tool pprof ch1-breeding-numbers 13gen-memprofile-gen12.mprof top25 Before: 38.303u 2.233s 0:23.41 173.1% 0+0k 40+62io 354pf+0w Showing nodes accounting for 2.29GB, 100% of 2.29GB total After: 23.435u 0.887s 0:19.54 124.4% 0+0k 40+52io 347pf+0w Showing nodes accounting for 1.12GB, 99.55% of 1.13GB total --- chapter-1-experiments/ch1-breeding-numbers.go | 22 +++++-------------- 1 file changed, 6 insertions(+), 16 deletions(-) diff --git a/chapter-1-experiments/ch1-breeding-numbers.go b/chapter-1-experiments/ch1-breeding-numbers.go index fc1c397..35f0e20 100644 --- a/chapter-1-experiments/ch1-breeding-numbers.go +++ b/chapter-1-experiments/ch1-breeding-numbers.go @@ -261,13 +261,11 @@ func main() { } fmt.Printf(" %d", generation) - // First generate all possible reduced form symbols per Axiom 1. - potentialNumbers := permuteExistingNumbers(generation, universe) - // Now prune out any symbols which are NOT valid numbers per Axiom 2. - validNumbers := pruneInvalidNumbers(potentialNumbers, universe) + // First generate all possible new numbers in this generation. + potentiallyNewNumbers := permuteExistingNumbers(generation, universe) // Attempt to add the new numbers to the universe. Any duplicates will // be weeded out in the attempt. - addNumbersToUniverse(validNumbers, &universe) + addNumbersToUniverse(potentiallyNewNumbers, &universe) // Setup any memory profiling requested by the user. This will snapshot // the heap at the end of every generation. @@ -313,7 +311,9 @@ func permuteExistingNumbers(generation int, universe surrealUniverse) []surrealN leftSet.insert(universe.numbers[i], universe) rightSet.insert(universe.numbers[j], universe) newSurrealNumber := surrealNumber{leftSet,rightSet,0.0,0,generation} - numbers = append(numbers, newSurrealNumber) + if isValidSurrealNumber(newSurrealNumber, universe) { + numbers = append(numbers, newSurrealNumber) + } } } // Now build permutations with one empty set and one 1-element set. @@ -329,16 +329,6 @@ func permuteExistingNumbers(generation int, universe surrealUniverse) []surrealN return numbers } -func pruneInvalidNumbers(candidates []surrealNumber, universe surrealUniverse) []surrealNumber { - var numbers []surrealNumber - for i := 0; i < len(candidates); i++ { - if isValidSurrealNumber(candidates[i], universe) { - numbers = append(numbers, candidates[i]) - } - } - return numbers -} - // Although a non-reduced-form number is technically valid, for the purposes of // this program we're declaring it invalid. func isValidSurrealNumber(candidate surrealNumber, universe surrealUniverse) bool { -- 2.20.1