From 535d4016ec5179cb673b697c2e81500a2097924c Mon Sep 17 00:00:00 2001 From: Kenneth Heafield Date: Tue, 18 Jun 2013 11:34:20 -0700 Subject: lazy dd880b4 including kenlm 6eef0f1 --- klm/lm/builder/lmplz_main.cc | 15 +-- klm/lm/builder/ngram.hh | 2 +- klm/lm/model.cc | 21 ++++ klm/lm/model.hh | 5 + klm/lm/search_hashed.cc | 29 +++--- klm/lm/search_hashed.hh | 19 ++-- klm/lm/state.hh | 2 +- klm/lm/virtual_interface.hh | 3 + klm/lm/vocab.hh | 2 +- klm/search/Makefile.am | 17 +--- klm/search/context.hh | 12 --- klm/search/edge_generator.cc | 12 ++- klm/search/vertex.cc | 204 ++++++++++++++++++++++++++++++++----- klm/search/vertex.hh | 121 ++++++++++++++-------- klm/search/vertex_generator.hh | 36 ++----- klm/util/double-conversion/utils.h | 6 +- klm/util/file.cc | 14 +-- klm/util/pool.cc | 4 +- klm/util/probing_hash_table.hh | 23 ++++- klm/util/proxy_iterator.hh | 25 +++-- klm/util/sized_iterator.hh | 21 +++- klm/util/stream/chain.hh | 2 +- klm/util/usage.cc | 15 +++ 23 files changed, 418 insertions(+), 192 deletions(-) (limited to 'klm') diff --git a/klm/lm/builder/lmplz_main.cc b/klm/lm/builder/lmplz_main.cc index 1e086dcc..c87abdb8 100644 --- a/klm/lm/builder/lmplz_main.cc +++ b/klm/lm/builder/lmplz_main.cc @@ -52,13 +52,14 @@ int main(int argc, char *argv[]) { std::cerr << "Builds unpruned language models with modified Kneser-Ney smoothing.\n\n" "Please cite:\n" - "@inproceedings{kenlm,\n" - "author = {Kenneth Heafield},\n" - "title = {{KenLM}: Faster and Smaller Language Model Queries},\n" - "booktitle = {Proceedings of the Sixth Workshop on Statistical Machine Translation},\n" - "month = {July}, year={2011},\n" - "address = {Edinburgh, UK},\n" - "publisher = {Association for Computational Linguistics},\n" + "@inproceedings{Heafield-estimate,\n" + " author = {Kenneth Heafield and Ivan Pouzyrevsky and Jonathan H. Clark and Philipp Koehn},\n" + " title = {Scalable Modified {Kneser-Ney} Language Model Estimation},\n" + " year = {2013},\n" + " month = {8},\n" + " booktitle = {Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics},\n" + " address = {Sofia, Bulgaria},\n" + " url = {http://kheafield.com/professional/edinburgh/estimate\\_paper.pdf},\n" "}\n\n" "Provide the corpus on stdin. The ARPA file will be written to stdout. Order of\n" "the model (-o) is the only mandatory option. As this is an on-disk program,\n" diff --git a/klm/lm/builder/ngram.hh b/klm/lm/builder/ngram.hh index 2984ed0b..f5681516 100644 --- a/klm/lm/builder/ngram.hh +++ b/klm/lm/builder/ngram.hh @@ -53,7 +53,7 @@ class NGram { Payload &Value() { return *reinterpret_cast(end_); } uint64_t &Count() { return Value().count; } - const uint64_t Count() const { return Value().count; } + uint64_t Count() const { return Value().count; } std::size_t Order() const { return end_ - begin_; } diff --git a/klm/lm/model.cc b/klm/lm/model.cc index a40fd2fb..a26654a6 100644 --- a/klm/lm/model.cc +++ b/klm/lm/model.cc @@ -304,5 +304,26 @@ template class GenericModel, SortedVocabulary>; } // namespace detail + +base::Model *LoadVirtual(const char *file_name, const Config &config, ModelType model_type) { + RecognizeBinary(file_name, model_type); + switch (model_type) { + case PROBING: + return new ProbingModel(file_name, config); + case REST_PROBING: + return new RestProbingModel(file_name, config); + case TRIE: + return new TrieModel(file_name, config); + case QUANT_TRIE: + return new QuantTrieModel(file_name, config); + case ARRAY_TRIE: + return new ArrayTrieModel(file_name, config); + case QUANT_ARRAY_TRIE: + return new QuantArrayTrieModel(file_name, config); + default: + UTIL_THROW(FormatLoadException, "Confused by model type " << model_type); + } +} + } // namespace ngram } // namespace lm diff --git a/klm/lm/model.hh b/klm/lm/model.hh index 13ff864e..60f55110 100644 --- a/klm/lm/model.hh +++ b/klm/lm/model.hh @@ -153,6 +153,11 @@ LM_NAME_MODEL(QuantArrayTrieModel, detail::GenericModel class ActivateUnigram { Weights *modify_; }; -// Find the lower order entry, inserting blanks along the way as necessary. +// Find the lower order entry, inserting blanks along the way as necessary. template void FindLower( const std::vector &keys, typename Value::Weights &unigram, @@ -64,7 +64,7 @@ template void FindLower( typename Value::ProbingEntry entry; // Backoff will always be 0.0. We'll get the probability and rest in another pass. entry.value.backoff = kNoExtensionBackoff; - // Go back and find the longest right-aligned entry, informing it that it extends left. Normally this will match immediately, but sometimes SRI is dumb. + // Go back and find the longest right-aligned entry, informing it that it extends left. Normally this will match immediately, but sometimes SRI is dumb. for (int lower = keys.size() - 2; ; --lower) { if (lower == -1) { between.push_back(&unigram); @@ -77,11 +77,11 @@ template void FindLower( } } -// Between usually has single entry, the value to adjust. But sometimes SRI stupidly pruned entries so it has unitialized blank values to be set here. +// Between usually has single entry, the value to adjust. But sometimes SRI stupidly pruned entries so it has unitialized blank values to be set here. template void AdjustLower( const Added &added, const Build &build, - std::vector &between, + std::vector &between, const unsigned int n, const std::vector &vocab_ids, typename Build::Value::Weights *unigrams, @@ -93,14 +93,14 @@ template void AdjustLower( } typedef util::ProbingHashTable Middle; float prob = -fabs(between.back()->prob); - // Order of the n-gram on which probabilities are based. + // Order of the n-gram on which probabilities are based. unsigned char basis = n - between.size(); assert(basis != 0); typename Build::Value::Weights **change = &between.back(); // Skip the basis. --change; if (basis == 1) { - // Hallucinate a bigram based on a unigram's backoff and a unigram probability. + // Hallucinate a bigram based on a unigram's backoff and a unigram probability. float &backoff = unigrams[vocab_ids[1]].backoff; SetExtension(backoff); prob += backoff; @@ -128,14 +128,14 @@ template void AdjustLower( typename std::vector::const_iterator i(between.begin()); build.MarkExtends(**i, added); const typename Value::Weights *longer = *i; - // Everything has probability but is not marked as extending. + // Everything has probability but is not marked as extending. for (++i; i != between.end(); ++i) { build.MarkExtends(**i, *longer); longer = *i; } } -// Continue marking lower entries even they know that they extend left. This is used for upper/lower bounds. +// Continue marking lower entries even they know that they extend left. This is used for upper/lower bounds. template void MarkLower( const std::vector &keys, const Build &build, @@ -144,15 +144,15 @@ template void MarkLower( int start_order, const typename Build::Value::Weights &longer) { if (start_order == 0) return; - typename util::ProbingHashTable::MutableIterator iter; - // Hopefully the compiler will realize that if MarkExtends always returns false, it can simplify this code. + // Hopefully the compiler will realize that if MarkExtends always returns false, it can simplify this code. for (int even_lower = start_order - 2 /* index in middle */; ; --even_lower) { if (even_lower == -1) { build.MarkExtends(unigram, longer); return; } - middle[even_lower].UnsafeMutableFind(keys[even_lower], iter); - if (!build.MarkExtends(iter->value, longer)) return; + if (!build.MarkExtends( + middle[even_lower].UnsafeMutableMustFind(keys[even_lower])->value, + longer)) return; } } @@ -168,7 +168,6 @@ template void ReadNGrams( Store &store, PositiveProbWarn &warn) { typedef typename Build::Value Value; - typedef util::ProbingHashTable Middle; assert(n >= 2); ReadNGramHeader(f, n); @@ -186,7 +185,7 @@ template void ReadNGrams( for (unsigned int h = 1; h < n - 1; ++h) { keys[h] = detail::CombineWordHash(keys[h-1], vocab_ids[h+1]); } - // Initially the sign bit is on, indicating it does not extend left. Most already have this but there might +0.0. + // Initially the sign bit is on, indicating it does not extend left. Most already have this but there might +0.0. util::SetSign(entry.value.prob); entry.key = keys[n-2]; @@ -203,7 +202,7 @@ template void ReadNGrams( } // namespace namespace detail { - + template uint8_t *HashedSearch::SetupMemory(uint8_t *start, const std::vector &counts, const Config &config) { std::size_t allocated = Unigram::Size(counts[0]); unigram_ = Unigram(start, counts[0], allocated); diff --git a/klm/lm/search_hashed.hh b/klm/lm/search_hashed.hh index 00595796..9d067bc2 100644 --- a/klm/lm/search_hashed.hh +++ b/klm/lm/search_hashed.hh @@ -71,7 +71,7 @@ template class HashedSearch { static const bool kDifferentRest = Value::kDifferentRest; static const unsigned int kVersion = 0; - // TODO: move probing_multiplier here with next binary file format update. + // TODO: move probing_multiplier here with next binary file format update. static void UpdateConfigFromBinary(int, const std::vector &, Config &) {} static uint64_t Size(const std::vector &counts, const Config &config) { @@ -102,14 +102,9 @@ template class HashedSearch { return ret; } -#pragma GCC diagnostic ignored "-Wuninitialized" MiddlePointer Unpack(uint64_t extend_pointer, unsigned char extend_length, Node &node) const { node = extend_pointer; - typename Middle::ConstIterator found; - bool got = middle_[extend_length - 2].Find(extend_pointer, found); - assert(got); - (void)got; - return MiddlePointer(found->value); + return MiddlePointer(middle_[extend_length - 2].MustFind(extend_pointer)->value); } MiddlePointer LookupMiddle(unsigned char order_minus_2, WordIndex word, Node &node, bool &independent_left, uint64_t &extend_pointer) const { @@ -126,14 +121,14 @@ template class HashedSearch { } LongestPointer LookupLongest(WordIndex word, const Node &node) const { - // Sign bit is always on because longest n-grams do not extend left. + // Sign bit is always on because longest n-grams do not extend left. typename Longest::ConstIterator found; if (!longest_.Find(CombineWordHash(node, word), found)) return LongestPointer(); return LongestPointer(found->value.prob); } - // Generate a node without necessarily checking that it actually exists. - // Optionally return false if it's know to not exist. + // Generate a node without necessarily checking that it actually exists. + // Optionally return false if it's know to not exist. bool FastMakeNode(const WordIndex *begin, const WordIndex *end, Node &node) const { assert(begin != end); node = static_cast(*begin); @@ -144,7 +139,7 @@ template class HashedSearch { } private: - // Interpret config's rest cost build policy and pass the right template argument to ApplyBuild. + // Interpret config's rest cost build policy and pass the right template argument to ApplyBuild. void DispatchBuild(util::FilePiece &f, const std::vector &counts, const Config &config, const ProbingVocabulary &vocab, PositiveProbWarn &warn); template void ApplyBuild(util::FilePiece &f, const std::vector &counts, const ProbingVocabulary &vocab, PositiveProbWarn &warn, const Build &build); @@ -153,7 +148,7 @@ template class HashedSearch { public: Unigram() {} - Unigram(void *start, uint64_t count, std::size_t /*allocated*/) : + Unigram(void *start, uint64_t count, std::size_t /*allocated*/) : unigram_(static_cast(start)) #ifdef DEBUG , count_(count) diff --git a/klm/lm/state.hh b/klm/lm/state.hh index d8e6c132..a6b9accb 100644 --- a/klm/lm/state.hh +++ b/klm/lm/state.hh @@ -91,7 +91,7 @@ inline uint64_t hash_value(const Left &left) { } struct ChartState { - bool operator==(const ChartState &other) { + bool operator==(const ChartState &other) const { return (right == other.right) && (left == other.left); } diff --git a/klm/lm/virtual_interface.hh b/klm/lm/virtual_interface.hh index 6a5a0196..17f064b2 100644 --- a/klm/lm/virtual_interface.hh +++ b/klm/lm/virtual_interface.hh @@ -6,6 +6,7 @@ #include "util/string_piece.hh" #include +#include namespace lm { namespace base { @@ -119,7 +120,9 @@ class Model { size_t StateSize() const { return state_size_; } const void *BeginSentenceMemory() const { return begin_sentence_memory_; } + void BeginSentenceWrite(void *to) const { memcpy(to, begin_sentence_memory_, StateSize()); } const void *NullContextMemory() const { return null_context_memory_; } + void NullContextWrite(void *to) const { memcpy(to, null_context_memory_, StateSize()); } // Requires in_state != out_state virtual float Score(const void *in_state, const WordIndex new_word, void *out_state) const = 0; diff --git a/klm/lm/vocab.hh b/klm/lm/vocab.hh index 3902f117..226ae438 100644 --- a/klm/lm/vocab.hh +++ b/klm/lm/vocab.hh @@ -25,7 +25,7 @@ uint64_t HashForVocab(const char *str, std::size_t len); inline uint64_t HashForVocab(const StringPiece &str) { return HashForVocab(str.data(), str.length()); } -class ProbingVocabularyHeader; +struct ProbingVocabularyHeader; } // namespace detail class WriteWordsWrapper : public EnumerateVocab { diff --git a/klm/search/Makefile.am b/klm/search/Makefile.am index 03554276..b8c8a050 100644 --- a/klm/search/Makefile.am +++ b/klm/search/Makefile.am @@ -1,23 +1,10 @@ noinst_LIBRARIES = libksearch.a libksearch_a_SOURCES = \ - applied.hh \ - config.hh \ - context.hh \ - dedupe.hh \ - edge.hh \ - edge_generator.hh \ - header.hh \ - nbest.hh \ - rule.hh \ - types.hh \ - vertex.hh \ - vertex_generator.hh \ edge_generator.cc \ nbest.cc \ rule.cc \ - vertex.cc \ - vertex_generator.cc + vertex.cc -AM_CPPFLAGS = -W -Wall -Wno-sign-compare -I$(top_srcdir)/klm +AM_CPPFLAGS = -W -Wall -Wno-sign-compare $(GTEST_CPPFLAGS) -I.. diff --git a/klm/search/context.hh b/klm/search/context.hh index 08f21bbf..c3c8e53b 100644 --- a/klm/search/context.hh +++ b/klm/search/context.hh @@ -12,16 +12,6 @@ class ContextBase { public: explicit ContextBase(const Config &config) : config_(config) {} - VertexNode *NewVertexNode() { - VertexNode *ret = vertex_node_pool_.construct(); - assert(ret); - return ret; - } - - void DeleteVertexNode(VertexNode *node) { - vertex_node_pool_.destroy(node); - } - unsigned int PopLimit() const { return config_.PopLimit(); } Score LMWeight() const { return config_.LMWeight(); } @@ -29,8 +19,6 @@ class ContextBase { const Config &GetConfig() const { return config_; } private: - boost::object_pool vertex_node_pool_; - Config config_; }; diff --git a/klm/search/edge_generator.cc b/klm/search/edge_generator.cc index eacf5de5..dd9d61e4 100644 --- a/klm/search/edge_generator.cc +++ b/klm/search/edge_generator.cc @@ -54,20 +54,20 @@ template PartialEdge EdgeGenerator::Pop(Context &context) { Arity victim = 0; Arity victim_completed; Arity incomplete; + unsigned char lowest_niceness = 255; // Select victim or return if complete. { Arity completed = 0; - unsigned char lowest_length = 255; for (Arity i = 0; i != arity; ++i) { if (top_nt[i].Complete()) { ++completed; - } else if (top_nt[i].Length() < lowest_length) { - lowest_length = top_nt[i].Length(); + } else if (top_nt[i].Niceness() < lowest_niceness) { + lowest_niceness = top_nt[i].Niceness(); victim = i; victim_completed = completed; } } - if (lowest_length == 255) { + if (lowest_niceness == 255) { return top; } incomplete = arity - completed; @@ -92,10 +92,14 @@ template PartialEdge EdgeGenerator::Pop(Context &context) { generate_.push(alternate); } +#ifndef NDEBUG + Score before = top.GetScore(); +#endif // top is now the continuation. FastScore(context, victim, victim - victim_completed, incomplete, old_value, top); // TODO: dedupe? generate_.push(top); + assert(lowest_niceness != 254 || top.GetScore() == before); // Invalid indicates no new hypothesis generated. return PartialEdge(); diff --git a/klm/search/vertex.cc b/klm/search/vertex.cc index 45842982..bf40810e 100644 --- a/klm/search/vertex.cc +++ b/klm/search/vertex.cc @@ -2,6 +2,8 @@ #include "search/context.hh" +#include + #include #include @@ -11,45 +13,193 @@ namespace search { namespace { -struct GreaterByBound : public std::binary_function { - bool operator()(const VertexNode *first, const VertexNode *second) const { - return first->Bound() > second->Bound(); +const uint64_t kCompleteAdd = static_cast(-1); + +class DivideLeft { + public: + explicit DivideLeft(unsigned char index) + : index_(index) {} + + uint64_t operator()(const lm::ngram::ChartState &state) const { + return (index_ < state.left.length) ? + state.left.pointers[index_] : + (kCompleteAdd - state.left.full); + } + + private: + unsigned char index_; +}; + +class DivideRight { + public: + explicit DivideRight(unsigned char index) + : index_(index) {} + + uint64_t operator()(const lm::ngram::ChartState &state) const { + return (index_ < state.right.length) ? + static_cast(state.right.words[index_]) : + (kCompleteAdd - state.left.full); + } + + private: + unsigned char index_; +}; + +template void Split(const Divider ÷r, const std::vector &hypos, std::vector &extend) { + // Map from divider to index in extend. + typedef boost::unordered_map Lookup; + Lookup lookup; + for (std::vector::const_iterator i = hypos.begin(); i != hypos.end(); ++i) { + uint64_t key = divider(i->state); + std::pair res(lookup.insert(std::make_pair(key, extend.size()))); + if (res.second) { + extend.resize(extend.size() + 1); + extend.back().AppendHypothesis(*i); + } else { + extend[res.first->second].AppendHypothesis(*i); + } } + //assert((extend.size() != 1) || (hypos.size() == 1)); +} + +lm::WordIndex Identify(const lm::ngram::Right &right, unsigned char index) { + return right.words[index]; +} + +uint64_t Identify(const lm::ngram::Left &left, unsigned char index) { + return left.pointers[index]; +} + +template class DetermineSame { + public: + DetermineSame(const Side &side, unsigned char guaranteed) + : side_(side), guaranteed_(guaranteed), shared_(side.length), complete_(true) {} + + void Consider(const Side &other) { + if (shared_ != other.length) { + complete_ = false; + if (shared_ > other.length) + shared_ = other.length; + } + for (unsigned char i = guaranteed_; i < shared_; ++i) { + if (Identify(side_, i) != Identify(other, i)) { + shared_ = i; + complete_ = false; + return; + } + } + } + + unsigned char Shared() const { return shared_; } + + bool Complete() const { return complete_; } + + private: + const Side &side_; + unsigned char guaranteed_, shared_; + bool complete_; }; +// Custom enum to save memory: valid values of policy_. +// Alternate and there is still alternation to do. +const unsigned char kPolicyAlternate = 0; +// Branch based on left state only, because right ran out or this is a left tree. +const unsigned char kPolicyOneLeft = 1; +// Branch based on right state only. +const unsigned char kPolicyOneRight = 2; +// Reveal everything in the next branch. Used to terminate the left/right policies. +// static const unsigned char kPolicyEverything = 3; + +} // namespace + +namespace { +struct GreaterByScore : public std::binary_function { + bool operator()(const HypoState &first, const HypoState &second) const { + return first.score > second.score; + } +}; } // namespace -void VertexNode::RecursiveSortAndSet(ContextBase &context, VertexNode *&parent_ptr) { - if (Complete()) { - assert(end_); - assert(extend_.empty()); - return; +void VertexNode::FinishRoot() { + std::sort(hypos_.begin(), hypos_.end(), GreaterByScore()); + extend_.clear(); + // HACK: extend to one hypo so that root can be blank. + state_.left.full = false; + state_.left.length = 0; + state_.right.length = 0; + right_full_ = false; + niceness_ = 0; + policy_ = kPolicyAlternate; + if (hypos_.size() == 1) { + extend_.resize(1); + extend_.front().AppendHypothesis(hypos_.front()); + extend_.front().FinishedAppending(0, 0); + } + if (hypos_.empty()) { + bound_ = -INFINITY; + } else { + bound_ = hypos_.front().score; } - if (extend_.size() == 1) { - parent_ptr = extend_[0]; - extend_[0]->RecursiveSortAndSet(context, parent_ptr); - context.DeleteVertexNode(this); - return; +} + +void VertexNode::FinishedAppending(const unsigned char common_left, const unsigned char common_right) { + assert(!hypos_.empty()); + assert(extend_.empty()); + bound_ = hypos_.front().score; + state_ = hypos_.front().state; + bool all_full = state_.left.full; + bool all_non_full = !state_.left.full; + DetermineSame left(state_.left, common_left); + DetermineSame right(state_.right, common_right); + for (std::vector::const_iterator i = hypos_.begin() + 1; i != hypos_.end(); ++i) { + all_full &= i->state.left.full; + all_non_full &= !i->state.left.full; + left.Consider(i->state.left); + right.Consider(i->state.right); } - for (std::vector::iterator i = extend_.begin(); i != extend_.end(); ++i) { - (*i)->RecursiveSortAndSet(context, *i); + state_.left.full = all_full && left.Complete(); + right_full_ = all_full && right.Complete(); + state_.left.length = left.Shared(); + state_.right.length = right.Shared(); + + if (!all_full && !all_non_full) { + policy_ = kPolicyAlternate; + } else if (left.Complete()) { + policy_ = kPolicyOneRight; + } else if (right.Complete()) { + policy_ = kPolicyOneLeft; + } else { + policy_ = kPolicyAlternate; } - std::sort(extend_.begin(), extend_.end(), GreaterByBound()); - bound_ = extend_.front()->Bound(); + niceness_ = state_.left.length + state_.right.length; } -void VertexNode::SortAndSet(ContextBase &context) { - // This is the root. The root might be empty. - if (extend_.empty()) { - bound_ = -INFINITY; - return; +void VertexNode::BuildExtend() { + // Already built. + if (!extend_.empty()) return; + // Nothing to build since this is a leaf. + if (hypos_.size() <= 1) return; + bool left_branch = true; + switch (policy_) { + case kPolicyAlternate: + left_branch = (state_.left.length <= state_.right.length); + break; + case kPolicyOneLeft: + left_branch = true; + break; + case kPolicyOneRight: + left_branch = false; + break; + } + if (left_branch) { + Split(DivideLeft(state_.left.length), hypos_, extend_); + } else { + Split(DivideRight(state_.right.length), hypos_, extend_); } - // The root cannot be replaced. There's always one transition. - for (std::vector::iterator i = extend_.begin(); i != extend_.end(); ++i) { - (*i)->RecursiveSortAndSet(context, *i); + for (std::vector::iterator i = extend_.begin(); i != extend_.end(); ++i) { + // TODO: provide more here for branching? + i->FinishedAppending(state_.left.length, state_.right.length); } - std::sort(extend_.begin(), extend_.end(), GreaterByBound()); - bound_ = extend_.front()->Bound(); } } // namespace search diff --git a/klm/search/vertex.hh b/klm/search/vertex.hh index ca9a4fcd..81c3cfed 100644 --- a/klm/search/vertex.hh +++ b/klm/search/vertex.hh @@ -16,59 +16,74 @@ namespace search { class ContextBase; +struct HypoState { + History history; + lm::ngram::ChartState state; + Score score; +}; + class VertexNode { public: - VertexNode() : end_() {} - - void InitRoot() { - extend_.clear(); - state_.left.full = false; - state_.left.length = 0; - state_.right.length = 0; - right_full_ = false; - end_ = History(); + VertexNode() {} + + void InitRoot() { hypos_.clear(); } + + /* The steps of building a VertexNode: + * 1. Default construct. + * 2. AppendHypothesis at least once, possibly multiple times. + * 3. FinishAppending with the number of words on left and right guaranteed + * to be common. + * 4. If !Complete(), call BuildExtend to construct the extensions + */ + // Must default construct, call AppendHypothesis 1 or more times then do FinishedAppending. + void AppendHypothesis(const NBestComplete &best) { + assert(hypos_.empty() || !(hypos_.front().state == *best.state)); + HypoState hypo; + hypo.history = best.history; + hypo.state = *best.state; + hypo.score = best.score; + hypos_.push_back(hypo); + } + void AppendHypothesis(const HypoState &hypo) { + hypos_.push_back(hypo); } - lm::ngram::ChartState &MutableState() { return state_; } - bool &MutableRightFull() { return right_full_; } + // Sort hypotheses for the root. + void FinishRoot(); - void AddExtend(VertexNode *next) { - extend_.push_back(next); - } + void FinishedAppending(const unsigned char common_left, const unsigned char common_right); - void SetEnd(History end, Score score) { - assert(!end_); - end_ = end; - bound_ = score; - } - - void SortAndSet(ContextBase &context); + void BuildExtend(); // Should only happen to a root node when the entire vertex is empty. bool Empty() const { - return !end_ && extend_.empty(); + return hypos_.empty() && extend_.empty(); } bool Complete() const { - return end_; + // HACK: prevent root from being complete. TODO: allow root to be complete. + return hypos_.size() == 1 && extend_.empty(); } const lm::ngram::ChartState &State() const { return state_; } bool RightFull() const { return right_full_; } + // Priority relative to other non-terminals. 0 is highest. + unsigned char Niceness() const { return niceness_; } + Score Bound() const { return bound_; } - unsigned char Length() const { - return state_.left.length + state_.right.length; - } - // Will be invalid unless this is a leaf. - History End() const { return end_; } + History End() const { + assert(hypos_.size() == 1); + return hypos_.front().history; + } - const VertexNode &operator[](size_t index) const { - return *extend_[index]; + VertexNode &operator[](size_t index) { + assert(!extend_.empty()); + return extend_[index]; } size_t Size() const { @@ -76,22 +91,26 @@ class VertexNode { } private: - void RecursiveSortAndSet(ContextBase &context, VertexNode *&parent); + // Hypotheses to be split. + std::vector hypos_; - std::vector extend_; + std::vector extend_; lm::ngram::ChartState state_; bool right_full_; + unsigned char niceness_; + + unsigned char policy_; + Score bound_; - History end_; }; class PartialVertex { public: PartialVertex() {} - explicit PartialVertex(const VertexNode &back) : back_(&back), index_(0) {} + explicit PartialVertex(VertexNode &back) : back_(&back), index_(0) {} bool Empty() const { return back_->Empty(); } @@ -100,17 +119,14 @@ class PartialVertex { const lm::ngram::ChartState &State() const { return back_->State(); } bool RightFull() const { return back_->RightFull(); } - Score Bound() const { return Complete() ? back_->Bound() : (*back_)[index_].Bound(); } - - unsigned char Length() const { return back_->Length(); } + Score Bound() const { return index_ ? (*back_)[index_].Bound() : back_->Bound(); } - bool HasAlternative() const { - return index_ + 1 < back_->Size(); - } + unsigned char Niceness() const { return back_->Niceness(); } // Split into continuation and alternative, rendering this the continuation. bool Split(PartialVertex &alternative) { assert(!Complete()); + back_->BuildExtend(); bool ret; if (index_ + 1 < back_->Size()) { alternative.index_ = index_ + 1; @@ -129,7 +145,7 @@ class PartialVertex { } private: - const VertexNode *back_; + VertexNode *back_; unsigned int index_; }; @@ -139,10 +155,21 @@ class Vertex { public: Vertex() {} - PartialVertex RootPartial() const { return PartialVertex(root_); } + //PartialVertex RootFirst() const { return PartialVertex(right_); } + PartialVertex RootAlternate() { return PartialVertex(root_); } + //PartialVertex RootLast() const { return PartialVertex(left_); } + + bool Empty() const { + return root_.Empty(); + } + + Score Bound() const { + return root_.Bound(); + } - History BestChild() const { - PartialVertex top(RootPartial()); + History BestChild() { + // left_ and right_ are not set at the root. + PartialVertex top(RootAlternate()); if (top.Empty()) { return History(); } else { @@ -158,6 +185,12 @@ class Vertex { template friend class VertexGenerator; template friend class RootVertexGenerator; VertexNode root_; + + // These will not be set for the root vertex. + // Branches only on left state. + //VertexNode left_; + // Branches only on right state. + //VertexNode right_; }; } // namespace search diff --git a/klm/search/vertex_generator.hh b/klm/search/vertex_generator.hh index 646b8189..91000012 100644 --- a/klm/search/vertex_generator.hh +++ b/klm/search/vertex_generator.hh @@ -4,10 +4,8 @@ #include "search/edge.hh" #include "search/types.hh" #include "search/vertex.hh" -#include "util/exception.hh" #include -#include namespace lm { namespace ngram { @@ -19,45 +17,25 @@ namespace search { class ContextBase; -#if BOOST_VERSION > 104200 -// Parallel structure to VertexNode. -struct Trie { - Trie() : under(NULL) {} - - VertexNode *under; - boost::unordered_map extend; -}; - -void AddHypothesis(ContextBase &context, Trie &root, const NBestComplete &end); - -#endif // BOOST_VERSION - // Output makes the single-best or n-best list. template class VertexGenerator { public: - VertexGenerator(ContextBase &context, Vertex &gen, Output &nbest) : context_(context), gen_(gen), nbest_(nbest) { - gen.root_.InitRoot(); - } + VertexGenerator(ContextBase &context, Vertex &gen, Output &nbest) : context_(context), gen_(gen), nbest_(nbest) {} void NewHypothesis(PartialEdge partial) { nbest_.Add(existing_[hash_value(partial.CompletedState())], partial); } void FinishedSearch() { -#if BOOST_VERSION > 104200 - Trie root; - root.under = &gen_.root_; + gen_.root_.InitRoot(); for (typename Existing::iterator i(existing_.begin()); i != existing_.end(); ++i) { - AddHypothesis(context_, root, nbest_.Complete(i->second)); + gen_.root_.AppendHypothesis(nbest_.Complete(i->second)); } existing_.clear(); - root.under->SortAndSet(context_); -#else - UTIL_THROW(util::Exception, "Upgrade Boost to >= 1.42.0 to use incremental search."); -#endif + gen_.root_.FinishRoot(); } - const Vertex &Generating() const { return gen_; } + Vertex &Generating() { return gen_; } private: ContextBase &context_; @@ -84,8 +62,8 @@ template class RootVertexGenerator { void FinishedSearch() { gen_.root_.InitRoot(); - NBestComplete completed(out_.Complete(combine_)); - gen_.root_.SetEnd(completed.history, completed.score); + gen_.root_.AppendHypothesis(out_.Complete(combine_)); + gen_.root_.FinishRoot(); } private: diff --git a/klm/util/double-conversion/utils.h b/klm/util/double-conversion/utils.h index 2bd71605..9ccb3b65 100644 --- a/klm/util/double-conversion/utils.h +++ b/klm/util/double-conversion/utils.h @@ -299,7 +299,11 @@ template inline Dest BitCast(const Source& source) { // Compile time assertion: sizeof(Dest) == sizeof(Source) // A compile error here means your Dest and Source have different sizes. - typedef char VerifySizesAreEqual[sizeof(Dest) == sizeof(Source) ? 1 : -1]; + typedef char VerifySizesAreEqual[sizeof(Dest) == sizeof(Source) ? 1 : -1] +#if __GNUC__ > 4 || __GNUC__ == 4 && __GNUC_MINOR__ >= 8 + __attribute__((unused)) +#endif + ; Dest dest; memmove(&dest, &source, sizeof(dest)); diff --git a/klm/util/file.cc b/klm/util/file.cc index c7d8e23b..bef04cb1 100644 --- a/klm/util/file.cc +++ b/klm/util/file.cc @@ -116,7 +116,7 @@ std::size_t GuardLarge(std::size_t size) { // The following operating systems have broken read/write/pread/pwrite that // only supports up to 2^31. #if defined(_WIN32) || defined(_WIN64) || defined(__APPLE__) || defined(OS_ANDROID) - return std::min(static_cast(INT_MAX), size); + return std::min(static_cast(static_cast(-1)), size); #else return size; #endif @@ -209,7 +209,7 @@ void WriteOrThrow(int fd, const void *data_void, std::size_t size) { #endif errno = 0; do { - ret = + ret = #if defined(_WIN32) || defined(_WIN64) _write #else @@ -229,7 +229,7 @@ void WriteOrThrow(FILE *to, const void *data, std::size_t size) { } void FSyncOrThrow(int fd) { -// Apparently windows doesn't have fsync? +// Apparently windows doesn't have fsync? #if !defined(_WIN32) && !defined(_WIN64) UTIL_THROW_IF_ARG(-1 == fsync(fd), FDException, (fd), "while syncing"); #endif @@ -248,7 +248,7 @@ template <> struct CheckOffT<8> { typedef CheckOffT::True IgnoredType; #endif -// Can't we all just get along? +// Can't we all just get along? void InternalSeek(int fd, int64_t off, int whence) { if ( #if defined(_WIN32) || defined(_WIN64) @@ -457,9 +457,9 @@ bool TryName(int fd, std::string &out) { std::ostringstream convert; convert << fd; name += convert.str(); - + struct stat sb; - if (-1 == lstat(name.c_str(), &sb)) + if (-1 == lstat(name.c_str(), &sb)) return false; out.resize(sb.st_size + 1); ssize_t ret = readlink(name.c_str(), &out[0], sb.st_size + 1); @@ -471,7 +471,7 @@ bool TryName(int fd, std::string &out) { } out.resize(ret); // Don't use the non-file names. - if (!out.empty() && out[0] != '/') + if (!out.empty() && out[0] != '/') return false; return true; #endif diff --git a/klm/util/pool.cc b/klm/util/pool.cc index 429ba158..db72a8ec 100644 --- a/klm/util/pool.cc +++ b/klm/util/pool.cc @@ -25,7 +25,9 @@ void Pool::FreeAll() { } void *Pool::More(std::size_t size) { - std::size_t amount = std::max(static_cast(32) << free_list_.size(), size); + // Double until we hit 2^21 (2 MB). Then grow in 2 MB blocks. + std::size_t desired_size = static_cast(32) << std::min(static_cast(16), free_list_.size()); + std::size_t amount = std::max(desired_size, size); uint8_t *ret = static_cast(MallocOrThrow(amount)); free_list_.push_back(ret); current_ = ret + size; diff --git a/klm/util/probing_hash_table.hh b/klm/util/probing_hash_table.hh index 57866ff9..51a2944d 100644 --- a/klm/util/probing_hash_table.hh +++ b/klm/util/probing_hash_table.hh @@ -109,9 +109,20 @@ template MutableIterator UnsafeMutableMustFind(const Key key) { + for (MutableIterator i(begin_ + (hash_(key) % buckets_));;) { + Key got(i->GetKey()); + if (equal_(got, key)) { return i; } + assert(!equal_(got, invalid_)); + if (++i == end_) i = begin_; + } } + template bool Find(const Key key, ConstIterator &out) const { #ifdef DEBUG assert(initialized_); @@ -124,6 +135,16 @@ template ConstIterator MustFind(const Key key) const { + for (ConstIterator i(begin_ + (hash_(key) % buckets_));;) { + Key got(i->GetKey()); + if (equal_(got, key)) { return i; } + assert(!equal_(got, invalid_)); + if (++i == end_) i = begin_; + } + } + void Clear() { Entry invalid; invalid.SetKey(invalid_); diff --git a/klm/util/proxy_iterator.hh b/klm/util/proxy_iterator.hh index 121a45fa..0ee1716f 100644 --- a/klm/util/proxy_iterator.hh +++ b/klm/util/proxy_iterator.hh @@ -6,11 +6,11 @@ /* This is a RandomAccessIterator that uses a proxy to access the underlying * data. Useful for packing data at bit offsets but still using STL - * algorithms. + * algorithms. * * Normally I would use boost::iterator_facade but some people are too lazy to * install boost and still want to use my language model. It's amazing how - * many operators an iterator has. + * many operators an iterator has. * * The Proxy needs to provide: * class InnerIterator; @@ -22,15 +22,15 @@ * operator<(InnerIterator) * operator+=(std::ptrdiff_t) * operator-(InnerIterator) - * and of course whatever Proxy needs to dereference it. + * and of course whatever Proxy needs to dereference it. * - * It's also a good idea to specialize std::swap for Proxy. + * It's also a good idea to specialize std::swap for Proxy. */ namespace util { template class ProxyIterator { private: - // Self. + // Self. typedef ProxyIterator S; typedef typename Proxy::InnerIterator InnerIterator; @@ -38,16 +38,21 @@ template class ProxyIterator { typedef std::random_access_iterator_tag iterator_category; typedef typename Proxy::value_type value_type; typedef std::ptrdiff_t difference_type; - typedef Proxy reference; + typedef Proxy & reference; typedef Proxy * pointer; ProxyIterator() {} - // For cast from non const to const. + // For cast from non const to const. template ProxyIterator(const ProxyIterator &in) : p_(*in) {} explicit ProxyIterator(const Proxy &p) : p_(p) {} - // p_'s operator= does value copying, but here we want iterator copying. + // p_'s swap does value swapping, but here we want iterator swapping + friend inline void swap(ProxyIterator &first, ProxyIterator &second) { + swap(first.I(), second.I()); + } + + // p_'s operator= does value copying, but here we want iterator copying. S &operator=(const S &other) { I() = other.I(); return *this; @@ -72,8 +77,8 @@ template class ProxyIterator { std::ptrdiff_t operator-(const S &other) const { return I() - other.I(); } - Proxy operator*() { return p_; } - const Proxy operator*() const { return p_; } + Proxy &operator*() { return p_; } + const Proxy &operator*() const { return p_; } Proxy *operator->() { return &p_; } const Proxy *operator->() const { return &p_; } Proxy operator[](std::ptrdiff_t amount) const { return *(*this + amount); } diff --git a/klm/util/sized_iterator.hh b/klm/util/sized_iterator.hh index cf998953..dce8f229 100644 --- a/klm/util/sized_iterator.hh +++ b/klm/util/sized_iterator.hh @@ -36,6 +36,11 @@ class SizedInnerIterator { void *Data() { return ptr_; } std::size_t EntrySize() const { return size_; } + friend inline void swap(SizedInnerIterator &first, SizedInnerIterator &second) { + std::swap(first.ptr_, second.ptr_); + std::swap(first.size_, second.size_); + } + private: uint8_t *ptr_; std::size_t size_; @@ -64,9 +69,19 @@ class SizedProxy { const void *Data() const { return inner_.Data(); } void *Data() { return inner_.Data(); } + /** + // TODO: this (deep) swap was recently added. why? if any std heap sort etc + // algs are using swap, that's going to be worse performance than using + // =. i'm not sure why we *want* a deep swap. if C++11 compilers are + // choosing between move constructor and swap, then we'd better implement a + // (deep) move constructor. it may also be that this is moot since i made + // ProxyIterator a reference and added a shallow ProxyIterator swap? (I + // need Ken or someone competent to judge whether that's correct also. - + // let me know at graehl@gmail.com + */ friend void swap(SizedProxy &first, SizedProxy &second) { std::swap_ranges( - static_cast(first.inner_.Data()), + static_cast(first.inner_.Data()), static_cast(first.inner_.Data()) + first.inner_.EntrySize(), static_cast(second.inner_.Data())); } @@ -87,7 +102,7 @@ typedef ProxyIterator SizedIterator; inline SizedIterator SizedIt(void *ptr, std::size_t size) { return SizedIterator(SizedProxy(ptr, size)); } -// Useful wrapper for a comparison function i.e. sort. +// Useful wrapper for a comparison function i.e. sort. template class SizedCompare : public std::binary_function { public: explicit SizedCompare(const Delegate &delegate = Delegate()) : delegate_(delegate) {} @@ -106,7 +121,7 @@ template class SizedCompare : public } const Delegate &GetDelegate() const { return delegate_; } - + private: const Delegate delegate_; }; diff --git a/klm/util/stream/chain.hh b/klm/util/stream/chain.hh index 154b9b33..0cc83a85 100644 --- a/klm/util/stream/chain.hh +++ b/klm/util/stream/chain.hh @@ -122,7 +122,7 @@ class Chain { threads_.push_back(new Thread(Complete(), kRecycle)); } - Chain &operator>>(const Recycler &recycle) { + Chain &operator>>(const Recycler &) { CompleteLoop(); return *this; } diff --git a/klm/util/usage.cc b/klm/util/usage.cc index 5fa3cc9a..8db375e1 100644 --- a/klm/util/usage.cc +++ b/klm/util/usage.cc @@ -21,6 +21,21 @@ namespace util { #if !defined(_WIN32) && !defined(_WIN64) namespace { + +// On Mac OS X, clock_gettime is not implemented. +// CLOCK_MONOTONIC is not defined either. +#ifdef __MACH__ +#define CLOCK_MONOTONIC 0 + +int clock_gettime(int clk_id, struct timespec *tp) { + struct timeval tv; + gettimeofday(&tv, NULL); + tp->tv_sec = tv.tv_sec; + tp->tv_nsec = tv.tv_usec * 1000; + return 0; +} +#endif // __MACH__ + float FloatSec(const struct timeval &tv) { return static_cast(tv.tv_sec) + (static_cast(tv.tv_usec) / 1000000.0); } -- cgit v1.2.3