https://github.com/ktf updated https://github.com/llvm/llvm-project/pull/66430
>From c14aaf14cbcd292165aece38ebdae74ce92a4d32 Mon Sep 17 00:00:00 2001 From: Giulio Eulisse <10544+...@users.noreply.github.com> Date: Thu, 14 Sep 2023 21:58:21 +0200 Subject: [PATCH 1/5] Introduce PagedVector class The goal of the class is to be an (almost) drop in replacement for SmallVector and std::vector when those are presized and filled later, as it happens in SourceManager and ASTReader. By doing so, sparsely accessed PagedVector can profit from reduced memory footprint. --- clang/include/clang/Basic/SourceManager.h | 3 +- clang/include/clang/Serialization/ASTReader.h | 5 +- clang/lib/Basic/SourceManager.cpp | 10 +- clang/lib/Serialization/ASTReader.cpp | 5 +- llvm/docs/ProgrammersManual.rst | 34 ++ llvm/include/llvm/ADT/PagedVector.h | 282 +++++++++++++++ llvm/unittests/ADT/CMakeLists.txt | 1 + llvm/unittests/ADT/PagedVectorTest.cpp | 342 ++++++++++++++++++ 8 files changed, 672 insertions(+), 10 deletions(-) create mode 100644 llvm/include/llvm/ADT/PagedVector.h create mode 100644 llvm/unittests/ADT/PagedVectorTest.cpp diff --git a/clang/include/clang/Basic/SourceManager.h b/clang/include/clang/Basic/SourceManager.h index 2f846502d6f3327..e37caa2252532f9 100644 --- a/clang/include/clang/Basic/SourceManager.h +++ b/clang/include/clang/Basic/SourceManager.h @@ -43,6 +43,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/IntrusiveRefCntPtr.h" +#include "llvm/ADT/PagedVector.h" #include "llvm/ADT/PointerIntPair.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" @@ -699,7 +700,7 @@ class SourceManager : public RefCountedBase<SourceManager> { /// /// Negative FileIDs are indexes into this table. To get from ID to an index, /// use (-ID - 2). - SmallVector<SrcMgr::SLocEntry, 0> LoadedSLocEntryTable; + llvm::PagedVector<SrcMgr::SLocEntry> LoadedSLocEntryTable; /// The starting offset of the next local SLocEntry. /// diff --git a/clang/include/clang/Serialization/ASTReader.h b/clang/include/clang/Serialization/ASTReader.h index dc1eb21c27801fe..65e19c6e44cf571 100644 --- a/clang/include/clang/Serialization/ASTReader.h +++ b/clang/include/clang/Serialization/ASTReader.h @@ -38,6 +38,7 @@ #include "llvm/ADT/DenseSet.h" #include "llvm/ADT/IntrusiveRefCntPtr.h" #include "llvm/ADT/MapVector.h" +#include "llvm/ADT/PagedVector.h" #include "llvm/ADT/STLExtras.h" #include "llvm/ADT/SetVector.h" #include "llvm/ADT/SmallPtrSet.h" @@ -487,7 +488,7 @@ class ASTReader /// /// When the pointer at index I is non-NULL, the type with /// ID = (I + 1) << FastQual::Width has already been loaded - std::vector<QualType> TypesLoaded; + llvm::PagedVector<QualType> TypesLoaded; using GlobalTypeMapType = ContinuousRangeMap<serialization::TypeID, ModuleFile *, 4>; @@ -501,7 +502,7 @@ class ASTReader /// /// When the pointer at index I is non-NULL, the declaration with ID /// = I + 1 has already been loaded. - std::vector<Decl *> DeclsLoaded; + llvm::PagedVector<Decl *> DeclsLoaded; using GlobalDeclMapType = ContinuousRangeMap<serialization::DeclID, ModuleFile *, 4>; diff --git a/clang/lib/Basic/SourceManager.cpp b/clang/lib/Basic/SourceManager.cpp index 0521ac7b30339ab..7fa8b8096ac4931 100644 --- a/clang/lib/Basic/SourceManager.cpp +++ b/clang/lib/Basic/SourceManager.cpp @@ -2344,11 +2344,11 @@ SourceManager::MemoryBufferSizes SourceManager::getMemoryBufferSizes() const { } size_t SourceManager::getDataStructureSizes() const { - size_t size = llvm::capacity_in_bytes(MemBufferInfos) - + llvm::capacity_in_bytes(LocalSLocEntryTable) - + llvm::capacity_in_bytes(LoadedSLocEntryTable) - + llvm::capacity_in_bytes(SLocEntryLoaded) - + llvm::capacity_in_bytes(FileInfos); + size_t size = llvm::capacity_in_bytes(MemBufferInfos) + + llvm::capacity_in_bytes(LocalSLocEntryTable) + + llvm::capacity_in_bytes(LoadedSLocEntryTable) + + llvm::capacity_in_bytes(SLocEntryLoaded) + + llvm::capacity_in_bytes(FileInfos); if (OverriddenFilesInfo) size += llvm::capacity_in_bytes(OverriddenFilesInfo->OverriddenFiles); diff --git a/clang/lib/Serialization/ASTReader.cpp b/clang/lib/Serialization/ASTReader.cpp index 0952244d037a77c..bb2a32ade0a0d7c 100644 --- a/clang/lib/Serialization/ASTReader.cpp +++ b/clang/lib/Serialization/ASTReader.cpp @@ -7944,9 +7944,10 @@ void ASTReader::PrintStats() { std::fprintf(stderr, "*** AST File Statistics:\n"); unsigned NumTypesLoaded = - TypesLoaded.size() - llvm::count(TypesLoaded, QualType()); + TypesLoaded.size() - llvm::count(TypesLoaded.materialized(), QualType()); unsigned NumDeclsLoaded = - DeclsLoaded.size() - llvm::count(DeclsLoaded, (Decl *)nullptr); + DeclsLoaded.size() - + llvm::count(DeclsLoaded.materialized(), (Decl *)nullptr); unsigned NumIdentifiersLoaded = IdentifiersLoaded.size() - llvm::count(IdentifiersLoaded, (IdentifierInfo *)nullptr); diff --git a/llvm/docs/ProgrammersManual.rst b/llvm/docs/ProgrammersManual.rst index 43dd985d9779ed2..22e95261e639256 100644 --- a/llvm/docs/ProgrammersManual.rst +++ b/llvm/docs/ProgrammersManual.rst @@ -1625,6 +1625,40 @@ SmallVector has grown a few other minor advantages over std::vector, causing and is no longer "private to the implementation". A name like ``SmallVectorHeader`` might be more appropriate. +.. _dss_pagedvector: + +llvm/ADT/PagedVector.h +^^^^^^^^^^^^^^^^^^^^^^ + +``PagedVector<Type, PageSize>`` is a random access container that allocates +``PageSize`` elements of type ``Type`` when the first element of a page is +accessed via the ``operator[]``. This is useful for cases where the number of +elements is known in advance; their actual initialization is expensive; and +they are sparsely used. This utility uses page-granular lazy initialization +when the element is accessed. When the number of used pages is small +significant memory savings can be achieved. + +The main advantage is that a ``PagedVector`` allows to delay the actual +allocation of the page until it's needed, at the extra cost of one pointer per +page and one extra indirection when accessing elements with their positional +index. + +In order to minimise the memory footprint of this container, it's important to +balance the PageSize so that it's not too small (otherwise the overhead of the +pointer per page might become too high) and not too big (otherwise the memory +is wasted if the page is not fully used). + +Moreover, while retaining the order of the elements based on their insertion +index, like a vector, iterating over the elements via ``begin()`` and ``end()`` +is not provided in the API, due to the fact accessing the elements in order +would allocate all the iterated pages, defeating memory savings and the purpose +of the ``PagedVector``. + +Finally a ``materialized_begin()`` and ``materialized_end`` iterators are +provided to access the elements associated to the accessed pages, which could +speed up operations that need to iterate over initialized elements in a +non-ordered manner. + .. _dss_vector: <vector> diff --git a/llvm/include/llvm/ADT/PagedVector.h b/llvm/include/llvm/ADT/PagedVector.h new file mode 100644 index 000000000000000..380da3e358e2408 --- /dev/null +++ b/llvm/include/llvm/ADT/PagedVector.h @@ -0,0 +1,282 @@ +//===- llvm/ADT/PagedVector.h - 'Lazyly allocated' vectors --------*- C++ +//-*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file defines the PagedVector class. +// +//===----------------------------------------------------------------------===// +#ifndef LLVM_ADT_PAGEDVECTOR_H +#define LLVM_ADT_PAGEDVECTOR_H + +#include "llvm/ADT/PointerIntPair.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/iterator_range.h" +#include "llvm/Support/Allocator.h" +#include <cassert> +#include <vector> + +namespace llvm { +/// A vector that allocates memory in pages. +/// +/// Order is kept, but memory is allocated only when one element of the page is +/// accessed. This introduces a level of indirection, but it is useful when you +/// have a sparsely initialised vector where the full size is allocated upfront. +/// +/// As a side effect the elements are initialised later than in a normal vector. +/// On the first access to one of the elements of a given page, all the elements +/// of the page are initialised. This also means that the elements of the page +/// are initialised beyond the size of the vector. +/// +/// Similarly on destruction the elements are destroyed only when the page is +/// not needed anymore, delaying invoking the destructor of the elements. +/// +/// Notice that this has iterators only on materialized elements. This +/// is deliberately done under the assumption you would dereference the elements +/// while iterating, therefore materialising them and losing the gains in terms +/// of memory usage this container provides. If you have such a use case, you +/// probably want to use a normal std::vector or a llvm::SmallVector. +template <typename T, size_t PageSize = 1024 / sizeof(T)> class PagedVector { + static_assert(PageSize > 1, "PageSize must be greater than 0. Most likely " + "you want it to be greater than 16."); + /// The actual number of elements in the vector which can be accessed. + size_t Size = 0; + + /// The position of the initial element of the page in the Data vector. + /// Pages are allocated contiguously in the Data vector. + mutable SmallVector<T *, 0> PageToDataPtrs; + /// Actual page data. All the page elements are allocated on the + /// first access of any of the elements of the page. Elements are default + /// constructed and elements of the page are stored contiguously. + PointerIntPair<BumpPtrAllocator *, 1, bool> Allocator; + +public: + using value_type = T; + + /// Default constructor. We build our own allocator and mark it as such with + /// `true` in the second pair element. + PagedVector() : Allocator(new BumpPtrAllocator, true) {} + PagedVector(BumpPtrAllocator *A) : Allocator(A, false) { + assert(A != nullptr && "Allocator cannot be nullptr"); + } + + ~PagedVector() { + clear(); + // If we own the allocator, delete it. + if (Allocator.getInt()) + delete Allocator.getPointer(); + } + + // Forbid copy and move as we do not need them for the current use case. + PagedVector(const PagedVector &) = delete; + PagedVector(PagedVector &&) = delete; + PagedVector &operator=(const PagedVector &) = delete; + PagedVector &operator=(PagedVector &&) = delete; + + /// Look up an element at position `Index`. + /// If the associated page is not filled, it will be filled with default + /// constructed elements. + T &operator[](size_t Index) const { + assert(Index < Size); + assert(Index / PageSize < PageToDataPtrs.size()); + T *&PagePtr = PageToDataPtrs[Index / PageSize]; + // If the page was not yet allocated, allocate it. + if (PagePtr == nullptr) { + T *NewPagePtr = Allocator.getPointer()->template Allocate<T>(PageSize); + // We need to invoke the default constructor on all the elements of the + // page. + std::uninitialized_value_construct_n(NewPagePtr, PageSize); + + PagePtr = NewPagePtr; + } + // Dereference the element in the page. + return PagePtr[Index % PageSize]; + } + + /// Return the capacity of the vector. I.e. the maximum size it can be + /// expanded to with the resize method without allocating more pages. + [[nodiscard]] size_t capacity() const { + return PageToDataPtrs.size() * PageSize; + } + + /// Return the size of the vector. I.e. the maximum index that can be + /// accessed, i.e. the maximum value which was used as argument of the + /// resize method. + [[nodiscard]] size_t size() const { return Size; } + + /// Resize the vector. Notice that the constructor of the elements will not + /// be invoked until an element of a given page is accessed, at which point + /// all the elements of the page will be constructed. + /// + /// If the new size is smaller than the current size, the elements of the + /// pages that are not needed anymore will be destroyed, however, elements of + /// the last page will not be destroyed. + /// + /// For these reason the usage of this vector is discouraged if you rely + /// on the construction / destructor of the elements to be invoked. + void resize(size_t NewSize) { + if (NewSize == 0) { + clear(); + return; + } + // Handle shrink case: destroy the elements in the pages that are not + // needed anymore and deallocate the pages. + // + // On the other hand, we do not destroy the extra elements in the last page, + // because we might need them later and the logic is simpler if we do not + // destroy them. This means that elements are only destroyed only when the + // page they belong to is destroyed. This is similar to what happens on + // access of the elements of a page, where all the elements of the page are + // constructed not only the one effectively neeeded. + size_t NewLastPage = (NewSize - 1) / PageSize; + if (NewSize < Size) { + // Destruct the elements in the pages that are not needed anymore. + // Notice that we need to do this only if the constructor of the elements + // is not trivial. + if constexpr (!std::is_trivially_destructible_v<T>) { + for (size_t I = NewLastPage + 1, N = PageToDataPtrs.size(); I < N; + ++I) { + T *Page = PageToDataPtrs[I]; + // We need to invoke the destructor on all the elements of the page. + if (Page != nullptr) + std::destroy_n(Page, PageSize); + } + } + for (size_t I = NewLastPage + 1, N = PageToDataPtrs.size(); I < N; ++I) { + T *Page = PageToDataPtrs[I]; + if (Page != nullptr) + Allocator.getPointer()->Deallocate(Page); + // We mark the page invalid, to avoid double deletion. + PageToDataPtrs[I] = nullptr; + } + } + + Size = NewSize; + PageToDataPtrs.resize(NewLastPage + 1); + } + + [[nodiscard]] bool empty() const { return Size == 0; } + + /// Clear the vector, i.e. clear the allocated pages, the whole page + /// lookup index and reset the size. + void clear() { + Size = 0; + for (T *Page : PageToDataPtrs) { + if (Page == nullptr) + continue; + std::destroy_n(Page, PageSize); + // If we do not own the allocator, deallocate the pages one by one. + if (!Allocator.getInt()) + Allocator.getPointer()->Deallocate(Page); + } + // If we own the allocator, simply reset it. + if (Allocator.getInt() == true) + Allocator.getPointer()->Reset(); + PageToDataPtrs.clear(); + } + + /// Iterator on all the elements of the vector + /// which have actually being constructed. + class MaterializedIterator { + const PagedVector *PV; + size_t ElementIdx; + + public: + using iterator_category = std::forward_iterator_tag; + using value_type = T; + using difference_type = std::ptrdiff_t; + using pointer = T *; + using reference = T &; + + MaterializedIterator(PagedVector const *PV, size_t ElementIdx) + : PV(PV), ElementIdx(ElementIdx) {} + + /// Pre-increment operator. + /// + /// When incrementing the iterator, we skip the elements which have not + /// been materialized yet. + MaterializedIterator &operator++() { + ++ElementIdx; + if (ElementIdx % PageSize == 0) { + while (ElementIdx < PV->Size && + PV->PageToDataPtrs[ElementIdx / PageSize] == nullptr) + ElementIdx += PageSize; + if (ElementIdx > PV->Size) + ElementIdx = PV->Size; + } + + return *this; + } + + MaterializedIterator operator++(int) { + MaterializedIterator Copy = *this; + ++*this; + return Copy; + } + + T const &operator*() const { + assert(ElementIdx < PV->Size); + assert(PV->PageToDataPtrs[ElementIdx / PageSize] != nullptr); + T *PagePtr = PV->PageToDataPtrs[ElementIdx / PageSize]; + return PagePtr[ElementIdx % PageSize]; + } + + friend bool operator==(MaterializedIterator const &LHS, + MaterializedIterator const &RHS); + friend bool operator!=(MaterializedIterator const &LHS, + MaterializedIterator const &RHS); + + [[nodiscard]] size_t getIndex() const { return ElementIdx; } + }; + + /// Equality operator. + friend bool operator==(MaterializedIterator const &LHS, + MaterializedIterator const &RHS) { + assert(LHS.PV == RHS.PV); + // Make sure we are comparing either end iterators or iterators pointing + // to materialized elements. + // It should not be possible to build two iterators pointing to non + // materialized elements. + assert(LHS.ElementIdx == LHS.PV->Size || + (LHS.ElementIdx < LHS.PV->Size && + LHS.PV->PageToDataPtrs[LHS.ElementIdx / PageSize] != nullptr)); + assert(RHS.ElementIdx == RHS.PV->Size || + (RHS.ElementIdx < RHS.PV->Size && + RHS.PV->PageToDataPtrs[RHS.ElementIdx / PageSize] != nullptr)); + return LHS.ElementIdx == RHS.ElementIdx; + } + + friend bool operator!=(MaterializedIterator const &LHS, + MaterializedIterator const &RHS) { + return !(LHS == RHS); + } + + /// Iterators over the materialized elements of the vector. + /// + /// This includes all the elements belonging to allocated pages, + /// even if they have not been accessed yet. It's enough to access + /// one element of a page to materialize all the elements of the page. + MaterializedIterator materialized_begin() const { + // Look for the first valid page. + for (size_t ElementIdx = 0; ElementIdx < Size; ElementIdx += PageSize) + if (PageToDataPtrs[ElementIdx / PageSize] != nullptr) + return MaterializedIterator(this, ElementIdx); + + return MaterializedIterator(this, Size); + } + + MaterializedIterator materialized_end() const { + return MaterializedIterator(this, Size); + } + + [[nodiscard]] llvm::iterator_range<MaterializedIterator> + materialized() const { + return {materialized_begin(), materialized_end()}; + } +}; +} // namespace llvm +#endif // LLVM_ADT_PAGEDVECTOR_H diff --git a/llvm/unittests/ADT/CMakeLists.txt b/llvm/unittests/ADT/CMakeLists.txt index c5190255ba7738e..9aa7120f30696da 100644 --- a/llvm/unittests/ADT/CMakeLists.txt +++ b/llvm/unittests/ADT/CMakeLists.txt @@ -51,6 +51,7 @@ add_llvm_unittest(ADTTests MapVectorTest.cpp MoveOnly.cpp PackedVectorTest.cpp + PagedVectorTest.cpp PointerEmbeddedIntTest.cpp PointerIntPairTest.cpp PointerSumTypeTest.cpp diff --git a/llvm/unittests/ADT/PagedVectorTest.cpp b/llvm/unittests/ADT/PagedVectorTest.cpp new file mode 100644 index 000000000000000..c6d7284d60da6aa --- /dev/null +++ b/llvm/unittests/ADT/PagedVectorTest.cpp @@ -0,0 +1,342 @@ +//===- llvm/unittest/ADT/PagedVectorTest.cpp ------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// PagedVector unit tests. +// +//===----------------------------------------------------------------------===// + +#include "llvm/ADT/PagedVector.h" +#include "gtest/gtest.h" +#include <iterator> + +namespace llvm { +TEST(PagedVectorTest, EmptyTest) { + PagedVector<int, 10> V; + EXPECT_EQ(V.empty(), true); + EXPECT_EQ(V.size(), 0ULL); + EXPECT_EQ(V.capacity(), 0ULL); + EXPECT_EQ(V.materialized_begin().getIndex(), 0ULL); + EXPECT_EQ(V.materialized_end().getIndex(), 0ULL); + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 0LL); + + EXPECT_DEATH(V[0], "Index < Size"); + EXPECT_DEATH(PagedVector<int>(nullptr), "Allocator cannot be null"); +} + +TEST(PagedVectorTest, ExpandTest) { + PagedVector<int, 10> V; + V.resize(2); + EXPECT_EQ(V.empty(), false); + EXPECT_EQ(V.size(), 2ULL); + EXPECT_EQ(V.capacity(), 10ULL); + EXPECT_EQ(V.materialized_begin().getIndex(), 2ULL); + EXPECT_EQ(V.materialized_end().getIndex(), 2ULL); + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 0LL); +} + +TEST(PagedVectorTest, FullPageFillingTest) { + PagedVector<int, 10> V; + V.resize(10); + EXPECT_EQ(V.empty(), false); + EXPECT_EQ(V.size(), 10ULL); + EXPECT_EQ(V.capacity(), 10ULL); + for (int I = 0; I < 10; ++I) { + V[I] = I; + } + EXPECT_EQ(V.empty(), false); + EXPECT_EQ(V.size(), 10ULL); + EXPECT_EQ(V.capacity(), 10ULL); + EXPECT_EQ(V.materialized_begin().getIndex(), 0ULL); + EXPECT_EQ(V.materialized_end().getIndex(), 10ULL); + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 10LL); + for (int I = 0; I < 10; ++I) { + EXPECT_EQ(V[I], I); + } +} + +TEST(PagedVectorTest, HalfPageFillingTest) { + PagedVector<int, 10> V; + V.resize(5); + EXPECT_EQ(V.empty(), false); + EXPECT_EQ(V.size(), 5ULL); + EXPECT_EQ(V.capacity(), 10ULL); + for (int I = 0; I < 5; ++I) { + V[I] = I; + } + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 5LL); + for (int I = 0; I < 5; ++I) { + EXPECT_EQ(V[I], I); + } + for (int I = 5; I < 10; ++I) { + EXPECT_DEATH(V[I], "Index < Size"); + } +} + +TEST(PagedVectorTest, FillFullMultiPageTest) { + PagedVector<int, 10> V; + V.resize(20); + EXPECT_EQ(V.empty(), false); + EXPECT_EQ(V.size(), 20ULL); + EXPECT_EQ(V.capacity(), 20ULL); + for (int I = 0; I < 20; ++I) { + V[I] = I; + } + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 20LL); + for (auto MI = V.materialized_begin(), ME = V.materialized_end(); MI != ME; + ++MI) { + EXPECT_EQ(*MI, std::distance(V.materialized_begin(), MI)); + } +} + +TEST(PagedVectorTest, FillHalfMultiPageTest) { + PagedVector<int, 10> V; + V.resize(20); + EXPECT_EQ(V.empty(), false); + EXPECT_EQ(V.size(), 20ULL); + EXPECT_EQ(V.capacity(), 20ULL); + for (int I = 0; I < 5; ++I) { + V[I] = I; + } + for (int I = 10; I < 15; ++I) { + V[I] = I; + } + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 20LL); + for (int I = 0; I < 5; ++I) { + EXPECT_EQ(V[I], I); + } + for (int I = 10; I < 15; ++I) { + EXPECT_EQ(V[I], I); + } +} + +TEST(PagedVectorTest, FillLastMultiPageTest) { + PagedVector<int, 10> V; + V.resize(20); + EXPECT_EQ(V.empty(), false); + EXPECT_EQ(V.size(), 20ULL); + EXPECT_EQ(V.capacity(), 20ULL); + for (int I = 10; I < 15; ++I) { + V[I] = I; + } + for (int I = 10; I < 15; ++I) { + EXPECT_EQ(V[I], I); + } + + // Since we fill the last page only, the materialized vector + // should contain only the last page. + int J = 10; + for (auto MI = V.materialized_begin(), ME = V.materialized_end(); MI != ME; + ++MI) { + if (J < 15) { + EXPECT_EQ(*MI, J); + } else { + EXPECT_EQ(*MI, 0); + } + ++J; + } + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 10LL); +} + +// Filling the first element of all the pages +// will allocate all of them +TEST(PagedVectorTest, FillSparseMultiPageTest) { + PagedVector<int, 10> V; + V.resize(100); + EXPECT_EQ(V.empty(), false); + EXPECT_EQ(V.size(), 100ULL); + EXPECT_EQ(V.capacity(), 100ULL); + for (int I = 0; I < 10; ++I) { + V[I * 10] = I; + } + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 100LL); + for (int I = 0; I < 100; ++I) { + if (I % 10 == 0) { + EXPECT_EQ(V[I], I / 10); + } else { + EXPECT_EQ(V[I], 0); + } + } +} + +struct TestHelper { + int A = -1; +}; + +// Use this to count how many times the constructor / destructor are called +struct TestHelper2 { + int A = -1; + static int constructed; + static int destroyed; + + TestHelper2() { constructed++; } + ~TestHelper2() { destroyed++; } +}; + +int TestHelper2::constructed = 0; +int TestHelper2::destroyed = 0; + +TEST(PagedVectorTest, FillNonTrivialConstructor) { + PagedVector<TestHelper, 10> V; + V.resize(10); + EXPECT_EQ(V.empty(), false); + EXPECT_EQ(V.size(), 10ULL); + EXPECT_EQ(V.capacity(), 10ULL); + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 0LL); + for (int I = 0; I < 10; ++I) { + EXPECT_EQ(V[I].A, -1); + } + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 10LL); +} + +// Elements are constructed, destructed in pages, so we expect +// the number of constructed / destructed elements to be a multiple of the +// page size and the constructor is invoked when the page is actually accessed +// the first time. +TEST(PagedVectorTest, FillNonTrivialConstructorDestructor) { + PagedVector<TestHelper2, 10> V; + V.resize(19); + EXPECT_EQ(TestHelper2::constructed, 0); + EXPECT_EQ(V.empty(), false); + EXPECT_EQ(V.size(), 19ULL); + EXPECT_EQ(V.capacity(), 20ULL); + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 0LL); + EXPECT_EQ(V[0].A, -1); + EXPECT_EQ(TestHelper2::constructed, 10); + + for (int I = 0; I < 10; ++I) { + EXPECT_EQ(V[I].A, -1); + EXPECT_EQ(TestHelper2::constructed, 10); + } + for (int I = 10; I < 11; ++I) { + EXPECT_EQ(V[I].A, -1); + EXPECT_EQ(TestHelper2::constructed, 20); + } + for (int I = 0; I < 19; ++I) { + EXPECT_EQ(V[I].A, -1); + EXPECT_EQ(TestHelper2::constructed, 20); + } + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 19LL); + // We initialise the whole page, not just the materialized part + // EXPECT_EQ(TestHelper2::constructed, 20); + V.resize(18); + EXPECT_EQ(TestHelper2::destroyed, 0); + V.resize(1); + EXPECT_EQ(TestHelper2::destroyed, 10); + V.resize(0); + EXPECT_EQ(TestHelper2::destroyed, 20); + + // Add a few empty pages so that we can test that the destructor + // is called only for the materialized pages + V.resize(50); + V[49].A = 0; + EXPECT_EQ(TestHelper2::constructed, 30); + EXPECT_EQ(TestHelper2::destroyed, 20); + EXPECT_EQ(V[49].A, 0); + V.resize(0); + EXPECT_EQ(TestHelper2::destroyed, 30); +} + +TEST(PagedVectorTest, ShrinkTest) { + PagedVector<int, 10> V; + V.resize(20); + EXPECT_EQ(V.empty(), false); + EXPECT_EQ(V.size(), 20ULL); + EXPECT_EQ(V.capacity(), 20ULL); + for (int I = 0; I < 20; ++I) { + V[I] = I; + } + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 20LL); + V.resize(9); + EXPECT_EQ(V.empty(), false); + EXPECT_EQ(V.size(), 9ULL); + EXPECT_EQ(V.capacity(), 10ULL); + for (int I = 0; I < 9; ++I) { + EXPECT_EQ(V[I], I); + } + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 9LL); + V.resize(0); + EXPECT_EQ(V.empty(), true); + EXPECT_EQ(V.size(), 0ULL); + EXPECT_EQ(V.capacity(), 0ULL); + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 0LL); + EXPECT_DEATH(V[0], "Index < Size"); +} + +TEST(PagedVectorTest, FunctionalityTest) { + PagedVector<int, 10> V; + EXPECT_EQ(V.empty(), true); + + // Next ten numbers are 10..19 + V.resize(2); + EXPECT_EQ(V.empty(), false); + V.resize(10); + V.resize(20); + V.resize(30); + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 0LL); + + EXPECT_EQ(V.size(), 30ULL); + for (int I = 0; I < 10; ++I) { + V[I] = I; + } + for (int I = 0; I < 10; ++I) { + EXPECT_EQ(V[I], I); + } + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 10LL); + for (int I = 20; I < 30; ++I) { + V[I] = I; + } + for (int I = 20; I < 30; ++I) { + EXPECT_EQ(V[I], I); + } + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 20LL); + + for (int I = 10; I < 20; ++I) { + V[I] = I; + } + for (int I = 10; I < 20; ++I) { + EXPECT_EQ(V[I], I); + } + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 30LL); + V.resize(35); + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 30LL); + for (int I = 30; I < 35; ++I) { + V[I] = I; + } + EXPECT_EQ(std::distance(V.materialized_begin(), V.materialized_end()), 35LL); + EXPECT_EQ(V.size(), 35ULL); + EXPECT_EQ(V.capacity(), 40ULL); + V.resize(37); + for (int I = 30; I < 37; ++I) { + V[I] = I; + } + EXPECT_EQ(V.size(), 37ULL); + EXPECT_EQ(V.capacity(), 40ULL); + for (int I = 0; I < 37; ++I) { + EXPECT_EQ(V[I], I); + } + + V.resize(41); + V[40] = 40; + EXPECT_EQ(V.size(), 41ULL); + EXPECT_EQ(V.capacity(), 50ULL); + for (int I = 0; I < 36; ++I) { + EXPECT_EQ(V[I], I); + } + for (int I = 37; I < 40; ++I) { + EXPECT_EQ(V[I], 0); + } + V.resize(50); + EXPECT_EQ(V.capacity(), 50ULL); + EXPECT_EQ(V.size(), 50ULL); + EXPECT_EQ(V[40], 40); + V.resize(50ULL); + V.clear(); + EXPECT_EQ(V.size(), 0ULL); + EXPECT_EQ(V.capacity(), 0ULL); +} +} // namespace llvm >From 2aaae647c57caeb8f111fcd414cfead839feae87 Mon Sep 17 00:00:00 2001 From: Giulio Eulisse <10544+...@users.noreply.github.com> Date: Thu, 28 Sep 2023 11:21:35 +0200 Subject: [PATCH 2/5] Update llvm/include/llvm/ADT/PagedVector.h Co-authored-by: Richard Smith <rich...@metafoo.co.uk> --- llvm/include/llvm/ADT/PagedVector.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/llvm/include/llvm/ADT/PagedVector.h b/llvm/include/llvm/ADT/PagedVector.h index 380da3e358e2408..6e5f9b6b2d39bf0 100644 --- a/llvm/include/llvm/ADT/PagedVector.h +++ b/llvm/include/llvm/ADT/PagedVector.h @@ -124,7 +124,7 @@ template <typename T, size_t PageSize = 1024 / sizeof(T)> class PagedVector { return; } // Handle shrink case: destroy the elements in the pages that are not - // needed anymore and deallocate the pages. + // needed any more and deallocate the pages. // // On the other hand, we do not destroy the extra elements in the last page, // because we might need them later and the logic is simpler if we do not >From 4e8d9c45dd7387b8cb539af69d740b4c2f6115e9 Mon Sep 17 00:00:00 2001 From: Giulio Eulisse <10544+...@users.noreply.github.com> Date: Thu, 28 Sep 2023 11:22:07 +0200 Subject: [PATCH 3/5] Update llvm/include/llvm/ADT/PagedVector.h Co-authored-by: Richard Smith <rich...@metafoo.co.uk> --- llvm/include/llvm/ADT/PagedVector.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/llvm/include/llvm/ADT/PagedVector.h b/llvm/include/llvm/ADT/PagedVector.h index 6e5f9b6b2d39bf0..6609646bdb5eeed 100644 --- a/llvm/include/llvm/ADT/PagedVector.h +++ b/llvm/include/llvm/ADT/PagedVector.h @@ -131,7 +131,7 @@ template <typename T, size_t PageSize = 1024 / sizeof(T)> class PagedVector { // destroy them. This means that elements are only destroyed only when the // page they belong to is destroyed. This is similar to what happens on // access of the elements of a page, where all the elements of the page are - // constructed not only the one effectively neeeded. + // constructed not only the one effectively needed. size_t NewLastPage = (NewSize - 1) / PageSize; if (NewSize < Size) { // Destruct the elements in the pages that are not needed anymore. >From 764d2670e3b69fd671845eb5b5eb2ad552a05cf4 Mon Sep 17 00:00:00 2001 From: Giulio Eulisse <10544+...@users.noreply.github.com> Date: Thu, 28 Sep 2023 11:22:17 +0200 Subject: [PATCH 4/5] Update llvm/include/llvm/ADT/PagedVector.h Co-authored-by: Richard Smith <rich...@metafoo.co.uk> --- llvm/include/llvm/ADT/PagedVector.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/llvm/include/llvm/ADT/PagedVector.h b/llvm/include/llvm/ADT/PagedVector.h index 6609646bdb5eeed..eeb427610300559 100644 --- a/llvm/include/llvm/ADT/PagedVector.h +++ b/llvm/include/llvm/ADT/PagedVector.h @@ -128,7 +128,7 @@ template <typename T, size_t PageSize = 1024 / sizeof(T)> class PagedVector { // // On the other hand, we do not destroy the extra elements in the last page, // because we might need them later and the logic is simpler if we do not - // destroy them. This means that elements are only destroyed only when the + // destroy them. This means that elements are only destroyed when the // page they belong to is destroyed. This is similar to what happens on // access of the elements of a page, where all the elements of the page are // constructed not only the one effectively needed. >From 329afbf54d87aeaf9675a8a6c89d798c98508a3f Mon Sep 17 00:00:00 2001 From: Giulio Eulisse <10544+...@users.noreply.github.com> Date: Thu, 28 Sep 2023 11:22:31 +0200 Subject: [PATCH 5/5] Update llvm/include/llvm/ADT/PagedVector.h Co-authored-by: Richard Smith <rich...@metafoo.co.uk> --- llvm/include/llvm/ADT/PagedVector.h | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/llvm/include/llvm/ADT/PagedVector.h b/llvm/include/llvm/ADT/PagedVector.h index eeb427610300559..92bfa8c587735a9 100644 --- a/llvm/include/llvm/ADT/PagedVector.h +++ b/llvm/include/llvm/ADT/PagedVector.h @@ -134,7 +134,7 @@ template <typename T, size_t PageSize = 1024 / sizeof(T)> class PagedVector { // constructed not only the one effectively needed. size_t NewLastPage = (NewSize - 1) / PageSize; if (NewSize < Size) { - // Destruct the elements in the pages that are not needed anymore. + // Destroy the elements in the pages that are not needed anymore. // Notice that we need to do this only if the constructor of the elements // is not trivial. if constexpr (!std::is_trivially_destructible_v<T>) { _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits