Put note into PartialEdge, delete edge_queue

Before with pop 25:
real    9m49.480s
user    9m38.389s
sys     0m10.354s

After with pop 25:
real    8m46.553s
user    8m35.138s
sys     0m10.654s

6 files changed, 60 insertions, 117 deletions

diff --git a/search/edge.hh b/search/edge.hh
index 3b096c1ae..d92578761 100644
--- a/search/edge.hh
+++ b/search/edge.hh
@@ -33,25 +33,34 @@ class PartialEdge {
       return *reinterpret_cast<const Arity*>(base_ + sizeof(Score));
     }
 
+    Note GetNote() const {
+      return *reinterpret_cast<const Note*>(base_ + sizeof(Score) + sizeof(Arity));
+    }
+    void SetNote(Note to) {
+      *reinterpret_cast<Note*>(base_ + sizeof(Score) + sizeof(Arity)) = to;
+    }
+
     // Non-terminals
     const PartialVertex *NT() const {
-      return reinterpret_cast<const PartialVertex*>(base_ + sizeof(Score) + sizeof(Arity));
+      return reinterpret_cast<const PartialVertex*>(base_ + kHeaderSize);
     }
     PartialVertex *NT() {
-      return reinterpret_cast<PartialVertex*>(base_ + sizeof(Score) + sizeof(Arity));
+      return reinterpret_cast<PartialVertex*>(base_ + kHeaderSize);
     }
 
     const lm::ngram::ChartState &CompletedState() const {
       return *Between();
     }
     const lm::ngram::ChartState *Between() const {
-      return reinterpret_cast<const lm::ngram::ChartState*>(base_ + sizeof(Score) + sizeof(Arity) + GetArity() * sizeof(PartialVertex));
+      return reinterpret_cast<const lm::ngram::ChartState*>(base_ + kHeaderSize + GetArity() * sizeof(PartialVertex));
     }
     lm::ngram::ChartState *Between() {
-      return reinterpret_cast<lm::ngram::ChartState*>(base_ + sizeof(Score) + sizeof(Arity) + GetArity() * sizeof(PartialVertex));
+      return reinterpret_cast<lm::ngram::ChartState*>(base_ + kHeaderSize + GetArity() * sizeof(PartialVertex));
     }
 
   private:
