Use another Vector as a swap to reduce computing complexity
When doing cache memory thinning, Vector's removeAt requires momory backward movement.
Its computing complexity is O((N-M)*M) where N is ogg page size, M=512.
For big ogg files, N >> M, it is about O(N*M), which is too high that cause ANR sometimes.
Using another Vector as a swap avoids the movement and reduces
computing complexity from O(N*M) to O(M).
Bug:267463829
Test: atest CtsMediaExtractorTestCases
Test: atest CtsMediaV2TestCases
Change-Id: I00ba80e4c59cc1cf9fa993444e1f9548fb7dd469
diff --git a/media/module/extractors/ogg/OggExtractor.cpp b/media/module/extractors/ogg/OggExtractor.cpp
index 1c6f516..d0e395a 100644
--- a/media/module/extractors/ogg/OggExtractor.cpp
+++ b/media/module/extractors/ogg/OggExtractor.cpp
@@ -993,16 +993,21 @@
size_t numerator = mTableOfContents.size();
if (numerator > kMaxNumTOCEntries) {
- size_t denom = numerator - kMaxNumTOCEntries;
+ Vector<TOCEntry> maxTOC;
+ maxTOC.setCapacity(kMaxNumTOCEntries);
+ size_t denom = numerator - kMaxNumTOCEntries;
size_t accum = 0;
- for (ssize_t i = mTableOfContents.size(); i > 0; --i) {
+ for (ssize_t i = 0; i < mTableOfContents.size(); i++) {
accum += denom;
if (accum >= numerator) {
- mTableOfContents.removeAt(i);
accum -= numerator;
+ } else {
+ maxTOC.push(mTableOfContents.itemAt(i));
}
}
+
+ mTableOfContents = maxTOC;
}
}