Open3D (C++ API)  0.19.0
Loading...
Searching...
No Matches
TBBHashBackend.h
Go to the documentation of this file.
1// ----------------------------------------------------------------------------
2// - Open3D: www.open3d.org -
3// ----------------------------------------------------------------------------
4// Copyright (c) 2018-2024 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
19namespace open3d {
20namespace core {
21template <typename Key, typename Hash, typename Eq>
23public:
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
64protected:
65 std::shared_ptr<tbb::concurrent_unordered_map<Key, buf_index_t, Hash, Eq>>
67
68 std::shared_ptr<CPUHashBackendBufferAccessor> buffer_accessor_;
69};
70
71template <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
81template <typename Key, typename Hash, typename Eq>
83
84template <typename Key, typename Hash, typename Eq>
86 return impl_->size();
87}
88
89template <typename Key, typename Hash, typename Eq>
90void 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
107template <typename Key, typename Hash, typename Eq>
108void 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
126template <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
138template <typename Key, typename Hash, typename Eq>
140 impl_->clear();
141 this->buffer_->ResetHeap();
142}
143
144template <typename Key, typename Hash, typename Eq>
146 impl_->rehash(std::ceil(capacity / impl_->max_load_factor()));
147}
148
149template <typename Key, typename Hash, typename Eq>
151 return impl_->unsafe_bucket_count();
152}
153
154template <typename Key, typename Hash, typename Eq>
155std::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
164template <typename Key, typename Hash, typename Eq>
166 return impl_->load_factor();
167}
168
169template <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
219template <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
void Reserve(int64_t capacity) override
Definition TBBHashBackend.h:145
~TBBHashBackend()
Definition TBBHashBackend.h:82
std::shared_ptr< tbb::concurrent_unordered_map< Key, buf_index_t, Hash, Eq > > GetImpl() const
Definition TBBHashBackend.h:57
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:66
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
Definition PinholeCameraIntrinsic.cpp:16