commit e532af3f045057159c7b5a06edc8868ae94a89ec
author Kelvin Zhang <zhangkelvin@google.com> Wed Jan 10 15:29:02 2024 -0800
committer Treehugger Robot <android-test-infra-autosubmit@system.gserviceaccount.com> Tue Jan 16 20:29:55 2024 +0000
tree 295ba0d7432fbf6b266bd5b9fd5301c9edbe8cd5
parent 19acf4fe19302d62709d24baa7c98cdd41054ff1

Improve ExtentRanges::AddExtent() runtime from O(n) to O(log n)

Old algorithm iterates over all extents to detect if there's any
intersection, use binary search instead.

Test: Add ~200K extents from an actual OTA, runtime improves from 13s to
0.4s
Bug: 315215541

Change-Id: Ia99eda3a22e726a9c02bfe2a152dc0a5c16efcfc

payload_generator/extent_ranges.cc

diff --git a/payload_generator/extent_ranges.cc b/payload_generator/extent_ranges.cc
index eecc8b3..32580b9 100644
--- a/payload_generator/extent_ranges.cc
+++ b/payload_generator/extent_ranges.cc
@@ -25,7 +25,6 @@
 
 #include "update_engine/common/utils.h"
 #include "update_engine/payload_consumer/payload_constants.h"
-#include "update_engine/payload_generator/extent_utils.h"
 
 using std::vector;
 
@@ -84,9 +83,8 @@
   ExtentSet::iterator begin_del = extent_set_.end();
   ExtentSet::iterator end_del = extent_set_.end();
   uint64_t del_blocks = 0;
-  for (ExtentSet::iterator it = extent_set_.begin(), e = extent_set_.end();
-       it != e;
-       ++it) {
+  const auto range = GetCandidateRange(extent);
+  for (ExtentSet::iterator it = range.begin(), e = range.end(); it != e; ++it) {
     const bool should_merge = merge_touching_extents_
                                   ? ExtentsOverlapOrTouch(*it, extent)
                                   : ExtentsOverlap(*it, extent);
@@ -291,12 +289,20 @@
 Range<ExtentRanges::ExtentSet::const_iterator> ExtentRanges::GetCandidateRange(
     const Extent& extent) const {
   auto lower_it = extent_set_.lower_bound(extent);
-  if (lower_it != extent_set_.begin()) {
+  while (lower_it != extent_set_.begin() &&
+         (lower_it == extent_set_.end() ||
+          lower_it->start_block() + lower_it->num_blocks() >
+              extent.start_block())) {
     --lower_it;
   }
 
-  const auto upper_it = extent_set_.upper_bound(
+  auto upper_it = extent_set_.upper_bound(
       ExtentForRange(extent.start_block() + extent.num_blocks(), 1));
+  while (upper_it != extent_set_.end() &&
+         upper_it->start_block() <=
+             extent.start_block() + extent.num_blocks()) {
+    ++upper_it;
+  }
   return {lower_it, upper_it};
 }