RandomSetter.h
Go to the documentation of this file.
1 // This file is part of Eigen, a lightweight C++ template library
2 // for linear algebra.
3 //
4 // Copyright (C) 2008 Gael Guennebaud <gael.guennebaud@inria.fr>
5 //
6 // This Source Code Form is subject to the terms of the Mozilla
7 // Public License v. 2.0. If a copy of the MPL was not distributed
8 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
9 
10 #ifndef EIGEN_RANDOMSETTER_H
11 #define EIGEN_RANDOMSETTER_H
12 
13 #if defined(EIGEN_GOOGLEHASH_SUPPORT)
14 // Ensure the ::google namespace exists, required for checking existence of
15 // ::google::dense_hash_map and ::google::sparse_hash_map.
16 namespace google {}
17 #endif
18 
19 namespace Eigen {
20 
25 template<typename Scalar> struct StdMapTraits
26 {
27  typedef int KeyType;
28  typedef std::map<KeyType,Scalar> Type;
29  enum {
30  IsSorted = 1
31  };
32 
33  static void setInvalidKey(Type&, const KeyType&) {}
34 };
35 
36 #ifdef EIGEN_UNORDERED_MAP_SUPPORT
37 
53 template<typename Scalar> struct StdUnorderedMapTraits
54 {
55  typedef int KeyType;
56  typedef std::unordered_map<KeyType,Scalar> Type;
57  enum {
58  IsSorted = 0
59  };
60 
61  static void setInvalidKey(Type&, const KeyType&) {}
62 };
63 #endif // EIGEN_UNORDERED_MAP_SUPPORT
64 
65 #if defined(EIGEN_GOOGLEHASH_SUPPORT)
66 
67 namespace google {
68 
69 // Namespace work-around, since sometimes dense_hash_map and sparse_hash_map
70 // are in the global namespace, and other times they are under ::google.
71 using namespace ::google;
72 
73 template<typename KeyType, typename Scalar>
74 struct DenseHashMap {
75  typedef dense_hash_map<KeyType, Scalar> type;
76 };
77 
78 template<typename KeyType, typename Scalar>
79 struct SparseHashMap {
80  typedef sparse_hash_map<KeyType, Scalar> type;
81 };
82 
83 } // namespace google
84 
89 template<typename Scalar> struct GoogleDenseHashMapTraits
90 {
91  typedef int KeyType;
93  enum {
94  IsSorted = 0
95  };
96 
97  static void setInvalidKey(Type& map, const KeyType& k)
98  { map.set_empty_key(k); }
99 };
100 
105 template<typename Scalar> struct GoogleSparseHashMapTraits
106 {
107  typedef int KeyType;
109  enum {
110  IsSorted = 0
111  };
112 
113  static void setInvalidKey(Type&, const KeyType&) {}
114 };
115 #endif
116 
166 template<typename SparseMatrixType,
167  template <typename T> class MapTraits =
168 #if defined(EIGEN_GOOGLEHASH_SUPPORT)
169  GoogleDenseHashMapTraits
170 #elif defined(_HASH_MAP)
171  GnuHashMapTraits
172 #else
174 #endif
175  ,int OuterPacketBits = 6>
177 {
179  typedef typename SparseMatrixType::StorageIndex StorageIndex;
180 
182  {
184  Scalar value;
185  };
186  typedef typename MapTraits<ScalarWrapper>::KeyType KeyType;
188  static const int OuterPacketMask = (1 << OuterPacketBits) - 1;
189  enum {
190  SwapStorage = 1 - MapTraits<ScalarWrapper>::IsSorted,
191  TargetRowMajor = (SparseMatrixType::Flags & RowMajorBit) ? 1 : 0,
192  SetterRowMajor = SwapStorage ? 1-TargetRowMajor : TargetRowMajor
193  };
194 
195  public:
196 
203  inline RandomSetter(SparseMatrixType& target)
204  : mp_target(&target)
205  {
206  const Index outerSize = SwapStorage ? target.innerSize() : target.outerSize();
207  const Index innerSize = SwapStorage ? target.outerSize() : target.innerSize();
208  m_outerPackets = outerSize >> OuterPacketBits;
209  if (outerSize&OuterPacketMask)
210  m_outerPackets += 1;
211  m_hashmaps = new HashMapType[m_outerPackets];
212  // compute number of bits needed to store inner indices
213  Index aux = innerSize - 1;
214  m_keyBitsOffset = 0;
215  while (aux)
216  {
217  ++m_keyBitsOffset;
218  aux = aux >> 1;
219  }
220  KeyType ik = (1<<(OuterPacketBits+m_keyBitsOffset));
221  for (Index k=0; k<m_outerPackets; ++k)
222  MapTraits<ScalarWrapper>::setInvalidKey(m_hashmaps[k],ik);
223 
224  // insert current coeffs
225  for (Index j=0; j<mp_target->outerSize(); ++j)
226  for (typename SparseMatrixType::InnerIterator it(*mp_target,j); it; ++it)
227  (*this)(TargetRowMajor?j:it.index(), TargetRowMajor?it.index():j) = it.value();
228  }
229 
232  {
233  KeyType keyBitsMask = (1<<m_keyBitsOffset)-1;
234  if (!SwapStorage) // also means the map is sorted
235  {
236  mp_target->setZero();
237  mp_target->makeCompressed();
238  mp_target->reserve(nonZeros());
239  Index prevOuter = -1;
240  for (Index k=0; k<m_outerPackets; ++k)
241  {
242  const Index outerOffset = (1<<OuterPacketBits) * k;
243  typename HashMapType::iterator end = m_hashmaps[k].end();
244  for (typename HashMapType::iterator it = m_hashmaps[k].begin(); it!=end; ++it)
245  {
246  const Index outer = (it->first >> m_keyBitsOffset) + outerOffset;
247  const Index inner = it->first & keyBitsMask;
248  if (prevOuter!=outer)
249  {
250  for (Index j=prevOuter+1;j<=outer;++j)
251  mp_target->startVec(j);
252  prevOuter = outer;
253  }
254  mp_target->insertBackByOuterInner(outer, inner) = it->second.value;
255  }
256  }
257  mp_target->finalize();
258  }
259  else
260  {
261  VectorXi positions(mp_target->outerSize());
262  positions.setZero();
263  // pass 1
264  for (Index k=0; k<m_outerPackets; ++k)
265  {
266  typename HashMapType::iterator end = m_hashmaps[k].end();
267  for (typename HashMapType::iterator it = m_hashmaps[k].begin(); it!=end; ++it)
268  {
269  const Index outer = it->first & keyBitsMask;
270  ++positions[outer];
271  }
272  }
273  // prefix sum
274  StorageIndex count = 0;
275  for (Index j=0; j<mp_target->outerSize(); ++j)
276  {
277  StorageIndex tmp = positions[j];
278  mp_target->outerIndexPtr()[j] = count;
279  positions[j] = count;
280  count += tmp;
281  }
282  mp_target->makeCompressed();
283  mp_target->outerIndexPtr()[mp_target->outerSize()] = count;
284  mp_target->resizeNonZeros(count);
285  // pass 2
286  for (Index k=0; k<m_outerPackets; ++k)
287  {
288  const Index outerOffset = (1<<OuterPacketBits) * k;
289  typename HashMapType::iterator end = m_hashmaps[k].end();
290  for (typename HashMapType::iterator it = m_hashmaps[k].begin(); it!=end; ++it)
291  {
292  const Index inner = (it->first >> m_keyBitsOffset) + outerOffset;
293  const Index outer = it->first & keyBitsMask;
294  // sorted insertion
295  // Note that we have to deal with at most 2^OuterPacketBits unsorted coefficients,
296  // moreover those 2^OuterPacketBits coeffs are likely to be sparse, an so only a
297  // small fraction of them have to be sorted, whence the following simple procedure:
298  Index posStart = mp_target->outerIndexPtr()[outer];
299  Index i = (positions[outer]++) - 1;
300  while ( (i >= posStart) && (mp_target->innerIndexPtr()[i] > inner) )
301  {
302  mp_target->valuePtr()[i+1] = mp_target->valuePtr()[i];
303  mp_target->innerIndexPtr()[i+1] = mp_target->innerIndexPtr()[i];
304  --i;
305  }
306  mp_target->innerIndexPtr()[i+1] = internal::convert_index<StorageIndex>(inner);
307  mp_target->valuePtr()[i+1] = it->second.value;
308  }
309  }
310  }
311  delete[] m_hashmaps;
312  }
313 
316  {
317  const Index outer = SetterRowMajor ? row : col;
318  const Index inner = SetterRowMajor ? col : row;
319  const Index outerMajor = outer >> OuterPacketBits; // index of the packet/map
320  const Index outerMinor = outer & OuterPacketMask; // index of the inner vector in the packet
321  const KeyType key = internal::convert_index<KeyType>((outerMinor<<m_keyBitsOffset) | inner);
322  return m_hashmaps[outerMajor][key].value;
323  }
324 
330  Index nonZeros() const
331  {
332  Index nz = 0;
333  for (Index k=0; k<m_outerPackets; ++k)
334  nz += static_cast<Index>(m_hashmaps[k].size());
335  return nz;
336  }
337 
338 
339  protected:
340 
341  HashMapType* m_hashmaps;
342  SparseMatrixType* mp_target;
344  unsigned char m_keyBitsOffset;
345 };
346 
347 } // end namespace Eigen
348 
349 #endif // EIGEN_RANDOMSETTER_H
MapTraits< ScalarWrapper >::KeyType KeyType
Definition: RandomSetter.h:186
const gtsam::Symbol key('X', 0)
SCALAR Scalar
Definition: bench_gemm.cpp:46
RandomSetter(SparseMatrixType &target)
Definition: RandomSetter.h:203
unsigned char m_keyBitsOffset
Definition: RandomSetter.h:344
MapTraits< ScalarWrapper >::Type HashMapType
Definition: RandomSetter.h:187
static void setInvalidKey(Type &, const KeyType &)
Definition: RandomSetter.h:33
Namespace containing all symbols from the Eigen library.
Definition: jet.h:637
SparseMatrixType::Scalar Scalar
Definition: RandomSetter.h:178
Index nonZeros() const
Definition: RandomSetter.h:330
const unsigned int RowMajorBit
Definition: Constants.h:66
Scalar Scalar int size
Definition: benchVecAdd.cpp:17
HashMapType * m_hashmaps
Definition: RandomSetter.h:341
m row(1)
SparseMatrixType::StorageIndex StorageIndex
Definition: RandomSetter.h:179
EIGEN_DEFAULT_DENSE_INDEX_TYPE Index
The Index type as used for the API.
Definition: Meta.h:74
SparseMatrixType * mp_target
Definition: RandomSetter.h:342
static EIGEN_DEPRECATED const end_t end
The RandomSetter is a wrapper object allowing to set/update a sparse matrix with random access...
Definition: RandomSetter.h:176
m col(1)
internal::enable_if< internal::valid_indexed_view_overload< RowIndices, ColIndices >::value &&internal::traits< typename EIGEN_INDEXED_VIEW_METHOD_TYPE< RowIndices, ColIndices >::type >::ReturnAsIndexedView, typename EIGEN_INDEXED_VIEW_METHOD_TYPE< RowIndices, ColIndices >::type >::type operator()(const RowIndices &rowIndices, const ColIndices &colIndices) EIGEN_INDEXED_VIEW_METHOD_CONST
std::ptrdiff_t j
std::map< KeyType, Scalar > Type
Definition: RandomSetter.h:28


gtsam
Author(s):
autogenerated on Tue Jul 4 2023 02:35:29