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