+    static const std::size_t kHeaderSize = sizeof(Score) + sizeof(Arity) + sizeof(Note);
+
     friend class PartialEdgePool;
     PartialEdge(void *base, Arity arity) : base_(static_cast<uint8_t*>(base)) {
       *reinterpret_cast<Arity*>(base_ + sizeof(Score)) = arity;
@@ -64,7 +73,7 @@ class PartialEdgePool {
   public:
     PartialEdge Allocate(Arity arity, Arity chart_states) {
       return PartialEdge(
-          pool_.Allocate(sizeof(Score) + sizeof(Arity) + arity * sizeof(PartialVertex) + chart_states * sizeof(lm::ngram::ChartState)),
+          pool_.Allocate(PartialEdge::kHeaderSize + arity * sizeof(PartialVertex) + chart_states * sizeof(lm::ngram::ChartState)),
           arity);
     }
 
diff --git a/search/edge_generator.cc b/search/edge_generator.cc
index 17caab866..baa91ed1b 100644
--- a/search/edge_generator.cc
+++ b/search/edge_generator.cc
@@ -4,16 +4,11 @@
 #include "lm/partial.hh"
 #include "search/context.hh"
 #include "search/vertex.hh"
-#include "search/vertex_generator.hh"
 
 #include <numeric>
 
 namespace search {
 
-EdgeGenerator::EdgeGenerator(PartialEdge root, Note note) : top_score_(root.GetScore()), arity_(root.GetArity()), note_(note) {
-  generate_.push(root);
-}
-
 namespace {
 
 template <class Model> void FastScore(const Context<Model> &context, Arity victim, Arity before_idx, Arity incomplete, const PartialVertex &previous_vertex, PartialEdge update) {
@@ -48,11 +43,12 @@ template <class Model> void FastScore(const Context<Model> &context, Arity victi
 
 } // namespace
 
-template <class Model> PartialEdge EdgeGenerator::Pop(Context<Model> &context, PartialEdgePool &partial_edge_pool) {
+template <class Model> PartialEdge EdgeGenerator::Pop(Context<Model> &context) {
   assert(!generate_.empty());
   PartialEdge top = generate_.top();
   generate_.pop();
-  PartialVertex *top_nt = top.NT();
+  PartialVertex *const top_nt = top.NT();
+  const Arity arity = top.GetArity();
 
   Arity victim = 0;
   Arity victim_completed;
@@ -61,7 +57,7 @@ template <class Model> PartialEdge EdgeGenerator::Pop(Context<Model> &context, P
   {
     Arity completed = 0;
     unsigned char lowest_length = 255;
-    for (Arity i = 0; i != arity_; ++i) {
+    for (Arity i = 0; i != arity; ++i) {
       if (top_nt[i].Complete()) {
         ++completed;
       } else if (top_nt[i].Length() < lowest_length) {
@@ -71,23 +67,23 @@ template <class Model> PartialEdge EdgeGenerator::Pop(Context<Model> &context, P
       }
     }
     if (lowest_length == 255) {
-      // Now top.between[0] is the full edge state.  
-      top_score_ = generate_.empty() ? -kScoreInf : generate_.top().GetScore();
       return top;
     }
-    incomplete = arity_ - completed;
+    incomplete = arity - completed;
   }
 
   PartialVertex old_value(top_nt[victim]);
   PartialVertex alternate_changed;
   if (top_nt[victim].Split(alternate_changed)) {
-    PartialEdge alternate = partial_edge_pool.Allocate(arity_, incomplete + 1);
+    PartialEdge alternate = partial_edge_pool_.Allocate(arity, incomplete + 1);
     alternate.SetScore(top.GetScore() + alternate_changed.Bound() - old_value.Bound());
 
+    alternate.SetNote(top.GetNote());
+
     PartialVertex *alternate_nt = alternate.NT();
     for (Arity i = 0; i < victim; ++i) alternate_nt[i] = top_nt[i];
     alternate_nt[victim] = alternate_changed;
-    for (Arity i = victim + 1; i < arity_; ++i) alternate_nt[i] = top_nt[i];
+    for (Arity i = victim + 1; i < arity; ++i) alternate_nt[i] = top_nt[i];
 
     memcpy(alternate.Between(), top.Between(), sizeof(lm::ngram::ChartState) * (incomplete + 1));
 
@@ -100,16 +96,15 @@ template <class Model> PartialEdge EdgeGenerator::Pop(Context<Model> &context, P
   // TODO: dedupe?  
   generate_.push(top);
 
-  top_score_ = generate_.top().GetScore();
   // Invalid indicates no new hypothesis generated.  
   return PartialEdge();
 }
 
-template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::RestProbingModel> &context, PartialEdgePool &partial_edge_pool);
-template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::ProbingModel> &context, PartialEdgePool &partial_edge_pool);
-template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::TrieModel> &context, PartialEdgePool &partial_edge_pool);
-template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::QuantTrieModel> &context, PartialEdgePool &partial_edge_pool);
-template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::ArrayTrieModel> &context, PartialEdgePool &partial_edge_pool);
-template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::QuantArrayTrieModel> &context, PartialEdgePool &partial_edge_pool);
+template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::RestProbingModel> &context);
+template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::ProbingModel> &context);
+template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::TrieModel> &context);
+template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::QuantTrieModel> &context);
+template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::ArrayTrieModel> &context);
+template PartialEdge EdgeGenerator::Pop(Context<lm::ngram::QuantArrayTrieModel> &context);
 
 } // namespace search
