Speed up sorting / reduce overhead of sorting

[springmeyer]

About a year ago @KaiBot3000, @aarthykc, and me put carmen under load, profiled with perf, and noticed a single, significant bottleneck in carmen-cache.

The bottleneck was the sorting of Context objects, specifically contextSortByRelev. This makes sense given Context objects are large (copying them is expensive), there may be a lot of them collected in memory, and the sort function is not simple.

After #93 we should see a slight speedup / reduction in the cost of this sorting because Context objects are now moved rather than copied. However I would not be surprised if the top bottleneck in carmen is still this sorting in carmen-cache. So this ticket stands to:

• remind us that this is worthwhile of more investigation
• document what we saw in case optimization work around sorting is picked up again
• reference Ensure Context is noncopyable #93 which includes some ideas for optimizations not yet attempted, including using std::partial_sort

Details:

• The sort function:

  carmen-cache/src/cpp_util.hpp

  Lines 192 to 206 in dfa468a

  	inline bool contextSortByRelev(Context const& a, Context const& b) noexcept {
  	if (b.relev > a.relev)
  	return false;
  	else if (b.relev < a.relev)
  	return true;
  	else if (b.coverList[0].scoredist > a.coverList[0].scoredist)
  	return false;
  	else if (b.coverList[0].scoredist < a.coverList[0].scoredist)
  	return true;
  	else if (b.coverList[0].idx < a.coverList[0].idx)
  	return false;
  	else if (b.coverList[0].idx > a.coverList[0].idx)
  	return true;
  	return (b.coverList[0].id > a.coverList[0].id);
  	}

• The place the sort takes place: (

  carmen-cache/src/coalesce.cpp

  Line 647 in dfa468a

  std::sort(contexts.begin(), contexts.end(), contextSortByRelev);

  ) was identified as a bottleneck during profiling of carmen with perf. This is no surprise, sorting is expensive
• The perf output that previously highlighted sorting as the primary bottleneck:

[springmeyer]

Update on this ticket: after landing #126 (and the concern that the prefiltering in #126 might be problematic faded away - #131) I think the bottleneck described above is likely somewhat mitigated. We saw that contextSortByRelev was a major hotspot when I presume, we were sorting hundreds or thousands of contexts. After the prefiltering in #126 I think we'll be sorting fewer. However this all should be tested. Someone interested in performance could:

• profile with perf in production to see if contextSortByRelev is still a bottleneck (https://jvns.ca/perf-zine.pdf)
• if it is then you could print out (or debug with lldb/gdb) how many context objects we're sorting now - are we still sorting an obscene amount for some queries? If so perhaps we could be even more aggressive than I was in Optimize coalesce #126 by doing something like:

diff --git a/src/coalesce.cpp b/src/coalesce.cpp
index 9f517d3..c6e2ae5 100644
--- a/src/coalesce.cpp
+++ b/src/coalesce.cpp
@@ -312,7 +312,7 @@ inline std::vector<Context> coalesceMulti(std::vector<PhrasematchSubq>& stack, c
                 } else if (covers[0].mask > covers[1].mask) {
                     context_relev -= 0.01;
                 }
-                if (maxrelev - context_relev < .25) {
+                if (maxrelev - context_relev < .15) {
                     contexts.emplace_back(std::move(covers), context_mask, context_relev);
                 }
             } else if (first || covers.size() > 1) {
@@ -333,7 +333,7 @@ inline std::vector<Context> coalesceMulti(std::vector<PhrasematchSubq>& stack, c
     // append coalesced to contexts by moving memory
     for (auto&& matched : coalesced) {
         for (auto&& context : matched.second) {
-            if (maxrelev - context.relev < .25) {
+            if (maxrelev - context.relev < .15) {
                 contexts.emplace_back(std::move(context));
             }
         }