Tpetra parallel linear algebra Version of the Day
Loading...
Searching...
No Matches
Tpetra_HashTable_def.hpp
1/*
2// @HEADER
3// ***********************************************************************
4//
5// Tpetra: Templated Linear Algebra Services Package
6// Copyright (2008) Sandia Corporation
7//
8// Under the terms of Contract DE-AC04-94AL85000 with Sandia Corporation,
9// the U.S. Government retains certain rights in this software.
10//
11// Redistribution and use in source and binary forms, with or without
12// modification, are permitted provided that the following conditions are
13// met:
14//
15// 1. Redistributions of source code must retain the above copyright
16// notice, this list of conditions and the following disclaimer.
17//
18// 2. Redistributions in binary form must reproduce the above copyright
19// notice, this list of conditions and the following disclaimer in the
20// documentation and/or other materials provided with the distribution.
21//
22// 3. Neither the name of the Corporation nor the names of the
23// contributors may be used to endorse or promote products derived from
24// this software without specific prior written permission.
25//
26// THIS SOFTWARE IS PROVIDED BY SANDIA CORPORATION "AS IS" AND ANY
27// EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
28// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
29// PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL SANDIA CORPORATION OR THE
30// CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
31// EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
32// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
33// PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
34// LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
35// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
36// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
37//
38// Questions? Contact Michael A. Heroux (maherou@sandia.gov)
39//
40// ************************************************************************
41// @HEADER
42*/
43
44#ifndef TPETRA_HASHTABLE_DEF_HPP_
45#define TPETRA_HASHTABLE_DEF_HPP_
46
47#include "Tpetra_HashTable_decl.hpp"
48#include "MurmurHash3.hpp"
49
50
51namespace Tpetra
52{
53
54namespace Details
55{
56
57template<typename KeyType, typename ValueType>
58int
59HashTable<KeyType, ValueType>::hashFunc( const KeyType key ) {
60#ifdef TPETRA_USE_MURMUR_HASH
61 uint32_t k;
62 MurmurHash3_x86_32((void *)&key, sizeof(KeyType),
63 1, (void *)&k);
64 return (int) (k%Size_);
65#else
66 // Epetra's version of hash, using it as default as we have observed
67 // this is much faster than murmur hash. However, this is not a good
68 // hash function for all data sets. For our typical use case, this is good.
69 // Use murmur if the maps are sparse.
70 int intkey = (int) ((key & 0x000000007fffffffLL) +
71 ((key & 0x7fffffff80000000LL) >> 31));
72 return (int) ((Seed_ ^ intkey)%Size_);
73#endif
74}
75
76template<typename KeyType, typename ValueType>
77int
78HashTable<KeyType, ValueType>::getRecommendedSize( const int size ) {
79 // A large list of prime numbers.
80 // Based on a recommendation by Andres Valloud in hash forums.
81 // There are only enough primes here so that between any number N and 2*N,
82 // there will be at least about 8 to choose from (except the first 10).
83 // This is a balance between a small list of primes, and getting a
84 // collection size that doesn't waste too much space. In addition,
85 // the primes in this table were chosen so that they do not divide
86 // 256^k +- a, for 1<=k<=8, and -32<=a<=32. This is so that
87 // using them as a modulo will not have a tendency to just throw away
88 // the most significant bits of the object's hash. The primes (except the
89 // first ten) or not close to any power of two to avoid aliasing
90 // between hash functions based on bit manipulation and the moduli.
91 int primes [ ] = {
92 3, 7, 13, 23, 53, 97, 193, 389, 769, 1543,
93 2237, 2423, 2617, 2797, 2999, 3167, 3359, 3539,
94 3727, 3911, 4441 , 4787 , 5119 , 5471 , 5801 , 6143 , 6521 , 6827
95 , 7177 , 7517 , 7853 , 8887 , 9587 , 10243 , 10937 , 11617 , 12289
96 , 12967 , 13649 , 14341 , 15013 , 15727
97 , 17749 , 19121 , 20479 , 21859 , 23209 , 24593 , 25939 , 27329
98 , 28669 , 30047 , 31469 , 35507 , 38231 , 40961 , 43711 , 46439
99 , 49157 , 51893 , 54617 , 57347 , 60077 , 62801 , 70583 , 75619
100 , 80669 , 85703 , 90749 , 95783 , 100823 , 105871 , 110909 , 115963
101 , 120997 , 126031 , 141157 , 151237 , 161323 , 171401 , 181499 , 191579
102 , 201653 , 211741 , 221813 , 231893 , 241979 , 252079
103 , 282311 , 302483 , 322649 , 342803 , 362969 , 383143 , 403301 , 423457
104 , 443629 , 463787 , 483953 , 504121 , 564617 , 604949 , 645313 , 685609
105 , 725939 , 766273 , 806609 , 846931 , 887261 , 927587 , 967919 , 1008239
106 , 1123477 , 1198397 , 1273289 , 1348177 , 1423067 , 1497983 , 1572869
107 , 1647761 , 1722667 , 1797581 , 1872461 , 1947359 , 2022253
108 , 2246953 , 2396759 , 2546543 , 2696363 , 2846161 , 2995973 , 3145739
109 , 3295541 , 3445357 , 3595117 , 3744941 , 3894707 , 4044503
110 , 4493921 , 4793501 , 5093089 , 5392679 , 5692279 , 5991883 , 6291469
111 , 6591059 , 6890641 , 7190243 , 7489829 , 7789447 , 8089033
112 , 8987807 , 9586981 , 10186177 , 10785371 , 11384539 , 11983729
113 , 12582917 , 13182109 , 13781291 , 14380469 , 14979667 , 15578861
114 , 16178053 , 17895707 , 19014187 , 20132683 , 21251141 , 22369661
115 , 23488103 , 24606583 , 25725083 , 26843549 , 27962027 , 29080529
116 , 30198989 , 31317469 , 32435981 , 35791397 , 38028379 , 40265327
117 , 42502283 , 44739259 , 46976221 , 49213237 , 51450131 , 53687099
118 , 55924061 , 58161041 , 60397993 , 62634959 , 64871921
119 , 71582857 , 76056727 , 80530643 , 85004567 , 89478503 , 93952427
120 , 98426347 , 102900263 , 107374217 , 111848111 , 116322053 , 120795971
121 , 125269877 , 129743807 , 143165587 , 152113427 , 161061283 , 170009141
122 , 178956983 , 187904819 , 196852693 , 205800547 , 214748383 , 223696237
123 , 232644089 , 241591943 , 250539763 , 259487603 , 268435399 };
124
125 int hsize = primes[220] ;
126 for (int i = 0 ; i < 221 ; i++)
127 {
128 if (size <= primes[i])
129 {
130 hsize = primes[i] ;
131 break ;
132 }
133 }
134
135 return hsize ;
136}
137
138template<typename KeyType, typename ValueType>
140HashTable( const int size, const unsigned int seed )
141 : Container_(NULL),
142 Seed_(seed)
143{
144 TEUCHOS_TEST_FOR_EXCEPTION(size < 0, std::runtime_error,
145 "HashTable : ERROR, size cannot be less than zero");
146
147 Size_ = getRecommendedSize(size);
148 Container_ = new Node * [Size_];
149 for( KeyType i = 0; i < Size_; ++i ) Container_[i] = NULL;
150#ifdef HAVE_TPETRA_DEBUG
151 maxc_ = 0;
152 nc_ = 0;
153#endif
154}
155
156template<typename KeyType, typename ValueType>
158HashTable( const HashTable & obj )
159 : Container_(NULL),
160 Size_(obj.Size_),
161 Seed_(obj.Seed_)
162{
163#ifdef HAVE_TPETRA_DEBUG
164 maxc_ = 0;
165 nc_ = 0;
166#endif
167 Container_ = new Node * [Size_];
168 for( KeyType i = 0; i < Size_; ++i ) Container_[i] = NULL;
169 for( KeyType i = 0; i < Size_; ++i ) {
170 Node * ptr = obj.Container_[i];
171 while( ptr ) { add( ptr->Key, ptr->Value ); ptr = ptr->Ptr; }
172 }
173}
174
175template<typename KeyType, typename ValueType>
176HashTable<KeyType, ValueType>::~HashTable() {
177 Node * ptr1;
178 Node * ptr2;
179 for( KeyType i = 0; i < Size_; ++i ) {
180 ptr1 = Container_[i];
181 while( ptr1 ) { ptr2 = ptr1; ptr1 = ptr1->Ptr; delete ptr2; }
182 }
183
184 delete [] Container_;
185}
186
187template<typename KeyType, typename ValueType>
188void
190add( const KeyType key, const ValueType value ) {
191 int v = hashFunc(key);
192 Node * n1 = Container_[v];
193 Container_[v] = new Node(key,value,n1);
194}
195
196template<typename KeyType, typename ValueType>
197ValueType
199get( const KeyType key ) {
200 Node * n = Container_[ hashFunc(key) ];
201
202#ifdef HAVE_TPETRA_DEBUG
203 int k = 0;
204#endif
205
206 while( n && (n->Key != key) ){
207 n = n->Ptr;
208#ifdef HAVE_TPETRA_DEBUG
209 ((k+1 > maxc_) ? maxc_ = k+1 : 0) ;
210 k++;
211#endif
212 }
213
214#ifdef HAVE_TPETRA_DEBUG
215 if (k != 0) nc_++;
216#endif
217 if( n ) return n->Value;
218 else return -1;
219}
220
221template <typename KeyType, typename ValueType>
223 std::ostringstream oss;
224 oss << "HashTable<"
225 << Teuchos::TypeNameTraits<KeyType>::name() << ","
226 << Teuchos::TypeNameTraits<ValueType>::name() << "> "
227 << "{ Size_: " << Size_ << " }";
228 return oss.str();
229}
230
231template <typename KeyType, typename ValueType>
233 Teuchos::FancyOStream &out,
234 const Teuchos::EVerbosityLevel verbLevel) const {
235 using std::endl;
236 using std::setw;
237 using Teuchos::OSTab;
238 using Teuchos::rcpFromRef;
239 using Teuchos::TypeNameTraits;
240 using Teuchos::VERB_DEFAULT;
241 using Teuchos::VERB_NONE;
242 using Teuchos::VERB_LOW;
243 using Teuchos::VERB_EXTREME;
244
245 Teuchos::EVerbosityLevel vl = verbLevel;
246 if (vl == VERB_DEFAULT) vl = VERB_LOW;
247
248 if (vl == VERB_NONE) {
249 // do nothing
250 }
251 else if (vl == VERB_LOW) {
252 out << this->description() << endl;
253 }
254 else { // MEDIUM, HIGH or EXTREME
255 out << "HashTable: {" << endl;
256 {
257 OSTab tab1 (rcpFromRef (out));
258
259 const std::string label = this->getObjectLabel ();
260 if (label != "") {
261 out << "label: " << label << endl;
262 }
263 out << "Template parameters: {" << endl;
264 {
265 OSTab tab2 (rcpFromRef (out));
266 out << "KeyType: " << TypeNameTraits<KeyType>::name () << endl
267 << "ValueType" << TypeNameTraits<ValueType>::name () << endl;
268 }
269 out << "}" << endl << "Table parameters: {" << endl;
270 {
271 OSTab tab2 (rcpFromRef (out));
272 out << "Size_: " << Size_ << endl;
273 }
274 out << "}" << endl;
275#ifdef HAVE_TPETRA_DEBUG
276 out << "Debug info: {" << endl;
277 {
278 OSTab tab2 (rcpFromRef (out));
279 out << "Maximum number of collisions for any key: " << maxc_ << endl
280 << "Total number of collisions: " << nc_ << endl;
281 }
282 out << "}" << endl;
283#endif // HAVE_TPETRA_DEBUG
284
285 if (vl >= VERB_EXTREME) {
286 out << "Contents: ";
287 if (Container_ == NULL || Size_ == 0) {
288 out << "[]" << endl;
289 } else {
290 out << "[" << endl;
291 {
292 OSTab tab2 (rcpFromRef (out));
293 for (KeyType i = 0; i < Size_; ++i) {
294 Node* curNode = Container_[i];
295 if (curNode == NULL) {
296 out << "NULL";
297 } else { // curNode != NULL
298 // Print all the buckets at the current table position i.
299 out << "[";
300 // Print the first bucket.
301 out << "[" << curNode->Key << "," << curNode->Value << "]";
302 curNode = curNode->Ptr;
303 // Print the remaining buckets, if there are any.
304 while (curNode != NULL) {
305 out << ", [" << curNode->Key << "," << curNode->Value << "]";
306 curNode = curNode->Ptr;
307 }
308 out << "]" << endl;
309 } // if curNode == or != NULL
310 if (i + 1 < Size_) {
311 out << ", ";
312 }
313 } // for each table position i
314 }
315 out << "]" << endl;
316 } // The table contains entries
317 } // vl >= VERB_EXTREME
318 }
319 out << "}" << endl;
320 } // if vl > VERB_LOW
321}
322
323} // namespace Details
324} // namespace Tpetra
325
326// Macro that explicitly instantiates HashTable for the given local
327// ordinal (LO) and global ordinal (GO) types. Note that HashTable's
328// template parameters occur in the opposite order of most Tpetra
329// classes. This is because HashTable performs global-to-local
330// lookup, and the convention in templated C++ lookup tables (such as
331// std::map) is <KeyType, ValueType>.
332//
333// This macro must be explanded within the Tpetra::Details namespace.
334#define TPETRA_HASHTABLE_INSTANT_DEFAULTNODE(LO,GO) \
335 template class HashTable< GO , LO >; \
336
337#endif
HashTable(const int size, const unsigned int seed=(2654435761U))
ValueType get(const KeyType key)
Get the value corresponding to the given key.
std::string description() const
Implementation of Teuchos::Describable.
void describe(Teuchos::FancyOStream &out, const Teuchos::EVerbosityLevel verbLevel=Teuchos::Describable::verbLevel_default) const
Print this object with the given verbosity to the output stream.
void add(const KeyType key, const ValueType value)
Add a key and its value to the hash table.
Implementation details of Tpetra.
Namespace Tpetra contains the class and methods constituting the Tpetra library.