diff --git a/search/edge_generator.hh b/search/edge_generator.hh
index 734993cab..43f257929 100644
--- a/search/edge_generator.hh
+++ b/search/edge_generator.hh
@@ -16,32 +16,41 @@ class ChartState;
 namespace search {
 
 template <class Model> class Context;
-class PartialEdgePool;
 
 class EdgeGenerator {
   public:
-    EdgeGenerator(PartialEdge root, Note note);
+    EdgeGenerator() {}
 
-    Score TopScore() const {
-      return top_score_;
+    PartialEdge AllocateEdge(Arity arity) {
+      return partial_edge_pool_.Allocate(arity);
     }
 
-    Note GetNote() const {
-      return note_;
+    void AddEdge(PartialEdge edge) {
+      generate_.push(edge);
     }
 
-    // Pop.  If there's a complete hypothesis, return it.  Otherwise return NULL.  
-    template <class Model> PartialEdge Pop(Context<Model> &context, PartialEdgePool &partial_edge_pool);
+    bool Empty() const { return generate_.empty(); }
+
+    // Pop.  If there's a complete hypothesis, return it.  Otherwise return an invalid PartialEdge.
+    template <class Model> PartialEdge Pop(Context<Model> &context);
+
+    template <class Model, class Output> void Search(Context<Model> &context, Output &output) {
+      unsigned to_pop = context.PopLimit();
+      while (to_pop > 0 && !generate_.empty()) {
+        PartialEdge got(Pop(context));
+        if (got.Valid()) {
+          output.NewHypothesis(got);
+          --to_pop;
+        }
+      }
+      output.FinishedSearch();
+    }
 
   private:
-    Score top_score_;
+    PartialEdgePool partial_edge_pool_;
 
     typedef std::priority_queue<PartialEdge> Generate;
     Generate generate_;
-
-    Arity arity_;
-
-    Note note_;
 };
 
 } // namespace search
diff --git a/search/edge_queue.hh b/search/edge_queue.hh
deleted file mode 100644
index fae70562f..000000000
--- a/search/edge_queue.hh
+++ /dev/null
@@ -1,70 +0,0 @@
-#ifndef SEARCH_EDGE_QUEUE__
-#define SEARCH_EDGE_QUEUE__
-
-#include "search/edge.hh"
-#include "search/edge_generator.hh"
-#include "search/note.hh"
-
-#include <boost/pool/pool.hpp>
-#include <boost/pool/object_pool.hpp>
-
-#include <queue>
-
-namespace search {
-
-template <class Model> class Context;
-
-class EdgeQueue {
-  public:
-    EdgeQueue() {}
-
-    PartialEdge AllocateEdge(Arity arity) {
-      return partial_edge_pool_.Allocate(arity);
-    }
-
-    void AddEdge(PartialEdge edge, Note note) {
-      generate_.push(edge_pool_.construct(edge, note));
-    }
-
-    bool Empty() const { return generate_.empty(); }
-
-    /* Generate hypotheses and send them to output.  Normally, output is a
-     * VertexGenerator, but the decoder may want to route edges to different
-     * vertices i.e. if they have different LHS non-terminal labels.  
-     */
-    template <class Model, class Output> void Search(Context<Model> &context, Output &output) {
-      int to_pop = context.PopLimit();
-      while (to_pop > 0 && !generate_.empty()) {
-        EdgeGenerator *top = generate_.top();
-        generate_.pop();
-        PartialEdge ret(top->Pop(context, partial_edge_pool_));
-        if (ret.Valid()) {
-          output.NewHypothesis(ret, top->GetNote());
-          --to_pop;
-          if (top->TopScore() != -kScoreInf) {
-            generate_.push(top);
-          }
-        } else {
-          generate_.push(top);
-        }
-      }
-      output.FinishedSearch();
-    }
-
-  private:
-    boost::object_pool<EdgeGenerator> edge_pool_;
-
-    struct LessByTopScore : public std::binary_function<const EdgeGenerator *, const EdgeGenerator *, bool> {
-      bool operator()(const EdgeGenerator *first, const EdgeGenerator *second) const {
-        return first->TopScore() < second->TopScore();
-      }
-    };
-
-    typedef std::priority_queue<EdgeGenerator*, std::vector<EdgeGenerator*>, LessByTopScore> Generate;
-    Generate generate_;
-
-    PartialEdgePool partial_edge_pool_;
-};
-
-} // namespace search
-#endif // SEARCH_EDGE_QUEUE__
diff --git a/search/vertex_generator.cc b/search/vertex_generator.cc
index 392cf8e5e..53220bc55 100644
--- a/search/vertex_generator.cc
+++ b/search/vertex_generator.cc
@@ -17,8 +17,8 @@ namespace {
 
 const uint64_t kCompleteAdd = static_cast<uint64_t>(-1);
 
-void FillFinal(PartialEdge partial, Note note, Final &out) {
-  const Final **final_out = out.Reset(partial.GetScore(), note);
+void FillFinal(PartialEdge partial, Final &out) {
+  const Final **final_out = out.Reset(partial.GetScore(), partial.GetNote());
   const PartialVertex *part = partial.NT();
   const PartialVertex *const part_end_loop = part + partial.GetArity();
   for (; part != part_end_loop; ++part, ++final_out) {
@@ -28,14 +28,14 @@ void FillFinal(PartialEdge partial, Note note, Final &out) {
 
 } // namespace
 
-void VertexGenerator::NewHypothesis(PartialEdge partial, Note note) {
+void VertexGenerator::NewHypothesis(PartialEdge partial) {
   const lm::ngram::ChartState &state = partial.CompletedState();
   std::pair<Existing::iterator, bool> got(existing_.insert(std::pair<uint64_t, Final*>(hash_value(state), NULL)));
   if (!got.second) {
     // Found it already.  
     Final &exists = *got.first->second;
     if (exists.Bound() < partial.GetScore())
-      FillFinal(partial, note, exists);
+      FillFinal(partial, exists);
     return;
   }
   unsigned char left = 0, right = 0;
@@ -62,7 +62,7 @@ void VertexGenerator::NewHypothesis(PartialEdge partial, Note note) {
   }
 
   node = &FindOrInsert(*node, kCompleteAdd - state.left.full, state, state.left.length, true, state.right.length, true);
-  got.first->second = CompleteTransition(*node, state, note, partial);
+  got.first->second = CompleteTransition(*node, state, partial);
 }
 
 VertexGenerator::Trie &VertexGenerator::FindOrInsert(VertexGenerator::Trie &node, uint64_t added, const lm::ngram::ChartState &state, unsigned char left, bool left_full, unsigned char right, bool right_full) {
@@ -80,12 +80,12 @@ VertexGenerator::Trie &VertexGenerator::FindOrInsert(VertexGenerator::Trie &node
   return next;
 }
 
-Final *VertexGenerator::CompleteTransition(VertexGenerator::Trie &starter, const lm::ngram::ChartState &state, Note note, PartialEdge partial) {
+Final *VertexGenerator::CompleteTransition(VertexGenerator::Trie &starter, const lm::ngram::ChartState &state, PartialEdge partial) {
   VertexNode &node = *starter.under;
   assert(node.State().left.full == state.left.full);
   assert(!node.End());
   Final *final = context_.NewFinal();
-  FillFinal(partial, note, *final);
+  FillFinal(partial, *final);
   node.SetEnd(final);
   return final;
 }
diff --git a/search/vertex_generator.hh b/search/vertex_generator.hh
index bb04573f8..96df3e0a8 100644
--- a/search/vertex_generator.hh
+++ b/search/vertex_generator.hh
@@ -24,7 +24,7 @@ class VertexGenerator {
   public:
     VertexGenerator(ContextBase &context, Vertex &gen);
 
-    void NewHypothesis(PartialEdge partial, Note note);
+    void NewHypothesis(PartialEdge partial);
 
     void FinishedSearch() {
       root_.under->SortAndSet(context_, NULL);
@@ -43,7 +43,7 @@ class VertexGenerator {
 
     Trie &FindOrInsert(Trie &node, uint64_t added, const lm::ngram::ChartState &state, unsigned char left, bool left_full, unsigned char right, bool right_full);
 
-    Final *CompleteTransition(Trie &node, const lm::ngram::ChartState &state, Note note, PartialEdge partial);
+    Final *CompleteTransition(Trie &node, const lm::ngram::ChartState &state, PartialEdge partial);
 
     ContextBase &context_;