commodity_t::find_price now uses memoization

This reduces the slowdown of using -V and -X from 36x in some cases down
to around 4-5x (for a debug build).

2 files changed, 123 insertions, 29 deletions

diff --git a/src/commodity.cc b/src/commodity.cc
index 2ed6553b..1554887c 100644
--- a/src/commodity.cc
+++ b/src/commodity.cc
@@ -268,13 +268,13 @@ commodity_t::varied_history_t::find_price(const commodity_t&            source,
     if (! commodity && ! comm.has_flags(COMMODITY_PRIMARY))
       continue;
 
-    DEBUG_INDENT("commodity.prices.find", indent);
+    DEBUG_INDENT("commodity.prices.find", indent + 1);
     DEBUG("commodity.prices.find",
 	  "searching for price via commodity '" << comm << "'");
 
     point = hist.second.find_price(moment, limit
 #if defined(DEBUG_ON)
-				   , indent + 1
+				   , indent + 2
 #endif
 				   );
     assert(! point || point->price.commodity() == comm);
@@ -283,16 +283,16 @@ commodity_t::varied_history_t::find_price(const commodity_t&            source,
       optional<price_point_t> xlat;
 
       if (commodity && comm != *commodity) {
-	DEBUG_INDENT("commodity.prices.find", indent);
+	DEBUG_INDENT("commodity.prices.find", indent + 1);
 	DEBUG("commodity.prices.find", "looking for translation price");
 
-	xlat = comm.find_price(commodity, moment, limit
+	xlat = comm.find_price(commodity, moment, limit, true
 #if defined(DEBUG_ON)
-			       , indent + 1
+			       , indent + 2
 #endif
 			       );
 	if (xlat) {
-	  DEBUG_INDENT("commodity.prices.find", indent);
+	  DEBUG_INDENT("commodity.prices.find", indent + 1);
 	  DEBUG("commodity.prices.find", "found translated price "
 		<< xlat->price << " from " << xlat->when);
 
@@ -300,12 +300,12 @@ commodity_t::varied_history_t::find_price(const commodity_t&            source,
 	  if (xlat->when < point->when) {
 	    point->when = xlat->when;
 
-	    DEBUG_INDENT("commodity.prices.find", indent);
+	    DEBUG_INDENT("commodity.prices.find", indent + 1);
 	    DEBUG("commodity.prices.find",
 		  "adjusting date of result back to " << point->when);
 	  }
 	} else {
-	  DEBUG_INDENT("commodity.prices.find", indent);
+	  DEBUG_INDENT("commodity.prices.find", indent + 1);
 	  DEBUG("commodity.prices.find", "saw no translated price there");
 	  continue;
 	}
@@ -313,7 +313,7 @@ commodity_t::varied_history_t::find_price(const commodity_t&            source,
 
       assert(! commodity || point->price.commodity() == *commodity);
 
-      DEBUG_INDENT("commodity.prices.find", indent);
+      DEBUG_INDENT("commodity.prices.find", indent + 1);
       DEBUG("commodity.prices.find",
 	    "saw a price there: " << point->price << " from " << point->when);
 
@@ -322,12 +322,12 @@ commodity_t::varied_history_t::find_price(const commodity_t&            source,
 	best  = *point;
 	found = true;
 
-	DEBUG_INDENT("commodity.prices.find", indent);
+	DEBUG_INDENT("commodity.prices.find", indent + 1);
 	DEBUG("commodity.prices.find",
 	      "search limit adjusted to " << *limit);
       }
     } else {
-      DEBUG_INDENT("commodity.prices.find", indent);
+      DEBUG_INDENT("commodity.prices.find", indent + 1);
       DEBUG("commodity.prices.find", "saw no price there");
     }
   }
@@ -361,6 +361,95 @@ commodity_t::varied_history_t::history(const optional<commodity_t&>& commodity)
 }
 
 optional<price_point_t>
+commodity_t::find_price(const optional<commodity_t&>& commodity,
+			const optional<datetime_t>&   moment,
+			const optional<datetime_t>&   oldest,
+			const bool                    nested
+#if defined(DEBUG_ON)
+			, const int indent
+#endif
+			) const
+{
+  if (! has_flags(COMMODITY_WALKED) && base->varied_history &&
+      (commodity || ! has_flags(COMMODITY_PRIMARY))) {
+    optional<base_t::time_and_commodity_t> pair;
+#if defined(VERIFY_ON)
+    optional<price_point_t> checkpoint;
+#endif
+
+    if (! nested) {
+      pair = base_t::time_and_commodity_t
+	(base_t::optional_time_pair_t(moment, oldest),
+	 commodity ? &(*commodity) : NULL);
+      DEBUG_INDENT("commodity.prices.find", indent);
+      DEBUG("commodity.prices.find", "looking for memoized args: "
+	    << (moment ? format_datetime(*moment) : "NONE") << ", "
+	    << (oldest ? format_datetime(*oldest) : "NONE") << ", "
+	    << (commodity ? commodity->symbol() : "NONE"));
+
+      base_t::memoized_price_map::iterator i = base->price_map.find(*pair);
+      if (i != base->price_map.end()) {
+	DEBUG_INDENT("commodity.prices.find", indent);
+	DEBUG("commodity.prices.find", "found! returning: "
+	      << ((*i).second ? (*i).second->price : amount_t(0L)));
+#if defined(VERIFY_ON)
+	IF_VERIFY() {
+	  checkpoint = (*i).second;
+	} else
+#endif // defined(VERIFY_ON)
+	return (*i).second;
+      }
+    }
+
+    optional<price_point_t> point;
+
+    const_cast<commodity_t&>(*this).add_flags(COMMODITY_WALKED);
+    try {
+      DEBUG_INDENT("commodity.prices.find", indent);
+      DEBUG("commodity.prices.find", "manually finding price...");
+
+      point = base->varied_history->find_price(*this, commodity,
+					       moment, oldest
+#if defined(DEBUG_ON)
+					       , indent
+#endif
+					       );
+    }
+    catch (...) {
+      const_cast<commodity_t&>(*this).drop_flags(COMMODITY_WALKED);
+      throw;
+    }
+    const_cast<commodity_t&>(*this).drop_flags(COMMODITY_WALKED);
+
+#if defined(VERIFY_ON)
+    if (DO_VERIFY() && pair) {
+      VERIFY(checkpoint == point);
+      return checkpoint;
+    }
+#endif // defined(VERIFY_ON)
+
+    if (! nested && pair) {
+      if (base->price_map.size() > base_t::max_price_map_size) {
+	DEBUG_INDENT("commodity.prices.find", indent);
+	DEBUG("commodity.prices.find",
+	      "price map has grown too large, clearing it by half");
+
+	for (std::size_t i = 0; i < base_t::max_price_map_size >> 1; i++)
+	  base->price_map.erase(base->price_map.begin());
+      }
+
+      DEBUG_INDENT("commodity.prices.find", indent);
+      DEBUG("commodity.prices.find",
+	    "remembered: " << (point ? point->price : amount_t(0L)));
+      base->price_map.insert
+	(base_t::memoized_price_map::value_type(*pair, point));
+    }
+    return point;
+  }
+  return none;
+}    
+
+optional<price_point_t>
 commodity_t::check_for_updated_price(const optional<price_point_t>& point,
 				     const optional<datetime_t>&    moment,
 				     const optional<commodity_t&>&  in_terms_of)
diff --git a/src/commodity.h b/src/commodity.h
index 483d98b0..d8aad10d 100644
--- a/src/commodity.h
+++ b/src/commodity.h
@@ -59,6 +59,10 @@ struct price_point_t
   datetime_t when;
   amount_t   price;
 
+  bool operator==(const price_point_t& other) const {
+    return when == other.when && price == other.price;
+  }
+
 #if defined(HAVE_BOOST_SERIALIZATION)
 private:
   /** Serialization. */
@@ -175,6 +179,16 @@ protected:
     optional<amount_t>	       smaller;
     optional<amount_t>	       larger;
 
+    typedef std::pair<optional<datetime_t>,
+		      optional<datetime_t> > optional_time_pair_t;
+    typedef std::pair<optional_time_pair_t,
+		      commodity_t *> time_and_commodity_t;
+    typedef std::map<time_and_commodity_t,
+		     optional<price_point_t> > memoized_price_map;
+
+    static const std::size_t   max_price_map_size = 16;
+    mutable memoized_price_map price_map;
+
     mutable bool               searched;
 
   public:
@@ -334,37 +348,28 @@ public:
 		 const bool reflexive = true) {
     if (! base->varied_history)
       base->varied_history = varied_history_t();
-
     base->varied_history->add_price(*this, date, price, reflexive);
+    DEBUG("commodity.prices.find", "Price added, clearing price_map");
+    base->price_map.clear();	// a price was added, invalid the map
   }
   bool remove_price(const datetime_t& date, commodity_t& commodity) {
-    if (base->varied_history)
+    if (base->varied_history) {
       base->varied_history->remove_price(date, commodity);
+      DEBUG("commodity.prices.find", "Price removed, clearing price_map");
+      base->price_map.clear();	// a price was added, invalid the map
+    }
     return false;
   }
 
   optional<price_point_t>
   find_price(const optional<commodity_t&>& commodity = none,
 	     const optional<datetime_t>&   moment    = none,
-	     const optional<datetime_t>&   oldest    = none
+	     const optional<datetime_t>&   oldest    = none,
+	     const bool                    nested    = false
 #if defined(DEBUG_ON)
 	     , const int indent = 0
 #endif
-	     ) const {
-    if (! has_flags(COMMODITY_WALKED) && base->varied_history &&
-	(commodity || ! has_flags(COMMODITY_PRIMARY))) {
-      const_cast<commodity_t&>(*this).add_flags(COMMODITY_WALKED);
-      optional<price_point_t> point =
-	base->varied_history->find_price(*this, commodity, moment, oldest
-#if defined(DEBUG_ON)
-					 , indent
-#endif
-					 );
-      const_cast<commodity_t&>(*this).drop_flags(COMMODITY_WALKED);
-      return point;
-    }
-    return none;
-  }    
+	     ) const;    
 
   optional<price_point_t>
   check_for_updated_price(const optional<price_point_t>& point,