equivalence_map.cc 20 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549
  1. // Copyright 2017 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "components/zucchini/equivalence_map.h"
  5. #include <algorithm>
  6. #include <utility>
  7. #include "base/containers/cxx20_erase.h"
  8. #include "base/logging.h"
  9. #include "base/numerics/safe_conversions.h"
  10. #include "components/zucchini/encoded_view.h"
  11. #include "components/zucchini/patch_reader.h"
  12. #include "components/zucchini/suffix_array.h"
  13. namespace zucchini {
  14. namespace {
  15. // TODO(haungs): Tune these numbers to improve pathological case results.
  16. // In pathological cases Zucchini can exhibit O(n^2) behavior if the seed
  17. // selection process runs to completion. To prevent this we impose a quota for
  18. // the total length of equivalences the seed selection process can perform
  19. // trials on. For regular use cases it is unlikely this quota will be exceeded,
  20. // and if it is the effects on patch size are expected to be small.
  21. constexpr uint64_t kSeedSelectionTotalVisitLengthQuota = 1 << 18; // 256 KiB
  22. // The aforementioned quota alone is insufficient, as exploring backwards will
  23. // still be very successful resulting in O(n) behavior in the case of a limited
  24. // seed selection trials. This results in O(n^2) behavior returning. To mitigate
  25. // this we also impose a cap on the ExtendEquivalenceBackward() exploration.
  26. constexpr offset_t kBackwardsExtendLimit = 1 << 16; // 64 KiB
  27. } // namespace
  28. /******** Utility Functions ********/
  29. double GetTokenSimilarity(
  30. const ImageIndex& old_image_index,
  31. const ImageIndex& new_image_index,
  32. const std::vector<TargetsAffinity>& targets_affinities,
  33. offset_t src,
  34. offset_t dst) {
  35. DCHECK(old_image_index.IsToken(src));
  36. DCHECK(new_image_index.IsToken(dst));
  37. TypeTag old_type = old_image_index.LookupType(src);
  38. TypeTag new_type = new_image_index.LookupType(dst);
  39. if (old_type != new_type)
  40. return kMismatchFatal;
  41. // Raw comparison.
  42. if (!old_image_index.IsReference(src) && !new_image_index.IsReference(dst)) {
  43. return old_image_index.GetRawValue(src) == new_image_index.GetRawValue(dst)
  44. ? 1.0
  45. : -1.5;
  46. }
  47. const ReferenceSet& old_ref_set = old_image_index.refs(old_type);
  48. const ReferenceSet& new_ref_set = new_image_index.refs(new_type);
  49. Reference old_reference = old_ref_set.at(src);
  50. Reference new_reference = new_ref_set.at(dst);
  51. PoolTag pool_tag = old_ref_set.pool_tag();
  52. double affinity = targets_affinities[pool_tag.value()].AffinityBetween(
  53. old_ref_set.target_pool().KeyForOffset(old_reference.target),
  54. new_ref_set.target_pool().KeyForOffset(new_reference.target));
  55. // Both targets are not associated, which implies a weak match.
  56. if (affinity == 0.0)
  57. return 0.5 * old_ref_set.width();
  58. // At least one target is associated, so values are compared.
  59. return affinity > 0.0 ? old_ref_set.width() : -2.0;
  60. }
  61. double GetEquivalenceSimilarity(
  62. const ImageIndex& old_image_index,
  63. const ImageIndex& new_image_index,
  64. const std::vector<TargetsAffinity>& targets_affinities,
  65. const Equivalence& equivalence) {
  66. double similarity = 0.0;
  67. for (offset_t k = 0; k < equivalence.length; ++k) {
  68. // Non-tokens are joined with the nearest previous token: skip until we
  69. // cover the unit.
  70. if (!new_image_index.IsToken(equivalence.dst_offset + k))
  71. continue;
  72. similarity += GetTokenSimilarity(
  73. old_image_index, new_image_index, targets_affinities,
  74. equivalence.src_offset + k, equivalence.dst_offset + k);
  75. if (similarity == kMismatchFatal)
  76. return kMismatchFatal;
  77. }
  78. return similarity;
  79. }
  80. EquivalenceCandidate ExtendEquivalenceForward(
  81. const ImageIndex& old_image_index,
  82. const ImageIndex& new_image_index,
  83. const std::vector<TargetsAffinity>& targets_affinities,
  84. const EquivalenceCandidate& candidate,
  85. double min_similarity) {
  86. Equivalence equivalence = candidate.eq;
  87. offset_t best_k = equivalence.length;
  88. double current_similarity = candidate.similarity;
  89. double best_similarity = current_similarity;
  90. double current_penalty = min_similarity;
  91. for (offset_t k = best_k;
  92. equivalence.src_offset + k < old_image_index.size() &&
  93. equivalence.dst_offset + k < new_image_index.size();
  94. ++k) {
  95. // Mismatch in type, |candidate| cannot be extended further.
  96. if (old_image_index.LookupType(equivalence.src_offset + k) !=
  97. new_image_index.LookupType(equivalence.dst_offset + k)) {
  98. break;
  99. }
  100. if (!new_image_index.IsToken(equivalence.dst_offset + k)) {
  101. // Non-tokens are joined with the nearest previous token: skip until we
  102. // cover the unit, and extend |best_k| if applicable.
  103. if (best_k == k)
  104. best_k = k + 1;
  105. continue;
  106. }
  107. double similarity = GetTokenSimilarity(
  108. old_image_index, new_image_index, targets_affinities,
  109. equivalence.src_offset + k, equivalence.dst_offset + k);
  110. current_similarity += similarity;
  111. current_penalty = std::max(0.0, current_penalty) - similarity;
  112. if (current_similarity < 0.0 || current_penalty >= min_similarity)
  113. break;
  114. if (current_similarity >= best_similarity) {
  115. best_similarity = current_similarity;
  116. best_k = k + 1;
  117. }
  118. }
  119. equivalence.length = best_k;
  120. return {equivalence, best_similarity};
  121. }
  122. EquivalenceCandidate ExtendEquivalenceBackward(
  123. const ImageIndex& old_image_index,
  124. const ImageIndex& new_image_index,
  125. const std::vector<TargetsAffinity>& targets_affinities,
  126. const EquivalenceCandidate& candidate,
  127. double min_similarity) {
  128. Equivalence equivalence = candidate.eq;
  129. offset_t best_k = 0;
  130. double current_similarity = candidate.similarity;
  131. double best_similarity = current_similarity;
  132. double current_penalty = 0.0;
  133. offset_t k_min = std::min(
  134. {equivalence.dst_offset, equivalence.src_offset, kBackwardsExtendLimit});
  135. for (offset_t k = 1; k <= k_min; ++k) {
  136. // Mismatch in type, |candidate| cannot be extended further.
  137. if (old_image_index.LookupType(equivalence.src_offset - k) !=
  138. new_image_index.LookupType(equivalence.dst_offset - k)) {
  139. break;
  140. }
  141. // Non-tokens are joined with the nearest previous token: skip until we
  142. // reach the next token.
  143. if (!new_image_index.IsToken(equivalence.dst_offset - k))
  144. continue;
  145. DCHECK_EQ(old_image_index.LookupType(equivalence.src_offset - k),
  146. new_image_index.LookupType(equivalence.dst_offset -
  147. k)); // Sanity check.
  148. double similarity = GetTokenSimilarity(
  149. old_image_index, new_image_index, targets_affinities,
  150. equivalence.src_offset - k, equivalence.dst_offset - k);
  151. current_similarity += similarity;
  152. current_penalty = std::max(0.0, current_penalty) - similarity;
  153. if (current_similarity < 0.0 || current_penalty >= min_similarity)
  154. break;
  155. if (current_similarity >= best_similarity) {
  156. best_similarity = current_similarity;
  157. best_k = k;
  158. }
  159. }
  160. equivalence.dst_offset -= best_k;
  161. equivalence.src_offset -= best_k;
  162. equivalence.length += best_k;
  163. return {equivalence, best_similarity};
  164. }
  165. EquivalenceCandidate VisitEquivalenceSeed(
  166. const ImageIndex& old_image_index,
  167. const ImageIndex& new_image_index,
  168. const std::vector<TargetsAffinity>& targets_affinities,
  169. offset_t src,
  170. offset_t dst,
  171. double min_similarity) {
  172. EquivalenceCandidate candidate{{src, dst, 0}, 0.0}; // Empty.
  173. if (!old_image_index.IsToken(src))
  174. return candidate;
  175. candidate =
  176. ExtendEquivalenceForward(old_image_index, new_image_index,
  177. targets_affinities, candidate, min_similarity);
  178. if (candidate.similarity < min_similarity)
  179. return candidate; // Not worth exploring any more.
  180. return ExtendEquivalenceBackward(old_image_index, new_image_index,
  181. targets_affinities, candidate,
  182. min_similarity);
  183. }
  184. /******** OffsetMapper ********/
  185. OffsetMapper::OffsetMapper(std::deque<Equivalence>&& equivalences,
  186. offset_t old_image_size,
  187. offset_t new_image_size)
  188. : equivalences_(std::move(equivalences)),
  189. old_image_size_(old_image_size),
  190. new_image_size_(new_image_size) {
  191. DCHECK_GT(new_image_size_, 0U);
  192. DCHECK(std::is_sorted(equivalences_.begin(), equivalences_.end(),
  193. [](const Equivalence& a, const Equivalence& b) {
  194. return a.src_offset < b.src_offset;
  195. }));
  196. // This is for testing. Assume pruned.
  197. }
  198. OffsetMapper::OffsetMapper(EquivalenceSource&& equivalence_source,
  199. offset_t old_image_size,
  200. offset_t new_image_size)
  201. : old_image_size_(old_image_size), new_image_size_(new_image_size) {
  202. DCHECK_GT(new_image_size_, 0U);
  203. for (auto e = equivalence_source.GetNext(); e.has_value();
  204. e = equivalence_source.GetNext()) {
  205. equivalences_.push_back(*e);
  206. }
  207. PruneEquivalencesAndSortBySource(&equivalences_);
  208. }
  209. OffsetMapper::OffsetMapper(const EquivalenceMap& equivalence_map,
  210. offset_t old_image_size,
  211. offset_t new_image_size)
  212. : equivalences_(equivalence_map.size()),
  213. old_image_size_(old_image_size),
  214. new_image_size_(new_image_size) {
  215. DCHECK_GT(new_image_size_, 0U);
  216. std::transform(equivalence_map.begin(), equivalence_map.end(),
  217. equivalences_.begin(),
  218. [](const EquivalenceCandidate& c) { return c.eq; });
  219. PruneEquivalencesAndSortBySource(&equivalences_);
  220. }
  221. OffsetMapper::~OffsetMapper() = default;
  222. // Safely evaluates |offset - unit.src_offset + unit.dst_offset| with signed
  223. // arithmetic, then clips the result to |[0, new_image_size_)|.
  224. offset_t OffsetMapper::NaiveExtendedForwardProject(const Equivalence& unit,
  225. offset_t offset) const {
  226. int64_t old_offset64 = offset;
  227. int64_t src_offset64 = unit.src_offset;
  228. int64_t dst_offset64 = unit.dst_offset;
  229. uint64_t new_offset64 = std::min<uint64_t>(
  230. std::max<int64_t>(0LL, old_offset64 - src_offset64 + dst_offset64),
  231. new_image_size_ - 1);
  232. return base::checked_cast<offset_t>(new_offset64);
  233. }
  234. offset_t OffsetMapper::ExtendedForwardProject(offset_t offset) const {
  235. DCHECK(!equivalences_.empty());
  236. if (offset < old_image_size_) {
  237. // Finds the equivalence unit whose "old" block is nearest to |offset|,
  238. // favoring the block with lower offset in case of a tie.
  239. auto pos = std::upper_bound(
  240. equivalences_.begin(), equivalences_.end(), offset,
  241. [](offset_t a, const Equivalence& b) { return a < b.src_offset; });
  242. // For tiebreaking: |offset - pos[-1].src_end()| is actually 1 less than
  243. // |offset|'s distance to "old" block of |pos[-1]|. Therefore "<" is used.
  244. if (pos != equivalences_.begin() &&
  245. (pos == equivalences_.end() || offset < pos[-1].src_end() ||
  246. offset - pos[-1].src_end() < pos->src_offset - offset)) {
  247. --pos;
  248. }
  249. return NaiveExtendedForwardProject(*pos, offset);
  250. }
  251. // Fake offsets.
  252. offset_t delta = offset - old_image_size_;
  253. return delta < kOffsetBound - new_image_size_ ? new_image_size_ + delta
  254. : kOffsetBound - 1;
  255. }
  256. void OffsetMapper::ForwardProjectAll(std::deque<offset_t>* offsets) const {
  257. DCHECK(std::is_sorted(offsets->begin(), offsets->end()));
  258. auto current = equivalences_.begin();
  259. for (auto& src : *offsets) {
  260. while (current != end() && current->src_end() <= src) {
  261. ++current;
  262. }
  263. if (current != end() && current->src_offset <= src) {
  264. src = src - current->src_offset + current->dst_offset;
  265. } else {
  266. src = kInvalidOffset;
  267. }
  268. }
  269. base::Erase(*offsets, kInvalidOffset);
  270. offsets->shrink_to_fit();
  271. }
  272. void OffsetMapper::PruneEquivalencesAndSortBySource(
  273. std::deque<Equivalence>* equivalences) {
  274. std::sort(equivalences->begin(), equivalences->end(),
  275. [](const Equivalence& a, const Equivalence& b) {
  276. return a.src_offset < b.src_offset;
  277. });
  278. for (auto current = equivalences->begin(); current != equivalences->end();
  279. ++current) {
  280. // A "reaper" is an equivalence after |current| that overlaps with it, but
  281. // is longer, and so truncates |current|. For example:
  282. // ****** <= |current|
  283. // **
  284. // ****
  285. // ****
  286. // ********** <= |next| as reaper.
  287. // If a reaper is found (as |next|), every equivalence strictly between
  288. // |current| and |next| would be truncated to 0 and discarded. Handling this
  289. // case is important to avoid O(n^2) behavior.
  290. bool next_is_reaper = false;
  291. // Look ahead to resolve overlaps, until a better candidate is found.
  292. auto next = current + 1;
  293. for (; next != equivalences->end(); ++next) {
  294. DCHECK_GE(next->src_offset, current->src_offset);
  295. if (next->src_offset >= current->src_end())
  296. break; // No more overlap.
  297. if (current->length < next->length) {
  298. // |next| is better: So it is a reaper that shrinks |current|.
  299. offset_t delta = current->src_end() - next->src_offset;
  300. current->length -= delta;
  301. next_is_reaper = true;
  302. break;
  303. }
  304. }
  305. if (next_is_reaper) {
  306. // Discard all equivalences strictly between |cur| and |next|.
  307. for (auto reduced = current + 1; reduced != next; ++reduced)
  308. reduced->length = 0;
  309. current = next - 1;
  310. } else {
  311. // Shrink all equivalences that overlap with |current|. These are all
  312. // worse than |current| since no reaper is found.
  313. for (auto reduced = current + 1; reduced != next; ++reduced) {
  314. offset_t delta = current->src_end() - reduced->src_offset;
  315. reduced->length -= std::min(reduced->length, delta);
  316. reduced->src_offset += delta;
  317. reduced->dst_offset += delta;
  318. DCHECK_EQ(reduced->src_offset, current->src_end());
  319. }
  320. }
  321. }
  322. // Discard all equivalences with length == 0.
  323. base::EraseIf(*equivalences, [](const Equivalence& equivalence) {
  324. return equivalence.length == 0;
  325. });
  326. equivalences->shrink_to_fit();
  327. }
  328. /******** EquivalenceMap ********/
  329. EquivalenceMap::EquivalenceMap() = default;
  330. EquivalenceMap::EquivalenceMap(std::vector<EquivalenceCandidate>&& equivalences)
  331. : candidates_(std::move(equivalences)) {
  332. SortByDestination();
  333. }
  334. EquivalenceMap::EquivalenceMap(EquivalenceMap&&) = default;
  335. EquivalenceMap::~EquivalenceMap() = default;
  336. void EquivalenceMap::Build(
  337. const std::vector<offset_t>& old_sa,
  338. const EncodedView& old_view,
  339. const EncodedView& new_view,
  340. const std::vector<TargetsAffinity>& targets_affinities,
  341. double min_similarity) {
  342. DCHECK_EQ(old_sa.size(), old_view.size());
  343. CreateCandidates(old_sa, old_view, new_view, targets_affinities,
  344. min_similarity);
  345. SortByDestination();
  346. Prune(old_view, new_view, targets_affinities, min_similarity);
  347. offset_t coverage = 0;
  348. offset_t current_offset = 0;
  349. for (auto candidate : candidates_) {
  350. DCHECK_GE(candidate.eq.dst_offset, current_offset);
  351. coverage += candidate.eq.length;
  352. current_offset = candidate.eq.dst_end();
  353. }
  354. LOG(INFO) << "Equivalence Count: " << size();
  355. LOG(INFO) << "Coverage / Extra / Total: " << coverage << " / "
  356. << new_view.size() - coverage << " / " << new_view.size();
  357. }
  358. void EquivalenceMap::CreateCandidates(
  359. const std::vector<offset_t>& old_sa,
  360. const EncodedView& old_view,
  361. const EncodedView& new_view,
  362. const std::vector<TargetsAffinity>& targets_affinities,
  363. double min_similarity) {
  364. candidates_.clear();
  365. // This is an heuristic to find 'good' equivalences on encoded views.
  366. // Equivalences are found in ascending order of |new_image|.
  367. offset_t dst_offset = 0;
  368. while (dst_offset < new_view.size()) {
  369. if (!new_view.IsToken(dst_offset)) {
  370. ++dst_offset;
  371. continue;
  372. }
  373. auto match =
  374. SuffixLowerBound(old_sa, old_view.begin(),
  375. new_view.begin() + dst_offset, new_view.end());
  376. offset_t next_dst_offset = dst_offset + 1;
  377. // TODO(huangs): Clean up.
  378. double best_similarity = min_similarity;
  379. uint64_t total_visit_length = 0;
  380. EquivalenceCandidate best_candidate = {{0, 0, 0}, 0.0};
  381. for (auto it = match; it != old_sa.end(); ++it) {
  382. EquivalenceCandidate candidate = VisitEquivalenceSeed(
  383. old_view.image_index(), new_view.image_index(), targets_affinities,
  384. static_cast<offset_t>(*it), dst_offset, min_similarity);
  385. if (candidate.similarity > best_similarity) {
  386. best_candidate = candidate;
  387. best_similarity = candidate.similarity;
  388. next_dst_offset = candidate.eq.dst_end();
  389. total_visit_length += candidate.eq.length;
  390. if (total_visit_length > kSeedSelectionTotalVisitLengthQuota) {
  391. break;
  392. }
  393. } else {
  394. break;
  395. }
  396. }
  397. total_visit_length = 0;
  398. for (auto it = match; it != old_sa.begin(); --it) {
  399. EquivalenceCandidate candidate = VisitEquivalenceSeed(
  400. old_view.image_index(), new_view.image_index(), targets_affinities,
  401. static_cast<offset_t>(it[-1]), dst_offset, min_similarity);
  402. if (candidate.similarity > best_similarity) {
  403. best_candidate = candidate;
  404. best_similarity = candidate.similarity;
  405. next_dst_offset = candidate.eq.dst_end();
  406. total_visit_length += candidate.eq.length;
  407. if (total_visit_length > kSeedSelectionTotalVisitLengthQuota) {
  408. break;
  409. }
  410. } else {
  411. break;
  412. }
  413. }
  414. if (best_candidate.similarity >= min_similarity) {
  415. candidates_.push_back(best_candidate);
  416. }
  417. dst_offset = next_dst_offset;
  418. }
  419. }
  420. void EquivalenceMap::SortByDestination() {
  421. std::sort(candidates_.begin(), candidates_.end(),
  422. [](const EquivalenceCandidate& a, const EquivalenceCandidate& b) {
  423. return a.eq.dst_offset < b.eq.dst_offset;
  424. });
  425. }
  426. void EquivalenceMap::Prune(
  427. const EncodedView& old_view,
  428. const EncodedView& new_view,
  429. const std::vector<TargetsAffinity>& target_affinities,
  430. double min_similarity) {
  431. // TODO(etiennep): unify with
  432. // OffsetMapper::PruneEquivalencesAndSortBySource().
  433. for (auto current = candidates_.begin(); current != candidates_.end();
  434. ++current) {
  435. if (current->similarity < min_similarity)
  436. continue; // This candidate will be discarded anyways.
  437. bool next_is_reaper = false;
  438. // Look ahead to resolve overlaps, until a better candidate is found.
  439. auto next = current + 1;
  440. for (; next != candidates_.end(); ++next) {
  441. DCHECK_GE(next->eq.dst_offset, current->eq.dst_offset);
  442. if (next->eq.dst_offset >= current->eq.dst_offset + current->eq.length)
  443. break; // No more overlap.
  444. if (current->similarity < next->similarity) {
  445. // |next| is better: So it is a reaper that shrinks |current|.
  446. offset_t delta = current->eq.dst_end() - next->eq.dst_offset;
  447. current->eq.length -= delta;
  448. current->similarity = GetEquivalenceSimilarity(
  449. old_view.image_index(), new_view.image_index(), target_affinities,
  450. current->eq);
  451. next_is_reaper = true;
  452. break;
  453. }
  454. }
  455. if (next_is_reaper) {
  456. // Discard all equivalences strictly between |cur| and |next|.
  457. for (auto reduced = current + 1; reduced != next; ++reduced) {
  458. reduced->eq.length = 0;
  459. reduced->similarity = 0;
  460. }
  461. current = next - 1;
  462. } else {
  463. // Shrinks all overlapping candidates following and worse than |current|.
  464. for (auto reduced = current + 1; reduced != next; ++reduced) {
  465. offset_t delta = current->eq.dst_end() - reduced->eq.dst_offset;
  466. reduced->eq.length -= std::min(reduced->eq.length, delta);
  467. reduced->eq.src_offset += delta;
  468. reduced->eq.dst_offset += delta;
  469. reduced->similarity = GetEquivalenceSimilarity(
  470. old_view.image_index(), new_view.image_index(), target_affinities,
  471. reduced->eq);
  472. DCHECK_EQ(reduced->eq.dst_offset, current->eq.dst_end());
  473. }
  474. }
  475. }
  476. // Discard all candidates with similarity smaller than |min_similarity|.
  477. base::EraseIf(candidates_,
  478. [min_similarity](const EquivalenceCandidate& candidate) {
  479. return candidate.similarity < min_similarity;
  480. });
  481. }
  482. } // namespace zucchini