michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /*
michael@0: 
michael@0:   A program that attempts to find an optimal function ordering for an
michael@0:   executable using a genetic algorithm whose fitness function is
michael@0:   computed using runtime profile information.
michael@0: 
michael@0:   The fitness function was inspired by Nat Friedman's <nat@nat.org>
michael@0:   work on `grope':
michael@0: 
michael@0:     _GNU Rope - A Subroutine Position Optimizer_
michael@0:     <http://www.hungry.com/~shaver/grope/grope.ps>
michael@0: 
michael@0:   Brendan Eich <brendan@mozilla.org> told me tales about Scott Furman
michael@0:   doing something like this, which sort of made me want to try it.
michael@0: 
michael@0:   As far as I can tell, it would take a lot of computers a lot of time
michael@0:   to actually find something useful on a non-trivial program using
michael@0:   this.
michael@0: 
michael@0:  */
michael@0: 
michael@0: #include <assert.h>
michael@0: #include <fstream>
michael@0: #include <hash_map>
michael@0: #include <vector>
michael@0: #include <limits.h>
michael@0: #include <unistd.h>
michael@0: #include <stdio.h>
michael@0: #include <fcntl.h>
michael@0: 
michael@0: #include "elf_symbol_table.h"
michael@0: 
michael@0: #define _GNU_SOURCE
michael@0: #include <getopt.h>
michael@0: 
michael@0: #define PAGE_SIZE 4096
michael@0: #define SYMBOL_ALIGN 4
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: class call_pair
michael@0: {
michael@0: public:
michael@0:     const Elf32_Sym *m_lo;
michael@0:     const Elf32_Sym *m_hi;
michael@0: 
michael@0:     call_pair(const Elf32_Sym *site1, const Elf32_Sym *site2)
michael@0:     {
michael@0:         if (site1 < site2) {
michael@0:             m_lo = site1;
michael@0:             m_hi = site2;
michael@0:         }
michael@0:         else {
michael@0:             m_hi = site1;
michael@0:             m_lo = site2;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     friend bool
michael@0:     operator==(const call_pair &lhs, const call_pair &rhs)
michael@0:     {
michael@0:         return (lhs.m_lo == rhs.m_lo) && (lhs.m_hi == rhs.m_hi);
michael@0:     }
michael@0: };
michael@0: 
michael@0: // Straight outta plhash.c!
michael@0: #define GOLDEN_RATIO 0x9E3779B9U
michael@0: 
michael@0: template<>
michael@0: struct hash<call_pair>
michael@0: {
michael@0:     size_t operator()(const call_pair &pair) const
michael@0:     {
michael@0:         size_t h = (reinterpret_cast<size_t>(pair.m_hi) >> 4);
michael@0:         h += (reinterpret_cast<size_t>(pair.m_lo) >> 4);
michael@0:         h *= GOLDEN_RATIO;
michael@0:         return h;
michael@0:     }
michael@0: };
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: struct hash<const Elf32_Sym *>
michael@0: {
michael@0:     size_t operator()(const Elf32_Sym *sym) const
michael@0:     {
michael@0:         return (reinterpret_cast<size_t>(sym) >> 4) * GOLDEN_RATIO;
michael@0:     }
michael@0: };
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: typedef hash_map<call_pair, unsigned int> call_graph_t;
michael@0: call_graph_t call_graph;
michael@0: 
michael@0: typedef hash_map<const Elf32_Sym *, unsigned int> histogram_t;
michael@0: histogram_t histogram;
michael@0: long long total_calls = 0;
michael@0: 
michael@0: elf_symbol_table symtab;
michael@0: 
michael@0: bool opt_debug = false;
michael@0: int opt_generations = 10;
michael@0: int opt_mutate = 0;
michael@0: const char *opt_out = "order.out";
michael@0: int opt_population_size = 100;
michael@0: int opt_tick = 0;
michael@0: bool opt_verbose = false;
michael@0: int opt_window = 0;
michael@0: 
michael@0: static struct option long_options[] = {
michael@0:     { "debug",       no_argument,       0, 'd' },
michael@0:     { "exe",         required_argument, 0, 'e' },
michael@0:     { "generations", required_argument, 0, 'g' },
michael@0:     { "help",        no_argument,       0, '?' },
michael@0:     { "mutate",      required_argument, 0, 'm' },
michael@0:     { "out",         required_argument, 0, 'o' },
michael@0:     { "population",  required_argument, 0, 'p' },
michael@0:     { "seed",        required_argument, 0, 's' },
michael@0:     { "tick",        optional_argument, 0, 't' },
michael@0:     { "verbose",     no_argument,       0, 'v' },
michael@0:     { "window",      required_argument, 0, 'w' },
michael@0:     { 0,             0,                 0, 0   }
michael@0: };
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: static long long
michael@0: llrand()
michael@0: {
michael@0:     long long result;
michael@0:     result = (long long) rand();
michael@0:     result *= (long long) (unsigned int) (RAND_MAX + 1);
michael@0:     result += (long long) rand();
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: class symbol_order {
michael@0: public:
michael@0:     typedef vector<const Elf32_Sym *> vector_t;
michael@0:     typedef long long score_t;
michael@0: 
michael@0:     static const score_t max_score;
michael@0: 
michael@0:     /**
michael@0:      * A vector of symbols that is this ordering.
michael@0:      */
michael@0:     vector_t m_ordering;
michael@0: 
michael@0:     /**
michael@0:      * The symbol ordering's score.
michael@0:      */
michael@0:     score_t  m_score;
michael@0: 
michael@0:     symbol_order() : m_score(0) {}
michael@0: 
michael@0:     /**
michael@0:      * ``Shuffle'' a symbol ordering, randomizing it.
michael@0:      */
michael@0:     void shuffle();
michael@0: 
michael@0:     /**
michael@0:      * Initialize this symbol ordering by performing a crossover from
michael@0:      * two ``parent'' symbol orderings.
michael@0:      */
michael@0:     void crossover_from(const symbol_order *father, const symbol_order *mother);
michael@0: 
michael@0:     /**
michael@0:      * Randomly mutate this symbol ordering.
michael@0:      */
michael@0:     void mutate();
michael@0: 
michael@0:     /**
michael@0:      * Score a symbol ordering based on paginated locality.
michael@0:      */
michael@0:     score_t compute_score_page();
michael@0: 
michael@0:     /**
michael@0:      * Score a symbol ordering based on a sliding window.
michael@0:      */
michael@0:     score_t compute_score_window(int window_size);
michael@0: 
michael@0:     static score_t compute_score(symbol_order &order);
michael@0: 
michael@0:     /**
michael@0:      * Use the symbol table to dump the ordered symbolic constants.
michael@0:      */
michael@0:     void dump_symbols() const;
michael@0: 
michael@0:     friend ostream &
michael@0:     operator<<(ostream &out, const symbol_order &order);
michael@0: };
michael@0: 
michael@0: const symbol_order::score_t
michael@0: symbol_order::max_score = ~((symbol_order::score_t)1 << ((sizeof(symbol_order::score_t) * 8) - 1));
michael@0: 
michael@0: symbol_order::score_t
michael@0: symbol_order::compute_score_page()
michael@0: {
michael@0:     m_score = 0;
michael@0: 
michael@0:     unsigned int off = 0; // XXX in reality, probably not page-aligned to start
michael@0: 
michael@0:     vector_t::const_iterator end = m_ordering.end(),
michael@0:         last = end,
michael@0:         sym = m_ordering.begin();
michael@0: 
michael@0:     while (sym != end) {
michael@0:         vector_t page;
michael@0: 
michael@0:         // If we had a symbol that spilled over from the last page,
michael@0:         // then include it here.
michael@0:         if (last != end)
michael@0:             page.push_back(*last);
michael@0: 
michael@0:         // Pack symbols into the page
michael@0:         do {
michael@0:             page.push_back(*sym);
michael@0: 
michael@0:             int size = (*sym)->st_size;
michael@0:             size += SYMBOL_ALIGN - 1;
michael@0:             size &= ~(SYMBOL_ALIGN - 1);
michael@0: 
michael@0:             off += size;
michael@0:         } while (++sym != end && off < PAGE_SIZE);
michael@0: 
michael@0:         // Remember if there was spill-over.
michael@0:         off %= PAGE_SIZE;
michael@0:         last = (off != 0) ? sym : end;
michael@0: 
michael@0:         // Now score the page as the count of all calls to symbols on
michael@0:         // the page, less calls between the symbols on the page.
michael@0:         vector_t::const_iterator page_end = page.end();
michael@0:         for (vector_t::const_iterator i = page.begin(); i != page_end; ++i) {
michael@0:             histogram_t::const_iterator func = histogram.find(*i);
michael@0:             if (func == histogram.end())
michael@0:                 continue;
michael@0: 
michael@0:             m_score += func->second;
michael@0: 
michael@0:             vector_t::const_iterator j = i;
michael@0:             for (++j; j != page_end; ++j) {
michael@0:                 call_graph_t::const_iterator call =
michael@0:                     call_graph.find(call_pair(*i, *j));
michael@0: 
michael@0:                 if (call != call_graph.end())
michael@0:                     m_score -= call->second;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     assert(m_score >= 0);
michael@0: 
michael@0:     // Integer reciprocal so we minimize instead of maximize.
michael@0:     if (m_score == 0)
michael@0:         m_score = 1;
michael@0: 
michael@0:     m_score = (total_calls / m_score) + 1;
michael@0: 
michael@0:     return m_score;
michael@0: }
michael@0: 
michael@0: symbol_order::score_t
michael@0: symbol_order::compute_score_window(int window_size)
michael@0: {
michael@0:     m_score = 0;
michael@0: 
michael@0:     vector_t::const_iterator *window = new vector_t::const_iterator[window_size];
michael@0:     int window_fill = 0;
michael@0: 
michael@0:     vector_t::const_iterator end = m_ordering.end(),
michael@0:         sym = m_ordering.begin();
michael@0: 
michael@0:     for (; sym != end; ++sym) {
michael@0:         histogram_t::const_iterator func = histogram.find(*sym);
michael@0:         if (func != histogram.end()) {
michael@0:             long long scale = ((long long) 1) << window_size;
michael@0: 
michael@0:             m_score += func->second * scale * 2;
michael@0: 
michael@0:             vector_t::const_iterator *limit = window + window_fill;
michael@0:             vector_t::const_iterator *iter;
michael@0:             for (iter = window ; iter < limit; ++iter) {
michael@0:                 call_graph_t::const_iterator call =
michael@0:                     call_graph.find(call_pair(*sym, **iter));
michael@0: 
michael@0:                 if (call != call_graph.end())
michael@0:                     m_score -= (call->second * scale);
michael@0:             
michael@0:                 scale >>= 1;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         // Slide the window.
michael@0:         vector_t::const_iterator *begin = window;
michael@0:         vector_t::const_iterator *iter;
michael@0:         for (iter = window + (window_size - 1); iter > begin; --iter)
michael@0:             *iter = *(iter - 1);
michael@0: 
michael@0:         if (window_fill < window_size)
michael@0:             ++window_fill;
michael@0: 
michael@0:         *window = sym;
michael@0:     }
michael@0: 
michael@0:     delete[] window;
michael@0: 
michael@0:     assert(m_score >= 0);
michael@0: 
michael@0:     // Integer reciprocal so we minimize instead of maximize.
michael@0:     if (m_score == 0)
michael@0:         m_score = 1;
michael@0: 
michael@0:     m_score = (total_calls / m_score) + 1;
michael@0: 
michael@0:     return m_score;
michael@0: }
michael@0: 
michael@0: symbol_order::score_t
michael@0: symbol_order::compute_score(symbol_order &order)
michael@0: {
michael@0:     if (opt_window)
michael@0:         return order.compute_score_window(opt_window);
michael@0: 
michael@0:     return order.compute_score_page();
michael@0: }
michael@0: 
michael@0: void
michael@0: symbol_order::shuffle()
michael@0: {
michael@0:     vector_t::iterator sym = m_ordering.begin();
michael@0:     vector_t::iterator end = m_ordering.end();
michael@0:     for (; sym != end; ++sym) {
michael@0:         int i = rand() % m_ordering.size();
michael@0:         const Elf32_Sym *temp = *sym;
michael@0:         *sym = m_ordering[i];
michael@0:         m_ordering[i] = temp;
michael@0:     }
michael@0: }
michael@0: 
michael@0: void
michael@0: symbol_order::crossover_from(const symbol_order *father, const symbol_order *mother)
michael@0: {
michael@0:     histogram_t used;
michael@0: 
michael@0:     m_ordering = vector_t(father->m_ordering.size(), 0);
michael@0: 
michael@0:     vector_t::const_iterator parent_sym = father->m_ordering.begin();
michael@0:     vector_t::iterator sym = m_ordering.begin();
michael@0:     vector_t::iterator end = m_ordering.end();
michael@0: 
michael@0:     for (; sym != end; ++sym, ++parent_sym) {
michael@0:         if (rand() % 2) {
michael@0:             *sym = *parent_sym;
michael@0:             used[*parent_sym] = 1;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     parent_sym = mother->m_ordering.begin();
michael@0:     sym = m_ordering.begin();
michael@0: 
michael@0:     for (; sym != end; ++sym) {
michael@0:         if (! *sym) {
michael@0:             while (used[*parent_sym])
michael@0:                 ++parent_sym;
michael@0: 
michael@0:             *sym = *parent_sym++;
michael@0:         }
michael@0:     }
michael@0: }
michael@0: 
michael@0: void
michael@0: symbol_order::mutate()
michael@0: {
michael@0:     int i, j;
michael@0:     i = rand() % m_ordering.size();
michael@0:     j = rand() % m_ordering.size();
michael@0: 
michael@0:     const Elf32_Sym *temp = m_ordering[i];
michael@0:     m_ordering[i] = m_ordering[j];
michael@0:     m_ordering[j] = temp;
michael@0: }
michael@0: 
michael@0: void
michael@0: symbol_order::dump_symbols() const
michael@0: {
michael@0:     ofstream out(opt_out);
michael@0: 
michael@0:     vector_t::const_iterator sym = m_ordering.begin();
michael@0:     vector_t::const_iterator end = m_ordering.end();
michael@0:     for (; sym != end; ++sym)
michael@0:         out << symtab.get_symbol_name(*sym) << endl;
michael@0: 
michael@0:     out.close();
michael@0: }
michael@0: 
michael@0: ostream &
michael@0: operator<<(ostream &out, const symbol_order &order)
michael@0: {
michael@0:     out << "symbol_order(" << order.m_score << ") ";
michael@0: 
michael@0:     symbol_order::vector_t::const_iterator sym = order.m_ordering.begin();
michael@0:     symbol_order::vector_t::const_iterator end = order.m_ordering.end();
michael@0:     for (; sym != end; ++sym)
michael@0:         out.form("%08x ", *sym);
michael@0: 
michael@0:     out << endl;
michael@0: 
michael@0:     return out;
michael@0: }
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: static void
michael@0: usage(const char *name)
michael@0: {
michael@0:     cerr << "usage: " << name << " [options] [<file> ...]" << endl;
michael@0:     cerr << "  Options:" << endl;
michael@0:     cerr << "  --debug, -d" << endl;
michael@0:     cerr << "      Print lots of verbose debugging cruft." << endl;
michael@0:     cerr << "  --exe=<image>, -e <image> (required)" << endl;
michael@0:     cerr << "      Specify the executable image from which to read symbol information." << endl;
michael@0:     cerr << "  --generations=<num>, -g <num>" << endl;
michael@0:     cerr << "      Specify the number of generations to run the GA (default is 10)." << endl;
michael@0:     cerr << "  --help, -?" << endl;
michael@0:     cerr << "      Print this message and exit." << endl;
michael@0:     cerr << "  --mutate=<num>, -m <num>" << endl;
michael@0:     cerr << "      Mutate every <num>th individual, or zero for no mutation (default)." << endl;
michael@0:     cerr << "  --out=<file>, -o <file>" << endl;
michael@0:     cerr << "      Specify the output file to which to dump the symbol ordering of the" << endl;
michael@0:     cerr << "      best individual (default is `order.out')." << endl;
michael@0:     cerr << "  --population=<num>, -p <num>" << endl;
michael@0:     cerr << "      Set the population size to <num> individuals (default is 100)." << endl;
michael@0:     cerr << "  --seed=<num>, -s <num>" << endl;
michael@0:     cerr << "      Specify a seed to srand()." << endl;
michael@0:     cerr << "  --tick[=<num>], -t [<num>]" << endl;
michael@0:     cerr << "      When reading address data, print a dot to stderr every <num>th" << endl;
michael@0:     cerr << "      address processed from the call trace. If specified with no argument," << endl;
michael@0:     cerr << "      a dot will be printed for every million addresses processed." << endl;
michael@0:     cerr << "  --verbose, -v" << endl;
michael@0:     cerr << "      Issue progress messages to stderr." << endl;
michael@0:     cerr << "  --window=<num>, -w <num>" << endl;
michael@0:     cerr << "      Use a sliding window instead of pagination to score orderings." << endl;
michael@0:     cerr << endl;
michael@0:     cerr << "This program uses a genetic algorithm to produce an `optimal' ordering for" << endl;
michael@0:     cerr << "an executable based on call patterns." << endl;
michael@0:     cerr << endl;
michael@0:     cerr << "Addresses from a call trace are read as binary data from the files" << endl;
michael@0:     cerr << "specified, or from stdin if no files are specified. These addresses" << endl;
michael@0:     cerr << "are used with the symbolic information from the executable to create" << endl;
michael@0:     cerr << "a call graph. This call graph is used to `score' arbitrary symbol" << endl;
michael@0:     cerr << "orderings, and provides the fitness function for the GA." << endl;
michael@0:     cerr << endl;
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * Using the symbol table, map a stream of address references into a
michael@0:  * callgraph and a histogram.
michael@0:  */
michael@0: static void
michael@0: map_addrs(int fd)
michael@0: {
michael@0:     const Elf32_Sym *last = 0;
michael@0:     unsigned int buf[128];
michael@0:     ssize_t cb;
michael@0: 
michael@0:     unsigned int count = 0;
michael@0:     while ((cb = read(fd, buf, sizeof buf)) > 0) {
michael@0:         if (cb % sizeof buf[0])
michael@0:             fprintf(stderr, "unaligned read\n");
michael@0: 
michael@0:         unsigned int *addr = buf;
michael@0:         unsigned int *limit = buf + (cb / 4);
michael@0: 
michael@0:         for (; addr < limit; ++addr) {
michael@0:             const Elf32_Sym *sym = symtab.lookup(*addr);
michael@0: 
michael@0:             if (last && sym && last != sym) {
michael@0:                 ++total_calls;
michael@0:                 ++histogram[sym];
michael@0:                 ++call_graph[call_pair(last, sym)];
michael@0: 
michael@0:                 if (opt_tick && (++count % opt_tick == 0)) {
michael@0:                     cerr << ".";
michael@0:                     flush(cerr);
michael@0:                 }
michael@0:             }
michael@0: 
michael@0:             last = sym;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (opt_tick)
michael@0:         cerr << endl;
michael@0: 
michael@0:     cerr << "Total calls: " << total_calls << endl;
michael@0:     total_calls *= 1024;
michael@0: 
michael@0:     if (opt_window)
michael@0:         total_calls <<= (opt_window + 1);
michael@0: }
michael@0: 
michael@0: static symbol_order *
michael@0: pick_parent(symbol_order *ordering, int max, int index)
michael@0: {
michael@0:     while (1) {
michael@0:         index -= ordering->m_score;
michael@0:         if (index < 0)
michael@0:             break;
michael@0: 
michael@0:         ++ordering;
michael@0:     }
michael@0: 
michael@0:     return ordering;
michael@0: }
michael@0: 
michael@0: /**
michael@0:  * The main program
michael@0:  */
michael@0: int
michael@0: main(int argc, char *argv[])
michael@0: {
michael@0:     const char *opt_exe = 0;
michael@0: 
michael@0:     int c;
michael@0:     while (1) {
michael@0:         int option_index = 0;
michael@0:         c = getopt_long(argc, argv, "?de:g:m:o:p:s:t:vw:", long_options, &option_index);
michael@0: 
michael@0:         if (c < 0)
michael@0:             break;
michael@0: 
michael@0:         switch (c) {
michael@0:         case '?':
michael@0:             usage(argv[0]);
michael@0:             return 0;
michael@0: 
michael@0:         case 'd':
michael@0:             opt_debug = true;
michael@0:             break;
michael@0: 
michael@0:         case 'e':
michael@0:             opt_exe = optarg;
michael@0:             break;
michael@0: 
michael@0:         case 'g':
michael@0:             opt_generations = atoi(optarg);
michael@0:             break;
michael@0: 
michael@0:         case 'm':
michael@0:             opt_mutate = atoi(optarg);
michael@0:             break;
michael@0: 
michael@0:         case 'o':
michael@0:             opt_out = optarg;
michael@0:             break;
michael@0: 
michael@0:         case 'p':
michael@0:             opt_population_size = atoi(optarg);
michael@0:             break;
michael@0: 
michael@0:         case 's':
michael@0:             srand(atoi(optarg));
michael@0:             break;
michael@0: 
michael@0:         case 't':
michael@0:             opt_tick = optarg ? atoi(optarg) : 1000000;
michael@0:             break;
michael@0: 
michael@0:         case 'v':
michael@0:             opt_verbose = true;
michael@0:             break;
michael@0: 
michael@0:         case 'w':
michael@0:             opt_window = atoi(optarg);
michael@0:             if (opt_window < 0 || opt_window > 8) {
michael@0:                 cerr << "invalid window size: " << opt_window << endl;
michael@0:                 return 1;
michael@0:             }
michael@0: 
michael@0:             break;
michael@0: 
michael@0:         default:
michael@0:             usage(argv[0]);
michael@0:             return 1;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Make sure an image was specified
michael@0:     if (! opt_exe) {
michael@0:         usage(argv[0]);
michael@0:         return 1;
michael@0:     }
michael@0: 
michael@0:     // Read the sym table.
michael@0:     symtab.init(opt_exe);
michael@0: 
michael@0:     // Process addresses to construct the call graph.
michael@0:     if (optind >= argc) {
michael@0:         map_addrs(STDIN_FILENO);
michael@0:     }
michael@0:     else {
michael@0:         do {
michael@0:             int fd = open(argv[optind], O_RDONLY);
michael@0:             if (fd < 0) {
michael@0:                 perror(argv[optind]);
michael@0:                 return 1;
michael@0:             }
michael@0: 
michael@0:             map_addrs(fd);
michael@0:             close(fd);
michael@0:         } while (++optind < argc);
michael@0:     }
michael@0: 
michael@0:     if (opt_debug) {
michael@0:         cerr << "Call graph:" << endl;
michael@0: 
michael@0:         call_graph_t::const_iterator limit = call_graph.end();
michael@0:         call_graph_t::const_iterator i;
michael@0:         for (i = call_graph.begin(); i != limit; ++i) {
michael@0:             const call_pair& pair = i->first;
michael@0:             cerr.form("%08x %08x %10d\n",
michael@0:                       pair.m_lo->st_value,
michael@0:                       pair.m_hi->st_value,
michael@0:                       i->second);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // Collect the symbols into a vector
michael@0:     symbol_order::vector_t ordering;
michael@0:     elf_symbol_table::const_iterator end = symtab.end();
michael@0:     for (elf_symbol_table::const_iterator sym = symtab.begin(); sym != end; ++sym) {
michael@0:         if (symtab.is_function(sym))
michael@0:             ordering.push_back(sym);
michael@0:     }
michael@0: 
michael@0:     if (opt_verbose) {
michael@0:         symbol_order initial;
michael@0:         initial.m_ordering = ordering;
michael@0:         cerr << "created initial ordering, score=" << symbol_order::compute_score(initial) << endl;
michael@0: 
michael@0:         if (opt_debug)
michael@0:             cerr << initial;
michael@0:     }
michael@0: 
michael@0:     // Create a population.
michael@0:     if (opt_verbose)
michael@0:         cerr << "creating population" << endl;
michael@0: 
michael@0:     symbol_order *population = new symbol_order[opt_population_size];
michael@0: 
michael@0:     symbol_order::score_t total = 0, min = symbol_order::max_score, max = 0;
michael@0: 
michael@0:     // Score it.
michael@0:     symbol_order *order = population;
michael@0:     symbol_order *limit = population + opt_population_size;
michael@0:     for (; order < limit; ++order) {
michael@0:         order->m_ordering = ordering;
michael@0:         order->shuffle();
michael@0: 
michael@0:         symbol_order::score_t score = symbol_order::compute_score(*order);
michael@0: 
michael@0:         if (opt_debug)
michael@0:             cerr << *order;
michael@0: 
michael@0:         if (min > score)
michael@0:             min = score;
michael@0:         if (max < score)
michael@0:             max = score;
michael@0: 
michael@0:         total += score;
michael@0:     }
michael@0: 
michael@0:     if (opt_verbose) {
michael@0:         cerr << "Initial population";
michael@0:         cerr << ": min=" << min;
michael@0:         cerr << ", max=" << max;
michael@0:         cerr << " mean=" << (total / opt_population_size);
michael@0:         cerr << endl;
michael@0:     }
michael@0: 
michael@0: 
michael@0:     // Run the GA.
michael@0:     if (opt_verbose)
michael@0:         cerr << "begininng ga" << endl;
michael@0: 
michael@0:     symbol_order::score_t best = 0;
michael@0: 
michael@0:     for (int generation = 1; generation <= opt_generations; ++generation) {
michael@0:         // Create a new population.
michael@0:         symbol_order *offspring = new symbol_order[opt_population_size];
michael@0: 
michael@0:         symbol_order *kid = offspring;
michael@0:         symbol_order *offspring_limit = offspring + opt_population_size;
michael@0:         for (; kid < offspring_limit; ++kid) {
michael@0:             // Pick parents.
michael@0:             symbol_order *father, *mother;
michael@0:             father = pick_parent(population, max, llrand() % total);
michael@0:             mother = pick_parent(population, max, llrand() % total);
michael@0: 
michael@0:             // Create a kid.
michael@0:             kid->crossover_from(father, mother);
michael@0: 
michael@0:             // Mutate, possibly.
michael@0:             if (opt_mutate) {
michael@0:                 if (rand() % opt_mutate == 0)
michael@0:                     kid->mutate();
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         delete[] population;
michael@0:         population = offspring;
michael@0: 
michael@0:         // Score the new population.
michael@0:         total = 0;
michael@0:         min = symbol_order::max_score;
michael@0:         max = 0;
michael@0: 
michael@0:         symbol_order *fittest = 0;
michael@0: 
michael@0:         limit = offspring_limit;
michael@0:         for (order = population; order < limit; ++order) {
michael@0:             symbol_order::score_t score = symbol_order::compute_score(*order);
michael@0: 
michael@0:             if (opt_debug)
michael@0:                 cerr << *order;
michael@0: 
michael@0:             if (min > score)
michael@0:                 min = score;
michael@0: 
michael@0:             if (max < score)
michael@0:                 max = score;
michael@0: 
michael@0:             if (best < score) {
michael@0:                 best = score;
michael@0:                 fittest = order;
michael@0:             }
michael@0: 
michael@0:             total += score;
michael@0:         }
michael@0: 
michael@0:         if (opt_verbose) {
michael@0:             cerr << "Generation " << generation;
michael@0:             cerr << ": min=" << min;
michael@0:             cerr << ", max=" << max;
michael@0:             if (fittest)
michael@0:                 cerr << "*";
michael@0:             cerr << " mean=" << (total / opt_population_size);
michael@0:             cerr << endl;
michael@0:         }
michael@0: 
michael@0:         // If we've found a new ``best'' individual, dump it.
michael@0:         if (fittest)
michael@0:             fittest->dump_symbols();
michael@0:     }
michael@0: 
michael@0:     delete[] population;
michael@0:     return 0;
michael@0: }