Use iterators "before" the use node in HUserRecord<>.
Create a new template class IntrusiveForwardList<> that
mimicks std::forward_list<> except that all allocations
are handled externally. This is essentially the same as
boost::intrusive::slist<> but since we're not using Boost
we have to reinvent the wheel.
Use the new container to replace the HUseList and use the
iterators to "before" use nodes in HUserRecord<> to avoid
the extra pointer to the previous node which was used
exclusively for removing nodes from the list. This reduces
the size of the HUseListNode by 25%, 32B to 24B in 64-bit
compiler, 16B to 12B in 32-bit compiler. This translates
directly to overall memory savings for the 64-bit compiler
but due to rounding up of the arena allocations to 8B, we
do not get any improvement in the 32-bit compiler.
Compiling the Nexus 5 boot image with the 64-bit dex2oat
on host this CL reduces the memory used for compiling the
most hungry method, BatteryStats.dumpLocked(), by ~3.3MiB:
Before:
MEM: used: 47829200, allocated: 48769120, lost: 939920
Number of arenas allocated: 345,
Number of allocations: 815492, avg size: 58
...
UseListNode 13744640
...
After:
MEM: used: 44393040, allocated: 45361248, lost: 968208
Number of arenas allocated: 319,
Number of allocations: 815492, avg size: 54
...
UseListNode 10308480
...
Note that while we do not ship the 64-bit dex2oat to the
device, the JIT compilation for 64-bit processes is using
the 64-bit libart-compiler.
Bug: 28173563
Change-Id: I985eabd4816f845372d8aaa825a1489cf9569208
diff --git a/compiler/utils/intrusive_forward_list.h b/compiler/utils/intrusive_forward_list.h
new file mode 100644
index 0000000..a90b0f5
--- /dev/null
+++ b/compiler/utils/intrusive_forward_list.h
@@ -0,0 +1,445 @@
+/*
+ * Copyright (C) 2016 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 ART_COMPILER_UTILS_INTRUSIVE_FORWARD_LIST_H_
+#define ART_COMPILER_UTILS_INTRUSIVE_FORWARD_LIST_H_
+
+#include <stdint.h>
+#include <functional>
+#include <iterator>
+#include <memory>
+#include <type_traits>
+
+#include "base/logging.h"
+#include "base/macros.h"
+
+namespace art {
+
+struct IntrusiveForwardListHook {
+ IntrusiveForwardListHook() : next_hook(nullptr) { }
+ explicit IntrusiveForwardListHook(const IntrusiveForwardListHook* hook) : next_hook(hook) { }
+
+ // Allow copyable values but do not copy the hook, it is not part of the value.
+ IntrusiveForwardListHook(const IntrusiveForwardListHook& other ATTRIBUTE_UNUSED)
+ : next_hook(nullptr) { }
+ IntrusiveForwardListHook& operator=(const IntrusiveForwardListHook& src ATTRIBUTE_UNUSED) {
+ return *this;
+ }
+
+ mutable const IntrusiveForwardListHook* next_hook;
+};
+
+template <typename T, IntrusiveForwardListHook T::* NextPtr = &T::hook>
+class IntrusiveForwardListMemberHook;
+
+template <typename T, typename HookTraits = IntrusiveForwardListMemberHook<T>>
+class IntrusiveForwardList;
+
+template <typename T, typename HookTraits>
+class IntrusiveForwardListIterator : public std::iterator<std::forward_iterator_tag, T> {
+ public:
+ // Construct/copy/destroy (except the private constructor used by IntrusiveForwardList<>).
+ IntrusiveForwardListIterator() : hook_(nullptr) { }
+ IntrusiveForwardListIterator(const IntrusiveForwardListIterator& src) = default;
+ IntrusiveForwardListIterator& operator=(const IntrusiveForwardListIterator& src) = default;
+
+ // Conversion from iterator to const_iterator.
+ template <typename OtherT,
+ typename = typename std::enable_if<std::is_same<T, const OtherT>::value>::type>
+ IntrusiveForwardListIterator(const IntrusiveForwardListIterator<OtherT, HookTraits>& src)
+ : hook_(src.hook_) { }
+
+ // Iteration.
+ IntrusiveForwardListIterator& operator++() {
+ DCHECK(hook_ != nullptr);
+ hook_ = hook_->next_hook;
+ return *this;
+ }
+ IntrusiveForwardListIterator operator++(int) {
+ IntrusiveForwardListIterator tmp(*this);
+ ++*this;
+ return tmp;
+ }
+
+ // Dereference
+ T& operator*() const {
+ DCHECK(hook_ != nullptr);
+ return *HookTraits::GetValue(hook_);
+ }
+ T* operator->() const {
+ return &**this;
+ }
+
+ private:
+ explicit IntrusiveForwardListIterator(const IntrusiveForwardListHook* hook) : hook_(hook) { }
+
+ const IntrusiveForwardListHook* hook_;
+
+ template <typename OtherT, typename OtherTraits>
+ friend class IntrusiveForwardListIterator;
+
+ template <typename OtherT, typename OtherTraits>
+ friend class IntrusiveForwardList;
+
+ template <typename OtherT1, typename OtherT2, typename OtherTraits>
+ friend typename std::enable_if<std::is_same<const OtherT1, const OtherT2>::value, bool>::type
+ operator==(const IntrusiveForwardListIterator<OtherT1, OtherTraits>& lhs,
+ const IntrusiveForwardListIterator<OtherT2, OtherTraits>& rhs);
+};
+
+template <typename T, typename OtherT, typename HookTraits>
+typename std::enable_if<std::is_same<const T, const OtherT>::value, bool>::type operator==(
+ const IntrusiveForwardListIterator<T, HookTraits>& lhs,
+ const IntrusiveForwardListIterator<OtherT, HookTraits>& rhs) {
+ return lhs.hook_ == rhs.hook_;
+}
+
+template <typename T, typename OtherT, typename HookTraits>
+typename std::enable_if<std::is_same<const T, const OtherT>::value, bool>::type operator!=(
+ const IntrusiveForwardListIterator<T, HookTraits>& lhs,
+ const IntrusiveForwardListIterator<OtherT, HookTraits>& rhs) {
+ return !(lhs == rhs);
+}
+
+// Intrusive version of std::forward_list<>. See also slist<> in Boost.Intrusive.
+//
+// This class template provides the same interface as std::forward_list<> as long
+// as the functions are meaningful for an intrusive container; this excludes emplace
+// functions and functions taking an std::initializer_list<> as the container does
+// not construct elements.
+template <typename T, typename HookTraits>
+class IntrusiveForwardList {
+ public:
+ typedef HookTraits hook_traits;
+ typedef T value_type;
+ typedef T& reference;
+ typedef const T& const_reference;
+ typedef T* pointer;
+ typedef const T* const_pointer;
+ typedef IntrusiveForwardListIterator< T, hook_traits> iterator;
+ typedef IntrusiveForwardListIterator<const T, hook_traits> const_iterator;
+
+ // Construct/copy/destroy.
+ IntrusiveForwardList() = default;
+ template <typename InputIterator>
+ IntrusiveForwardList(InputIterator first, InputIterator last) : IntrusiveForwardList() {
+ insert_after(before_begin(), first, last);
+ }
+ IntrusiveForwardList(IntrusiveForwardList&& src) : first_(src.first_.next_hook) {
+ src.first_.next_hook = nullptr;
+ }
+ IntrusiveForwardList& operator=(const IntrusiveForwardList& src) = delete;
+ IntrusiveForwardList& operator=(IntrusiveForwardList&& src) {
+ IntrusiveForwardList tmp(std::move(src));
+ tmp.swap(*this);
+ return *this;
+ }
+ ~IntrusiveForwardList() = default;
+
+ // Iterators.
+ iterator before_begin() { return iterator(&first_); }
+ const_iterator before_begin() const { return const_iterator(&first_); }
+ iterator begin() { return iterator(first_.next_hook); }
+ const_iterator begin() const { return const_iterator(first_.next_hook); }
+ iterator end() { return iterator(nullptr); }
+ const_iterator end() const { return const_iterator(nullptr); }
+ const_iterator cbefore_begin() const { return const_iterator(&first_); }
+ const_iterator cbegin() const { return const_iterator(first_.next_hook); }
+ const_iterator cend() const { return const_iterator(nullptr); }
+
+ // Capacity.
+ bool empty() const { return begin() == end(); }
+ size_t max_size() { return static_cast<size_t>(-1); }
+
+ // Element access.
+ reference front() { return *begin(); }
+ const_reference front() const { return *begin(); }
+
+ // Modifiers.
+ template <typename InputIterator>
+ void assign(InputIterator first, InputIterator last) {
+ IntrusiveForwardList tmp(first, last);
+ tmp.swap(*this);
+ }
+ void push_front(value_type& value) {
+ insert_after(before_begin(), value);
+ }
+ void pop_front() {
+ DCHECK(!empty());
+ erase_after(before_begin());
+ }
+ iterator insert_after(const_iterator position, value_type& value) {
+ const IntrusiveForwardListHook* new_hook = hook_traits::GetHook(&value);
+ new_hook->next_hook = position.hook_->next_hook;
+ position.hook_->next_hook = new_hook;
+ return iterator(new_hook);
+ }
+ template <typename InputIterator>
+ iterator insert_after(const_iterator position, InputIterator first, InputIterator last) {
+ while (first != last) {
+ position = insert_after(position, *first++);
+ }
+ return iterator(position.hook_);
+ }
+ iterator erase_after(const_iterator position) {
+ const_iterator last = position;
+ std::advance(last, 2);
+ return erase_after(position, last);
+ }
+ iterator erase_after(const_iterator position, const_iterator last) {
+ DCHECK(position != last);
+ position.hook_->next_hook = last.hook_;
+ return iterator(last.hook_);
+ }
+ void swap(IntrusiveForwardList& other) {
+ std::swap(first_.next_hook, other.first_.next_hook);
+ }
+ void clear() {
+ first_.next_hook = nullptr;
+ }
+
+ // Operations.
+ void splice_after(const_iterator position, IntrusiveForwardList& src) {
+ DCHECK(position != end());
+ splice_after(position, src, src.before_begin(), src.end());
+ }
+ void splice_after(const_iterator position, IntrusiveForwardList&& src) {
+ splice_after(position, src); // Use l-value overload.
+ }
+ // Splice the element after `i`.
+ void splice_after(const_iterator position, IntrusiveForwardList& src, const_iterator i) {
+ const_iterator last = i;
+ std::advance(last, 2);
+ splice_after(position, src, i, last);
+ }
+ // Splice the element after `i`.
+ void splice_after(const_iterator position, IntrusiveForwardList&& src, const_iterator i) {
+ splice_after(position, src, i); // Use l-value overload.
+ }
+ // Splice elements between `first` and `last`, i.e. open range `(first, last)`.
+ void splice_after(const_iterator position,
+ IntrusiveForwardList& src,
+ const_iterator first,
+ const_iterator last) {
+ DCHECK(position != end());
+ DCHECK(first != last);
+ if (++const_iterator(first) == last) {
+ // Nothing to do.
+ return;
+ }
+ // If position is just before end() and last is src.end(), we can finish this quickly.
+ if (++const_iterator(position) == end() && last == src.end()) {
+ position.hook_->next_hook = first.hook_->next_hook;
+ first.hook_->next_hook = nullptr;
+ return;
+ }
+ // Otherwise we need to find the position before last to fix up the hook.
+ const_iterator before_last = first;
+ while (++const_iterator(before_last) != last) {
+ ++before_last;
+ }
+ // Detach (first, last).
+ const IntrusiveForwardListHook* first_taken = first.hook_->next_hook;
+ first.hook_->next_hook = last.hook_;
+ // Attach the sequence to the new position.
+ before_last.hook_->next_hook = position.hook_->next_hook;
+ position.hook_->next_hook = first_taken;
+ }
+ // Splice elements between `first` and `last`, i.e. open range `(first, last)`.
+ void splice_after(const_iterator position,
+ IntrusiveForwardList&& src,
+ const_iterator first,
+ const_iterator last) {
+ splice_after(position, src, first, last); // Use l-value overload.
+ }
+ void remove(const value_type& value) {
+ remove_if([value](const value_type& v) { return value == v; });
+ }
+ template <typename Predicate>
+ void remove_if(Predicate pred) {
+ iterator prev = before_begin();
+ for (iterator current = begin(); current != end(); ++current) {
+ if (pred(*current)) {
+ erase_after(prev);
+ current = prev;
+ } else {
+ prev = current;
+ }
+ }
+ }
+ void unique() {
+ unique(std::equal_to<value_type>());
+ }
+ template <typename BinaryPredicate>
+ void unique(BinaryPredicate pred) {
+ if (!empty()) {
+ iterator prev = begin();
+ iterator current = prev;
+ ++current;
+ for (; current != end(); ++current) {
+ if (pred(*prev, *current)) {
+ erase_after(prev);
+ current = prev;
+ } else {
+ prev = current;
+ }
+ }
+ }
+ }
+ void merge(IntrusiveForwardList& other) {
+ merge(other, std::less<value_type>());
+ }
+ void merge(IntrusiveForwardList&& other) {
+ merge(other); // Use l-value overload.
+ }
+ template <typename Compare>
+ void merge(IntrusiveForwardList& other, Compare cmp) {
+ iterator prev = before_begin();
+ iterator current = begin();
+ iterator other_prev = other.before_begin();
+ iterator other_current = other.begin();
+ while (current != end() && other_current != other.end()) {
+ if (cmp(*other_current, *current)) {
+ ++other_current;
+ splice_after(prev, other, other_prev);
+ ++prev;
+ } else {
+ prev = current;
+ ++current;
+ }
+ DCHECK(++const_iterator(prev) == current);
+ DCHECK(++const_iterator(other_prev) == other_current);
+ }
+ splice_after(prev, other);
+ }
+ template <typename Compare>
+ void merge(IntrusiveForwardList&& other, Compare cmp) {
+ merge(other, cmp); // Use l-value overload.
+ }
+ void sort() {
+ sort(std::less<value_type>());
+ }
+ template <typename Compare>
+ void sort(Compare cmp) {
+ size_t n = std::distance(begin(), end());
+ if (n >= 2u) {
+ const_iterator middle = before_begin();
+ std::advance(middle, n / 2u);
+ IntrusiveForwardList second_half;
+ second_half.splice_after(second_half.before_begin(), *this, middle, end());
+ sort(cmp);
+ second_half.sort(cmp);
+ merge(second_half, cmp);
+ }
+ }
+ void reverse() {
+ IntrusiveForwardList reversed;
+ while (!empty()) {
+ value_type& value = front();
+ erase_after(before_begin());
+ reversed.insert_after(reversed.before_begin(), value);
+ }
+ reversed.swap(*this);
+ }
+
+ // Extensions.
+ bool HasExactlyOneElement() const {
+ return !empty() && ++begin() == end();
+ }
+ size_t SizeSlow() const {
+ return std::distance(begin(), end());
+ }
+ bool ContainsNode(const_reference node) const {
+ for (auto&& n : *this) {
+ if (std::addressof(n) == std::addressof(node)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ private:
+ static IntrusiveForwardListHook* ModifiableHook(const IntrusiveForwardListHook* hook) {
+ return const_cast<IntrusiveForwardListHook*>(hook);
+ }
+
+ IntrusiveForwardListHook first_;
+};
+
+template <typename T, typename HookTraits>
+void swap(IntrusiveForwardList<T, HookTraits>& lhs, IntrusiveForwardList<T, HookTraits>& rhs) {
+ lhs.swap(rhs);
+}
+
+template <typename T, typename HookTraits>
+bool operator==(const IntrusiveForwardList<T, HookTraits>& lhs,
+ const IntrusiveForwardList<T, HookTraits>& rhs) {
+ auto lit = lhs.begin();
+ auto rit = rhs.begin();
+ for (; lit != lhs.end() && rit != rhs.end(); ++lit, ++rit) {
+ if (*lit != *rit) {
+ return false;
+ }
+ }
+ return lit == lhs.end() && rit == rhs.end();
+}
+
+template <typename T, typename HookTraits>
+bool operator!=(const IntrusiveForwardList<T, HookTraits>& lhs,
+ const IntrusiveForwardList<T, HookTraits>& rhs) {
+ return !(lhs == rhs);
+}
+
+template <typename T, typename HookTraits>
+bool operator<(const IntrusiveForwardList<T, HookTraits>& lhs,
+ const IntrusiveForwardList<T, HookTraits>& rhs) {
+ return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
+}
+
+template <typename T, typename HookTraits>
+bool operator>(const IntrusiveForwardList<T, HookTraits>& lhs,
+ const IntrusiveForwardList<T, HookTraits>& rhs) {
+ return rhs < lhs;
+}
+
+template <typename T, typename HookTraits>
+bool operator<=(const IntrusiveForwardList<T, HookTraits>& lhs,
+ const IntrusiveForwardList<T, HookTraits>& rhs) {
+ return !(rhs < lhs);
+}
+
+template <typename T, typename HookTraits>
+bool operator>=(const IntrusiveForwardList<T, HookTraits>& lhs,
+ const IntrusiveForwardList<T, HookTraits>& rhs) {
+ return !(lhs < rhs);
+}
+
+template <typename T, IntrusiveForwardListHook T::* NextPtr>
+class IntrusiveForwardListMemberHook {
+ public:
+ static const IntrusiveForwardListHook* GetHook(const T* value) {
+ return &(value->*NextPtr);
+ }
+
+ static T* GetValue(const IntrusiveForwardListHook* hook) {
+ return reinterpret_cast<T*>(
+ reinterpret_cast<uintptr_t>(hook) - OFFSETOF_MEMBERPTR(T, NextPtr));
+ }
+};
+
+} // namespace art
+
+#endif // ART_COMPILER_UTILS_INTRUSIVE_FORWARD_LIST_H_