Logo Search packages:      
Sourcecode: acovea version File versions

acovea.cpp

//---------------------------------------------------------------------
//  ACOVEA -- Analysis of Compiler Options Via Evolution Algorithm
//
//  acovea.cpp
//
//  Class definitions for the ACOVEA algorithm
//---------------------------------------------------------------------
//
//  COPYRIGHT NOTICE, DISCLAIMER, and LICENSE:
//
//  This notice applies *only* to this specific expression of this
//  algorithm, and does not imply ownership or invention of the
//  implemented algorithm.
//  
//  If you modify this file, you may insert additional notices
//  immediately following this sentence.
//  
//  Copyright 2003, 2004 Scott Robert Ladd. All rights reserved.
//  All rights reserved, except as noted herein.
//
//  This computer program source file is supplied "AS IS". Scott Robert
//  Ladd (hereinafter referred to as "Author") disclaims all warranties,
//  expressed or implied, including, without limitation, the warranties
//  of merchantability and of fitness for any purpose. The Author
//  assumes no liability for direct, indirect, incidental, special,
//  exemplary, or consequential damages, which may result from the use
//  of this software, even if advised of the possibility of such damage.
//  
//  The Author hereby grants anyone permission to use, copy, modify, and
//  distribute this source code, or portions hereof, for any purpose,
//  without fee, subject to the following restrictions:
//  
//      1. The origin of this source code must not be misrepresented.
//  
//      2. Altered versions must be plainly marked as such and must not
//         be misrepresented as being the original source.
//  
//      3. This Copyright notice may not be removed or altered from any
//         source or altered source distribution.
//  
//  The Author specifically permits (without fee) and encourages the use
//  of this source code for entertainment, education, or decoration. If
//  you use this source code in a product, acknowledgment is not required
//  but would be appreciated.
//  
//  Acknowledgement:
//      This license is based on the wonderful simple license that
//      accompanies libpng.
//
//-----------------------------------------------------------------------
//
//  For more information on this software package, please visit
//  Scott's web site, Coyote Gulch Productions, at:
//
//      http://www.coyotegulch.com
//  
//-----------------------------------------------------------------------

#include "acovea.h"
using namespace acovea;

#include "libcoyotl/realutil.h"
#include "libcoyotl/sortutil.h"
using namespace libcoyotl;

#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>

#include <vector>
#include <cstring>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <stdexcept>
using namespace std;

// the expat XML parsing library
#include "expat.h"

// global version string
const string acovea::common::G_VERSION  = "4.0.0";

//----------------------------------------------------------
// abstract definition of a compiler option or switch

// creation constructor
option::option(bool a_enabled)
  : m_enabled(a_enabled)
{
    // nada
}

// copy constructor
option::option(const option & a_source)
  : m_enabled(a_source.m_enabled)
{
    // nada
}

// assignment 
option & option::operator = (const option & a_source)
{
    m_enabled = a_source.m_enabled;
    return *this;
}

// randomize settings of this option
void option::randomize()
{
    m_enabled = (g_random.get_rand_real2() < 0.5);
}

// mutate this option
void option::mutate()
{
    m_enabled = !m_enabled;
}

// virtual destructor (does nothing unless overridden)
option::~option()
{
    // nada
};

//----------------------------------------------------------
// an option that is just a string

// creation constructor
simple_option::simple_option(const string & a_name, bool a_enabled)
  : option(a_enabled),
    m_name(a_name)
{
    // nada
}

simple_option::simple_option(const char * a_name, bool a_enabled)
  : option(a_enabled),
    m_name(a_name)
{
    // nada
}

// copy constructor
simple_option::simple_option(const simple_option & a_source)
  : option(a_source),
    m_name(a_source.m_name)
{
    // nada
}

// assignment operator
simple_option & simple_option::operator = (const simple_option & a_source)
{
    option::operator = (a_source);
    m_name = a_source.m_name;
    return *this;
}

// clone
option * simple_option::clone()
{
    return new simple_option(*this);
}
            
//----------------------------------------------------------
// value settings tracker 

// constructor
tuning_settings_tracker::tuning_settings_tracker(const tuning_option & a_option)
  : m_values()
{
    // add value to list
    m_values.push_back(a_option.is_enabled() ? a_option.get_value() : 0);
}

// copy constructor
tuning_settings_tracker::tuning_settings_tracker(const tuning_settings_tracker & a_source)
  : m_values(a_source.m_values)
{
    // nada
}

// assignment
tuning_settings_tracker & tuning_settings_tracker::operator = (const tuning_settings_tracker & a_source)
{
    m_values = a_source.m_values;
}       

// get a string representing this settings tracker
string tuning_settings_tracker::get_settings_text()
{
    stringstream result;
    long average = 0;
    int nonzero_count = 0;
    
    if (m_values.size() > 0)
    {
        for (vector<int>::iterator value = m_values.begin(); value != m_values.end(); ++value)
        {
            result << (*value) << " ";
            average += (*value);
            
            if ((*value) > 0)
                ++nonzero_count;
        }
    
        if (nonzero_count > 0)
            average /= nonzero_count;
        else
            average  = 0;
        
        result << ", average = " << average << " across " << nonzero_count << " populations";
    }
    
    return result.str();
}

