================
@@ -1625,6 +1625,35 @@ 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[]`` or the ``at()``
+method. This is useful for the case in which the number of elements is known
in advance and
+their actual initialization is expensive and sparse so that it's only done
lazily 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 integer per page and one extra indirection when
accessing elements with their positional
+index.
+
+In order to maximise 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 integer per page might
become too high) and not too big
+(otherwise the memory is wasted if the page is not fully used).
+
+The PagedVector can only be expanded at the end, and it's not possible to
shrink it, to keep the implementation
+simple and not give the false hope that the resize operation is cheap.
+
+Moreover, while retaining the oder of the elements based on their insertion
index, like a vector, iterating over
----------------
zygoloid wrote:
Typo "oder"
https://github.com/llvm/llvm-project/pull/66430
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
