Open3D (C++ API)  0.18.0+252c867
TBBHashBackend.h
Go to the documentation of this file.
1 // ----------------------------------------------------------------------------
2 // - Open3D: www.open3d.org -
3 // ----------------------------------------------------------------------------
4 // Copyright (c) 2018-2023 www.open3d.org
5 // SPDX-License-Identifier: MIT
6 // ----------------------------------------------------------------------------
7 
8 #pragma once
9 
10 #include <tbb/concurrent_unordered_map.h>
11 
12 #include <limits>
13 #include <unordered_map>
14 
18 
19 namespace open3d {
20 namespace core {
21 template <typename Key, typename Hash, typename Eq>
23 public:
24  TBBHashBackend(int64_t init_capacity,
25  int64_t key_dsize,
26  const std::vector<int64_t>& value_dsizes,
27  const Device& device);
29 
30  void Reserve(int64_t capacity) override;
31 
32  void Insert(const void* input_keys,
33  const std::vector<const void*>& input_values_soa,
34  buf_index_t* output_buf_indices,
35  bool* output_masks,
36  int64_t count) override;
37 
38  void Find(const void* input_keys,
39  buf_index_t* output_buf_indices,
40  bool* output_masks,
41  int64_t count) override;
42 
43  void Erase(const void* input_keys,
44  bool* output_masks,
45  int64_t count) override;
46 
47  int64_t GetActiveIndices(buf_index_t* output_indices) override;
48 
49  void Clear() override;
50 
51  int64_t Size() const override;
52  int64_t GetBucketCount() const override;
53  std::vector<int64_t> BucketSizes() const override;
54  float LoadFactor() const override;
55 
56  std::shared_ptr<tbb::concurrent_unordered_map<Key, buf_index_t, Hash, Eq>>
57  GetImpl() const {
58  return impl_;
59  }
60 
61  void Allocate(int64_t capacity) override;
62  void Free() override{};
63 
64 protected:
65  std::shared_ptr<tbb::concurrent_unordered_map<Key, buf_index_t, Hash, Eq>>
67 
68  std::shared_ptr<CPUHashBackendBufferAccessor> buffer_accessor_;
69 };
70 
71 template <typename Key, typename Hash, typename Eq>
73  int64_t init_capacity,
74  int64_t key_dsize,
75  const std::vector<int64_t>& value_dsizes,
76  const Device& device)
77  : DeviceHashBackend(init_capacity, key_dsize, value_dsizes, device) {
78  Allocate(init_capacity);
79 }
80 
81 template <typename Key, typename Hash, typename Eq>
83 
84 template <typename Key, typename Hash, typename Eq>
86  return impl_->size();
87 }
88 
89 template <typename Key, typename Hash, typename Eq>
90 void TBBHashBackend<Key, Hash, Eq>::Find(const void* input_keys,
91  buf_index_t* output_buf_indices,
92  bool* output_masks,
93  int64_t count) {
94  const Key* input_keys_templated = static_cast<const Key*>(input_keys);
95 
96 #pragma omp parallel for num_threads(utility::EstimateMaxThreads())
97  for (int64_t i = 0; i < count; ++i) {
98  const Key& key = input_keys_templated[i];
99 
100  auto iter = impl_->find(key);
101  bool flag = (iter != impl_->end());
102  output_masks[i] = flag;
103  output_buf_indices[i] = flag ? iter->second : 0;
104  }
105 }
106 
107 template <typename Key, typename Hash, typename Eq>
108 void TBBHashBackend<Key, Hash, Eq>::Erase(const void* input_keys,
109  bool* output_masks,
110  int64_t count) {
111  const Key* input_keys_templated = static_cast<const Key*>(input_keys);
112 
113  for (int64_t i = 0; i < count; ++i) {
114  const Key& key = input_keys_templated[i];
115 
116  auto iter = impl_->find(key);
117  bool flag = (iter != impl_->end());
118  output_masks[i] = flag;
119  if (flag) {
120  buffer_accessor_->DeviceFree(iter->second);
121  impl_->unsafe_erase(iter);
122  }
123  }
124 }
125 
126 template <typename Key, typename Hash, typename Eq>
128  buf_index_t* output_buf_indices) {
129  int64_t count = impl_->size();
130  int64_t i = 0;
131  for (auto iter = impl_->begin(); iter != impl_->end(); ++iter, ++i) {
132  output_buf_indices[i] = static_cast<int64_t>(iter->second);
133  }
134 
135  return count;
136 }
137 
138 template <typename Key, typename Hash, typename Eq>
140  impl_->clear();
141  this->buffer_->ResetHeap();
142 }
143 
144 template <typename Key, typename Hash, typename Eq>
146  impl_->rehash(std::ceil(capacity / impl_->max_load_factor()));
147 }
148 
149 template <typename Key, typename Hash, typename Eq>
151  return impl_->unsafe_bucket_count();
152 }
153 
154 template <typename Key, typename Hash, typename Eq>
155 std::vector<int64_t> TBBHashBackend<Key, Hash, Eq>::BucketSizes() const {
156  int64_t bucket_count = impl_->unsafe_bucket_count();
157  std::vector<int64_t> ret;
158  for (int64_t i = 0; i < bucket_count; ++i) {
159  ret.push_back(impl_->unsafe_bucket_size(i));
160  }
161  return ret;
162 }
163 
164 template <typename Key, typename Hash, typename Eq>
166  return impl_->load_factor();
167 }
168 
169 template <typename Key, typename Hash, typename Eq>
171  const void* input_keys,
172  const std::vector<const void*>& input_values_soa,
173  buf_index_t* output_buf_indices,
174  bool* output_masks,
175  int64_t count) {
176  const Key* input_keys_templated = static_cast<const Key*>(input_keys);
177 
178  size_t n_values = input_values_soa.size();
179 
180 #pragma omp parallel for num_threads(utility::EstimateMaxThreads())
181  for (int64_t i = 0; i < count; ++i) {
182  output_buf_indices[i] = 0;
183  output_masks[i] = false;
184 
185  const Key& key = input_keys_templated[i];
186 
187  // Try to insert a dummy buffer index.
188  auto res = impl_->insert({key, 0});
189 
190  // Lazy copy key value pair to buffer only if succeeded
191  if (res.second) {
192  buf_index_t buf_index = buffer_accessor_->DeviceAllocate();
193  void* key_ptr = buffer_accessor_->GetKeyPtr(buf_index);
194 
195  // Copy templated key to buffer
196  *static_cast<Key*>(key_ptr) = key;
197 
198  // Copy/reset non-templated value in buffer
199  for (size_t j = 0; j < n_values; ++j) {
200  uint8_t* dst_value = static_cast<uint8_t*>(
201  buffer_accessor_->GetValuePtr(buf_index, j));
202 
203  const uint8_t* src_value =
204  static_cast<const uint8_t*>(input_values_soa[j]) +
205  this->value_dsizes_[j] * i;
206  std::memcpy(dst_value, src_value, this->value_dsizes_[j]);
207  }
208 
209  // Update from dummy 0
210  res.first->second = buf_index;
211 
212  // Write to return variables
213  output_buf_indices[i] = buf_index;
214  output_masks[i] = true;
215  }
216  }
217 }
218 
219 template <typename Key, typename Hash, typename Eq>
221  this->capacity_ = capacity;
222 
223  this->buffer_ = std::make_shared<HashBackendBuffer>(
224  this->capacity_, this->key_dsize_, this->value_dsizes_,
225  this->device_);
226 
227  buffer_accessor_ =
228  std::make_shared<CPUHashBackendBufferAccessor>(*this->buffer_);
229 
230  impl_ = std::make_shared<
231  tbb::concurrent_unordered_map<Key, buf_index_t, Hash, Eq>>(
232  capacity, Hash(), Eq());
233 }
234 
235 } // namespace core
236 } // namespace open3d
Definition: DeviceHashBackend.h:20
Definition: Device.h:18
Definition: TBBHashBackend.h:22
void Insert(const void *input_keys, const std::vector< const void * > &input_values_soa, buf_index_t *output_buf_indices, bool *output_masks, int64_t count) override
Parallel insert contiguous arrays of keys and values.
Definition: TBBHashBackend.h:170
void Find(const void *input_keys, buf_index_t *output_buf_indices, bool *output_masks, int64_t count) override
Parallel find a contiguous array of keys.
Definition: TBBHashBackend.h:90
void Erase(const void *input_keys, bool *output_masks, int64_t count) override
Parallel erase a contiguous array of keys.
Definition: TBBHashBackend.h:108
TBBHashBackend(int64_t init_capacity, int64_t key_dsize, const std::vector< int64_t > &value_dsizes, const Device &device)
Definition: TBBHashBackend.h:72
std::shared_ptr< CPUHashBackendBufferAccessor > buffer_accessor_
Definition: TBBHashBackend.h:68
std::vector< int64_t > BucketSizes() const override
Get the number of entries per bucket.
Definition: TBBHashBackend.h:155
std::shared_ptr< tbb::concurrent_unordered_map< Key, buf_index_t, Hash, Eq > > GetImpl() const
Definition: TBBHashBackend.h:57
void Reserve(int64_t capacity) override
Definition: TBBHashBackend.h:145
~TBBHashBackend()
Definition: TBBHashBackend.h:82
int64_t GetActiveIndices(buf_index_t *output_indices) override
Parallel collect all iterators in the hash table.
Definition: TBBHashBackend.h:127
void Clear() override
Clear stored map without reallocating memory.
Definition: TBBHashBackend.h:139
std::shared_ptr< tbb::concurrent_unordered_map< Key, buf_index_t, Hash, Eq > > impl_
Definition: TBBHashBackend.h:62
int64_t GetBucketCount() const override
Get the number of buckets of the hash map.
Definition: TBBHashBackend.h:150
void Free() override
Definition: TBBHashBackend.h:62
void Allocate(int64_t capacity) override
Definition: TBBHashBackend.h:220
int64_t Size() const override
Get the size (number of valid entries) of the hash map.
Definition: TBBHashBackend.h:85
float LoadFactor() const override
Get the current load factor, defined as size / bucket count.
Definition: TBBHashBackend.h:165
int count
Definition: FilePCD.cpp:42
uint32_t buf_index_t
Definition: HashBackendBuffer.h:44
FN_SPECIFIERS MiniVec< float, N > ceil(const MiniVec< float, N > &a)
Definition: MiniVec.h:89
Definition: PinholeCameraIntrinsic.cpp:16