[search] Implemented batching of search results.search-results-batching

7 files changed, 102 insertions, 63 deletions

diff --git a/search/geocoder.cpp b/search/geocoder.cpp
index 74ae905ba4..f808b30609 100644
--- a/search/geocoder.cpp
+++ b/search/geocoder.cpp
@@ -604,14 +604,17 @@ void Geocoder::GoImpl(vector<shared_ptr<MwmInfo>> & infos, bool inViewport)
       m_lastMatchedRegion = nullptr;
       MatchRegions(ctx, REGION_TYPE_COUNTRY);
 
-      if (index < numIntersectingMaps || m_preRanker.IsEmpty())
+      if (index < numIntersectingMaps || m_preRanker.NumSentResults() == 0)
         MatchAroundPivot(ctx);
+
+      if (index + 1 >= numIntersectingMaps)
+        m_preRanker.UpdateResults(false /* lastUpdate */);
     };
 
     // Iterates through all alive mwms and performs geocoding.
     ForEachCountry(infos, processCountry);
 
-    m_preRanker.FinalizeResults();
+    m_preRanker.UpdateResults(true /* lastUpdate */);
   }
   catch (CancelException & e)
   {
diff --git a/search/pre_ranker.cpp b/search/pre_ranker.cpp
index 8eb94a74a2..1f6efbaa04 100644
--- a/search/pre_ranker.cpp
+++ b/search/pre_ranker.cpp
@@ -46,12 +46,15 @@ struct ComparePreResult1
 };
 }  // namespace
 
+// static
+size_t const PreRanker::kBatchSize = 100;
+
 PreRanker::PreRanker(Index const & index, Ranker & ranker, size_t limit)
   : m_index(index), m_ranker(ranker), m_limit(limit), m_pivotFeatures(index)
 {
 }
 
-void PreRanker::FillMissingFieldsInResults()
+void PreRanker::FillMissingFieldsInPreResults()
 {
   MwmSet::MwmId mwmId;
   MwmSet::MwmHandle mwmHandle;
@@ -76,7 +79,7 @@ void PreRanker::FillMissingFieldsInResults()
     info.m_rank = rankTable->Get(id.m_index);
   });
 
-  if (Size() <= Limit())
+  if (Size() <= kBatchSize)
     return;
 
   m_pivotFeatures.SetPosition(m_params.m_accuratePivotCenter, m_params.m_scale);
@@ -99,7 +102,7 @@ void PreRanker::Filter(bool viewportSearch)
 
   sort(m_results.begin(), m_results.end(), &PreResult1::LessDistance);
 
-  if (m_limit != 0 && m_results.size() > m_limit)
+  if (m_results.size() > kBatchSize)
   {
     // Priority is some kind of distance from the viewport or
     // position, therefore if we have a bunch of results with the same
@@ -108,15 +111,15 @@ void PreRanker::Filter(bool viewportSearch)
     // feature id) this code randomly selects tail of the
     // sorted-by-priority list of pre-results.
 
-    double const last = m_results[m_limit - 1].GetDistance();
+    double const last = m_results[kBatchSize - 1].GetDistance();
 
-    auto b = m_results.begin() + m_limit - 1;
+    auto b = m_results.begin() + kBatchSize - 1;
     for (; b != m_results.begin() && b->GetDistance() == last; --b)
       ;
     if (b->GetDistance() != last)
       ++b;
 
-    auto e = m_results.begin() + m_limit;
+    auto e = m_results.begin() + kBatchSize;
     for (; e != m_results.end() && e->GetDistance() == last; ++e)
       ;
 
@@ -132,11 +135,11 @@ void PreRanker::Filter(bool viewportSearch)
     minstd_rand engine;
     shuffle(b, e, engine);
   }
-  filtered.insert(m_results.begin(), m_results.begin() + min(m_results.size(), m_limit));
+  filtered.insert(m_results.begin(), m_results.begin() + min(m_results.size(), kBatchSize));
 
   if (!viewportSearch)
   {
-    size_t n = min(m_results.size(), m_limit);
+    size_t n = min(m_results.size(), kBatchSize);
     nth_element(m_results.begin(), m_results.begin() + n, m_results.end(), &PreResult1::LessRank);
     filtered.insert(m_results.begin(), m_results.begin() + n);
   }