// accumulate values
settings_tracker & tuning_settings_tracker::operator += (const settings_tracker & tracker)
{
    try
    {
        // this will crash is a non-value setting_tracker is the argument
        const vector<int> & new_values = (dynamic_cast<const tuning_settings_tracker &>(tracker)).m_values;
        
        // add new values to list
        for (vector<int>::const_iterator value = new_values.begin(); value != new_values.end(); ++value)
            m_values.push_back(*value);
    }
    catch (...)
    {
        cerr << "mixed tracker types in tuning_settings_tracker\n";
    }
    
    return *this;
}
        
//----------------------------------------------------------
// an option or switch that requires an integer argument

// creation constructor
tuning_option::tuning_option(const string & a_name,
                           bool a_enabled,
                           int  a_default,
                           int  a_min_value,
                           int  a_max_value,
                           int  a_step,
                           char a_separator)
  : simple_option(a_name, a_enabled),
    m_value(a_default),
    m_default(a_default),
    m_min_value(a_min_value),
    m_max_value(a_max_value),
    m_step(a_step),
    m_separator(a_separator)
{
    // make sure min < max
    if (m_min_value > m_max_value)
    {
        int temp = m_min_value;
        m_min_value = m_max_value;
        m_max_value = temp;
    }

    // step must be >= 1;
    if (m_step < 1)
        m_step = 1;
    
    // possibly adjust value to randomize populations
    size_t choice = g_random.get_rand_index(3);
    
    switch (choice)
    {
        case 0:
            m_value += m_step;
            break;
        case 1:
            m_value -= m_step;
            break;
    }

    // ensure value is inside specified range
    if (m_value < m_min_value)
        m_value = m_min_value;

    if (m_value > m_max_value)
        m_value = m_max_value;
}

// copy constructor
tuning_option::tuning_option(const tuning_option & a_source)
  : simple_option(a_source),
    m_value(a_source.m_value),
    m_default(a_source.m_default),
    m_min_value(a_source.m_min_value),
    m_max_value(a_source.m_max_value),
    m_step(a_source.m_step),
    m_separator(a_source.m_separator)
{
    // nada
}

// assignment operator
tuning_option & tuning_option::operator = (const tuning_option & a_source)
{
    simple_option::operator = (a_source);
    m_value       = a_source.m_value;
    m_default     = a_source.m_default;
    m_min_value   = a_source.m_min_value;
    m_max_value   = a_source.m_max_value;
    m_step        = a_source.m_step;
    m_separator   = a_source.m_separator;
    return *this;
}

// get the string for this option
string tuning_option::get() const
{
    stringstream result;
    result << m_name << m_separator << m_value;
    return result.str();
}

// mutate this option
void tuning_option::mutate()
{
    // select our mutation
    if (g_random.get_rand_real2() < 0.5)
        option::mutate();
    else
    {
        // mutate value of this option, up or down randomly
        if (g_random.get_rand_real2() < 0.5)
            m_value -= m_step;
        else
            m_value += m_step;

        // ensure value stays within bounds
        if (m_value < m_min_value)
            m_value = m_min_value;

        if (m_value > m_max_value)
            m_value = m_max_value;
    }
}

// clone
option * tuning_option::clone()
{
    return new tuning_option(*this);
}

//----------------------------------------------------------
// an option or switch set to one of several mutually-exclusive states
// creation constructor
enum_option::enum_option(const vector<string> & a_choices, bool a_enabled)
  : option(a_enabled),
    m_choices(a_choices),
    m_setting(g_random.get_rand_index(a_choices.size()))    
{
    // nada
}

// creation constructor
enum_option::enum_option(const char ** a_choices, size_t a_num_choices, bool a_enabled)
  : option(a_enabled),
    m_choices(),
    m_setting(g_random.get_rand_index(a_num_choices))    
{
    for (int n = 0; n < a_num_choices; ++n)
        m_choices.push_back(string(a_choices[n]));
}

// creation constructor
enum_option::enum_option(const char * a_choices, bool a_enabled)
  : option(a_enabled),
    m_choices(),
    m_setting(0)    
{
    // start tokenizing
    char * choices = strdup(a_choices);
    char * token   = strtok(choices,"|");

    while (token != NULL)
    {
        // add token to choice list
        m_choices.push_back(string(token));

        // next token
        token = strtok(NULL,"|");
    }
    
    m_setting = g_random.get_rand_index(m_choices.size());
    
    free(choices);
}

// copy constructor
enum_option::enum_option(const enum_option & a_source)
  : option(a_source),
    m_choices(a_source.m_choices),
    m_setting(a_source.m_setting)
{
    // nada
}

// assignment 
enum_option & enum_option::operator = (const enum_option & a_source)
{
    option::operator = (a_source);
    m_choices = a_source.m_choices;
    m_setting = a_source.m_setting;
}

// clone
option * enum_option::clone()
{
    return new enum_option(*this);
}

// get the string for this option
string enum_option::get() const
{
    return m_choices[m_setting];
}

// randomize settings of this option
void enum_option::randomize()
{
    // randomize enabled
    m_enabled = (g_random.get_rand_real2() < 0.5);
    
    // randomize setting
    m_setting = g_random.get_rand_index(m_choices.size());
}

