libui: rewrite Region with FatVector
Region is heavily used by SurfaceFlinger and the Android animation
framework, but it uses the libutils Vector internally. libutils Vector
allocates four elements via malloc() regardless of the contents of the
Vector. However, Region is overwhelmingly a single-element Vector
(occasionally two), which can be allocated on the stack easily enough.
FatVector is an existing wrapper around std::vector that allows for a
stack-allocated vector when the contents are small enough. Using
FatVector in Region instead of libutils Vector avoids all of the
malloc/free overhead, which improves SurfaceFlinger per-frame runtime
by ~4%.
This CL moves FatVector from libhwui to make it usable by Region.
Test: boots, works, passes tests
Bug: 149096186
Change-Id: I265c6c831bc82f31afe0d100aec2f98344f2390b
diff --git a/libs/ui/Region.cpp b/libs/ui/Region.cpp
index bf487c4..cd2a448 100644
--- a/libs/ui/Region.cpp
+++ b/libs/ui/Region.cpp
@@ -67,19 +67,20 @@
// ----------------------------------------------------------------------------
Region::Region() {
- mStorage.add(Rect(0,0));
+ mStorage.push_back(Rect(0, 0));
}
Region::Region(const Region& rhs)
- : mStorage(rhs.mStorage)
{
+ mStorage.clear();
+ mStorage.insert(mStorage.begin(), rhs.mStorage.begin(), rhs.mStorage.end());
#if defined(VALIDATE_REGIONS)
validate(rhs, "rhs copy-ctor");
#endif
}
Region::Region(const Rect& rhs) {
- mStorage.add(rhs);
+ mStorage.push_back(rhs);
}
Region::~Region()
@@ -100,8 +101,8 @@
* final, correctly ordered region buffer. Each rectangle will be compared with the span directly
* above it, and subdivided to resolve any remaining T-junctions.
*/
-static void reverseRectsResolvingJunctions(const Rect* begin, const Rect* end,
- Vector<Rect>& dst, int spanDirection) {
+static void reverseRectsResolvingJunctions(const Rect* begin, const Rect* end, FatVector<Rect>& dst,
+ int spanDirection) {
dst.clear();
const Rect* current = end - 1;
@@ -109,7 +110,7 @@
// add first span immediately
do {
- dst.add(*current);
+ dst.push_back(*current);
current--;
} while (current->top == lastTop && current >= begin);
@@ -147,12 +148,12 @@
if (prev.right <= left) break;
if (prev.right > left && prev.right < right) {
- dst.add(Rect(prev.right, top, right, bottom));
+ dst.push_back(Rect(prev.right, top, right, bottom));
right = prev.right;
}
if (prev.left > left && prev.left < right) {
- dst.add(Rect(prev.left, top, right, bottom));
+ dst.push_back(Rect(prev.left, top, right, bottom));
right = prev.left;
}
@@ -166,12 +167,12 @@
if (prev.left >= right) break;
if (prev.left > left && prev.left < right) {
- dst.add(Rect(left, top, prev.left, bottom));
+ dst.push_back(Rect(left, top, prev.left, bottom));
left = prev.left;
}
if (prev.right > left && prev.right < right) {
- dst.add(Rect(left, top, prev.right, bottom));
+ dst.push_back(Rect(left, top, prev.right, bottom));
left = prev.right;
}
// if an entry in the previous span is too far left, nothing further right in the
@@ -183,7 +184,7 @@
}
if (left < right) {
- dst.add(Rect(left, top, right, bottom));
+ dst.push_back(Rect(left, top, right, bottom));
}
current--;
@@ -201,13 +202,14 @@
if (r.isEmpty()) return r;
if (r.isRect()) return r;
- Vector<Rect> reversed;
+ FatVector<Rect> reversed;
reverseRectsResolvingJunctions(r.begin(), r.end(), reversed, direction_RTL);
Region outputRegion;
- reverseRectsResolvingJunctions(reversed.begin(), reversed.end(),
- outputRegion.mStorage, direction_LTR);
- outputRegion.mStorage.add(r.getBounds()); // to make region valid, mStorage must end with bounds
+ reverseRectsResolvingJunctions(reversed.data(), reversed.data() + reversed.size(),
+ outputRegion.mStorage, direction_LTR);
+ outputRegion.mStorage.push_back(
+ r.getBounds()); // to make region valid, mStorage must end with bounds
#if defined(VALIDATE_REGIONS)
validate(outputRegion, "T-Junction free region");
@@ -222,7 +224,8 @@
validate(*this, "this->operator=");
validate(rhs, "rhs.operator=");
#endif
- mStorage = rhs.mStorage;
+ mStorage.clear();
+ mStorage.insert(mStorage.begin(), rhs.mStorage.begin(), rhs.mStorage.end());
return *this;
}
@@ -231,7 +234,7 @@
if (mStorage.size() >= 2) {
const Rect bounds(getBounds());
mStorage.clear();
- mStorage.add(bounds);
+ mStorage.push_back(bounds);
}
return *this;
}
@@ -255,25 +258,25 @@
void Region::clear()
{
mStorage.clear();
- mStorage.add(Rect(0,0));
+ mStorage.push_back(Rect(0, 0));
}
void Region::set(const Rect& r)
{
mStorage.clear();
- mStorage.add(r);
+ mStorage.push_back(r);
}
void Region::set(int32_t w, int32_t h)
{
mStorage.clear();
- mStorage.add(Rect(w, h));
+ mStorage.push_back(Rect(w, h));
}
void Region::set(uint32_t w, uint32_t h)
{
mStorage.clear();
- mStorage.add(Rect(w, h));
+ mStorage.push_back(Rect(w, h));
}
bool Region::isTriviallyEqual(const Region& region) const {
@@ -299,8 +302,7 @@
void Region::addRectUnchecked(int l, int t, int r, int b)
{
Rect rect(l,t,r,b);
- size_t where = mStorage.size() - 1;
- mStorage.insertAt(rect, where, 1);
+ mStorage.insert(mStorage.end() - 1, rect);
}
// ----------------------------------------------------------------------------
@@ -350,7 +352,7 @@
Region& Region::scaleSelf(float sx, float sy) {
size_t count = mStorage.size();
- Rect* rects = mStorage.editArray();
+ Rect* rects = mStorage.data();
while (count) {
rects->left = static_cast<int32_t>(static_cast<float>(rects->left) * sx + 0.5f);
rects->right = static_cast<int32_t>(static_cast<float>(rects->right) * sx + 0.5f);
@@ -455,10 +457,10 @@
class Region::rasterizer : public region_operator<Rect>::region_rasterizer
{
Rect bounds;
- Vector<Rect>& storage;
+ FatVector<Rect>& storage;
Rect* head;
Rect* tail;
- Vector<Rect> span;
+ FatVector<Rect> span;
Rect* cur;
public:
explicit rasterizer(Region& reg)
@@ -485,8 +487,8 @@
flushSpan();
}
if (storage.size()) {
- bounds.top = storage.itemAt(0).top;
- bounds.bottom = storage.top().bottom;
+ bounds.top = storage.front().top;
+ bounds.bottom = storage.back().bottom;
if (storage.size() == 1) {
storage.clear();
}
@@ -494,7 +496,7 @@
bounds.left = 0;
bounds.right = 0;
}
- storage.add(bounds);
+ storage.push_back(bounds);
}
void Region::rasterizer::operator()(const Rect& rect)
@@ -509,15 +511,15 @@
return;
}
}
- span.add(rect);
- cur = span.editArray() + (span.size() - 1);
+ span.push_back(rect);
+ cur = span.data() + (span.size() - 1);
}
void Region::rasterizer::flushSpan()
{
bool merge = false;
if (tail-head == ssize_t(span.size())) {
- Rect const* p = span.editArray();
+ Rect const* p = span.data();
Rect const* q = head;
if (p->top == q->bottom) {
merge = true;
@@ -532,17 +534,17 @@
}
}
if (merge) {
- const int bottom = span[0].bottom;
+ const int bottom = span.front().bottom;
Rect* r = head;
while (r != tail) {
r->bottom = bottom;
r++;
}
} else {
- bounds.left = min(span.itemAt(0).left, bounds.left);
- bounds.right = max(span.top().right, bounds.right);
- storage.appendVector(span);
- tail = storage.editArray() + storage.size();
+ bounds.left = min(span.front().left, bounds.left);
+ bounds.right = max(span.back().right, bounds.right);
+ storage.insert(storage.end(), span.begin(), span.end());
+ tail = storage.data() + storage.size();
head = tail - span.size();
}
span.clear();
@@ -550,7 +552,7 @@
bool Region::validate(const Region& reg, const char* name, bool silent)
{
- if (reg.mStorage.isEmpty()) {
+ if (reg.mStorage.empty()) {
ALOGE_IF(!silent, "%s: mStorage is empty, which is never valid", name);
// return immediately as the code below assumes mStorage is non-empty
return false;
@@ -689,9 +691,8 @@
}
sk_dst.op(sk_lhs, sk_rhs, sk_op);
- if (sk_dst.isEmpty() && dst.isEmpty())
- return;
-
+ if (sk_dst.empty() && dst.empty()) return;
+
bool same = true;
Region::const_iterator head = dst.begin();
Region::const_iterator const tail = dst.end();
@@ -786,7 +787,7 @@
validate(reg, "translate (before)");
#endif
size_t count = reg.mStorage.size();
- Rect* rects = reg.mStorage.editArray();
+ Rect* rects = reg.mStorage.data();
while (count) {
rects->offsetBy(dx, dy);
rects++;
@@ -866,24 +867,25 @@
ALOGE("Region::unflatten() failed, invalid region");
return BAD_VALUE;
}
- mStorage = result.mStorage;
+ mStorage.clear();
+ mStorage.insert(mStorage.begin(), result.mStorage.begin(), result.mStorage.end());
return NO_ERROR;
}
// ----------------------------------------------------------------------------
Region::const_iterator Region::begin() const {
- return mStorage.array();
+ return mStorage.data();
}
Region::const_iterator Region::end() const {
// Workaround for b/77643177
// mStorage should never be empty, but somehow it is and it's causing
// an abort in ubsan
- if (mStorage.isEmpty()) return mStorage.array();
+ if (mStorage.empty()) return mStorage.data();
size_t numRects = isRect() ? 1 : mStorage.size() - 1;
- return mStorage.array() + numRects;
+ return mStorage.data() + numRects;
}
Rect const* Region::getArray(size_t* count) const {
diff --git a/libs/ui/include/ui/FatVector.h b/libs/ui/include/ui/FatVector.h
new file mode 100644
index 0000000..25fe3a0
--- /dev/null
+++ b/libs/ui/include/ui/FatVector.h
@@ -0,0 +1,93 @@
+/*
+ * Copyright 2019, The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ANDROID_REGION_FAT_VECTOR_H
+#define ANDROID_REGION_FAT_VECTOR_H
+
+#include <stddef.h>
+#include <stdlib.h>
+#include <utils/Log.h>
+#include <type_traits>
+
+#include <vector>
+
+namespace android {
+
+template <typename T, size_t SIZE = 4>
+class InlineStdAllocator {
+public:
+ struct Allocation {
+ private:
+ Allocation(const Allocation&) = delete;
+ void operator=(const Allocation&) = delete;
+
+ public:
+ Allocation() {}
+ // char array instead of T array, so memory is uninitialized, with no destructors run
+ char array[sizeof(T) * SIZE];
+ bool inUse = false;
+ };
+
+ typedef T value_type; // needed to implement std::allocator
+ typedef T* pointer; // needed to implement std::allocator
+
+ explicit InlineStdAllocator(Allocation& allocation) : mAllocation(allocation) {}
+ InlineStdAllocator(const InlineStdAllocator& other) : mAllocation(other.mAllocation) {}
+ ~InlineStdAllocator() {}
+
+ T* allocate(size_t num, const void* = 0) {
+ if (!mAllocation.inUse && num <= SIZE) {
+ mAllocation.inUse = true;
+ return static_cast<T*>(static_cast<void*>(mAllocation.array));
+ } else {
+ return static_cast<T*>(static_cast<void*>(malloc(num * sizeof(T))));
+ }
+ }
+
+ void deallocate(pointer p, size_t) {
+ if (p == static_cast<T*>(static_cast<void*>(mAllocation.array))) {
+ mAllocation.inUse = false;
+ } else {
+ // 'free' instead of delete here - destruction handled separately
+ free(p);
+ }
+ }
+ Allocation& mAllocation;
+};
+
+/**
+ * std::vector with SIZE elements preallocated into an internal buffer.
+ *
+ * Useful for avoiding the cost of malloc in cases where only SIZE or
+ * fewer elements are needed in the common case.
+ */
+template <typename T, size_t SIZE = 4>
+class FatVector : public std::vector<T, InlineStdAllocator<T, SIZE>> {
+public:
+ FatVector()
+ : std::vector<T, InlineStdAllocator<T, SIZE>>(InlineStdAllocator<T, SIZE>(mAllocation)) {
+ this->reserve(SIZE);
+ }
+
+ explicit FatVector(size_t capacity) : FatVector() { this->resize(capacity); }
+
+private:
+ typename InlineStdAllocator<T, SIZE>::Allocation mAllocation;
+};
+
+} // namespace android
+
+#endif // ANDROID_REGION_FAT_VECTOR_H
diff --git a/libs/ui/include/ui/Region.h b/libs/ui/include/ui/Region.h
index 2db3b10..6bb7b8d 100644
--- a/libs/ui/include/ui/Region.h
+++ b/libs/ui/include/ui/Region.h
@@ -21,13 +21,13 @@
#include <sys/types.h>
#include <ostream>
-#include <utils/Vector.h>
-
#include <ui/Rect.h>
#include <utils/Flattenable.h>
#include <android-base/macros.h>
+#include "FatVector.h"
+
#include <string>
namespace android {
@@ -180,7 +180,7 @@
// with an extra Rect as the last element which is set to the
// bounds of the region. However, if the region is
// a simple Rect then mStorage contains only that rect.
- Vector<Rect> mStorage;
+ FatVector<Rect> mStorage;
};
@@ -235,4 +235,3 @@
}; // namespace android
#endif // ANDROID_UI_REGION_H
-
diff --git a/libs/ui/include_vndk/ui/FatVector.h b/libs/ui/include_vndk/ui/FatVector.h
new file mode 120000
index 0000000..bf30166
--- /dev/null
+++ b/libs/ui/include_vndk/ui/FatVector.h
@@ -0,0 +1 @@
+../../include/ui/FatVector.h
\ No newline at end of file