VirtualMachinePool.h

Go to the documentation of this file.

#pragma once

#include "DiscreteDistribution.h"
#include "VirtualMachineControl.h"

#include <vector>
#include <queue>


template<typename VirtualMachineState_t>
DiscreteDistribution<typename VirtualMachineState_t::output_t>  marginal_vms_output(std::vector<VirtualMachineState_t>& v) {
    
    DiscreteDistribution<typename VirtualMachineState_t::output_t> out;
    for(auto& vms : v) {
        if(vms.status == vmstatus_t::COMPLETE) { // can't add up probability for errors
            out.addmass(vms.get_output(), vms.lp);
        }
        else {
            assert(false && "*** You should not be computing marginal outcomes with VMS states that didn't complete.");
        }
    }
    return out;
}


template<typename VirtualMachineState_t>
class VirtualMachinePool : public VirtualMachineControl {

    struct compare_VirtualMachineState_t_prt {
        bool operator()(const VirtualMachineState_t* lhs, const VirtualMachineState_t* rhs) { return lhs->lp < rhs->lp; }
    };
    
public: 

    typedef typename VirtualMachineState_t::output_t output_t;
    typedef typename VirtualMachineState_t::input_t  input_t;
    
    // how many steps have I run so far? -- this needs to be global so that we can keep track of 
    // whether we should push a new state that occurs too late. 
    unsigned long total_vms_steps; 
    double worst_lp;
    unsigned long total_instruction_count;
    
    std::priority_queue<VirtualMachineState_t*, std::vector<VirtualMachineState_t*>, VirtualMachinePool::compare_VirtualMachineState_t_prt> Q; // Q of states sorted by probability
    //std::priority_queue<VirtualMachineState_t*, ReservedVector<VirtualMachineState_t*,16>, VirtualMachinePool::compare_VirtualMachineState_t_prt> Q; // Does not seem to speed things up 

    VirtualMachinePool() : total_vms_steps(0), worst_lp(infinity), total_instruction_count(0) { 
    }
    

    virtual ~VirtualMachinePool() {
        clear();
    }
    
    virtual void clear() {
        while(not Q.empty()) {
            VirtualMachineState_t* vms = Q.top(); Q.pop();
            delete vms; 
        }
        
        total_vms_steps = 0;
        worst_lp = infinity;
    }
    
    bool wouldIadd(double lp) {
        // we won't add stuff that's worse than MIN_LP or that will never run
        // (it will never run if it's lp < worst_lp and we don't have enough steps to get there)
        return lp > MIN_LP and 
               (Q.size() + total_vms_steps <= MAX_STEPS or lp > worst_lp);
    }
    
    void push(VirtualMachineState_t* o) { 
        if(wouldIadd(o->lp)){ // TODO: might be able to add an optimization here that doesn't push if we don't have enough steps left to get it 
            Q.push(o);          
            worst_lp = std::min(worst_lp, o->lp); //keep track of the worst we've seen
        } 
        // else nothing 
    }
    
    template<typename T>
    bool copy_increment_push(const VirtualMachineState_t* x, T v, double lpinc) {
        if(wouldIadd(x->lp + lpinc)) {  
            assert(x->status == vmstatus_t::GOOD);
            auto s = new VirtualMachineState_t(*x); // copy
            s->template push<T>(v); // add v
            s->lp += lpinc;
            this->push(s);  
            return true;
        }   
        return false;
    }
    
    template<typename T>
    bool increment_push(VirtualMachineState_t* s, T v, double lpinc) {      
        if(wouldIadd(s->lp + lpinc)) {      
            assert(s->status == vmstatus_t::GOOD);
            s->template push<T>(v); // add this
            s->lp += lpinc;
            this->push(s);  
            return true;
        }   
        return false;
    }

    DiscreteDistribution<output_t> run() { 

        DiscreteDistribution<output_t> out;
        
        total_vms_steps = 0;
        while(total_vms_steps < MAX_STEPS && out.size() < MAX_OUTPUTS && !Q.empty()) {
            
            VirtualMachineState_t* vms = Q.top(); Q.pop();
            assert(vms->status == vmstatus_t::GOOD);
            
            // if we ever go back to the non-pointer version, we might need fanciness to move out of top https://stackoverflow.com/questions/20149471/move-out-element-of-std-priority-queue-in-c11
            assert(vms->lp >= MIN_LP);
            
            total_vms_steps++;
            
            auto y = vms->run();
            //print("!", (int)vms->status, vms->recursion_depth, total_vms_steps);
            
            if(vms->status == vmstatus_t::COMPLETE) { // can't add up probability for errors
                out.addmass(y, vms->lp);
                total_instruction_count += vms->runtime_counter.total;
            }
            
            // not else if because we need to delete complete ones too
            if(vms->status != vmstatus_t::RANDOM_CHOICE_NO_DELETE) {
                total_instruction_count += vms->runtime_counter.total; 
                delete vms; // if our previous copy isn't pushed back on the stack, delete it
            } 
            else {
                // else restore to running order when we're RANDOM_CHOICE_NO_DELETE so it keeps running
                vms->status = vmstatus_t::GOOD;
            }
        }

        // this leaves some in the stack, but they are cleaned up by the destructor
        // (this way we can resume running if we want to)
        return out;     
    }
    
    
    std::vector<VirtualMachineState_t> run_vms() { 
        
        std::vector<VirtualMachineState_t> out;
        
        total_vms_steps = 0;
        while(total_vms_steps < MAX_STEPS && !Q.empty()) {
            
            VirtualMachineState_t* vms = Q.top(); Q.pop();
            assert(vms->status == vmstatus_t::GOOD);
            assert(vms->lp >= MIN_LP);
            
            total_vms_steps++;
            
            vms->run();
                
            if(vms->status == vmstatus_t::COMPLETE) {
                out.push_back(*vms);
                total_instruction_count += vms->runtime_counter.total; 
            }
            
            if(vms->status != vmstatus_t::RANDOM_CHOICE_NO_DELETE) { 
                total_instruction_count += vms->runtime_counter.total; 
                delete vms; // if our previous copy isn't pushed back on the stack, delete it
            }
            else {
                // else restore to running order
                vms->status = vmstatus_t::GOOD;
            }
        }

        return out;     
    }
    
};