// mutate this option
void enum_option::mutate()
{
    // select our mutation
    if (g_random.get_rand() & 1)
        option::mutate();
    else
    {
        // mutate setting of this option
        if (m_choices.size() == 2)
        {
            if (m_setting == 0)
                m_setting = 1;
            else
                m_setting = 0;
        }
        else
        {
            int new_setting = m_setting;
        
            // find a different setting
            while (new_setting == m_setting)
                new_setting = g_random.get_rand_index(m_choices.size());
            
            m_setting = new_setting;
        }
    }
}

// virtual destructor (does nothing unless overridden)
enum_option::~enum_option()
{
    // nada
}

//----------------------------------------------------------
// a vector of options

// constructor
chromosome::chromosome()
{
    // nada
}

// copy constructor
chromosome::chromosome(const chromosome & a_source)
{
    // add elements from source
    for (int n = 0; n < a_source.size(); ++n)
        push_back(a_source[n]->clone());
}

// assignment
chromosome & chromosome::operator = (const chromosome & a_source)
{
    // remove all elements from the vector
    clear();
    
    // add elements from source
    for (int n = 0; n < a_source.size(); ++n)
        push_back(a_source[n]->clone());
    
    return *this;
}

// destructor
chromosome::~chromosome()
{
    // free memory allocated in elements of vector
    for (vector<option *>::iterator opt = begin(); opt != end(); ++opt)
        delete *opt;
}

//----------------------------------------------------------
// the definition of a compiler

// static functions used by XML parser
static void parser_start(void * compiler_ptr, const char * element, const char ** attr)
{
    // have the compiler process this element
    static_cast<compiler *>(compiler_ptr)->import_element(element, attr);
}

static void parser_end(void * compiler_ptr, const char * element)
{
    // nada
}
            
// import an XML element
void compiler::import_element(const char * element, const char ** attr)
{
    int i;
    const char * value = NULL;
    const char * type = NULL;
    int defval  = 0;
    int minval  = 0;
    int maxval  = 0;
    int stepval = 0;
    char sep    = '=';
    
    if (0 == strcmp(element,"description"))
    {
        for (i = 0; attr[i] != NULL; i += 2)
        {
            if (0 == strcmp(attr[i],"value"))
                value = attr[i + 1];
        }
        
        if (value != NULL)
            m_description = string(value);
    }
    else if (0 == strcmp(element,"command"))
    {
        for (i = 0; attr[i] != NULL; i += 2)
        {
            if (0 == strcmp(attr[i],"value"))
                value = attr[i + 1];
        }
        
        if (value != NULL)
        {
            char * v = strdup(value);
            char * token = strtok(v,"|");
            
            while (token != NULL)
            {
                  m_command.push_back(string(token));
                token = strtok(NULL,"|");
            }
            
            free(v);
        }
    }
    else if (0 == strcmp(element,"flag"))
    {
        // search attributes
        for (i = 0; attr[i] != NULL; i += 2)
        {
            if (0 == strcmp(attr[i],"value"))
                value = attr[i + 1];
            else if (0 == strcmp(attr[i],"type"))
                type = attr[i + 1];
            else if (0 == strcmp(attr[i],"default"))
                defval = atoi(attr[i + 1]);
            else if (0 == strcmp(attr[i],"min"))
                minval = atoi(attr[i + 1]);
            else if (0 == strcmp(attr[i],"max"))
                maxval = atoi(attr[i + 1]);
            else if (0 == strcmp(attr[i],"step"))
                stepval = atoi(attr[i + 1]);
            else if (0 == strcmp(attr[i],"separator"))
                sep = attr[i + 1][0];
        }
        
        if ((value != NULL) && (type != NULL))
        {
            if (0 == strcmp(type,"simple"))
            {
                // cout << "simple_option: " << value << endl;
                m_options.push_back(new simple_option(value,false));
            }
            else if (0 == strcmp(type,"enum"))
            {
                // cout << "enum_option: " << value << endl;
                m_options.push_back(new enum_option(value,false));
            }
            else if (0 == strcmp(type,"tuning"))
            {
                // cout << "enum_option: " << value << endl;
                m_options.push_back(new tuning_option(value,false,defval,minval,maxval,stepval,sep));
            }
        }
    }
    else
    {
        // ignore anything we don't understand, like George W. Bush
    }
}

// creation constructor
compiler::compiler(const string & a_config_name)
  : m_config_name(a_config_name),
    m_command(),
    m_description(),
    m_options()
{
    // create an XML parser
      XML_Parser parser = XML_ParserCreate(NULL); 
    
    if (!parser)
        throw runtime_error("unable to create XML parser");
    
    // set the "user data" for the parser to this compiler
    XML_SetUserData(parser,static_cast<void *>(this));
    
    // set the element handler
    XML_SetElementHandler(parser,parser_start,parser_end);
    
    // read the input file to a buffer
    char * xml_buffer = new char[65538];
    
    FILE * xml_file = fopen(m_config_name.c_str(),"r");
    
    if (xml_file == NULL)
    {
        // try opening it in the source directory
        string temp_name(ACOVEA_CONFIG_DIR);
        temp_name += m_config_name; 
                
          xml_file = fopen(temp_name.c_str(),"r");
    
          if (xml_file == NULL)
          throw runtime_error("unable to open configuration file");
    }
    
    long nread = fread(xml_buffer,1,65538,xml_file);
    
    if (ferror(xml_file))
        throw runtime_error("unable to read from configuration file");

    // we're done with the file    
    fclose(xml_file);
    
      // parse the file and report any error    
    if (!XML_Parse(parser,xml_buffer,nread,1))
    {
        /*
        stderr << "invalid configuration file\nerror at line "
               << XML_GetCurrentLineNumber(parser)
               << "\n"
               << XML_ErrorString(XML_GetErrorCode(parser))
               << "\n"
        */
                
        throw runtime_error("XML parsing error");
    }
    
    // release memory
    delete [] xml_buffer;
}

