Open3D (C++ API)  0.15.1
TBBHashBackend.h
Go to the documentation of this file.
1// ----------------------------------------------------------------------------
2// - Open3D: www.open3d.org -
3// ----------------------------------------------------------------------------
4// The MIT License (MIT)
5//
6// Copyright (c) 2018-2021 www.open3d.org
7//
8// Permission is hereby granted, free of charge, to any person obtaining a copy
9// of this software and associated documentation files (the "Software"), to deal
10// in the Software without restriction, including without limitation the rights
11// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12// copies of the Software, and to permit persons to whom the Software is
13// furnished to do so, subject to the following conditions:
14//
15// The above copyright notice and this permission notice shall be included in
16// all copies or substantial portions of the Software.
17//
18// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
23// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
24// IN THE SOFTWARE.
25// ----------------------------------------------------------------------------
26
27#pragma once
28
29#include <tbb/concurrent_unordered_map.h>
30
31#include <limits>
32#include <unordered_map>
33
37
38namespace open3d {
39namespace core {
40template <typename Key, typename Hash, typename Eq>
42public:
43 TBBHashBackend(int64_t init_capacity,
44 int64_t key_dsize,
45 const std::vector<int64_t>& value_dsizes,
46 const Device& device);
48
49 void Reserve(int64_t capacity) override;
50
51 void Insert(const void* input_keys,
52 const std::vector<const void*>& input_values_soa,
53 buf_index_t* output_buf_indices,
54 bool* output_masks,
55 int64_t count) override;
56
57 void Find(const void* input_keys,
58 buf_index_t* output_buf_indices,
59 bool* output_masks,
60 int64_t count) override;
61
62 void Erase(const void* input_keys,
63 bool* output_masks,
64 int64_t count) override;
65
66 int64_t GetActiveIndices(buf_index_t* output_indices) override;
67
68 void Clear() override;
69
70 int64_t Size() const override;
71 int64_t GetBucketCount() const override;
72 std::vector<int64_t> BucketSizes() const override;
73 float LoadFactor() const override;
74
75 std::shared_ptr<tbb::concurrent_unordered_map<Key, buf_index_t, Hash, Eq>>
76 GetImpl() const {
77 return impl_;
78 }
79
80 void Allocate(int64_t capacity) override;
81 void Free() override{};
82
83protected:
84 std::shared_ptr<tbb::concurrent_unordered_map<Key, buf_index_t, Hash, Eq>>
86
87 std::shared_ptr<CPUHashBackendBufferAccessor> buffer_accessor_;
88};
89
90template <typename Key, typename Hash, typename Eq>
92 int64_t init_capacity,
93 int64_t key_dsize,
94 const std::vector<int64_t>& value_dsizes,
95 const Device& device)
96 : DeviceHashBackend(init_capacity, key_dsize, value_dsizes, device) {
97 Allocate(init_capacity);
98}
99
100template <typename Key, typename Hash, typename Eq>
102
103template <typename Key, typename Hash, typename Eq>
105 return impl_->size();
106}
107
108template <typename Key, typename Hash, typename Eq>
109void TBBHashBackend<Key, Hash, Eq>::Find(const void* input_keys,
110 buf_index_t* output_buf_indices,
111 bool* output_masks,
112 int64_t count) {
113 const Key* input_keys_templated = static_cast<const Key*>(input_keys);
114
115#pragma omp parallel for num_threads(utility::EstimateMaxThreads())
116 for (int64_t i = 0; i < count; ++i) {
117 const Key& key = input_keys_templated[i];
118
119 auto iter = impl_->find(key);
120 bool flag = (iter != impl_->end());
121 output_masks[i] = flag;
122 output_buf_indices[i] = flag ? iter->second : 0;
123 }
124}
125
126template <typename Key, typename Hash, typename Eq>
127void TBBHashBackend<Key, Hash, Eq>::Erase(const void* input_keys,
128 bool* output_masks,
129 int64_t count) {
130 const Key* input_keys_templated = static_cast<const Key*>(input_keys);
131
132 for (int64_t i = 0; i < count; ++i) {
133 const Key& key = input_keys_templated[i];
134
135 auto iter = impl_->find(key);
136 bool flag = (iter != impl_->end());
137 output_masks[i] = flag;
138 if (flag) {
139 buffer_accessor_->DeviceFree(iter->second);
140 impl_->unsafe_erase(iter);
141 }
142 }
143}
144
145template <typename Key, typename Hash, typename Eq>
147 buf_index_t* output_buf_indices) {
148 int64_t count = impl_->size();
149 int64_t i = 0;
150 for (auto iter = impl_->begin(); iter != impl_->end(); ++iter, ++i) {
151 output_buf_indices[i] = static_cast<int64_t>(iter->second);
152 }
153
154 return count;
155}
156
157template <typename Key, typename Hash, typename Eq>
159 impl_->clear();
160 this->buffer_->ResetHeap();
161}
162
163template <typename Key, typename Hash, typename Eq>
165 impl_->rehash(std::ceil(capacity / impl_->max_load_factor()));
166}
167
168template <typename Key, typename Hash, typename Eq>
170 return impl_->unsafe_bucket_count();
171}
172
173template <typename Key, typename Hash, typename Eq>
174std::vector<int64_t> TBBHashBackend<Key, Hash, Eq>::BucketSizes() const {
175 int64_t bucket_count = impl_->unsafe_bucket_count();
176 std::vector<int64_t> ret;
177 for (int64_t i = 0; i < bucket_count; ++i) {
178 ret.push_back(impl_->unsafe_bucket_size(i));
179 }
180 return ret;
181}
182
183template <typename Key, typename Hash, typename Eq>
185 return impl_->load_factor();
186}
187
188template <typename Key, typename Hash, typename Eq>
190 const void* input_keys,
191 const std::vector<const void*>& input_values_soa,
192 buf_index_t* output_buf_indices,
193 bool* output_masks,
194 int64_t count) {
195 const Key* input_keys_templated = static_cast<const Key*>(input_keys);
196
197 size_t n_values = input_values_soa.size();
198
199#pragma omp parallel for num_threads(utility::EstimateMaxThreads())
200 for (int64_t i = 0; i < count; ++i) {
201 output_buf_indices[i] = 0;
202 output_masks[i] = false;
203
204 const Key& key = input_keys_templated[i];
205
206 // Try to insert a dummy buffer index.
207 auto res = impl_->insert({key, 0});
208
209 // Lazy copy key value pair to buffer only if succeeded
210 if (res.second) {
211 buf_index_t buf_index = buffer_accessor_->DeviceAllocate();
212 void* key_ptr = buffer_accessor_->GetKeyPtr(buf_index);
213
214 // Copy templated key to buffer
215 *static_cast<Key*>(key_ptr) = key;
216
217 // Copy/reset non-templated value in buffer
218 for (size_t j = 0; j < n_values; ++j) {
219 uint8_t* dst_value = static_cast<uint8_t*>(
220 buffer_accessor_->GetValuePtr(buf_index, j));
221
222 const uint8_t* src_value =
223 static_cast<const uint8_t*>(input_values_soa[j]) +
224 this->value_dsizes_[j] * i;
225 std::memcpy(dst_value, src_value, this->value_dsizes_[j]);
226 }
227
228 // Update from dummy 0
229 res.first->second = buf_index;
230
231 // Write to return variables
232 output_buf_indices[i] = buf_index;
233 output_masks[i] = true;
234 }
235 }
236}
237
238template <typename Key, typename Hash, typename Eq>
240 this->capacity_ = capacity;
241
242 this->buffer_ = std::make_shared<HashBackendBuffer>(
243 this->capacity_, this->key_dsize_, this->value_dsizes_,
244 this->device_);
245
246 buffer_accessor_ =
247 std::make_shared<CPUHashBackendBufferAccessor>(*this->buffer_);
248
249 impl_ = std::make_shared<
250 tbb::concurrent_unordered_map<Key, buf_index_t, Hash, Eq>>(
251 capacity, Hash(), Eq());
252}
253
254} // namespace core
255} // namespace open3d
Definition: DeviceHashBackend.h:39
Definition: Device.h:39
Definition: TBBHashBackend.h:41
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:189
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:109
void Erase(const void *input_keys, bool *output_masks, int64_t count) override
Parallel erase a contiguous array of keys.
Definition: TBBHashBackend.h:127
TBBHashBackend(int64_t init_capacity, int64_t key_dsize, const std::vector< int64_t > &value_dsizes, const Device &device)
Definition: TBBHashBackend.h:91
std::shared_ptr< CPUHashBackendBufferAccessor > buffer_accessor_
Definition: TBBHashBackend.h:87
std::vector< int64_t > BucketSizes() const override
Get the number of entries per bucket.
Definition: TBBHashBackend.h:174
void Reserve(int64_t capacity) override
Definition: TBBHashBackend.h:164
~TBBHashBackend()
Definition: TBBHashBackend.h:101
std::shared_ptr< tbb::concurrent_unordered_map< Key, buf_index_t, Hash, Eq > > GetImpl() const
Definition: TBBHashBackend.h:76
int64_t GetActiveIndices(buf_index_t *output_indices) override
Parallel collect all iterators in the hash table.
Definition: TBBHashBackend.h:146
void Clear() override
Clear stored map without reallocating memory.
Definition: TBBHashBackend.h:158
std::shared_ptr< tbb::concurrent_unordered_map< Key, buf_index_t, Hash, Eq > > impl_
Definition: TBBHashBackend.h:85
int64_t GetBucketCount() const override
Get the number of buckets of the hash map.
Definition: TBBHashBackend.h:169
void Free() override
Definition: TBBHashBackend.h:81
void Allocate(int64_t capacity) override
Definition: TBBHashBackend.h:239
int64_t Size() const override
Get the size (number of valid entries) of the hash map.
Definition: TBBHashBackend.h:104
float LoadFactor() const override
Get the current load factor, defined as size / bucket count.
Definition: TBBHashBackend.h:184
int count
Definition: FilePCD.cpp:61
uint32_t buf_index_t
Definition: HashBackendBuffer.h:63
FN_SPECIFIERS MiniVec< float, N > ceil(const MiniVec< float, N > &a)
Definition: MiniVec.h:108
Definition: PinholeCameraIntrinsic.cpp:35