@@ -146,12 +149,14 @@ void PreRanker::Filter(bool viewportSearch)
   copy(filtered.begin(), filtered.end(), back_inserter(m_results));
 }
 
-void PreRanker::FinalizeResults()
+void PreRanker::UpdateResults(bool lastUpdate)
 {
-  FillMissingFieldsInResults();
+  FillMissingFieldsInPreResults();
   Filter(m_viewportSearch);
+  m_numSentResults += m_results.size();
   m_ranker.SetPreResults1(move(m_results));
   m_results.clear();
+  m_ranker.UpdateResults(lastUpdate);
 }
 
 void PreRanker::ClearCaches() { m_pivotFeatures.Clear(); }
diff --git a/search/pre_ranker.hpp b/search/pre_ranker.hpp
index 7c55c9e269..58ff6c39b7 100644
--- a/search/pre_ranker.hpp
+++ b/search/pre_ranker.hpp
@@ -34,9 +34,16 @@ public:
     int m_scale = 0;
   };
 
+  static size_t const kBatchSize;
+
   PreRanker(Index const & index, Ranker & ranker, size_t limit);
 
-  inline void Init(Params const & params) { m_params = params; }
+  inline void Init(Params const & params)
+  {
+    m_numSentResults = 0;
+    m_params = params;
+  }
+
   inline void SetViewportSearch(bool viewportSearch) { m_viewportSearch = viewportSearch; }
   inline void SetAccuratePivotCenter(m2::PointD const & center)
   {
@@ -46,22 +53,24 @@ public:
   template <typename... TArgs>
   void Emplace(TArgs &&... args)
   {
+    if (m_numSentResults >= m_limit)
+      return;
     m_results.emplace_back(forward<TArgs>(args)...);
   }
 
-  // Computes missing fields for all results.
-  void FillMissingFieldsInResults();
+  // Computes missing fields for all pre-results.
+  void FillMissingFieldsInPreResults();
 
   void Filter(bool viewportSearch);
 
-  // This function is used in geocoder to indicate that
+  // Emit a new batch of results up the pipeline (i.e. to ranker).
+  // Use lastUpdate in geocoder to indicate that
   // no more results will be added.
-  void FinalizeResults();
+  void UpdateResults(bool lastUpdate);
 
   inline size_t Size() const { return m_results.size(); }
+  inline size_t NumSentResults() const { return m_numSentResults; }
   inline size_t Limit() const { return m_limit; }
-  inline bool IsEmpty() const { return Size() == 0; }
-  inline void Clear() { m_results.clear(); };
 
   template <typename TFn>
   void ForEach(TFn && fn)
@@ -79,6 +88,9 @@ private:
   Params m_params;
   bool m_viewportSearch = false;
 
+  // Amount of results sent up the pipeline.
+  size_t m_numSentResults = 0;
+
   // Cache of nested rects used to estimate distance from a feature to the pivot.
   NestedRectsCache m_pivotFeatures;
 
diff --git a/search/processor.cpp b/search/processor.cpp
index b3cc1e97f0..0a7c40b146 100644
--- a/search/processor.cpp
+++ b/search/processor.cpp
@@ -165,7 +165,6 @@ void Processor::Init(bool viewportSearch)
 {
   m_tokens.clear();
   m_prefix.clear();
-  m_preRanker.Clear();
   m_preRanker.SetViewportSearch(viewportSearch);
 }
 
@@ -407,7 +406,7 @@ void Processor::Search(SearchParams const & params, m2::RectD const & viewport)
   InitGeocoder(geocoderParams);
 
   InitPreRanker(geocoderParams);
-  InitRanker();
+  InitRanker(geocoderParams);
 
   try
   {
@@ -426,7 +425,6 @@ void Processor::Search(SearchParams const & params, m2::RectD const & viewport)
     if (viewportSearch)
     {
       m_geocoder.GoInViewport();
-      m_ranker.FlushViewportResults(geocoderParams);
     }
     else
     {
@@ -434,9 +432,10 @@ void Processor::Search(SearchParams const & params, m2::RectD const & viewport)
         m_ranker.SuggestStrings(m_ranker.GetResults());
 
       m_geocoder.GoEverywhere();
-      m_ranker.FlushResults(geocoderParams);
     }
 
+    m_ranker.FlushResults();
+
     if (!IsCancelled())
       params.m_onResults(m_ranker.GetResults());
   }
@@ -688,7 +687,7 @@ void Processor::InitPreRanker(Geocoder::Params const & geocoderParams)
   m_preRanker.Init(params);
 }
 
-void Processor::InitRanker()
+void Processor::InitRanker(Geocoder::Params const & geocoderParams)
 {
   size_t const kResultsCount = 30;
   bool const viewportSearch = m_mode == Mode::Viewport;
@@ -713,8 +712,9 @@ void Processor::InitRanker()
   params.m_prefix = m_prefix;
   params.m_categoryLocales = GetCategoryLocales();
   params.m_accuratePivotCenter = GetPivotPoint();
+  params.m_viewportSearch = viewportSearch;
   params.m_onResults = m_onResults;
-  m_ranker.Init(params);
+  m_ranker.Init(params, geocoderParams);
 }
 
 void Processor::ClearCaches()
diff --git a/search/processor.hpp b/search/processor.hpp
index be70b433b9..ddc340556e 100644
--- a/search/processor.hpp
+++ b/search/processor.hpp
@@ -100,7 +100,7 @@ public:
   void InitParams(QueryParams & params);
   void InitGeocoder(Geocoder::Params & params);
   void InitPreRanker(Geocoder::Params const & geocoderParams);
-  void InitRanker();
+  void InitRanker(Geocoder::Params const & geocoderParams);
 
   void ClearCaches();
 
diff --git a/search/ranker.cpp b/search/ranker.cpp
index 1b12aecb38..800d8ad934 100644
--- a/search/ranker.cpp
+++ b/search/ranker.cpp
@@ -8,6 +8,7 @@
 #include "base/logging.hpp"
 
 #include "std/algorithm.hpp"
+#include "std/iterator.hpp"
 #include "std/unique_ptr.hpp"
 
 namespace search
@@ -130,6 +131,9 @@ public:
 };
 }  // namespace
 
+// static
+size_t const Ranker::kBatchSize = 10;
+
 class PreResult2Maker
 {
   Ranker & m_ranker;
@@ -284,10 +288,12 @@ Ranker::Ranker(Index const & index, storage::CountryInfoGetter const & infoGette
 {
 }
 
-void Ranker::Init(Params const & params)
+void Ranker::Init(Params const & params, Geocoder::Params const & geocoderParams)
 {
   m_params = params;
+  m_geocoderParams = geocoderParams;
   m_preResults1.clear();
+  m_leftovers.clear();
   m_results.Clear();
 }
 
@@ -477,56 +483,64 @@ void Ranker::ProcessSuggestions(vector<IndexedValue> & vec, Results & res) const
   }
 }
 
