Fleet  0.0.9
Inference in the LOT
VirtualMachinePool.h
Go to the documentation of this file.
1 #pragma once
2 
3 #include "DiscreteDistribution.h"
5 
6 #include <vector>
7 #include <queue>
8 
9 
14 template<typename VirtualMachineState_t>
16 
18  for(auto& vms : v) {
19  if(vms.status == vmstatus_t::COMPLETE) { // can't add up probability for errors
20  out.addmass(vms.get_output(), vms.lp);
21  }
22  else {
23  assert(false && "*** You should not be computing marginal outcomes with VMS states that didn't complete.");
24  }
25  }
26  return out;
27 }
28 
29 
41 template<typename VirtualMachineState_t>
43 
51  struct compare_VirtualMachineState_t_prt {
52  bool operator()(const VirtualMachineState_t* lhs, const VirtualMachineState_t* rhs) { return lhs->lp < rhs->lp; }
53  };
54 
55 public:
56 
57  typedef typename VirtualMachineState_t::output_t output_t;
58  typedef typename VirtualMachineState_t::input_t input_t;
59 
60  // how many steps have I run so far? -- this needs to be global so that we can keep track of
61  // whether we should push a new state that occurs too late.
62  unsigned long total_vms_steps;
63  double worst_lp;
64  unsigned long total_instruction_count;
65 
66  std::priority_queue<VirtualMachineState_t*, std::vector<VirtualMachineState_t*>, VirtualMachinePool::compare_VirtualMachineState_t_prt> Q; // Q of states sorted by probability
67  //std::priority_queue<VirtualMachineState_t*, ReservedVector<VirtualMachineState_t*,16>, VirtualMachinePool::compare_VirtualMachineState_t_prt> Q; // Does not seem to speed things up
68 
69  VirtualMachinePool() : total_vms_steps(0), worst_lp(infinity), total_instruction_count(0) {
70  }
71 
72 
73  virtual ~VirtualMachinePool() {
74  clear();
75  }
76 
80  virtual void clear() {
81  while(not Q.empty()) {
82  VirtualMachineState_t* vms = Q.top(); Q.pop();
83  delete vms;
84  }
85  total_vms_steps = 0;
86  worst_lp = infinity;
87  }
88 
94  bool wouldIadd(double lp) {
95  // we won't add stuff that's worse than MIN_LP or that will never run
96  // (it will never run if it's lp < worst_lp and we don't have enough steps to get there)
97  return lp > MIN_LP and
98  (Q.size() + total_vms_steps <= MAX_STEPS or lp > worst_lp);
99  }
100 
105  void push(VirtualMachineState_t* o) {
106  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
107  Q.push(o);
108  worst_lp = std::min(worst_lp, o->lp); //keep track of the worst we've seen
109  }
110  // else nothing
111  }
112 
122  template<typename T>
123  bool copy_increment_push(const VirtualMachineState_t* x, T v, double lpinc) {
124  if(wouldIadd(x->lp + lpinc)) {
125  assert(x->status == vmstatus_t::GOOD);
126  auto s = new VirtualMachineState_t(*x); // copy
127  s->template push<T>(v); // add v
128  s->lp += lpinc;
129  this->push(s);
130  return true;
131  }
132  return false;
133  }
134 
142  template<typename T>
143  bool increment_push(VirtualMachineState_t* s, T v, double lpinc) {
144  if(wouldIadd(s->lp + lpinc)) {
145  assert(s->status == vmstatus_t::GOOD);
146  s->template push<T>(v); // add this
147  s->lp += lpinc;
148  this->push(s);
149  return true;
150  }
151  return false;
152  }
153 
163 
165 
166  total_vms_steps = 0;
167  while(total_vms_steps < MAX_STEPS && out.size() < MAX_OUTPUTS && !Q.empty()) {
168 
169  VirtualMachineState_t* vms = Q.top(); Q.pop();
170  assert(vms->status == vmstatus_t::GOOD);
171 
172  // 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
173  assert(vms->lp >= MIN_LP);
174 
175  total_vms_steps++;
176 
177  auto y = vms->run();
178 
179  if(vms->status == vmstatus_t::COMPLETE) { // can't add up probability for errors
180  out.addmass(y, vms->lp);
181  total_instruction_count += vms->runtime_counter.total;
182  }
183 
184  // not else if because we need to delete complete ones too
185  if(vms->status != vmstatus_t::RANDOM_CHOICE_NO_DELETE) {
186  total_instruction_count += vms->runtime_counter.total;
187  delete vms; // if our previous copy isn't pushed back on the stack, delete it
188  }
189  else {
190  // else restore to running order when we're RANDOM_CHOICE_NO_DELETE so it keeps running
191  vms->status = vmstatus_t::GOOD;
192  }
193  }
194 
195  // this leaves some in the stack, but they are cleaned up by the destructor
196  // (this way we can resume running if we want to)
197  return out;
198  }
199 
200 
208  std::vector<VirtualMachineState_t> run_vms() {
209 
210  std::vector<VirtualMachineState_t> out;
211 
212  total_vms_steps = 0;
213  while(total_vms_steps < MAX_STEPS && !Q.empty()) {
214 
215  VirtualMachineState_t* vms = Q.top(); Q.pop();
216  assert(vms->status == vmstatus_t::GOOD);
217  assert(vms->lp >= MIN_LP);
218 
219  total_vms_steps++;
220 
221  vms->run();
222 
223  if(vms->status == vmstatus_t::COMPLETE) {
224  out.push_back(*vms);
225  total_instruction_count += vms->runtime_counter.total;
226  }
227 
228  if(vms->status != vmstatus_t::RANDOM_CHOICE_NO_DELETE) {
229  total_instruction_count += vms->runtime_counter.total;
230  delete vms; // if our previous copy isn't pushed back on the stack, delete it
231  }
232  else {
233  // else restore to running order
234  vms->status = vmstatus_t::GOOD;
235  }
236  }
237 
238  return out;
239  }
240 
241 };
static unsigned long MAX_STEPS
Definition: VirtualMachineControl.h:30
Definition: VirtualMachineControl.h:13
void push(VirtualMachineState_t *o)
Add the VirtualMachineState_t o to this pool (but again checking if I&#39;d add)
Definition: VirtualMachinePool.h:105
VirtualMachinePool()
Definition: VirtualMachinePool.h:69
DiscreteDistribution< output_t > run()
This runs and adds up the probability mass for everything, returning a dictionary outcomes->log_proba...
Definition: VirtualMachinePool.h:162
std::priority_queue< VirtualMachineState_t *, std::vector< VirtualMachineState_t * >, VirtualMachinePool::compare_VirtualMachineState_t_prt > Q
Definition: VirtualMachinePool.h:66
virtual void clear()
Remove everything and reset my values.
Definition: VirtualMachinePool.h:80
Definition: DiscreteDistribution.h:25
static double MIN_LP
Definition: VirtualMachineControl.h:36
static unsigned long MAX_OUTPUTS
Definition: VirtualMachineControl.h:33
bool copy_increment_push(const VirtualMachineState_t *x, T v, double lpinc)
This is an important opimization where we will make a copy of x, push v into it&#39;s stack...
Definition: VirtualMachinePool.h:123
constexpr double infinity
Definition: Numerics.h:18
void addmass(T x, double v)
Definition: DiscreteDistribution.h:91
unsigned long total_vms_steps
Definition: VirtualMachinePool.h:62
bool increment_push(VirtualMachineState_t *s, T v, double lpinc)
Same as copy_increment_push, but does not make a copy – just add.
Definition: VirtualMachinePool.h:143
std::vector< VirtualMachineState_t > run_vms()
Run but return a vector of completed virtual machines instead of marginalizing outputs. You might want this if you needed to separate execution paths, or wanted to access runtime counts. This also can get joint distributions on outputs by running a VirtualMachineState multiple times.
Definition: VirtualMachinePool.h:208
VirtualMachineState_t::output_t output_t
Definition: VirtualMachinePool.h:57
This stores a distribution from values of T to log probabilities. It is used as the return value from...
bool wouldIadd(double lp)
Returns true if I would add something with this lp, given my MAX_STEPS and the stack. This lets us speed up by checking if we would add before copying/constructing a VMS.
Definition: VirtualMachinePool.h:94
unsigned long total_instruction_count
Definition: VirtualMachinePool.h:64
size_t size() const
Definition: DiscreteDistribution.h:202
double worst_lp
Definition: VirtualMachinePool.h:63
virtual ~VirtualMachinePool()
Definition: VirtualMachinePool.h:73
DiscreteDistribution< typename VirtualMachineState_t::output_t > marginal_vms_output(std::vector< VirtualMachineState_t > &v)
Compute the marginal output of a collection of VirtualMachineStates (as we might get from run_vms) ...
Definition: VirtualMachinePool.h:15
VirtualMachineState_t::input_t input_t
Definition: VirtualMachinePool.h:58
Definition: VirtualMachinePool.h:42