// copy constructor
compiler::compiler(const compiler & a_source)
  : m_config_name(a_source.m_config_name),
    m_command(a_source.m_command),
    m_description(a_source.m_description),
    m_options(a_source.m_options)
{
    // nada
}

// assignment
compiler & compiler::operator = (const compiler & a_source)
{
    // call base class operator
    compiler::operator = (a_source);
    
    // assign members
    m_config_name   = a_source.m_config_name;
    m_command       = a_source.m_command;
    m_description   = a_source.m_description;
    m_options       = a_source.m_options;

    return *this;
}

// return a string description of the compiler and the configuration
string compiler::get_description() const
{
    return m_description;
}

// return name of the configuration file
string compiler::get_config_name() const
{
    return m_config_name;
}

// return an argument list for compiling a given program
vector<string> compiler::get_compile_command(const string &     a_source_name,
                                             const string &     a_exec_name,
                                             const chromosome & a_options) const
{
    // start with the command head
    vector<string> command(m_command);
    command.push_back(a_exec_name);
    
    // add enabled options
    for (int n = 0; n < a_options.size(); ++n)
    {
        if (a_options[n]->is_enabled())
            command.push_back(a_options[n]->get());
    }
    
    command.push_back(a_source_name);
    
    // return complete command set
    return command;
}

// get a random set of options for this compiler
chromosome compiler::get_random_options() const
{
    int n;
    
    // result
    chromosome options;
    
    // push_back options
    for (n = 0; n < m_options.size(); ++n)
        options.push_back(m_options[n]->clone());
    
    for (n = 0; n < m_options.size(); ++n)
          options[n]->randomize();
    
    // done
    return options;
}

// breed a new options set from two parents
chromosome compiler::breed(const chromosome & a_parent1,
                           const chromosome & a_parent2) const
{
    // This function assumes that the two lists are the same length, and
    // contain the same list of options in the same order
    if (a_parent1.size() != a_parent2.size())
    {
        char message[128];
        snprintf(message,128,"incompatible option vectors in breeding (sizes %d and %d)",a_parent1.size(),a_parent2.size());
        throw invalid_argument(message);
    }
    
    // result
    chromosome child;
    
    // randomly pick an option from one of the parents
    for (int n = 0; n < a_parent1.size(); ++n)
    {
        if (g_random.get_rand() & 1)
            child.push_back(a_parent1[n]->clone());
        else
            child.push_back(a_parent2[n]->clone());
    }
    
    // done
    return child;
}

// mutate an option set
void compiler::mutate(chromosome & a_options,
                            double a_mutation_chance) const
{
    for (int n = 0; n < a_options.size(); ++n)
    {
        if (g_random.get_rand_real2() < a_mutation_chance)
            a_options[n]->mutate();
    }
}

// get the option set size (should be fized for all chromosomes created
//   by this compiler)
size_t compiler::chromosome_length() const
{
    return m_options.size();
}
            
// destructor (to support derived classes)
compiler::~compiler()
{
    // nada
}

//----------------------------------------------------------
// the organism undergoing evolution
acovea_organism::acovea_organism()
  : organism< chromosome >()
{
    // nada
}

acovea_organism::acovea_organism(const compiler & a_target)
  : organism< chromosome >(a_target.get_random_options())
{
    // nada
}

acovea_organism::acovea_organism(const compiler & a_target,
                                 const chromosome & a_genes)
  : organism< chromosome >(a_genes)
{
    // nada
}

acovea_organism::acovea_organism(const acovea_organism & a_source)
  : organism< chromosome >(a_source)
{
    // nada
}

acovea_organism::acovea_organism(const acovea_organism & a_parent1,
                                 const acovea_organism & a_parent2,
                                 const compiler & a_target)
  : organism< chromosome >()
{
    m_genes = a_target.breed(a_parent1.genes(),a_parent2.genes());
}

acovea_organism::~acovea_organism()
{
    // nada
}

acovea_organism & acovea_organism::operator = (const acovea_organism & a_source)
{
    organism< chromosome >::operator = (a_source);
    return *this;
}

//----------------------------------------------------------
// mutation operator
acovea_mutator::acovea_mutator(double a_mutation_rate, const compiler & a_target)
  : m_mutation_rate(a_mutation_rate),
    m_target(a_target)
{
    // adjust mutation rate if necessary
    if (m_mutation_rate >= 0.95)
        m_mutation_rate = 0.95;
    else if (m_mutation_rate < 0.0)
        m_mutation_rate = 0.0;
}

// copy constructor
acovea_mutator::acovea_mutator(const acovea_mutator & a_source)
  : m_mutation_rate(a_source.m_mutation_rate),
    m_target(a_source.m_target)
{
    // nada
}

// destructor
acovea_mutator::~acovea_mutator()
{
    // nada
}

// assignment -- note, this can not change the target!
acovea_mutator & acovea_mutator::operator = (const acovea_mutator & a_source)
{
    m_mutation_rate = a_source.m_mutation_rate;
    return *this;
}

