diff options
author | Kenneth Heafield <github@kheafield.com> | 2012-10-17 19:49:41 +0400 |
---|---|---|
committer | Kenneth Heafield <github@kheafield.com> | 2012-10-17 19:49:41 +0400 |
commit | 3ced55e33db8aaf27cee61dd3895f840f440f491 (patch) | |
tree | aad14c3502a5f5f59287e24b7cdcfe1b8aa82250 /search | |
parent | f4116ec6f5bc2740350ed627a5cbfc99a8c2df16 (diff) |
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
Diffstat (limited to 'search')
-rw-r--r-- | search/edge.hh | 19 | ||||
-rw-r--r-- | search/edge_generator.cc | 35 | ||||
-rw-r--r-- | search/edge_generator.hh | 35 | ||||
-rw-r--r-- | search/edge_queue.hh | 70 | ||||
-rw-r--r-- | search/vertex_generator.cc | 14 | ||||
-rw-r--r-- | search/vertex_generator.hh | 4 |
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_; |