-void Ranker::FlushResults(Geocoder::Params const & params)
+void Ranker::UpdateResults(bool lastUpdate)
 {
-  vector<IndexedValue> values;
+  BailIfCancelled();
+
+  vector<IndexedValue> values = move(m_leftovers);
+  m_leftovers.clear();
   vector<FeatureID> streets;
-  MakePreResult2(params, values, streets);
+  MakePreResult2(m_geocoderParams, values, streets);
   RemoveDuplicatingLinear(values);
   if (values.empty())
     return;
 
-  sort(values.rbegin(), values.rend(), my::LessBy(&IndexedValue::GetRank));
-
-  ProcessSuggestions(values, m_results);
+  if (m_params.m_viewportSearch)
+  {
+    sort(values.begin(), values.end(), my::LessBy(&IndexedValue::GetDistanceToPivot));
+  }
+  else
+  {
+    sort(values.rbegin(), values.rend(), my::LessBy(&IndexedValue::GetRank));
+    ProcessSuggestions(values, m_results);
+  }
 
   // Emit feature results.
   size_t count = m_results.GetCount();
-  for (size_t i = 0; i < values.size() && count < m_params.m_limit; ++i)
+  size_t i;
+  for (i = 0; i < values.size(); ++i)
   {
+    if (!lastUpdate && i >= kBatchSize && !m_params.m_viewportSearch)
+      break;
     BailIfCancelled();
 
-    LOG(LDEBUG, (values[i]));
-
-    auto const & preResult2 = *values[i];
-    if (m_results.AddResult(MakeResult(preResult2)))
-      ++count;
-  }
-}
-
-void Ranker::FlushViewportResults(Geocoder::Params const & geocoderParams)
-{
-  vector<IndexedValue> values;
-  vector<FeatureID> streets;
-  MakePreResult2(geocoderParams, values, streets);
-  RemoveDuplicatingLinear(values);
-  if (values.empty())
-    return;
-
-  sort(values.begin(), values.end(), my::LessBy(&IndexedValue::GetDistanceToPivot));
+    if (m_params.m_viewportSearch)
+    {
+      m_results.AddResultNoChecks(
+          (*(values[i]))
+              .GenerateFinalResult(m_infoGetter, &m_categories, &m_params.m_preferredTypes,
+                                   m_params.m_currentLocaleCode,
+                                   nullptr /* Viewport results don't need calculated address */));
+    }
+    else
+    {
+      if (count >= m_params.m_limit)
+        break;
 
-  for (size_t i = 0; i < values.size(); ++i)
-  {
-    BailIfCancelled();
+      LOG(LDEBUG, (values[i]));
 
-    m_results.AddResultNoChecks(
-        (*(values[i]))
-            .GenerateFinalResult(m_infoGetter, &m_categories, &m_params.m_preferredTypes,
-                                 m_params.m_currentLocaleCode,
-                                 nullptr /* Viewport results don't need calculated address */));
+      auto const & preResult2 = *values[i];
+      if (m_results.AddResult(MakeResult(preResult2)))
+        ++count;
+    }
   }
+  move(values.begin() + i, values.end(), back_inserter(m_leftovers));
+
+  m_preResults1.clear();
+  m_params.m_onResults(m_results);
 }
 
+void Ranker::FlushResults() { UpdateResults(true /* lastUpdate */); }
 void Ranker::ClearCaches()
 {
   m_locality.ClearCache();
diff --git a/search/ranker.hpp b/search/ranker.hpp
index f753c8e984..04fc003ae9 100644
--- a/search/ranker.hpp
+++ b/search/ranker.hpp
@@ -49,6 +49,7 @@ public:
     string m_pivotRegion;
     set<uint32_t> m_preferredTypes;
     bool m_suggestsEnabled = false;
+    bool m_viewportSearch = false;
 
     string m_query;
     buffer_vector<strings::UniString, 32> m_tokens;
@@ -64,11 +65,13 @@ public:
     TOnResults m_onResults;
   };
 
+  static size_t const kBatchSize;
+
   Ranker(Index const & index, storage::CountryInfoGetter const & infoGetter,
          CategoriesHolder const & categories, vector<Suggest> const & suggests,
          my::Cancellable const & cancellable);
 
-  void Init(Params const & params);
+  void Init(Params const & params, Geocoder::Params const & geocoderParams);
 
   inline void SetAccuratePivotCenter(m2::PointD const & center)
   {
@@ -91,8 +94,8 @@ public:
   void ProcessSuggestions(vector<IndexedValue> & vec, Results & res) const;
 
   Results & GetResults() { return m_results; }
-  void FlushResults(Geocoder::Params const & geocoderParams);
-  void FlushViewportResults(Geocoder::Params const & geocoderParams);
+  void UpdateResults(bool lastUpdate);
+  void FlushResults();
 
   void SetPreResults1(vector<PreResult1> && preResults1) { m_preResults1 = move(preResults1); }
   void ClearCaches();
@@ -126,6 +129,7 @@ private:
   friend class PreResult2Maker;
 
   Params m_params;
+  Geocoder::Params m_geocoderParams;
   ReverseGeocoder const m_reverseGeocoder;
   my::Cancellable const & m_cancellable;
   KeywordLangMatcher m_keywordsScorer;
@@ -138,6 +142,7 @@ private:
   vector<Suggest> const & m_suggests;
 
   vector<PreResult1> m_preResults1;
+  vector<IndexedValue> m_leftovers;
   Results m_results;
 };
 }  // namespace search