KenLM 85c82bd, revamp Moses timer to have more precision

7 files changed, 253 insertions, 47 deletions

diff --git a/util/file_piece.cc b/util/file_piece.cc
index b5961bea6..9c7e00c4c 100644
--- a/util/file_piece.cc
+++ b/util/file_piece.cc
@@ -74,7 +74,9 @@ StringPiece FilePiece::ReadLine(char delim) {
       }
     }
     if (at_end_) {
-      if (position_ == position_end_) Shift();
+      if (position_ == position_end_) {
+        Shift();
+      }
       return Consume(position_end_);
     }
     skip = position_end_ - position_;
diff --git a/util/file_piece.hh b/util/file_piece.hh
index c07c60119..ed3dc5adf 100644
--- a/util/file_piece.hh
+++ b/util/file_piece.hh
@@ -12,6 +12,7 @@
 #include <iosfwd>
 #include <string>
 
+#include <assert.h>
 #include <stdint.h>
 
 namespace util {
@@ -66,8 +67,14 @@ class FilePiece {
 
     // Skip spaces defined by isspace.
     void SkipSpaces(const bool *delim = kSpaces) {
+      assert(position_ <= position_end_);
       for (; ; ++position_) {
-        if (position_ == position_end_) Shift();
+        if (position_ == position_end_) {
+          Shift();
+          // And break out at end of file.
+          if (position_ == position_end_) return;
+        }
+        assert(position_ < position_end_);
         if (!delim[static_cast<unsigned char>(*position_)]) return;
       }
     }
@@ -86,6 +93,7 @@ class FilePiece {
     template <class T> T ReadNumber();
 
     StringPiece Consume(const char *to) {
+      assert(to >= position_);
       StringPiece ret(position_, to - position_);
       position_ = to;
       return ret;
diff --git a/util/multi_intersection.hh b/util/multi_intersection.hh
index 8334d39df..04678352d 100644
--- a/util/multi_intersection.hh
+++ b/util/multi_intersection.hh
@@ -66,7 +66,7 @@ template <class Iterator, class Output, class Less> void AllIntersection(std::ve
 
   std::sort(sets.begin(), sets.end(), detail::RangeLessBySize<boost::iterator_range<Iterator> >());
   boost::optional<Value> ret;
-  for (boost::optional<Value> ret; ret = detail::FirstIntersectionSorted(sets, less); sets.front().advance_begin(1)) {
+  for (boost::optional<Value> ret; (ret = detail::FirstIntersectionSorted(sets, less)); sets.front().advance_begin(1)) {
     out(*ret);
   }
 }
diff --git a/util/probing_hash_table.hh b/util/probing_hash_table.hh
index 51a2944d9..9566028f5 100644
--- a/util/probing_hash_table.hh
+++ b/util/probing_hash_table.hh
@@ -2,6 +2,7 @@
 #define UTIL_PROBING_HASH_TABLE__
 
 #include "util/exception.hh"
+#include "util/scoped.hh"
 
 #include <algorithm>
 #include <cstddef>
@@ -25,6 +26,8 @@ struct IdentityHash {
   template <class T> T operator()(T arg) const { return arg; }
 };
 
+template <class EntryT, class HashT, class EqualT> class AutoProbing;
+
 /* Non-standard hash table
  * Buckets must be set at the beginning and must be greater than maximum number
  * of elements, else it throws ProbingSizeException.
@@ -33,7 +36,6 @@ struct IdentityHash {
  * Uses linear probing to find value.
  * Only insert and lookup operations.  
  */
-
 template <class EntryT, class HashT, class EqualT = std::equal_to<typename EntryT::Key> > class ProbingHashTable {
   public:
     typedef EntryT Entry;
@@ -43,7 +45,6 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry
     typedef HashT Hash;
     typedef EqualT Equal;
 
-  public:
     static uint64_t Size(uint64_t entries, float multiplier) {
       uint64_t buckets = std::max(entries + 1, static_cast<uint64_t>(multiplier * static_cast<float>(entries)));
       return buckets * sizeof(Entry);
@@ -82,7 +83,7 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry
 #ifdef DEBUG
       assert(initialized_);
 #endif
-      for (MutableIterator i(begin_ + (hash_(t.GetKey()) % buckets_));;) {
+      for (MutableIterator i = Ideal(t);;) {
         Key got(i->GetKey());
         if (equal_(got, t.GetKey())) { out = i; return true; }
         if (equal_(got, invalid_)) {
@@ -224,6 +225,8 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry
     }
 
   private:
+    friend class AutoProbing<Entry, Hash, Equal>;
+
     template <class T> MutableIterator Ideal(const T &t) {
       return begin_ + (hash_(t.GetKey()) % buckets_);
     }
@@ -247,6 +250,74 @@ template <class EntryT, class HashT, class EqualT = std::equal_to<typename Entry
 #endif
 };
 
+// Resizable linear probing hash table.  This owns the memory.  
+template <class EntryT, class HashT, class EqualT = std::equal_to<typename EntryT::Key> > class AutoProbing {
+  private:
+    typedef ProbingHashTable<EntryT, HashT, EqualT> Backend;
+  public:
+    typedef EntryT Entry;
+    typedef typename Entry::Key Key;
+    typedef const Entry *ConstIterator;
+    typedef Entry *MutableIterator;
+    typedef HashT Hash;
+    typedef EqualT Equal;
+
+    AutoProbing(std::size_t initial_size = 10, const Key &invalid = Key(), const Hash &hash_func = Hash(), const Equal &equal_func = Equal()) :
+      allocated_(Backend::Size(initial_size, 1.5)), mem_(util::MallocOrThrow(allocated_)), backend_(mem_.get(), allocated_, invalid, hash_func, equal_func) {
+      threshold_ = initial_size * 1.2;
+    }
+
+    // Assumes that the key is unique.  Multiple insertions won't cause a failure, just inconsistent lookup.
+    template <class T> MutableIterator Insert(const T &t) {
+      DoubleIfNeeded();
+      return backend_.UncheckedInsert(t);
+    }
+
+    template <class T> bool FindOrInsert(const T &t, MutableIterator &out) {
+      DoubleIfNeeded();
+      return backend_.FindOrInsert(t, out);
+    }
+
+    template <class Key> bool UnsafeMutableFind(const Key key, MutableIterator &out) {
+      return backend_.UnsafeMutableFind(key, out);
+    }
+
+    template <class Key> MutableIterator UnsafeMutableMustFind(const Key key) {
+      return backend_.UnsafeMutableMustFind(key);
+    }
+
+    template <class Key> bool Find(const Key key, ConstIterator &out) const {
+      return backend_.Find(key, out);
+    }
+
+    template <class Key> ConstIterator MustFind(const Key key) const {
+      return backend_.MustFind(key);
+    }
+
+    std::size_t Size() const {
+      return backend_.SizeNoSerialization();
+    }
+
+    void Clear() {
+      backend_.Clear();
+    }
+
+  private:
+    void DoubleIfNeeded() {
+      if (Size() < threshold_)
+        return;
+      mem_.call_realloc(backend_.DoubleTo());
+      allocated_ = backend_.DoubleTo();
+      backend_.Double(mem_.get());
+      threshold_ *= 2;
+    }
+
+    std::size_t allocated_;
+    util::scoped_malloc mem_;
+    Backend backend_;
+    std::size_t threshold_;
+};
+
 } // namespace util
 
 #endif // UTIL_PROBING_HASH_TABLE__
diff --git a/util/tokenize_piece.hh b/util/tokenize_piece.hh
index a588c3fca..24eae8fbe 100644
--- a/util/tokenize_piece.hh
+++ b/util/tokenize_piece.hh
@@ -58,6 +58,23 @@ class AnyCharacter {
     StringPiece chars_;
 };
 
+class BoolCharacter {
+  public:
+    BoolCharacter() {}
+
+    explicit BoolCharacter(const bool *delimiter) { delimiter_ = delimiter; }
+
+    StringPiece Find(const StringPiece &in) const {
+      for (const char *i = in.data(); i != in.data() + in.size(); ++i) {
+        if (delimiter_[static_cast<unsigned char>(*i)]) return StringPiece(i, 1);
+      }
+      return StringPiece(in.data() + in.size(), 0);
+    }
+
+  private:
+    const bool *delimiter_;
+};
+
 class AnyCharacterLast {
   public:
     AnyCharacterLast() {}
diff --git a/util/usage.cc b/util/usage.cc
index 25fc09755..2f870d854 100644
--- a/util/usage.cc
+++ b/util/usage.cc
@@ -10,61 +10,109 @@
 
 #include <string.h>
 #include <ctype.h>
-#if !defined(_WIN32) && !defined(_WIN64)
+#include <time.h>
+#if defined(_WIN32) || defined(_WIN64)
+// This code lifted from physmem.c in gnulib.  See the copyright statement
+// below.  
+# define WIN32_LEAN_AND_MEAN
+# include <windows.h>
+/*  MEMORYSTATUSEX is missing from older windows headers, so define
+    a local replacement.  */
+typedef struct
+{
+  DWORD dwLength;
+  DWORD dwMemoryLoad;
+  DWORDLONG ullTotalPhys;
+  DWORDLONG ullAvailPhys;
+  DWORDLONG ullTotalPageFile;
+  DWORDLONG ullAvailPageFile;
+  DWORDLONG ullTotalVirtual;
+  DWORDLONG ullAvailVirtual;
+  DWORDLONG ullAvailExtendedVirtual;
+} lMEMORYSTATUSEX;
+typedef WINBOOL (WINAPI *PFN_MS_EX) (lMEMORYSTATUSEX*);
+#else
 #include <sys/resource.h>
 #include <sys/time.h>
-#include <time.h>
 #include <unistd.h>
 #endif
 
-namespace util {
+#if defined(__MACH__) || defined(__FreeBSD__) || defined(__APPLE__)
+#include <sys/types.h>
+#include <sys/sysctl.h>
+#endif
 
-#if !defined(_WIN32) && !defined(_WIN64)
+namespace util {
 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) {
+#if defined(__MACH__)
+typedef struct timeval Wall;
+Wall GetWall() {
   struct timeval tv;
   gettimeofday(&tv, NULL);
-  tp->tv_sec = tv.tv_sec;
-  tp->tv_nsec = tv.tv_usec * 1000;
-  return 0;
+  return tv;
 }
-#endif // __MACH__
-
-float FloatSec(const struct timeval &tv) {
-  return static_cast<float>(tv.tv_sec) + (static_cast<float>(tv.tv_usec) / 1000000.0);
+#elif defined(_WIN32) || defined(_WIN64)
+typedef time_t Wall;
+Wall GetWall() {
+  return time(NULL);
 }
-float FloatSec(const struct timespec &tv) {
-  return static_cast<float>(tv.tv_sec) + (static_cast<float>(tv.tv_nsec) / 1000000000.0);
+#else
+typedef struct timespec Wall;
+Wall GetWall() {
+  Wall ret;
+  clock_gettime(CLOCK_MONOTONIC, &ret);
+  return ret;
 }
+#endif
 
-const char *SkipSpaces(const char *at) {
-  for (; *at == ' ' || *at == '\t'; ++at) {}
-  return at;
+// These all assume first > second
+double Subtract(time_t first, time_t second) {
+  return difftime(first, second);
+}
+double DoubleSec(time_t tv) {
+  return static_cast<double>(tv);
+}
+#if !defined(_WIN32) && !defined(_WIN64)
+double Subtract(const struct timeval &first, const struct timeval &second) {
+  return static_cast<double>(first.tv_sec - second.tv_sec) + static_cast<double>(first.tv_usec - second.tv_usec) / 1000000.0;
+}
+double Subtract(const struct timespec &first, const struct timespec &second) {
+  return static_cast<double>(first.tv_sec - second.tv_sec) + static_cast<double>(first.tv_nsec - second.tv_nsec) / 1000000000.0;
 }
+double DoubleSec(const struct timeval &tv) {
+  return static_cast<double>(tv.tv_sec) + (static_cast<double>(tv.tv_usec) / 1000000.0);
+}
+double DoubleSec(const struct timespec &tv) {
+  return static_cast<double>(tv.tv_sec) + (static_cast<double>(tv.tv_nsec) / 1000000000.0);
+}
+#endif
 
 class RecordStart {
   public:
     RecordStart() {
-      clock_gettime(CLOCK_MONOTONIC, &started_);
+      started_ = GetWall();
     }
 
-    const struct timespec &Started() const {
+    const Wall &Started() const {
       return started_;
     }
 
   private:
-    struct timespec started_;
+    Wall started_;
 };
 
 const RecordStart kRecordStart;
+
+const char *SkipSpaces(const char *at) {
+  for (; *at == ' ' || *at == '\t'; ++at) {}
+  return at;
+}
 } // namespace
-#endif
+
+double WallTime() {
+  return Subtract(GetWall(), kRecordStart.Started());
+}
 
 void PrintUsage(std::ostream &out) {
 #if !defined(_WIN32) && !defined(_WIN64)
@@ -88,27 +136,84 @@ void PrintUsage(std::ostream &out) {
     return;
   }
   out << "RSSMax:" << usage.ru_maxrss << " kB" << '\t';
-  out << "user:" << FloatSec(usage.ru_utime) << "\tsys:" << FloatSec(usage.ru_stime) << '\t';
-  out << "CPU:" << (FloatSec(usage.ru_utime) + FloatSec(usage.ru_stime));
-
-  struct timespec current;
-  clock_gettime(CLOCK_MONOTONIC, &current);
-  out << "\treal:" << (FloatSec(current) - FloatSec(kRecordStart.Started())) << '\n';
+  out << "user:" << DoubleSec(usage.ru_utime) << "\tsys:" << DoubleSec(usage.ru_stime) << '\t';
+  out << "CPU:" << (DoubleSec(usage.ru_utime) + DoubleSec(usage.ru_stime));
+  out << '\t';
 #endif
+
+  out << "real:" << WallTime() << '\n';
 }
 
+/* Adapted from physmem.c in gnulib 831b84c59ef413c57a36b67344467d66a8a2ba70 */
+/* Calculate the size of physical memory.
+
+   Copyright (C) 2000-2001, 2003, 2005-2006, 2009-2013 Free Software
+   Foundation, Inc.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU Lesser General Public License as published by
+   the Free Software Foundation; either version 2.1 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+/* Written by Paul Eggert.  */
 uint64_t GuessPhysicalMemory() {
+#if defined(_SC_PHYS_PAGES) && defined(_SC_PAGESIZE)
+  {
+    long pages = sysconf(_SC_PHYS_PAGES);
+    long page_size = sysconf(_SC_PAGESIZE);
+    if (pages != -1 && page_size != -1)
+      return static_cast<uint64_t>(pages) * static_cast<uint64_t>(page_size);
+  }
+#endif
+#ifdef HW_PHYSMEM
+  { /* This works on *bsd and darwin.  */
+    unsigned int physmem;
+    size_t len = sizeof physmem;
+    static int mib[2] = { CTL_HW, HW_PHYSMEM };
+
+    if (sysctl (mib, sizeof(mib) / sizeof(mib[0]), &physmem, &len, NULL, 0) == 0
+        && len == sizeof (physmem))
+      return static_cast<uint64_t>(physmem);
+  }
+#endif
+
 #if defined(_WIN32) || defined(_WIN64)
-  return 0;
-#elif defined(_SC_PHYS_PAGES) && defined(_SC_PAGESIZE)
-  long pages = sysconf(_SC_PHYS_PAGES);
-  if (pages == -1) return 0;
-  long page_size = sysconf(_SC_PAGESIZE);
-  if (page_size == -1) return 0;
-  return static_cast<uint64_t>(pages) * static_cast<uint64_t>(page_size);
-#else
-  return 0;
+  { /* this works on windows */
+    PFN_MS_EX pfnex;
+    HMODULE h = GetModuleHandle ("kernel32.dll");
+
+    if (!h)
+      return 0;
+
+    /*  Use GlobalMemoryStatusEx if available.  */
+    if ((pfnex = (PFN_MS_EX) GetProcAddress (h, "GlobalMemoryStatusEx")))
+      {
+        lMEMORYSTATUSEX lms_ex;
+        lms_ex.dwLength = sizeof lms_ex;
+        if (!pfnex (&lms_ex))
+          return 0;
+        return lms_ex.ullTotalPhys;
+      }
+
+    /*  Fall back to GlobalMemoryStatus which is always available.
+        but returns wrong results for physical memory > 4GB.  */
+    else
+      {
+        MEMORYSTATUS ms;
+        GlobalMemoryStatus (&ms);
+        return ms.dwTotalPhys;
+      }
+  }
 #endif
+  return 0;
 }
 
 namespace {
diff --git a/util/usage.hh b/util/usage.hh
index e19eda7bf..da53b9e32 100644
--- a/util/usage.hh
+++ b/util/usage.hh
@@ -7,6 +7,9 @@
 #include <stdint.h>
 
 namespace util {
+// Time in seconds since process started.  Zero on unsupported platforms.
+double WallTime();
+
 void PrintUsage(std::ostream &to);
 
 // Determine how much physical memory there is.  Return 0 on failure.