Add ImmutableVector and ImmutableVectorView templates. These templates allow creating and using heap-allocated but immutable arrays of items. They will be used by future CLs in a few key classes to reduce GN RAM usage drastically. Here's how an ImmutableVector compares to an std::vector<> in terms of memory usage: - An empty instance is just an 8-byte null pointer, vs 24 bytes for an empty vector. - Its heap block is sized precisely to fit the instance's size, while the std::vector<> will generally over-allocate its storage space (calling reserve() does not guarantee minimal heap usage). Note that constructing an non-empty ImmutableVector requires a source container (std::vector<> or otherwise), or a callable that can produce a fixed number of items for in-place construction (see source code for details). An ImmutableVectorView is a non-owning reference to an ImmutableVectorView, it is copyable and movable since the vector is immutable. Bug: None Change-Id: I2cb669b7b0fab777bc7067ee7529690b300ea735 Reviewed-on: https://gn-review.googlesource.com/c/gn/+/13621 Reviewed-by: Sylvain Defresne <sdefresne@chromium.org> Commit-Queue: David Turner <digit@google.com>
diff --git a/build/gen.py b/build/gen.py index 8b833d0..f695ccd 100755 --- a/build/gen.py +++ b/build/gen.py
@@ -761,6 +761,7 @@ 'src/gn/functions_unittest.cc', 'src/gn/hash_table_base_unittest.cc', 'src/gn/header_checker_unittest.cc', + 'src/gn/immutable_vector_unittest.cc', 'src/gn/inherited_libraries_unittest.cc', 'src/gn/input_conversion_unittest.cc', 'src/gn/json_project_writer_unittest.cc',
diff --git a/src/gn/immutable_vector.h b/src/gn/immutable_vector.h new file mode 100644 index 0000000..306819b --- /dev/null +++ b/src/gn/immutable_vector.h
@@ -0,0 +1,244 @@ +// Copyright 2022 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef TOOLS_GN_IMMUTABLE_VECTOR_H_ +#define TOOLS_GN_IMMUTABLE_VECTOR_H_ + +#include <cstdlib> +#include <type_traits> +#include <utility> + +#include "util/aligned_alloc.h" + +// An ImmutableVector<T> represents a fixed-size vector of constant items of +// type T. The in-memory representation is more efficient, only using one +// pointer to a single heap-allocated memory block that also contains the size. +// +// An ImmutableVectorView<T> acts as a copyable and movable reference to another +// ImmutableVector<T> instance. They both point to the same memory in the heap, +// but the view is not owning and is invalidated when the instance it points to +// is destroyed. +// +// Apart from that, they can be used with the same methods as a const +// std::vector<T>. +// +template <typename T> +class ImmutableVector; + +template <typename T> +class ImmutableVectorView { + public: + // Default constructor + ImmutableVectorView() = default; + + // Constructor from an ImmutableVector. + ImmutableVectorView(const ImmutableVector<T>& vector) + : header_(vector.header_) {} + + // Usual methods to access items. + const T* data() const { return begin(); } + size_t size() const { return header_ ? header_->size : 0u; } + bool empty() const { return size() == 0; } + const T& operator[](size_t offset) const { return begin()[offset]; }; + + const T* begin() const { return header_ ? &header_->item0 : nullptr; } + const T* end() const { + return header_ ? &header_->item0 + header_->size : nullptr; + } + + const T& front() const { return begin()[0]; } + const T& back() const { return end()[-1]; } + + // For use with standard algorithms and templates. + using element_type = T; + using value_type = std::remove_cv_t<T>; + using size_type = std::size_t; + using difference_type = std::ptrdiff_t; + using pointer = T*; + using const_pointer = const T*; + using reference = T&; + using const_reference = const T&; + using iterator = const T*; + using const_iterator = const T*; + + const_iterator find(const T& item) const { + auto it = begin(); + auto it_end = end(); + for (; it != it_end; ++it) { + if (*it == item) + break; + } + return it; + } + + bool contains(const T& item) const { + for (const auto& cur_item : *this) + if (cur_item == item) + return true; + + return false; + } + + protected: + struct Header { + size_t size; + T item0; + }; + + ImmutableVectorView(Header* header) : header_(header) {} + + Header* header_ = nullptr; +}; + +template <typename T> +class ImmutableVector : public ImmutableVectorView<T> { + public: + // Default constructor. + ImmutableVector() = default; + + // Range constructors. + ImmutableVector(const T* begin, size_t size) + : ImmutableVectorView<T>(AllocateAndCopyFrom(begin, size)) {} + + ImmutableVector(const T* begin, const T* end) + : ImmutableVector(begin, end - begin) {} + + // In-place constructor + // |producer| must be a callable that generates a T instance that will + // be used to construct items in place in the allocated vector. + template <typename P, + typename = std::void_t< + decltype(static_cast<const T&>(std::declval<P>()()))>> + ImmutableVector(P producer, size_t size) { + if (size) { + this->header_ = AllocateFor(size); + auto* dst = &(this->header_->item0); + auto* dst_limit = dst + size; + for (; dst != dst_limit; ++dst) + new (dst) T(producer()); + } + } + + // Container constructor + // + // This uses std::void_t<> to select container types whose values + // are convertible to |const T&|, and which have |begin()| and |size()| + // methods. + // + // This constructor copies items from the constructor into the + // ImmutableVector. + template <typename C, + typename = std::void_t< + decltype(static_cast<const T>(*std::declval<C>().begin())), + decltype(std::declval<C>().size())>> + ImmutableVector(const C& container) { + size_t size = container.size(); + if (size) { + this->header_ = AllocateFor(size); + auto src = container.begin(); + auto* dst = &(this->header_->item0); + auto* dst_limit = dst + size; + for (; dst != dst_limit; ++dst, ++src) { + new (dst) T(*src); + } + } + } + + // Another container constructor where the items can be moved into + // the resulting ImmutableVector. + template <typename C, + typename = std::void_t< + decltype(static_cast<const T>(*std::declval<C>().begin())), + decltype(std::declval<C>().size())>> + ImmutableVector(C&& container) { + size_t size = container.size(); + if (size) { + this->header_ = AllocateFor(size); + auto src = container.begin(); + auto* dst = &(this->header_->item0); + auto* dst_limit = dst + size; + for (; dst != dst_limit; ++dst, ++src) + new (dst) T(std::move(*src)); + } + } + + // Initializer-list container. + ImmutableVector(std::initializer_list<T> list) + : ImmutableVector(list.begin(), list.size()) {} + + // Copy operations + ImmutableVector(const ImmutableVector& other) + : ImmutableVectorView<T>( + AllocateAndCopyFrom(other.begin(), other.size())) {} + + ImmutableVector& operator=(const ImmutableVector& other) { + if (this != &other) { + this->~ImmutableVector(); + new (this) ImmutableVector(other); + } + return *this; + } + + // Move operations + ImmutableVector(ImmutableVector&& other) noexcept { + this->header_ = other.header_; + other.header_ = nullptr; + } + + ImmutableVector& operator=(ImmutableVector&& other) noexcept { + if (this != &other) { + this->~ImmutableVector(); + new (this) ImmutableVector(std::move(other)); + } + return *this; + } + + // Destructor + ~ImmutableVector() { + if (this->header_) { + auto* cur = &(this->header_->item0); + auto* limit = cur + this->size(); + while (cur != limit) { + (*cur).~T(); + cur++; + } + Allocator::Free(this->header_); + } + } + + protected: + friend class ImmutableVectorView<T>; + + using Header = typename ImmutableVectorView<T>::Header; + + // Don't use std::max() here to avoid including <algorithm> which is massive. + static constexpr size_t kAlignment = alignof(T) > alignof(Header) + ? alignof(T) + : alignof(Header); + + using Allocator = AlignedAlloc<kAlignment>; + + static Header* AllocateFor(size_t count) { + if (!count) + return nullptr; + + auto* header = reinterpret_cast<Header*>( + Allocator::Alloc(sizeof(Header) + (count - 1u) * sizeof(T))); + header->size = count; + return header; + } + + static Header* AllocateAndCopyFrom(const T* begin, size_t size) { + Header* header = AllocateFor(size); + if (size) { + T* dst = &(header->item0); + T* limit = dst + size; + for (; dst != limit; ++dst, ++begin) + new (dst) T(*begin); + } + return header; + } +}; + +#endif // TOOLS_GN_IMMUTABLE_VECTOR_H_
diff --git a/src/gn/immutable_vector_unittest.cc b/src/gn/immutable_vector_unittest.cc new file mode 100644 index 0000000..3561ed2 --- /dev/null +++ b/src/gn/immutable_vector_unittest.cc
@@ -0,0 +1,81 @@ +// Copyright 2022 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "gn/immutable_vector.h" +#include "util/test/test.h" + +#include <set> +#include <vector> + +TEST(ImmutableVector, CreationDestruction) { + ImmutableVector<int> empty; + EXPECT_TRUE(empty.empty()); + EXPECT_EQ(0u, empty.size()); + + ImmutableVector<int> vec1 = {100, 42}; + EXPECT_FALSE(vec1.empty()); + EXPECT_EQ(2u, vec1.size()); + EXPECT_EQ(100, vec1.front()); + EXPECT_EQ(42, vec1.back()); + EXPECT_EQ(100, vec1[0]); + EXPECT_EQ(42, vec1[1]); + EXPECT_TRUE(vec1.begin()); + EXPECT_TRUE(vec1.end()); + EXPECT_NE(vec1.begin(), vec1.end()); + EXPECT_EQ(vec1.begin() + 2, vec1.end()); + + std::vector<int> input; + input.push_back(100); + input.push_back(42); + input.push_back(-12); + ImmutableVector<int> vec2(input); + EXPECT_FALSE(vec2.empty()); + EXPECT_EQ(3u, vec2.size()); + EXPECT_EQ(100, vec2.front()); + EXPECT_EQ(100, vec2[0]); + EXPECT_EQ(42, vec2[1]); + EXPECT_EQ(-12, vec2[2]); + EXPECT_NE(vec2.begin(), &input[0]); + EXPECT_NE(vec2.end(), &input[0] + 3); +} + +TEST(ImmutableVetor, InPlaceConstruction) { + size_t count = 0; + auto count_producer = [&count]() { return count++; }; + ImmutableVector<int> vec(count_producer, 5u); + EXPECT_EQ(5u, vec.size()); + EXPECT_EQ(0, vec[0]); + EXPECT_EQ(1, vec[1]); + EXPECT_EQ(2, vec[2]); + EXPECT_EQ(3, vec[3]); + EXPECT_EQ(4, vec[4]); +} + +TEST(ImmutableVector, CopyAndMoveOperations) { + ImmutableVector<int> vec1 = {1, 2, 3, 4}; + ImmutableVector<int> vec2 = vec1; + ImmutableVector<int> vec3 = std::move(vec1); + + EXPECT_TRUE(vec1.empty()); + EXPECT_EQ(4u, vec2.size()); + EXPECT_EQ(4u, vec3.size()); + EXPECT_NE(vec2.begin(), vec3.begin()); + EXPECT_NE(vec2.end(), vec3.end()); + EXPECT_TRUE(std::equal(vec2.begin(), vec2.end(), vec3.begin(), vec3.end())); +} + +TEST(ImmutableVectorView, Creation) { + ImmutableVector<int> vec1 = {1, 3, 5, 7}; + ImmutableVectorView<int> view1 = vec1; + ImmutableVectorView<int> view2(view1); + + EXPECT_EQ(vec1.size(), view1.size()); + EXPECT_EQ(vec1.size(), view2.size()); + + EXPECT_EQ(vec1.begin(), view1.begin()); + EXPECT_EQ(vec1.end(), view1.end()); + + EXPECT_EQ(vec1.begin(), view2.begin()); + EXPECT_EQ(vec1.end(), view2.end()); +}