"log"
"os"
"runtime/pprof"
- "strconv"
+ "sort"
)
// =============================================================================
}
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 {
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:
- if num.leftSet.cardinality() == 1{
+ if num.leftSet.cardinality() == 1 {
index := u.getIndex(num.leftSet.members[0])
- num.identifier = u.nextUniqueID
- u.nextUniqueID++
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])
- num.identifier = u.nextUniqueID
- u.nextUniqueID++
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
}
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:]...)
type surrealNumber struct {
leftSet surrealSet
rightSet surrealSet
+ value float64
identifier uint
generation int
}
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.
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.
}
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)
-
- // 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")
+ // 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.
// 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++ {
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)
- newSurrealNumber := surrealNumber{tempSet,surrealSet{},0,generation}
+ newSurrealNumber := surrealNumber{tempSet,surrealSet{},0.0,0,generation}
numbers = append(numbers, newSurrealNumber)
- newSurrealNumber = surrealNumber{surrealSet{},tempSet,0,generation}
+ newSurrealNumber = surrealNumber{surrealSet{},tempSet,0.0,0,generation}
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 {