// mutation
void acovea_mutator::mutate(vector< acovea_organism > & a_population)
{
    for (vector< acovea_organism >::iterator org = a_population.begin(); org != a_population.end(); ++org)
        m_target.mutate(org->genes(),m_mutation_rate);
}

//----------------------------------------------------------
// reproduction operator
// creation constructor
acovea_reproducer::acovea_reproducer(double a_crossover_rate, const compiler & a_target)
  : m_crossover_rate(a_crossover_rate),
    m_target(a_target)
{
    // adjust crossover rate if necessary
    if (m_crossover_rate > 1.0)
        m_crossover_rate = 1.0;
    else if (m_crossover_rate < 0.0)
        m_crossover_rate = 0.0;
}

// copy constructor
acovea_reproducer::acovea_reproducer(const acovea_reproducer & a_source)
  : m_crossover_rate(a_source.m_crossover_rate),
    m_target(a_source.m_target)
{
    // nada
}

// destructor
acovea_reproducer::~acovea_reproducer()
{
    // nada
}

// assignment; can't change target (which is a ref)
acovea_reproducer & acovea_reproducer::operator = (const acovea_reproducer & a_source)
{
    m_crossover_rate = a_source.m_crossover_rate;
    return *this;
}

// interrogator
vector<acovea_organism> acovea_reproducer::breed(const vector< acovea_organism > & a_population,
                                                 size_t a_limit)
{
    // result
    vector< acovea_organism > children;

    if (a_limit > 0U)
    {
        // construct a fitness wheel
        vector<double> wheel_weights;

        for (vector< acovea_organism >::const_iterator org = a_population.begin(); org != a_population.end(); ++org)
            wheel_weights.push_back(org->fitness());

        roulette_wheel fitness_wheel(wheel_weights);

        // create children
        while (a_limit > 0)
        {
            // clone an existing organism as a child
            size_t first_index = fitness_wheel.get_index();
            acovea_organism * child;

            // do we crossover?
            if (g_random.get_rand_real2() <= m_crossover_rate)
            {
                // select a second parent
                size_t second_index = first_index;

                while (second_index == first_index)
                    second_index = fitness_wheel.get_index();

                // reproduce
                child = new acovea_organism(m_target,
                                            m_target.breed(a_population[first_index].genes(),
                                                           a_population[second_index].genes()));
            }
            else
                // no crossover; just copy first organism chosen
                child = new acovea_organism(a_population[first_index]);

            // add child to new population
            children.push_back(*child);
            delete child;

            // one down, more to go?
            --a_limit;
        }
    }

    // outa here!
    return children;
}

//----------------------------------------------------------
// fitness landscape

acovea_landscape::acovea_landscape(string a_bench_name, const compiler & a_target)
    : m_bench_name(a_bench_name),
      m_target(a_target)
{
    // nada
}

acovea_landscape::acovea_landscape(const acovea_landscape & a_source)
    : m_bench_name(a_source.m_bench_name),
      m_target(a_source.m_target)
{
    // nada
}

acovea_landscape & acovea_landscape::operator = (const acovea_landscape & a_source)
{
    m_bench_name = a_source.m_bench_name;
    // can't duplicate m_target since it's a reference
    return *this;
}

acovea_landscape::~acovea_landscape()
{
    // nada
}
        
double acovea_landscape::test(acovea_organism & a_org, bool a_show) const
{
    // get genes
    chromosome chrom = a_org.genes();
    
    // generate a unique file name
    char temp_name[16];
    snprintf(temp_name,16,"ACOVEA%08X",g_random.get_rand());
    // cerr << "temp = " << temp_name << "\n";
    
    // get a command line
    vector<string> command = m_target.get_compile_command(m_bench_name,temp_name,chrom);
    
    // allocate array of string pointers for exec
    char ** argv = new char * [command.size() + 1];
    
    // create string representing the command
    string command_text;

    // fill list and string versions of command    
    for (int n = 0; n < command.size(); ++n)
    {
        // dupe so we know the string doesn't go away
        argv[n] = strdup(command[n].c_str());
        command_text += command[n] + " ";
    }
    
    // cout << command_text << endl;
    
    // terminate argument list
    argv[command.size()] = NULL;
    
    // create compile process and wait for it to finish
    pid_t child_pid;
    int child_result;
    child_pid = fork();

    if (child_pid == 0)
        execvp(argv[0],argv);

    wait(&child_result);

    // we're done compiling; clean up string dupes!
    for (int n = 0; n < command.size(); ++n)
        free(argv[n]);

    // make sure compile succeeded before running program
    if (child_result == 0)
    {        
        // run the program
        string exec_name("./");
        exec_name += temp_name;
        argv[0] = strdup(exec_name.c_str());
        argv[1] = "-ga";
        argv[2] = NULL;
        
        // constants for I/O descriptors
        static const int PIPE_IN  = 0;
        static const int PIPE_OUT = 1;

        // create pipe
        int fds[2];
        pipe(fds);

        // fork and exec program
        child_pid = fork();

        if (child_pid == 0)
        {
            // redirect std. output for child
            close(STDOUT_FILENO);
            dup2(fds[PIPE_OUT],STDOUT_FILENO);
            close(fds[PIPE_IN]);
            close(fds[PIPE_OUT]);
            
            execve(exec_name.c_str(),argv,NULL);
        }

        // redirect std. input for parent
        close(STDIN_FILENO);
        dup2(fds[PIPE_IN],STDIN_FILENO);
        close(fds[PIPE_IN]);
        close(fds[PIPE_OUT]);

        // wait for child to finish
        wait(&child_result);

        if (child_result == 0)
        {
            // read run time 
            double run_time = 0.0;
            char temp[32];
            fgets(temp,32,stdin);
            run_time = atof(temp);
        
            // print result
            // cerr << "rcvd: " << run_time << "\n";
            
            // very short run time indicate a problem
            if (run_time < 1.0)
            {
                // handle a compiler error
                cerr << "\nSHORT RUN TIME ERROR:\n" << command_text << endl;
                run_time = BOGUS_RUN_TIME;
            }
        
            // free memory
            free(argv[0]);

            // record fitness based on return value and penalty for number of option enabled
            a_org.fitness() = run_time;
        }
        else
        {
            // handle a compiler error
            cerr << "\nRUN FAILED:\n" << command_text << endl;
            a_org.fitness() = BOGUS_RUN_TIME;
        }
    }
    else
    {
        // handle a compiler error
        cerr << "\nCOMPILE FAILED:\n" << command_text << endl;
        a_org.fitness() = BOGUS_RUN_TIME; // very unfit chromosome!
    }
    
    // remove temporary file
    remove(temp_name);

    // done
    return a_org.fitness();
}

