VTK  9.3.1
vtkSMPThreadLocalBackend.h
Go to the documentation of this file.
1 // SPDX-FileCopyrightText: Copyright (c) Ken Martin, Will Schroeder, Bill Lorensen
2 // SPDX-License-Identifier: BSD-3-Clause
3 
4 // Thread Specific Storage is implemented as a Hash Table, with the Thread Id
5 // as the key and a Pointer to the data as the value. The Hash Table implements
6 // Open Addressing with Linear Probing. A fixed-size array (HashTableArray) is
7 // used as the hash table. The size of this array is allocated to be large
8 // enough to store thread specific data for all the threads with a Load Factor
9 // of 0.5. In case the number of threads changes dynamically and the current
10 // array is not able to accommodate more entries, a new array is allocated that
11 // is twice the size of the current array. To avoid rehashing and blocking the
12 // threads, a rehash is not performed immediately. Instead, a linked list of
13 // hash table arrays is maintained with the current array at the root and older
14 // arrays along the list. All lookups are sequentially performed along the
15 // linked list. If the root array does not have an entry, it is created for
16 // faster lookup next time. The ThreadSpecific::GetStorage() function is thread
17 // safe and only blocks when a new array needs to be allocated, which should be
18 // rare.
19 //
20 // This implementation is the same as the OpenMP equivalent but with std::mutex
21 // and std::lock_guard instead of omp_lock_t and custom lock guard.
22 
23 #ifndef STDThreadvtkSMPThreadLocalBackend_h
24 #define STDThreadvtkSMPThreadLocalBackend_h
25 
26 #include "vtkCommonCoreModule.h" // For export macro
27 #include "vtkSystemIncludes.h"
28 
29 #include <atomic>
30 #include <cstdint> // For uint_fast32_t
31 #include <mutex> // std::mutex, std::lock_guard
32 #include <thread>
33 
34 namespace vtk
35 {
36 namespace detail
37 {
38 namespace smp
39 {
40 namespace STDThread
41 {
42 VTK_ABI_NAMESPACE_BEGIN
43 
44 typedef size_t ThreadIdType;
45 typedef uint_fast32_t HashType;
46 typedef void* StoragePointerType;
47 
48 struct Slot
49 {
50  std::atomic<ThreadIdType> ThreadId;
51  std::mutex Mutex;
52  StoragePointerType Storage;
53 
54  Slot();
55  ~Slot() = default;
56 
57 private:
58  // not copyable
59  Slot(const Slot&);
60  void operator=(const Slot&);
61 };
62 
64 {
65  size_t Size, SizeLg;
66  std::atomic<size_t> NumberOfEntries;
69 
70  explicit HashTableArray(size_t sizeLg);
72 
73 private:
74  // disallow copying
76  void operator=(const HashTableArray&);
77 };
78 
79 class VTKCOMMONCORE_EXPORT ThreadSpecific final
80 {
81 public:
82  explicit ThreadSpecific(unsigned numThreads);
83  ~ThreadSpecific();
84 
85  StoragePointerType& GetStorage();
86  size_t GetSize() const;
87 
88 private:
89  std::atomic<HashTableArray*> Root;
90  std::atomic<size_t> Size;
91  std::mutex Mutex;
92 
94 };
95 
97 {
98 public:
100  : ThreadSpecificStorage(nullptr)
101  , CurrentArray(nullptr)
102  , CurrentSlot(0)
103  {
104  }
105 
107  {
108  this->ThreadSpecificStorage = &threadSpecifc;
109  }
110 
111  void SetToBegin()
112  {
113  this->CurrentArray = this->ThreadSpecificStorage->Root;
114  this->CurrentSlot = 0;
115  if (!this->CurrentArray->Slots->Storage)
116  {
117  this->Forward();
118  }
119  }
120 
121  void SetToEnd()
122  {
123  this->CurrentArray = nullptr;
124  this->CurrentSlot = 0;
125  }
126 
127  bool GetInitialized() const { return this->ThreadSpecificStorage != nullptr; }
128 
129  bool GetAtEnd() const { return this->CurrentArray == nullptr; }
130 
131  void Forward()
132  {
133  while (true)
134  {
135  if (++this->CurrentSlot >= this->CurrentArray->Size)
136  {
137  this->CurrentArray = this->CurrentArray->Prev;
138  this->CurrentSlot = 0;
139  if (!this->CurrentArray)
140  {
141  break;
142  }
143  }
144  Slot* slot = this->CurrentArray->Slots + this->CurrentSlot;
145  if (slot->Storage)
146  {
147  break;
148  }
149  }
150  }
151 
152  StoragePointerType& GetStorage() const
153  {
154  Slot* slot = this->CurrentArray->Slots + this->CurrentSlot;
155  return slot->Storage;
156  }
157 
159  {
160  return (this->ThreadSpecificStorage == it.ThreadSpecificStorage) &&
161  (this->CurrentArray == it.CurrentArray) && (this->CurrentSlot == it.CurrentSlot);
162  }
163 
164 private:
165  ThreadSpecific* ThreadSpecificStorage;
166  HashTableArray* CurrentArray;
167  size_t CurrentSlot;
168 };
169 
170 VTK_ABI_NAMESPACE_END
171 } // STDThread;
172 } // namespace smp
173 } // namespace detail
174 } // namespace vtk
175 
176 #endif
177 /* VTK-HeaderTest-Exclude: INCLUDES:CLASSES */
std::atomic< ThreadIdType > ThreadId
Specialization of tuple ranges and iterators for vtkAOSDataArrayTemplate.
bool operator==(const ThreadSpecificStorageIterator &it) const