Logo ROOT  
Reference Guide
 
Loading...
Searching...
No Matches
RPagePool.hxx
Go to the documentation of this file.
1/// \file ROOT/RPagePool.hxx
2/// \ingroup NTuple
3/// \author Jakob Blomer <jblomer@cern.ch>
4/// \date 2018-10-09
5
6/*************************************************************************
7 * Copyright (C) 1995-2019, Rene Brun and Fons Rademakers. *
8 * All rights reserved. *
9 * *
10 * For the licensing terms see $ROOTSYS/LICENSE. *
11 * For the list of contributors see $ROOTSYS/README/CREDITS. *
12 *************************************************************************/
13
14#ifndef ROOT_RPagePool
15#define ROOT_RPagePool
16
17#include <ROOT/RPage.hxx>
19#include <ROOT/RNTupleUtil.hxx>
20
21#include <cstddef>
22#include <map>
23#include <mutex>
24#include <typeindex>
25#include <typeinfo>
26#include <unordered_map>
27#include <unordered_set>
28#include <vector>
29
30namespace ROOT {
31namespace Internal {
32
33// clang-format off
34/**
35\class ROOT::Internal::RPagePool
36\ingroup NTuple
37\brief A thread-safe cache of pages loaded from the page source.
38
39The page pool is used as a cache for pages loaded from a page source.
40In this way, identical page needed at the same time, only need to be loaded once.
41Page sources also use the page pool to stage (preload) pages unsealed by IMT tasks.
42*/
43// clang-format on
44class RPagePool {
45 friend class RPageRef;
46
47public:
48 // Search key for a set of pages covering the same column and in-memory target type.
49 // Within the set of pages, one needs to find the page of a given index.
50 struct RKey {
52 std::type_index fInMemoryType = std::type_index(typeid(void));
53
54 bool operator==(const RKey &other) const
55 {
56 return this->fColumnId == other.fColumnId && this->fInMemoryType == other.fInMemoryType;
57 }
58
59 bool operator!=(const RKey &other) const { return !(*this == other); }
60 };
61
62private:
63 /// Hash function to be used in the unordered map fLookupByKey
64 struct RKeyHasher {
65 /// Like boost::hash_combine
66 std::size_t operator()(const RKey &k) const
67 {
68 auto seed = std::hash<ROOT::DescriptorId_t>()(k.fColumnId);
69 return seed ^ (std::hash<std::type_index>()(k.fInMemoryType) + 0x9e3779b9 + (seed << 6) + (seed >> 2));
70 }
71 };
72
73 /// Every page in the page pool is annotated with a search key and a reference counter.
74 struct REntry {
77 std::int64_t fRefCounter = 0;
78 };
79
80 /// Used in fLookupByKey to store both the absolute and the cluster-local page index of the referenced page.
81 /// This allows to do binary search for one or the other. Note that elements in fLookupByKey must have
82 /// _both_ values to be valid. If RPagePosition is used as a search key, only one of the two needs to be set.
86
87 bool operator<(const RPagePosition &other) const
88 {
90 (other.fGlobalFirstElement != ROOT::kInvalidNTupleIndex)) {
91 return fGlobalFirstElement < other.fGlobalFirstElement;
92 }
93
96 assert(other.fClusterFirstElement.GetClusterId() != ROOT::kInvalidDescriptorId &&
97 other.fClusterFirstElement.GetIndexInCluster() != ROOT::kInvalidNTupleIndex);
98 if (fClusterFirstElement.GetClusterId() == other.fClusterFirstElement.GetClusterId())
99 return fClusterFirstElement.GetIndexInCluster() < other.fClusterFirstElement.GetIndexInCluster();
100 return fClusterFirstElement.GetClusterId() < other.fClusterFirstElement.GetClusterId();
101 }
102
103 // Constructor used to store a page in fLookupByKey
104 explicit RPagePosition(const RPage &page)
105 : fGlobalFirstElement(page.GetGlobalRangeFirst()),
106 fClusterFirstElement({page.GetClusterInfo().GetId(), page.GetLocalRangeFirst()})
107 {
108 }
109
110 // Search key constructors
113 };
114
115 std::vector<REntry> fEntries; ///< All cached pages in the page pool
116 /// Used in ReleasePage() to find the page index in fPages
117 std::unordered_map<void *, std::size_t> fLookupByBuffer;
118 /// Used in GetPage() to find the right page in fEntries. Lookup for the key (pair of on-disk and in-memory type)
119 /// takes place in O(1). The selected pages are identified by index into the fEntries vector (map's value)
120 /// and sorted by the position of the page in the column (map's key). Thus, access to pages of the page set
121 /// has logarithmic complexity.
122 std::unordered_map<RKey, std::map<RPagePosition, std::size_t>, RKeyHasher> fLookupByKey;
123 /// Remembers pages with reference counter 0, organized by the page's cluster id. The pages are identified
124 /// by their page buffer address. The fLookupByBuffer map can be used to resolve the address to a page.
125 /// Once a page gets used, it is removed from the unused pages list. Evict will remove all unused pages
126 /// from a given cluster id.
127 std::unordered_map<ROOT::DescriptorId_t, std::unordered_set<void *>> fUnusedPages;
128 std::mutex fLock; ///< The page pool is accessed concurrently due to parallel decompression
129
130 /// Add a new page to the fLookupByBuffer and fLookupByKey data structures.
131 REntry &AddPage(RPage page, const RKey &key, std::int64_t initialRefCounter);
132
133 /// Give back a page to the pool and decrease the reference counter. There must not be any pointers anymore into
134 /// this page. If the reference counter drops to zero, the page pool might decide to call the deleter given in
135 /// during registration. Called by the RPageRef destructor.
136 void ReleasePage(const RPage &page);
137
138 /// Called by GetPage(), when the reference counter increases from zero to one
139 void RemoveFromUnusedPages(const RPage &page);
140
141 /// Called both by ReleasePage() and by Evict() to remove an unused page from the pool
142 void ErasePage(std::size_t entryIdx, decltype(fLookupByBuffer)::iterator lookupByBufferItr);
143
144public:
145 RPagePool() = default;
146 RPagePool(const RPagePool&) = delete;
147 RPagePool& operator =(const RPagePool&) = delete;
148 ~RPagePool() = default;
149
150 /// Adds a new page to the pool. Upon registration, the page pool takes ownership of the page's memory.
151 /// The new page has its reference counter set to 1.
153 /// Like RegisterPage() but the reference counter is initialized to 0. In addition, the page is added
154 /// to the set of unused pages of the page's cluster (see Evict()).
155 void PreloadPage(RPage page, RKey key);
156 /// Removes unused pages (pages with reference counter 0) from the page pool. Users of PreloadPage() should
157 /// use Evict() appropriately to avoid accumulation of unused pages.
159 /// Tries to find the page corresponding to column and index in the cache. If the page is found, its reference
160 /// counter is increased
163};
164
165// clang-format off
166/**
167\class ROOT::Internal::RPageRef
168\ingroup NTuple
169\brief Reference to a page stored in the page pool
170
171The referenced page knows about its page pool and decreases the reference counter on destruction.
172*/
173// clang-format on
174class RPageRef {
175 friend class RPagePool;
176
179
180 // Called as delegated constructor and directly by the page pool
182 {
183 // We leave the fPage::fPageAllocator member unset (nullptr), since fPage is a non-owning view on the page
184 fPage.fBuffer = page.fBuffer;
185 fPage.fElementSize = page.fElementSize;
186 fPage.fNElements = page.fNElements;
187 fPage.fMaxElements = page.fMaxElements;
188 fPage.fRangeFirst = page.fRangeFirst;
189 fPage.fClusterInfo = page.fClusterInfo;
190 }
191
192public:
193 RPageRef() = default;
194 RPageRef(const RPageRef &other) = delete;
195 RPageRef &operator=(const RPageRef &other) = delete;
196
198
200 {
201 if (this != &other) {
202 std::swap(fPage, other.fPage);
203 std::swap(fPagePool, other.fPagePool);
204 }
205 return *this;
206 }
207
209 {
210 if (fPagePool)
212 }
213
214 const RPage &Get() const { return fPage; }
215};
216
217} // namespace Internal
218} // namespace ROOT
219
220#endif
ROOT::Detail::TRangeCast< T, true > TRangeDynCast
TRangeDynCast is an adapter class that allows the typed iteration through a TCollection.
A thread-safe cache of pages loaded from the page source.
Definition RPagePool.hxx:44
void ErasePage(std::size_t entryIdx, decltype(fLookupByBuffer)::iterator lookupByBufferItr)
Called both by ReleasePage() and by Evict() to remove an unused page from the pool.
Definition RPagePool.cxx:63
void Evict(ROOT::DescriptorId_t clusterId)
Removes unused pages (pages with reference counter 0) from the page pool.
REntry & AddPage(RPage page, const RKey &key, std::int64_t initialRefCounter)
Add a new page to the fLookupByBuffer and fLookupByKey data structures.
Definition RPagePool.cxx:24
std::unordered_map< ROOT::DescriptorId_t, std::unordered_set< void * > > fUnusedPages
Remembers pages with reference counter 0, organized by the page's cluster id.
RPagePool(const RPagePool &)=delete
std::mutex fLock
The page pool is accessed concurrently due to parallel decompression.
RPageRef GetPage(RKey key, ROOT::NTupleSize_t globalIndex)
Tries to find the page corresponding to column and index in the cache.
std::unordered_map< RKey, std::map< RPagePosition, std::size_t >, RKeyHasher > fLookupByKey
Used in GetPage() to find the right page in fEntries.
void PreloadPage(RPage page, RKey key)
Like RegisterPage() but the reference counter is initialized to 0.
Definition RPagePool.cxx:55
RPageRef RegisterPage(RPage page, RKey key)
Adds a new page to the pool.
Definition RPagePool.cxx:49
RPagePool & operator=(const RPagePool &)=delete
void RemoveFromUnusedPages(const RPage &page)
Called by GetPage(), when the reference counter increases from zero to one.
std::unordered_map< void *, std::size_t > fLookupByBuffer
Used in ReleasePage() to find the page index in fPages.
std::vector< REntry > fEntries
All cached pages in the page pool.
void ReleasePage(const RPage &page)
Give back a page to the pool and decrease the reference counter.
Definition RPagePool.cxx:88
Reference to a page stored in the page pool.
RPageRef(RPageRef &&other)
RPageRef & operator=(const RPageRef &other)=delete
RPageRef & operator=(RPageRef &&other)
RPageRef(const RPage &page, RPagePool *pagePool)
const RPage & Get() const
RPageRef(const RPageRef &other)=delete
A page is a slice of a column that is mapped into memory.
Definition RPage.hxx:44
RClusterInfo fClusterInfo
Definition RPage.hxx:76
std::uint32_t fNElements
Definition RPage.hxx:72
std::uint32_t fMaxElements
The capacity of the page in number of elements.
Definition RPage.hxx:74
ROOT::NTupleSize_t fRangeFirst
Definition RPage.hxx:75
std::uint32_t fElementSize
Definition RPage.hxx:71
Addresses a column element or field item relative to a particular cluster, instead of a global NTuple...
ROOT::NTupleSize_t GetIndexInCluster() const
ROOT::DescriptorId_t GetClusterId() const
tbb::task_arena is an alias of tbb::interface7::task_arena, which doesn't allow to forward declare tb...
std::uint64_t DescriptorId_t
Distriniguishes elements of the same type within a descriptor, e.g. different fields.
constexpr NTupleSize_t kInvalidNTupleIndex
std::uint64_t NTupleSize_t
Integer type long enough to hold the maximum number of entries in a column.
constexpr DescriptorId_t kInvalidDescriptorId
Every page in the page pool is annotated with a search key and a reference counter.
Definition RPagePool.hxx:74
Hash function to be used in the unordered map fLookupByKey.
Definition RPagePool.hxx:64
std::size_t operator()(const RKey &k) const
Like boost::hash_combine.
Definition RPagePool.hxx:66
ROOT::DescriptorId_t fColumnId
Definition RPagePool.hxx:51
bool operator!=(const RKey &other) const
Definition RPagePool.hxx:59
bool operator==(const RKey &other) const
Definition RPagePool.hxx:54
Used in fLookupByKey to store both the absolute and the cluster-local page index of the referenced pa...
Definition RPagePool.hxx:83
bool operator<(const RPagePosition &other) const
Definition RPagePool.hxx:87
RPagePosition(ROOT::NTupleSize_t globalIndex)
RPagePosition(RNTupleLocalIndex localIndex)