// fitness testing
double acovea_landscape::test(vector< acovea_organism > & a_population) const
{
    double result = 0.0;

    // test each org
    for (vector< acovea_organism >::iterator org = a_population.begin(); org != a_population.end(); ++org)
        result += test(*org,false);

    // done; return average population fitness
    return result / a_population.size();
}

//----------------------------------------------------------
// status and statistics
acovea_reporter::acovea_reporter(string a_bench_name,
                                 size_t a_number_of_populations,
                                 const compiler & a_target)
  : m_bench_name(a_bench_name),
    m_number_of_populations(a_number_of_populations),
    m_target(a_target),
    m_opt_names(),
    m_opt_counts()
{
    // we don't care about settings, just what they're named
    chromosome options = a_target.get_random_options();
    
    // allocate and initialize option names and counts
    for (int n = 0; n < options.size(); ++n)
    {
        vector<string> choices = options[n]->get_choices();
        
        for (int i = 0; i < choices.size(); ++i)
        {
            m_opt_names.push_back(choices[i]);
        
            m_opt_counts.push_back(vector<unsigned long>(m_number_of_populations + 1));
                    
            for (int p = 0; p <  m_number_of_populations + 1; ++p)
                m_opt_counts[n + i][p] = 0UL;
        }
    }
}

acovea_reporter::~acovea_reporter()
{
    // nada
}

        
// display an option list
int acovea_reporter::display_option_list(const chromosome & a_options, int a_pop_no)
{
    int count = 0;
    int n = 0;
    
    // get a command line
    vector<string> command = m_target.get_compile_command(m_bench_name,"TEMP",a_options);
    
    // create string representing the command
    string command_text;

    // fill list and string versions of command    
    for (int n = 0; n < command.size(); ++n)
        command_text += command[n] + " ";

    // display command line    
    cout << command_text << endl;

    // increment totals
    for (int i = 0; i < a_options.size(); ++i)
    {
        vector<string> choices = a_options[i]->get_choices();
        
        if (a_options[i]->is_enabled()) 
        {
            ++count;
                
            if (choices.size() == 1)
            {
                if (a_pop_no >= 0)
                {
                    ++m_opt_counts[n][a_pop_no];
                    ++m_opt_counts[n][m_number_of_populations];
                }
            }
            else
            {
                if (a_pop_no >= 0)
                {
                    ++m_opt_counts[n + a_options[i]->get_setting()][a_pop_no];
                    ++m_opt_counts[n + a_options[i]->get_setting()][m_number_of_populations];
                }
            }
        }
        
        n += choices.size();
    }
    
    return count;
}

bool acovea_reporter::report(const vector< vector< acovea_organism > > & a_populations,
                             size_t iteration,
                             double & a_fitness,
                             bool a_finished)
{
    // exit if populations is empty
    if (a_populations.size() < 1U)
        return false;

    // find best organisms for each population
    acovea_organism * best_one  = new acovea_organism[a_populations.size()];
    
    // long times are poor fitness, so we start impossibly big
    for (int p = 0; p < m_number_of_populations; ++p)
        best_one[p].fitness() = BOGUS_RUN_TIME; 
    
    double avg_count   = 0.0;
    double avg_fitness = 0.0;
    
    // check each population and find smallest fitness (= shortest run time)
    for (int p = 0; p < m_number_of_populations; ++p)
    {
        for (vector< acovea_organism >::const_iterator org = a_populations[p].begin(); org != a_populations[p].end(); ++org)
        {
            if (org->fitness() < best_one[p].fitness())
                best_one[p] = *org;

            if (org->fitness() != BOGUS_RUN_TIME)
            {
                avg_count += 1.0;
                avg_fitness += org->fitness();
            }
        }
    }
    
    // compute average fitness for all organisms
    avg_fitness /= avg_count;
    
    // summarize
    cout << "------------------------------------------------------------\n"
         << "iteration " << iteration
         << ": average fitness = " << avg_fitness
         << ", best fitnesses = ";

    // only display common options if more than one population
    if (m_number_of_populations == 1)
    {
        // display fitness
        cout << best_one[0].fitness() << "\n\nbest options for current population\n";

        if (0 == display_option_list(best_one[0].genes(),0))
            cout << "    ** NONE **\n";

        // print option count summary
        cout << "\n   Option counts:" << "\n";

        for (int i = 0; i < m_opt_names.size(); ++i)
            cout << setw(40) << right << m_opt_names[i] << " " << setw(4) << m_opt_counts[i][1] << "\n";
    }
    else
    {
        // display best fitnesses, compute "common" genes for multiple populations
        chromosome common_options = best_one[0].genes();
        chromosome reject_options = best_one[0].genes();
        
        for (int p = 0; p < m_number_of_populations; ++p)
        {
            // display fitness
            cout << best_one[p].fitness() << " ";

            // keep shared genes
            if (p != 0)
            {
                chromosome temp = best_one[p].genes();

                for (int n = 0; n < common_options.size(); ++n)
                {
                    common_options[n]->set_enabled(common_options[n]->is_enabled() & temp[n]->is_enabled());
                    reject_options[n]->set_enabled(reject_options[n]->is_enabled() | temp[n]->is_enabled());
                }
            }
        }

        // reverse the sense of options in rejects, for display routine
        for (int n = 0; n < common_options.size(); ++n)
            reject_options[n]->set_enabled(!reject_options[n]->is_enabled());
                
        cout << "\n";

        // display best organisms from each population
        for (int p = 0; p < m_number_of_populations; ++p)
        {
            cout << "\nbest options for population " << p << "\n";

            if (0 == display_option_list(best_one[p].genes(),p))
                cout << "    ** NONE **\n";
        }

        // display common options
        cout << "\ncommon options (found in all populations)\n";

        if (0 == display_option_list(common_options))
            cout << "    ** NONE **\n";

        // display common options
        cout << "\nrejected options (rejected by all populations)\n";
        
        if (0 == display_option_list(reject_options))
            cout << "    ** NONE **\n";

        // print option count summary
        cout << "\nOption counts:" << "\n";

        for (int i = 0; i < m_opt_names.size(); ++i)
        {
            cout << setw(40) << right << m_opt_names[i];

            for (int p = 0; p <= m_number_of_populations; ++p)
                cout << " " << setw(4) << m_opt_counts[i][p];

            cout << "\n";
        }
    }
    
    cout << "\n    value options:\n";
    
    // report any value options
    bool settings_count = 0;
        
    for (int n = 0; n < m_target.chromosome_length(); ++n)
    {
        if (best_one[0].genes()[n]->has_settings())
        {
            // get tracker from first population and accumulate into it
            settings_tracker * tracker = best_one[0].genes()[n]->alloc_settings_tracker();
            
            if (best_one[0].genes()[n]->is_enabled())
                ++settings_count;

            // accumulate from any additional populations            
            for (int p = 1; p < m_number_of_populations; ++p)
            {
                settings_tracker * temp = best_one[p].genes()[n]->alloc_settings_tracker();
                (*tracker) += (*temp);
                delete temp;
            
                if (best_one[p].genes()[n]->is_enabled())
                    ++settings_count;
            }
            
            // display
            cout << setw(32) << right << best_one[0].genes()[n]->get_choices()[0]
                 << ": " << tracker->get_settings_text() << "\n";
            
            // clean-up
            delete tracker;
        }
    }
    
    cout << "\n" << endl;
    
    // report final statistics
    if (a_finished)
    {
        // format time
        char time_text[256];
        time_t now = time(NULL);
        strftime(time_text,256,"%Y %b %d %X",localtime(&now));

        // display final 
        cout << "\nrun complete time: "  << time_text 
             << "\n\noptimistic options:" << endl;
        
        // calculate the mean
        double mean = 0.0;
        
        for (int i = 0; i < m_opt_names.size(); ++i)
            mean += static_cast<double>(m_opt_counts[i][m_number_of_populations]);

        mean /= static_cast<double>(m_opt_names.size());

        // calculate variance
        double variance = 0.0;
        
        for (int i = 0; i < m_opt_names.size(); ++i)
        {
            double diff = static_cast<double>(m_opt_counts[i][m_number_of_populations]) - mean;
            variance += (diff * diff);
        }

        variance /= static_cast<double>(m_opt_names.size());

        // calculate 2 times the std. deviation (sigma)
        double sigma = sqrt(variance);

        // calculate zscores and report
        double zscores [m_opt_names.size()];
        
        for (int i = 0; i < m_opt_names.size(); ++i)
            zscores[i] = sigdig(((static_cast<double>(m_opt_counts[i][m_number_of_populations]) - mean) / sigma),4);
        
        // report best options
        bool flag = false;
        
        for (int i = 0; i < m_opt_names.size(); ++i)
        {
            if (zscores[i] >= 1.0)
            {
                flag = true;
                cout << right << setw(30) << m_opt_names[i] << " (" << zscores[i] << ")" << endl;
            }
        }
        
        if (!flag)
            cout << "    none" << endl;
        
        cout << "\npessimistic options:" << endl;
        flag = false;
            
        for (int i = 0; i < m_opt_names.size(); ++i)
        {
            if (zscores[i] <= -1.0)
            {
                flag = true;
                cout << right << setw(30) << m_opt_names[i] << " (" << zscores[i] << ")" << endl;
            }
        }
        
        if (!flag)
            cout << "    none" << endl;
    }

    // clean up    
    delete [] best_one;
    
    return true;
}

