Modified heap profiling to only dump at end of program, not after every generation.

[surreal-numbers] / chapter-1-experiments / ch1-breeding-numbers.go

diff --git a/chapter-1-experiments/ch1-breeding-numbers.go b/chapter-1-experiments/ch1-breeding-numbers.go
index fbba0ec..c5baa14 100644 (file)
--- a/chapter-1-experiments/ch1-breeding-numbers.go
+++ b/chapter-1-experiments/ch1-breeding-numbers.go
@@ -9,7 +9,7 @@ import (
     "log"
     "os"
     "runtime/pprof"
     "log"
     "os"
     "runtime/pprof"

-    "strconv"
+    "sort"

 )
 
 // =============================================================================
 )
 
 // =============================================================================


@@ -38,12 +38,14 @@ type surrealUniverse struct {
 }
 
 func (u *surrealUniverse) getIndex(num surrealNumber) int {
 }
 
 func (u *surrealUniverse) getIndex(num surrealNumber) int {

-    for i := 0; i < len(u.numbers); i++ {
-        if num.identifier == u.numbers[i].identifier {
-            return i
-        }
-    }
-    return -1 // This should be unreachable.
+    // Since getIndex() is only ever called on 'num' which already exists in
+    // the universe, we return the result directly, without bothering to
+    // confirm an exact match.
+    //
+    // Also, we can get away with a direct comparison of these floating point
+    // numbers since there will be an exact match, guaranteed since 'num' is
+    // already in the universe.
+    return sort.Search(u.cardinality(), func(i int) bool {return u.numbers[i].value >= num.value})

 }
 
 func (u *surrealUniverse) cardinality() int {
 }
 
 func (u *surrealUniverse) cardinality() int {


@@ -73,23 +75,26 @@ func (u *surrealUniverse) insert(num surrealNumber) {
     switch ancestorCount {
         case 0:
             if u.cardinality() == 0 {
     switch ancestorCount {
         case 0:
             if u.cardinality() == 0 {

+                num.value = 0.0

                 num.identifier = u.nextUniqueID
                 u.nextUniqueID++
                 u.numbers = append(u.numbers, num)
             }
         case 1:
                 num.identifier = u.nextUniqueID
                 u.nextUniqueID++
                 u.numbers = append(u.numbers, num)
             }
         case 1:

-            if num.leftSet.cardinality() == 1{
+            if num.leftSet.cardinality() == 1 {

                 index := u.getIndex(num.leftSet.members[0])
                 index := u.getIndex(num.leftSet.members[0])

-                num.identifier = u.nextUniqueID
-                u.nextUniqueID++

                 if index+1 == u.cardinality() {
                 if index+1 == u.cardinality() {

+                    num.value = u.numbers[u.cardinality()-1].value + 1.0
+                    num.identifier = u.nextUniqueID
+                    u.nextUniqueID++

                     u.numbers = append(u.numbers, num)
                 }
             } else {
                 index := u.getIndex(num.rightSet.members[0])
                     u.numbers = append(u.numbers, num)
                 }
             } else {
                 index := u.getIndex(num.rightSet.members[0])

-                num.identifier = u.nextUniqueID
-                u.nextUniqueID++

                 if index == 0 {
                 if index == 0 {

+                    num.value = u.numbers[0].value - 1.0
+                    num.identifier = u.nextUniqueID
+                    u.nextUniqueID++

                     u.numbers = append(u.numbers[:1], u.numbers...)
                     u.numbers[0] = num
                 }
                     u.numbers = append(u.numbers[:1], u.numbers...)
                     u.numbers[0] = num
                 }


@@ -98,6 +103,7 @@ func (u *surrealUniverse) insert(num surrealNumber) {
             leftIndex := u.getIndex(num.leftSet.members[0])
             rightIndex := u.getIndex(num.rightSet.members[0])
             if leftIndex+1 == rightIndex {
             leftIndex := u.getIndex(num.leftSet.members[0])
             rightIndex := u.getIndex(num.rightSet.members[0])
             if leftIndex+1 == rightIndex {

+                num.value = (num.leftSet.members[0].value + num.rightSet.members[0].value) / 2

                 num.identifier = u.nextUniqueID
                 u.nextUniqueID++
                 u.numbers = append(u.numbers[:rightIndex+1], u.numbers[rightIndex:]...)
                 num.identifier = u.nextUniqueID
                 u.nextUniqueID++
                 u.numbers = append(u.numbers[:rightIndex+1], u.numbers[rightIndex:]...)


@@ -173,6 +179,7 @@ func (u *surrealUniverse) greaterThan(left, right surrealNumber) bool {
 type surrealNumber struct {
     leftSet surrealSet
     rightSet surrealSet
 type surrealNumber struct {
     leftSet surrealSet
     rightSet surrealSet

+    value float64

     identifier uint
     generation int
 }
     identifier uint
     generation int
 }


@@ -214,7 +221,7 @@ func (s *surrealSet) remove(num surrealNumber, u surrealUniverse) {
 func main() {
     // Flags to enable various performance profiling options.
     cpuProfile := flag.String("cpuprofile", "", "Filename for saving CPU profile output.")
 func main() {
     // Flags to enable various performance profiling options.
     cpuProfile := flag.String("cpuprofile", "", "Filename for saving CPU profile output.")

-    memProfilePrefix := flag.String("memprofileprefix", "", "Filename PREFIX for saving memory profile output.")
+    memProfile := flag.String("memprofile", "", "Filename for saving memory profile output.")

     suppressOutput := flag.Bool("silent", false, "Suppress printing of numberline at end of simulation. Useful when profiling.")
 
     // Obtain termination conditions from user.
     suppressOutput := flag.Bool("silent", false, "Suppress printing of numberline at end of simulation. Useful when profiling.")
 
     // Obtain termination conditions from user.


@@ -241,7 +248,7 @@ func main() {
     var universe surrealUniverse
     universe.nextUniqueID = 0
     fmt.Println("Seeding generation 0 by hand.")
     var universe surrealUniverse
     universe.nextUniqueID = 0
     fmt.Println("Seeding generation 0 by hand.")

-    universe.insert(surrealNumber{surrealSet{}, surrealSet{}, 0, 0})
+    universe.insert(surrealNumber{surrealSet{}, surrealSet{}, 0.0, 0, 0})

 
     // Breed however many generations of numbers were requested by the user and
     // add them all to the universe.
 
     // Breed however many generations of numbers were requested by the user and
     // add them all to the universe.


@@ -253,27 +260,24 @@ func main() {
         }
         fmt.Printf(" %d", generation)
 
         }
         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.
         // Attempt to add the new numbers to the universe. Any duplicates will
         // be weeded out in the attempt.

-        addNumbersToUniverse(validNumbers, &universe)
-
-        // Setup any memory profiling requested by the user. This will snapshot
-        // the heap at the end of every generation.
-        if *memProfilePrefix != "" {
-            memProFile, err := os.Create(*memProfilePrefix + "-gen" + strconv.Itoa(generation) + ".mprof")
-            if err != nil {
-                log.Fatal("ERROR: Unable to write heap profile to disk:", err)
-            }
-            pprof.WriteHeapProfile(memProFile)
-            memProFile.Close()
-        }
+        addNumbersToUniverse(potentiallyNewNumbers, &universe)

     }
     fmt.Printf(".\n")
 
     }
     fmt.Printf(".\n")
 

+    // Setup any memory profiling requested by the user. This will snapshot
+    // the heap only at this point, after all numbers were generated.
+    if *memProfile != "" {
+        memProFile, err := os.Create(*memProfile)
+        if err != nil {
+            log.Fatal("ERROR: Unable to open heap profile output file:", err)
+        }
+        pprof.WriteHeapProfile(memProFile)
+        memProFile.Close()
+    }

 
     // Print the number line with generation on the horizontal axis and
     // magnitude on the vertical axis.
 
     // Print the number line with generation on the horizontal axis and
     // magnitude on the vertical axis.


@@ -292,7 +296,11 @@ func main() {
 // right sets. This covers all the reduced form permutations. Any longer
 // permutations will be similar to one of the reduced forms.
 func permuteExistingNumbers(generation int, universe surrealUniverse) []surrealNumber {
 // right sets. This covers all the reduced form permutations. Any longer
 // permutations will be similar to one of the reduced forms.
 func permuteExistingNumbers(generation int, universe surrealUniverse) []surrealNumber {

-    var numbers []surrealNumber
+    // Profiling indicates that most calls to growSlice() and memMove()
+    // originate in this function. Allocating a sufficiently large slice
+    // upfront results in 2x speed improvement and 1/3 reduction in heap usage.
+    numberOfPermutations := ((universe.cardinality()+1) * (universe.cardinality()+1)) - 1
+    numbers := make([]surrealNumber, 0, numberOfPermutations)

 
     // First build permutations with 1 element in each set.
     for i := 0; i < universe.cardinality(); i++ {
 
     // First build permutations with 1 element in each set.
     for i := 0; i < universe.cardinality(); i++ {


@@ -300,33 +308,25 @@ func permuteExistingNumbers(generation int, universe surrealUniverse) []surrealN
             var leftSet, rightSet surrealSet
             leftSet.insert(universe.numbers[i], universe)
             rightSet.insert(universe.numbers[j], universe)
             var leftSet, rightSet surrealSet
             leftSet.insert(universe.numbers[i], universe)
             rightSet.insert(universe.numbers[j], universe)

-            newSurrealNumber := surrealNumber{leftSet,rightSet,0,generation}
-            numbers = append(numbers, newSurrealNumber)
+            newSurrealNumber := surrealNumber{leftSet,rightSet,0.0,0,generation}
+            if isValidSurrealNumber(newSurrealNumber, universe) {
+                numbers = append(numbers, newSurrealNumber)
+            }

         }
     }
     // Now build permutations with one empty set and one 1-element set.
     for i := 0; i < universe.cardinality(); i++ {
         var tempSet surrealSet
         tempSet.insert(universe.numbers[i], universe)
         }
     }
     // Now build permutations with one empty set and one 1-element set.
     for i := 0; i < universe.cardinality(); i++ {
         var tempSet surrealSet
         tempSet.insert(universe.numbers[i], universe)

-        newSurrealNumber := surrealNumber{tempSet,surrealSet{},0,generation}
+        newSurrealNumber := surrealNumber{tempSet,surrealSet{},0.0,0,generation}

         numbers = append(numbers, newSurrealNumber)
         numbers = append(numbers, newSurrealNumber)

-        newSurrealNumber = surrealNumber{surrealSet{},tempSet,0,generation}
+        newSurrealNumber = surrealNumber{surrealSet{},tempSet,0.0,0,generation}

         numbers = append(numbers, newSurrealNumber)
     }
 
     return numbers
 }
 
         numbers = append(numbers, newSurrealNumber)
     }
 
     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 {
 // 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 {