1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/tools/reorder/garope.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,765 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +/*
1.9 +
1.10 + A program that attempts to find an optimal function ordering for an
1.11 + executable using a genetic algorithm whose fitness function is
1.12 + computed using runtime profile information.
1.13 +
1.14 + The fitness function was inspired by Nat Friedman's <nat@nat.org>
1.15 + work on `grope':
1.16 +
1.17 + _GNU Rope - A Subroutine Position Optimizer_
1.18 + <http://www.hungry.com/~shaver/grope/grope.ps>
1.19 +
1.20 + Brendan Eich <brendan@mozilla.org> told me tales about Scott Furman
1.21 + doing something like this, which sort of made me want to try it.
1.22 +
1.23 + As far as I can tell, it would take a lot of computers a lot of time
1.24 + to actually find something useful on a non-trivial program using
1.25 + this.
1.26 +
1.27 + */
1.28 +
1.29 +#include <assert.h>
1.30 +#include <fstream>
1.31 +#include <hash_map>
1.32 +#include <vector>
1.33 +#include <limits.h>
1.34 +#include <unistd.h>
1.35 +#include <stdio.h>
1.36 +#include <fcntl.h>
1.37 +
1.38 +#include "elf_symbol_table.h"
1.39 +
1.40 +#define _GNU_SOURCE
1.41 +#include <getopt.h>
1.42 +
1.43 +#define PAGE_SIZE 4096
1.44 +#define SYMBOL_ALIGN 4
1.45 +
1.46 +//----------------------------------------------------------------------
1.47 +
1.48 +class call_pair
1.49 +{
1.50 +public:
1.51 + const Elf32_Sym *m_lo;
1.52 + const Elf32_Sym *m_hi;
1.53 +
1.54 + call_pair(const Elf32_Sym *site1, const Elf32_Sym *site2)
1.55 + {
1.56 + if (site1 < site2) {
1.57 + m_lo = site1;
1.58 + m_hi = site2;
1.59 + }
1.60 + else {
1.61 + m_hi = site1;
1.62 + m_lo = site2;
1.63 + }
1.64 + }
1.65 +
1.66 + friend bool
1.67 + operator==(const call_pair &lhs, const call_pair &rhs)
1.68 + {
1.69 + return (lhs.m_lo == rhs.m_lo) && (lhs.m_hi == rhs.m_hi);
1.70 + }
1.71 +};
1.72 +
1.73 +// Straight outta plhash.c!
1.74 +#define GOLDEN_RATIO 0x9E3779B9U
1.75 +
1.76 +template<>
1.77 +struct hash<call_pair>
1.78 +{
1.79 + size_t operator()(const call_pair &pair) const
1.80 + {
1.81 + size_t h = (reinterpret_cast<size_t>(pair.m_hi) >> 4);
1.82 + h += (reinterpret_cast<size_t>(pair.m_lo) >> 4);
1.83 + h *= GOLDEN_RATIO;
1.84 + return h;
1.85 + }
1.86 +};
1.87 +
1.88 +//----------------------------------------------------------------------
1.89 +
1.90 +struct hash<const Elf32_Sym *>
1.91 +{
1.92 + size_t operator()(const Elf32_Sym *sym) const
1.93 + {
1.94 + return (reinterpret_cast<size_t>(sym) >> 4) * GOLDEN_RATIO;
1.95 + }
1.96 +};
1.97 +
1.98 +//----------------------------------------------------------------------
1.99 +
1.100 +typedef hash_map<call_pair, unsigned int> call_graph_t;
1.101 +call_graph_t call_graph;
1.102 +
1.103 +typedef hash_map<const Elf32_Sym *, unsigned int> histogram_t;
1.104 +histogram_t histogram;
1.105 +long long total_calls = 0;
1.106 +
1.107 +elf_symbol_table symtab;
1.108 +
1.109 +bool opt_debug = false;
1.110 +int opt_generations = 10;
1.111 +int opt_mutate = 0;
1.112 +const char *opt_out = "order.out";
1.113 +int opt_population_size = 100;
1.114 +int opt_tick = 0;
1.115 +bool opt_verbose = false;
1.116 +int opt_window = 0;
1.117 +
1.118 +static struct option long_options[] = {
1.119 + { "debug", no_argument, 0, 'd' },
1.120 + { "exe", required_argument, 0, 'e' },
1.121 + { "generations", required_argument, 0, 'g' },
1.122 + { "help", no_argument, 0, '?' },
1.123 + { "mutate", required_argument, 0, 'm' },
1.124 + { "out", required_argument, 0, 'o' },
1.125 + { "population", required_argument, 0, 'p' },
1.126 + { "seed", required_argument, 0, 's' },
1.127 + { "tick", optional_argument, 0, 't' },
1.128 + { "verbose", no_argument, 0, 'v' },
1.129 + { "window", required_argument, 0, 'w' },
1.130 + { 0, 0, 0, 0 }
1.131 +};
1.132 +
1.133 +//----------------------------------------------------------------------
1.134 +
1.135 +static long long
1.136 +llrand()
1.137 +{
1.138 + long long result;
1.139 + result = (long long) rand();
1.140 + result *= (long long) (unsigned int) (RAND_MAX + 1);
1.141 + result += (long long) rand();
1.142 + return result;
1.143 +}
1.144 +
1.145 +//----------------------------------------------------------------------
1.146 +
1.147 +class symbol_order {
1.148 +public:
1.149 + typedef vector<const Elf32_Sym *> vector_t;
1.150 + typedef long long score_t;
1.151 +
1.152 + static const score_t max_score;
1.153 +
1.154 + /**
1.155 + * A vector of symbols that is this ordering.
1.156 + */
1.157 + vector_t m_ordering;
1.158 +
1.159 + /**
1.160 + * The symbol ordering's score.
1.161 + */
1.162 + score_t m_score;
1.163 +
1.164 + symbol_order() : m_score(0) {}
1.165 +
1.166 + /**
1.167 + * ``Shuffle'' a symbol ordering, randomizing it.
1.168 + */
1.169 + void shuffle();
1.170 +
1.171 + /**
1.172 + * Initialize this symbol ordering by performing a crossover from
1.173 + * two ``parent'' symbol orderings.
1.174 + */
1.175 + void crossover_from(const symbol_order *father, const symbol_order *mother);
1.176 +
1.177 + /**
1.178 + * Randomly mutate this symbol ordering.
1.179 + */
1.180 + void mutate();
1.181 +
1.182 + /**
1.183 + * Score a symbol ordering based on paginated locality.
1.184 + */
1.185 + score_t compute_score_page();
1.186 +
1.187 + /**
1.188 + * Score a symbol ordering based on a sliding window.
1.189 + */
1.190 + score_t compute_score_window(int window_size);
1.191 +
1.192 + static score_t compute_score(symbol_order &order);
1.193 +
1.194 + /**
1.195 + * Use the symbol table to dump the ordered symbolic constants.
1.196 + */
1.197 + void dump_symbols() const;
1.198 +
1.199 + friend ostream &
1.200 + operator<<(ostream &out, const symbol_order &order);
1.201 +};
1.202 +
1.203 +const symbol_order::score_t
1.204 +symbol_order::max_score = ~((symbol_order::score_t)1 << ((sizeof(symbol_order::score_t) * 8) - 1));
1.205 +
1.206 +symbol_order::score_t
1.207 +symbol_order::compute_score_page()
1.208 +{
1.209 + m_score = 0;
1.210 +
1.211 + unsigned int off = 0; // XXX in reality, probably not page-aligned to start
1.212 +
1.213 + vector_t::const_iterator end = m_ordering.end(),
1.214 + last = end,
1.215 + sym = m_ordering.begin();
1.216 +
1.217 + while (sym != end) {
1.218 + vector_t page;
1.219 +
1.220 + // If we had a symbol that spilled over from the last page,
1.221 + // then include it here.
1.222 + if (last != end)
1.223 + page.push_back(*last);
1.224 +
1.225 + // Pack symbols into the page
1.226 + do {
1.227 + page.push_back(*sym);
1.228 +
1.229 + int size = (*sym)->st_size;
1.230 + size += SYMBOL_ALIGN - 1;
1.231 + size &= ~(SYMBOL_ALIGN - 1);
1.232 +
1.233 + off += size;
1.234 + } while (++sym != end && off < PAGE_SIZE);
1.235 +
1.236 + // Remember if there was spill-over.
1.237 + off %= PAGE_SIZE;
1.238 + last = (off != 0) ? sym : end;
1.239 +
1.240 + // Now score the page as the count of all calls to symbols on
1.241 + // the page, less calls between the symbols on the page.
1.242 + vector_t::const_iterator page_end = page.end();
1.243 + for (vector_t::const_iterator i = page.begin(); i != page_end; ++i) {
1.244 + histogram_t::const_iterator func = histogram.find(*i);
1.245 + if (func == histogram.end())
1.246 + continue;
1.247 +
1.248 + m_score += func->second;
1.249 +
1.250 + vector_t::const_iterator j = i;
1.251 + for (++j; j != page_end; ++j) {
1.252 + call_graph_t::const_iterator call =
1.253 + call_graph.find(call_pair(*i, *j));
1.254 +
1.255 + if (call != call_graph.end())
1.256 + m_score -= call->second;
1.257 + }
1.258 + }
1.259 + }
1.260 +
1.261 + assert(m_score >= 0);
1.262 +
1.263 + // Integer reciprocal so we minimize instead of maximize.
1.264 + if (m_score == 0)
1.265 + m_score = 1;
1.266 +
1.267 + m_score = (total_calls / m_score) + 1;
1.268 +
1.269 + return m_score;
1.270 +}
1.271 +
1.272 +symbol_order::score_t
1.273 +symbol_order::compute_score_window(int window_size)
1.274 +{
1.275 + m_score = 0;
1.276 +
1.277 + vector_t::const_iterator *window = new vector_t::const_iterator[window_size];
1.278 + int window_fill = 0;
1.279 +
1.280 + vector_t::const_iterator end = m_ordering.end(),
1.281 + sym = m_ordering.begin();
1.282 +
1.283 + for (; sym != end; ++sym) {
1.284 + histogram_t::const_iterator func = histogram.find(*sym);
1.285 + if (func != histogram.end()) {
1.286 + long long scale = ((long long) 1) << window_size;
1.287 +
1.288 + m_score += func->second * scale * 2;
1.289 +
1.290 + vector_t::const_iterator *limit = window + window_fill;
1.291 + vector_t::const_iterator *iter;
1.292 + for (iter = window ; iter < limit; ++iter) {
1.293 + call_graph_t::const_iterator call =
1.294 + call_graph.find(call_pair(*sym, **iter));
1.295 +
1.296 + if (call != call_graph.end())
1.297 + m_score -= (call->second * scale);
1.298 +
1.299 + scale >>= 1;
1.300 + }
1.301 + }
1.302 +
1.303 + // Slide the window.
1.304 + vector_t::const_iterator *begin = window;
1.305 + vector_t::const_iterator *iter;
1.306 + for (iter = window + (window_size - 1); iter > begin; --iter)
1.307 + *iter = *(iter - 1);
1.308 +
1.309 + if (window_fill < window_size)
1.310 + ++window_fill;
1.311 +
1.312 + *window = sym;
1.313 + }
1.314 +
1.315 + delete[] window;
1.316 +
1.317 + assert(m_score >= 0);
1.318 +
1.319 + // Integer reciprocal so we minimize instead of maximize.
1.320 + if (m_score == 0)
1.321 + m_score = 1;
1.322 +
1.323 + m_score = (total_calls / m_score) + 1;
1.324 +
1.325 + return m_score;
1.326 +}
1.327 +
1.328 +symbol_order::score_t
1.329 +symbol_order::compute_score(symbol_order &order)
1.330 +{
1.331 + if (opt_window)
1.332 + return order.compute_score_window(opt_window);
1.333 +
1.334 + return order.compute_score_page();
1.335 +}
1.336 +
1.337 +void
1.338 +symbol_order::shuffle()
1.339 +{
1.340 + vector_t::iterator sym = m_ordering.begin();
1.341 + vector_t::iterator end = m_ordering.end();
1.342 + for (; sym != end; ++sym) {
1.343 + int i = rand() % m_ordering.size();
1.344 + const Elf32_Sym *temp = *sym;
1.345 + *sym = m_ordering[i];
1.346 + m_ordering[i] = temp;
1.347 + }
1.348 +}
1.349 +
1.350 +void
1.351 +symbol_order::crossover_from(const symbol_order *father, const symbol_order *mother)
1.352 +{
1.353 + histogram_t used;
1.354 +
1.355 + m_ordering = vector_t(father->m_ordering.size(), 0);
1.356 +
1.357 + vector_t::const_iterator parent_sym = father->m_ordering.begin();
1.358 + vector_t::iterator sym = m_ordering.begin();
1.359 + vector_t::iterator end = m_ordering.end();
1.360 +
1.361 + for (; sym != end; ++sym, ++parent_sym) {
1.362 + if (rand() % 2) {
1.363 + *sym = *parent_sym;
1.364 + used[*parent_sym] = 1;
1.365 + }
1.366 + }
1.367 +
1.368 + parent_sym = mother->m_ordering.begin();
1.369 + sym = m_ordering.begin();
1.370 +
1.371 + for (; sym != end; ++sym) {
1.372 + if (! *sym) {
1.373 + while (used[*parent_sym])
1.374 + ++parent_sym;
1.375 +
1.376 + *sym = *parent_sym++;
1.377 + }
1.378 + }
1.379 +}
1.380 +
1.381 +void
1.382 +symbol_order::mutate()
1.383 +{
1.384 + int i, j;
1.385 + i = rand() % m_ordering.size();
1.386 + j = rand() % m_ordering.size();
1.387 +
1.388 + const Elf32_Sym *temp = m_ordering[i];
1.389 + m_ordering[i] = m_ordering[j];
1.390 + m_ordering[j] = temp;
1.391 +}
1.392 +
1.393 +void
1.394 +symbol_order::dump_symbols() const
1.395 +{
1.396 + ofstream out(opt_out);
1.397 +
1.398 + vector_t::const_iterator sym = m_ordering.begin();
1.399 + vector_t::const_iterator end = m_ordering.end();
1.400 + for (; sym != end; ++sym)
1.401 + out << symtab.get_symbol_name(*sym) << endl;
1.402 +
1.403 + out.close();
1.404 +}
1.405 +
1.406 +ostream &
1.407 +operator<<(ostream &out, const symbol_order &order)
1.408 +{
1.409 + out << "symbol_order(" << order.m_score << ") ";
1.410 +
1.411 + symbol_order::vector_t::const_iterator sym = order.m_ordering.begin();
1.412 + symbol_order::vector_t::const_iterator end = order.m_ordering.end();
1.413 + for (; sym != end; ++sym)
1.414 + out.form("%08x ", *sym);
1.415 +
1.416 + out << endl;
1.417 +
1.418 + return out;
1.419 +}
1.420 +
1.421 +//----------------------------------------------------------------------
1.422 +
1.423 +static void
1.424 +usage(const char *name)
1.425 +{
1.426 + cerr << "usage: " << name << " [options] [<file> ...]" << endl;
1.427 + cerr << " Options:" << endl;
1.428 + cerr << " --debug, -d" << endl;
1.429 + cerr << " Print lots of verbose debugging cruft." << endl;
1.430 + cerr << " --exe=<image>, -e <image> (required)" << endl;
1.431 + cerr << " Specify the executable image from which to read symbol information." << endl;
1.432 + cerr << " --generations=<num>, -g <num>" << endl;
1.433 + cerr << " Specify the number of generations to run the GA (default is 10)." << endl;
1.434 + cerr << " --help, -?" << endl;
1.435 + cerr << " Print this message and exit." << endl;
1.436 + cerr << " --mutate=<num>, -m <num>" << endl;
1.437 + cerr << " Mutate every <num>th individual, or zero for no mutation (default)." << endl;
1.438 + cerr << " --out=<file>, -o <file>" << endl;
1.439 + cerr << " Specify the output file to which to dump the symbol ordering of the" << endl;
1.440 + cerr << " best individual (default is `order.out')." << endl;
1.441 + cerr << " --population=<num>, -p <num>" << endl;
1.442 + cerr << " Set the population size to <num> individuals (default is 100)." << endl;
1.443 + cerr << " --seed=<num>, -s <num>" << endl;
1.444 + cerr << " Specify a seed to srand()." << endl;
1.445 + cerr << " --tick[=<num>], -t [<num>]" << endl;
1.446 + cerr << " When reading address data, print a dot to stderr every <num>th" << endl;
1.447 + cerr << " address processed from the call trace. If specified with no argument," << endl;
1.448 + cerr << " a dot will be printed for every million addresses processed." << endl;
1.449 + cerr << " --verbose, -v" << endl;
1.450 + cerr << " Issue progress messages to stderr." << endl;
1.451 + cerr << " --window=<num>, -w <num>" << endl;
1.452 + cerr << " Use a sliding window instead of pagination to score orderings." << endl;
1.453 + cerr << endl;
1.454 + cerr << "This program uses a genetic algorithm to produce an `optimal' ordering for" << endl;
1.455 + cerr << "an executable based on call patterns." << endl;
1.456 + cerr << endl;
1.457 + cerr << "Addresses from a call trace are read as binary data from the files" << endl;
1.458 + cerr << "specified, or from stdin if no files are specified. These addresses" << endl;
1.459 + cerr << "are used with the symbolic information from the executable to create" << endl;
1.460 + cerr << "a call graph. This call graph is used to `score' arbitrary symbol" << endl;
1.461 + cerr << "orderings, and provides the fitness function for the GA." << endl;
1.462 + cerr << endl;
1.463 +}
1.464 +
1.465 +/**
1.466 + * Using the symbol table, map a stream of address references into a
1.467 + * callgraph and a histogram.
1.468 + */
1.469 +static void
1.470 +map_addrs(int fd)
1.471 +{
1.472 + const Elf32_Sym *last = 0;
1.473 + unsigned int buf[128];
1.474 + ssize_t cb;
1.475 +
1.476 + unsigned int count = 0;
1.477 + while ((cb = read(fd, buf, sizeof buf)) > 0) {
1.478 + if (cb % sizeof buf[0])
1.479 + fprintf(stderr, "unaligned read\n");
1.480 +
1.481 + unsigned int *addr = buf;
1.482 + unsigned int *limit = buf + (cb / 4);
1.483 +
1.484 + for (; addr < limit; ++addr) {
1.485 + const Elf32_Sym *sym = symtab.lookup(*addr);
1.486 +
1.487 + if (last && sym && last != sym) {
1.488 + ++total_calls;
1.489 + ++histogram[sym];
1.490 + ++call_graph[call_pair(last, sym)];
1.491 +
1.492 + if (opt_tick && (++count % opt_tick == 0)) {
1.493 + cerr << ".";
1.494 + flush(cerr);
1.495 + }
1.496 + }
1.497 +
1.498 + last = sym;
1.499 + }
1.500 + }
1.501 +
1.502 + if (opt_tick)
1.503 + cerr << endl;
1.504 +
1.505 + cerr << "Total calls: " << total_calls << endl;
1.506 + total_calls *= 1024;
1.507 +
1.508 + if (opt_window)
1.509 + total_calls <<= (opt_window + 1);
1.510 +}
1.511 +
1.512 +static symbol_order *
1.513 +pick_parent(symbol_order *ordering, int max, int index)
1.514 +{
1.515 + while (1) {
1.516 + index -= ordering->m_score;
1.517 + if (index < 0)
1.518 + break;
1.519 +
1.520 + ++ordering;
1.521 + }
1.522 +
1.523 + return ordering;
1.524 +}
1.525 +
1.526 +/**
1.527 + * The main program
1.528 + */
1.529 +int
1.530 +main(int argc, char *argv[])
1.531 +{
1.532 + const char *opt_exe = 0;
1.533 +
1.534 + int c;
1.535 + while (1) {
1.536 + int option_index = 0;
1.537 + c = getopt_long(argc, argv, "?de:g:m:o:p:s:t:vw:", long_options, &option_index);
1.538 +
1.539 + if (c < 0)
1.540 + break;
1.541 +
1.542 + switch (c) {
1.543 + case '?':
1.544 + usage(argv[0]);
1.545 + return 0;
1.546 +
1.547 + case 'd':
1.548 + opt_debug = true;
1.549 + break;
1.550 +
1.551 + case 'e':
1.552 + opt_exe = optarg;
1.553 + break;
1.554 +
1.555 + case 'g':
1.556 + opt_generations = atoi(optarg);
1.557 + break;
1.558 +
1.559 + case 'm':
1.560 + opt_mutate = atoi(optarg);
1.561 + break;
1.562 +
1.563 + case 'o':
1.564 + opt_out = optarg;
1.565 + break;
1.566 +
1.567 + case 'p':
1.568 + opt_population_size = atoi(optarg);
1.569 + break;
1.570 +
1.571 + case 's':
1.572 + srand(atoi(optarg));
1.573 + break;
1.574 +
1.575 + case 't':
1.576 + opt_tick = optarg ? atoi(optarg) : 1000000;
1.577 + break;
1.578 +
1.579 + case 'v':
1.580 + opt_verbose = true;
1.581 + break;
1.582 +
1.583 + case 'w':
1.584 + opt_window = atoi(optarg);
1.585 + if (opt_window < 0 || opt_window > 8) {
1.586 + cerr << "invalid window size: " << opt_window << endl;
1.587 + return 1;
1.588 + }
1.589 +
1.590 + break;
1.591 +
1.592 + default:
1.593 + usage(argv[0]);
1.594 + return 1;
1.595 + }
1.596 + }
1.597 +
1.598 + // Make sure an image was specified
1.599 + if (! opt_exe) {
1.600 + usage(argv[0]);
1.601 + return 1;
1.602 + }
1.603 +
1.604 + // Read the sym table.
1.605 + symtab.init(opt_exe);
1.606 +
1.607 + // Process addresses to construct the call graph.
1.608 + if (optind >= argc) {
1.609 + map_addrs(STDIN_FILENO);
1.610 + }
1.611 + else {
1.612 + do {
1.613 + int fd = open(argv[optind], O_RDONLY);
1.614 + if (fd < 0) {
1.615 + perror(argv[optind]);
1.616 + return 1;
1.617 + }
1.618 +
1.619 + map_addrs(fd);
1.620 + close(fd);
1.621 + } while (++optind < argc);
1.622 + }
1.623 +
1.624 + if (opt_debug) {
1.625 + cerr << "Call graph:" << endl;
1.626 +
1.627 + call_graph_t::const_iterator limit = call_graph.end();
1.628 + call_graph_t::const_iterator i;
1.629 + for (i = call_graph.begin(); i != limit; ++i) {
1.630 + const call_pair& pair = i->first;
1.631 + cerr.form("%08x %08x %10d\n",
1.632 + pair.m_lo->st_value,
1.633 + pair.m_hi->st_value,
1.634 + i->second);
1.635 + }
1.636 + }
1.637 +
1.638 + // Collect the symbols into a vector
1.639 + symbol_order::vector_t ordering;
1.640 + elf_symbol_table::const_iterator end = symtab.end();
1.641 + for (elf_symbol_table::const_iterator sym = symtab.begin(); sym != end; ++sym) {
1.642 + if (symtab.is_function(sym))
1.643 + ordering.push_back(sym);
1.644 + }
1.645 +
1.646 + if (opt_verbose) {
1.647 + symbol_order initial;
1.648 + initial.m_ordering = ordering;
1.649 + cerr << "created initial ordering, score=" << symbol_order::compute_score(initial) << endl;
1.650 +
1.651 + if (opt_debug)
1.652 + cerr << initial;
1.653 + }
1.654 +
1.655 + // Create a population.
1.656 + if (opt_verbose)
1.657 + cerr << "creating population" << endl;
1.658 +
1.659 + symbol_order *population = new symbol_order[opt_population_size];
1.660 +
1.661 + symbol_order::score_t total = 0, min = symbol_order::max_score, max = 0;
1.662 +
1.663 + // Score it.
1.664 + symbol_order *order = population;
1.665 + symbol_order *limit = population + opt_population_size;
1.666 + for (; order < limit; ++order) {
1.667 + order->m_ordering = ordering;
1.668 + order->shuffle();
1.669 +
1.670 + symbol_order::score_t score = symbol_order::compute_score(*order);
1.671 +
1.672 + if (opt_debug)
1.673 + cerr << *order;
1.674 +
1.675 + if (min > score)
1.676 + min = score;
1.677 + if (max < score)
1.678 + max = score;
1.679 +
1.680 + total += score;
1.681 + }
1.682 +
1.683 + if (opt_verbose) {
1.684 + cerr << "Initial population";
1.685 + cerr << ": min=" << min;
1.686 + cerr << ", max=" << max;
1.687 + cerr << " mean=" << (total / opt_population_size);
1.688 + cerr << endl;
1.689 + }
1.690 +
1.691 +
1.692 + // Run the GA.
1.693 + if (opt_verbose)
1.694 + cerr << "begininng ga" << endl;
1.695 +
1.696 + symbol_order::score_t best = 0;
1.697 +
1.698 + for (int generation = 1; generation <= opt_generations; ++generation) {
1.699 + // Create a new population.
1.700 + symbol_order *offspring = new symbol_order[opt_population_size];
1.701 +
1.702 + symbol_order *kid = offspring;
1.703 + symbol_order *offspring_limit = offspring + opt_population_size;
1.704 + for (; kid < offspring_limit; ++kid) {
1.705 + // Pick parents.
1.706 + symbol_order *father, *mother;
1.707 + father = pick_parent(population, max, llrand() % total);
1.708 + mother = pick_parent(population, max, llrand() % total);
1.709 +
1.710 + // Create a kid.
1.711 + kid->crossover_from(father, mother);
1.712 +
1.713 + // Mutate, possibly.
1.714 + if (opt_mutate) {
1.715 + if (rand() % opt_mutate == 0)
1.716 + kid->mutate();
1.717 + }
1.718 + }
1.719 +
1.720 + delete[] population;
1.721 + population = offspring;
1.722 +
1.723 + // Score the new population.
1.724 + total = 0;
1.725 + min = symbol_order::max_score;
1.726 + max = 0;
1.727 +
1.728 + symbol_order *fittest = 0;
1.729 +
1.730 + limit = offspring_limit;
1.731 + for (order = population; order < limit; ++order) {
1.732 + symbol_order::score_t score = symbol_order::compute_score(*order);
1.733 +
1.734 + if (opt_debug)
1.735 + cerr << *order;
1.736 +
1.737 + if (min > score)
1.738 + min = score;
1.739 +
1.740 + if (max < score)
1.741 + max = score;
1.742 +
1.743 + if (best < score) {
1.744 + best = score;
1.745 + fittest = order;
1.746 + }
1.747 +
1.748 + total += score;
1.749 + }
1.750 +
1.751 + if (opt_verbose) {
1.752 + cerr << "Generation " << generation;
1.753 + cerr << ": min=" << min;
1.754 + cerr << ", max=" << max;
1.755 + if (fittest)
1.756 + cerr << "*";
1.757 + cerr << " mean=" << (total / opt_population_size);
1.758 + cerr << endl;
1.759 + }
1.760 +
1.761 + // If we've found a new ``best'' individual, dump it.
1.762 + if (fittest)
1.763 + fittest->dump_symbols();
1.764 + }
1.765 +
1.766 + delete[] population;
1.767 + return 0;
1.768 +}