// constructor
acovea_world::acovea_world(string a_bench_name,
                           const compiler & a_target,
                           size_t a_number_of_populations,
                           size_t a_population_size,
                           double a_survival_rate,
                           double a_migration_rate,
                           double a_mutation_rate,
                           double a_crossover_rate,
                           scaling_mode a_scaling_mode,
                           size_t a_generations)
  : m_generations(a_generations),
    m_target(a_target),
    m_bench_name(a_bench_name),
    m_mutator(a_mutation_rate, a_target),
    m_reproducer(a_crossover_rate, a_target),
    m_migrator(size_t(a_population_size * a_migration_rate + 0.5)),
    m_null_scaler(),
    m_ln_scaler(),
    m_window_scaler(),
    m_expon_scaler(1.0,1.0,2.0),
    m_quad_scaler(1.0,2.0,1.0),
    m_selector(size_t(a_population_size * a_survival_rate + 0.5)),
    m_reporter(a_bench_name,a_number_of_populations, a_target),
    m_evocosm(NULL)
{
    // pick a fitness scaler based on argument
    scaler< acovea_organism > * chosen_scaler;
    string scaler_name;
    string scaler_code;
    
    switch (a_scaling_mode)    
    {
    case SCALING_NONE:
        chosen_scaler = &m_null_scaler;
        scaler_name = "none";
        scaler_code = "na"; // not any
        break;
    case SCALING_LINEAR:
        chosen_scaler = &m_ln_scaler;
        scaler_name = "linear";
        scaler_code  = "l";
        break;
    case SCALING_EXPONENTIAL:
        chosen_scaler = &m_expon_scaler;
        scaler_name = "exponential";
        scaler_code  = "e";
        break;
    case SCALING_WINDOWED:
        chosen_scaler = &m_window_scaler;
        scaler_name = "windowed";
        scaler_code  = "w";
        break;
    case SCALING_QUADRATIC:
        chosen_scaler = &m_quad_scaler;
        scaler_name = "quadratic";
        scaler_code  = "q";
        break;
    }

    char time_text[100];
    time_t now = time(NULL);
    strftime(time_text,100,"%Y %b %d %X\n",localtime(&now));
    
    char hostname[256];
    gethostname(hostname,256);
    
    cout << "\nACOVEA - Analysis of Compiler Options Via Evolutionary Algorithm"
         << "\n         Invented by Scott Robert Ladd:  Coyote Gulch Productions"
         << "\n                                         scott.ladd@coyotegulch.com"
         << "\n                                         http://www.coyotegulch.com\n"
         << "\n  test application: " << a_bench_name
         << "\n       test system: " << hostname
         << "\nconfig description: " << m_target.get_description()
         << "\ntest configuration: " << m_target.get_config_name()
         << "\n    acovea version: " << G_VERSION
         << "\n   evocosm version: " << libevocosm::globals::VERSION
         << "\n   test start time: " << time_text
         << "\n  # of populations: " << a_number_of_populations
         << "\n   population size: " << a_population_size
         << "\n     survival rate: " << (a_survival_rate  * 100) << "% (" << size_t(a_population_size * a_survival_rate + 0.5) << ")"
         << "\n    migration rate: " << (a_migration_rate * 100) << "% (" << size_t(a_population_size * a_migration_rate + 0.5) << ")"
         << "\n     mutation rate: " << (a_mutation_rate  * 100) << "%"
         << "\n    crossover rate: " << (a_crossover_rate * 100) << "%"
         << "\n   fitness scaling: " << scaler_name
         << "\ngenerations to run: " << a_generations
         << "\nrandom number seed: " << libevocosm::globals::get_seed()
         << "\n" << endl;

    // create evocosm with requested arguments
    m_evocosm = new evocosm<acovea_organism, acovea_landscape> (a_population_size,
                                                                a_number_of_populations,
                                                                0,
                                                                1,
                                                                m_mutator,
                                                                m_reproducer,
                                                                *chosen_scaler,
                                                                m_migrator,
                                                                m_selector,
                                                                m_reporter,
                                                                *this,
                                                                *this,
                                                                true);
}

acovea_organism acovea_world::create()
{
    return acovea_organism(m_target);
}

void acovea_world::append(vector<acovea_organism> & a_population, size_t a_size)
{
    // fill remaining population with random values    
    for (size_t i = 0; i < a_size; ++i)
        a_population.push_back(acovea_organism(m_target));
}

acovea_landscape acovea_world::generate()
{
    return acovea_landscape(m_bench_name,m_target);
}

double acovea_world::run()
{
    double fitness = 0.0;

    // continue for specified number of iterations
    for (size_t count = 1; count <= m_generations; ++count)
    {
        // run a generation
        bool keep_going =  m_evocosm->run_generation(count == m_generations,fitness);

        if (!keep_going)
        {
            cerr << "generation failed; run aborted\n";
            break;
        }
    }
    
    return fitness;
}

acovea_world::~acovea_world()
{
    delete m_evocosm;
}


Generated by  Doxygen 1.6.0   Back to index