10 #ifndef TPETRA_DETAILS_FIXEDHASHTABLE_DEF_HPP
11 #define TPETRA_DETAILS_FIXEDHASHTABLE_DEF_HPP
13 #include "Tpetra_Details_FixedHashTable_decl.hpp"
15 #ifdef TPETRA_USE_MURMUR_HASH
16 #include "Kokkos_Functional.hpp"
17 #endif // TPETRA_USE_MURMUR_HASH
18 #if KOKKOS_VERSION >= 40799
19 #include "KokkosKernels_ArithTraits.hpp"
21 #include "Kokkos_ArithTraits.hpp"
23 #include "Teuchos_TypeNameTraits.hpp"
25 #include <type_traits>
47 template <
class ExecSpace>
48 bool worthBuildingFixedHashTableInParallel() {
49 return ExecSpace().concurrency() > 1;
70 template <
class CountsViewType,
72 class SizeType =
typename KeysViewType::size_type>
75 typedef CountsViewType counts_view_type;
76 typedef KeysViewType keys_view_type;
77 typedef typename CountsViewType::execution_space execution_space;
78 typedef typename CountsViewType::memory_space memory_space;
79 typedef SizeType size_type;
80 typedef typename keys_view_type::non_const_value_type key_type;
96 const keys_view_type& keys,
106 KOKKOS_INLINE_FUNCTION
void
111 Kokkos::atomic_inc(&counts_[hashVal]);
114 using value_type = Kokkos::pair<int, key_type>;
119 KOKKOS_INLINE_FUNCTION
void
123 const key_type keyVal = keys_[i];
125 if (hashVal < hash_value_type(0) ||
126 hashVal >= hash_value_type(counts_.extent(0))) {
130 Kokkos::atomic_inc(&counts_[hashVal]);
135 KOKKOS_INLINE_FUNCTION
void init(value_type& dst)
const {
137 dst.second = key_type(0);
140 KOKKOS_INLINE_FUNCTION
void
141 join(value_type& dst,
142 const value_type& src)
const {
143 const bool good = dst.first == 0 || src.first == 0;
144 dst.first = good ? 0 : dst.first;
150 counts_view_type counts_;
152 keys_view_type keys_;
167 template <
class KeyType>
169 KOKKOS_INLINE_FUNCTION
171 #if KOKKOS_VERSION >= 40799
172 :
minKey_(::KokkosKernels::ArithTraits<KeyType>::max())
174 :
minKey_(::Kokkos::ArithTraits<KeyType>::max())
189 #if KOKKOS_VERSION >= 40799
190 maxKey_(::KokkosKernels::ArithTraits<KeyType>::is_integer ? ::KokkosKernels::ArithTraits<KeyType>::min() : -::KokkosKernels::ArithTraits<KeyType>::max())
192 maxKey_(::Kokkos::ArithTraits<KeyType>::is_integer ? ::Kokkos::ArithTraits<KeyType>::min() : -::Kokkos::ArithTraits<KeyType>::max())
195 static_assert(std::is_arithmetic<KeyType>::value,
197 "KeyType must be some kind of number type.");
200 KOKKOS_INLINE_FUNCTION
202 const KeyType& initMaxKey)
206 static_assert(std::is_arithmetic<KeyType>::value,
208 "KeyType must be some kind of number type.");
245 template <
class PairsViewType,
247 class CountsViewType,
248 class SizeType =
typename KeysViewType::size_type>
251 typedef typename CountsViewType::non_const_type counts_view_type;
252 typedef typename counts_view_type::const_type offsets_view_type;
254 typedef PairsViewType pairs_view_type;
255 typedef typename KeysViewType::const_type keys_view_type;
256 typedef typename offsets_view_type::execution_space execution_space;
257 typedef typename offsets_view_type::memory_space memory_space;
258 typedef SizeType size_type;
260 typedef typename keys_view_type::non_const_value_type key_type;
261 typedef typename pairs_view_type::non_const_value_type pair_type;
285 const counts_view_type& counts,
286 const offsets_view_type& ptr,
287 const keys_view_type& keys,
288 const typename pair_type::second_type startingValue)
293 , size_(counts.extent(0))
294 , startingValue_(startingValue)
295 #if KOKKOS_VERSION >= 40799
296 , initMinKey_(::KokkosKernels::ArithTraits<key_type>::max())
297 , initMaxKey_(::KokkosKernels::ArithTraits<key_type>::is_integer ? ::KokkosKernels::ArithTraits<key_type>::min() : -::KokkosKernels::ArithTraits<key_type>::max()){}
299 , initMinKey_(::Kokkos::ArithTraits<key_type>::max())
300 , initMaxKey_(::Kokkos::ArithTraits<key_type>::is_integer ? ::Kokkos::ArithTraits<key_type>::min() : -::Kokkos::ArithTraits<key_type>::max()) {
323 const counts_view_type& counts,
324 const offsets_view_type& ptr,
325 const keys_view_type& keys,
326 const typename pair_type::second_type startingValue,
327 const key_type initMinKey,
328 const key_type initMaxKey)
333 , size_(counts.extent(0))
334 , startingValue_(startingValue)
335 , initMinKey_(initMinKey)
336 , initMaxKey_(initMaxKey) {
346 KOKKOS_INLINE_FUNCTION
void
347 join(value_type& dst,
348 const value_type& src)
const {
349 if (src.maxKey_ > dst.maxKey_) {
350 dst.maxKey_ = src.maxKey_;
352 if (src.minKey_ < dst.minKey_) {
353 dst.minKey_ = src.minKey_;
355 dst.success_ = dst.success_ && src.success_;
362 KOKKOS_INLINE_FUNCTION
void
365 typedef typename offsets_view_type::non_const_value_type offset_type;
366 typedef typename pair_type::second_type val_type;
367 typedef typename std::remove_reference<decltype(counts_[0])>::type atomic_incr_type;
369 const key_type key = keys_[i];
376 const val_type theVal = startingValue_ +
static_cast<val_type
>(i);
380 const offset_type count = Kokkos::atomic_fetch_add(&counts_[hashVal], atomic_incr_type(-1));
384 const offset_type curPos = ptr_[hashVal + 1] - count;
386 pairs_[curPos].first = key;
387 pairs_[curPos].second = theVal;
392 pairs_view_type pairs_;
393 counts_view_type counts_;
394 offsets_view_type ptr_;
395 keys_view_type keys_;
397 typename pair_type::second_type startingValue_;
399 key_type initMinKey_;
401 key_type initMaxKey_;
427 template <
class OffsetsViewType,
429 class SizeType =
typename OffsetsViewType::size_type>
432 typedef typename OffsetsViewType::const_type offsets_view_type;
433 typedef typename PairsViewType::const_type pairs_view_type;
434 typedef typename offsets_view_type::execution_space execution_space;
435 typedef typename offsets_view_type::memory_space memory_space;
436 typedef SizeType size_type;
439 typedef int value_type;
446 const offsets_view_type& ptr)
449 , size_(ptr_.extent(0) == 0 ? size_type(0) : ptr_.extent(0) - 1) {}
452 KOKKOS_INLINE_FUNCTION
void init(value_type& dst)
const {
457 KOKKOS_INLINE_FUNCTION
void
459 const value_type& src)
const {
460 dst = dst + src > 0 ? 1 : 0;
464 KOKKOS_INLINE_FUNCTION
void
466 typedef typename offsets_view_type::non_const_value_type offset_type;
467 typedef typename pairs_view_type::non_const_value_type pair_type;
468 typedef typename pair_type::first_type key_type;
473 const offset_type beg = ptr_[i];
474 const offset_type end = ptr_[i + 1];
475 bool foundDuplicateKey =
false;
480 for (offset_type j = beg + 1; j < end; ++j) {
481 const key_type curKey = pairs_[j].first;
482 for (offset_type k = beg; k < j; ++k) {
483 if (pairs_[k].first == curKey) {
484 foundDuplicateKey =
true;
489 dst = (dst > 0) || foundDuplicateKey ? 1 : 0;
494 pairs_view_type pairs_;
495 offsets_view_type ptr_;
505 template <
class KeyType,
class ValueType,
class DeviceType>
509 , maxVal_(keys.size() == 0 ? static_cast<ValueType>(0) : static_cast<ValueType>(keys.size() - 1))
510 , checkedForDuplicateKeys_(false) {
511 const ValueType startingValue =
static_cast<ValueType
>(0);
512 const KeyType initMinKey = this->minKey_;
513 const KeyType initMaxKey = this->maxKey_;
514 this->init(keys, startingValue, initMinKey, initMaxKey,
515 initMinKey, initMinKey,
false);
518 template <
class KeyType,
class ValueType,
class DeviceType>
522 , maxVal_(keys.size() == 0 ? static_cast<ValueType>(0) : static_cast<ValueType>(keys.size() - 1))
523 , checkedForDuplicateKeys_(false) {
524 typedef typename keys_type::non_const_type nonconst_keys_type;
529 const ValueType startingValue =
static_cast<ValueType
>(0);
530 host_input_keys_type keys_k(keys.size() == 0 ? NULL : keys.getRawPtr(),
532 using Kokkos::ViewAllocateWithoutInitializing;
533 nonconst_keys_type keys_d(ViewAllocateWithoutInitializing(
"FixedHashTable::keys"),
537 const KeyType initMinKey = this->minKey_;
538 const KeyType initMaxKey = this->maxKey_;
539 this->init(keys_d, startingValue, initMinKey, initMaxKey,
540 initMinKey, initMinKey,
false);
543 template <
class KeyType,
class ValueType,
class DeviceType>
546 const ValueType startingValue)
547 : minVal_(startingValue)
548 , maxVal_(keys.size() == 0 ? startingValue : static_cast<ValueType>(startingValue + keys.size() - 1))
549 , checkedForDuplicateKeys_(false) {
550 typedef typename keys_type::non_const_type nonconst_keys_type;
555 host_input_keys_type keys_k(keys.size() == 0 ? NULL : keys.getRawPtr(),
557 using Kokkos::ViewAllocateWithoutInitializing;
558 nonconst_keys_type keys_d(ViewAllocateWithoutInitializing(
"FixedHashTable::keys"),
563 #if KOKKOS_VERSION >= 40799
564 const KeyType initMinKey = ::KokkosKernels::ArithTraits<KeyType>::max();
566 const KeyType initMinKey = ::Kokkos::ArithTraits<KeyType>::max();
580 #if KOKKOS_VERSION >= 40799
581 const KeyType initMaxKey = ::KokkosKernels::ArithTraits<KeyType>::is_integer ? ::KokkosKernels::ArithTraits<KeyType>::min() : -::KokkosKernels::ArithTraits<KeyType>::max();
583 const KeyType initMaxKey = ::Kokkos::ArithTraits<KeyType>::is_integer ? ::Kokkos::ArithTraits<KeyType>::min() : -::Kokkos::ArithTraits<KeyType>::max();
585 this->init(keys_d, startingValue, initMinKey, initMaxKey,
586 initMinKey, initMinKey,
false);
589 template <
class KeyType,
class ValueType,
class DeviceType>
592 const KeyType firstContigKey,
593 const KeyType lastContigKey,
594 const ValueType startingValue)
595 : minVal_(startingValue)
596 , maxVal_(keys.size() == 0 ? startingValue : static_cast<ValueType>(startingValue + keys.size() - 1))
597 , firstContigKey_(firstContigKey)
598 , lastContigKey_(lastContigKey)
599 , checkedForDuplicateKeys_(false) {
600 #if KOKKOS_VERSION >= 40799
601 const KeyType initMinKey = ::KokkosKernels::ArithTraits<KeyType>::max();
603 const KeyType initMinKey = ::Kokkos::ArithTraits<KeyType>::max();
617 #if KOKKOS_VERSION >= 40799
618 const KeyType initMaxKey = ::KokkosKernels::ArithTraits<KeyType>::is_integer ? ::KokkosKernels::ArithTraits<KeyType>::min() : -::KokkosKernels::ArithTraits<KeyType>::max();
620 const KeyType initMaxKey = ::Kokkos::ArithTraits<KeyType>::is_integer ? ::Kokkos::ArithTraits<KeyType>::min() : -::Kokkos::ArithTraits<KeyType>::max();
622 this->init(keys, startingValue, initMinKey, initMaxKey,
623 firstContigKey, lastContigKey,
true);
626 template <
class KeyType,
class ValueType,
class DeviceType>
629 const KeyType firstContigKey,
630 const KeyType lastContigKey,
631 const ValueType startingValue)
632 : minVal_(startingValue)
633 , maxVal_(keys.size() == 0 ? startingValue : static_cast<ValueType>(startingValue + keys.size() - 1))
634 , firstContigKey_(firstContigKey)
635 , lastContigKey_(lastContigKey)
636 , checkedForDuplicateKeys_(false) {
637 typedef typename keys_type::non_const_type nonconst_keys_type;
642 host_input_keys_type keys_k(keys.size() == 0 ? NULL : keys.getRawPtr(),
644 using Kokkos::ViewAllocateWithoutInitializing;
645 nonconst_keys_type keys_d(ViewAllocateWithoutInitializing(
"FixedHashTable::keys"),
650 #if KOKKOS_VERSION >= 40799
651 const KeyType initMinKey = ::KokkosKernels::ArithTraits<KeyType>::max();
653 const KeyType initMinKey = ::Kokkos::ArithTraits<KeyType>::max();
667 #if KOKKOS_VERSION >= 40799
668 const KeyType initMaxKey = ::KokkosKernels::ArithTraits<KeyType>::is_integer ? ::KokkosKernels::ArithTraits<KeyType>::min() : -::KokkosKernels::ArithTraits<KeyType>::max();
670 const KeyType initMaxKey = ::Kokkos::ArithTraits<KeyType>::is_integer ? ::Kokkos::ArithTraits<KeyType>::min() : -::Kokkos::ArithTraits<KeyType>::max();
672 this->init(keys_d, startingValue, initMinKey, initMaxKey,
673 firstContigKey, lastContigKey,
true);
676 template <
class KeyType,
class ValueType,
class DeviceType>
679 const ValueType startingValue)
680 : minVal_(startingValue)
681 , maxVal_(keys.size() == 0 ? startingValue : static_cast<ValueType>(startingValue + keys.size() - 1))
682 , checkedForDuplicateKeys_(false) {
683 #if KOKKOS_VERSION >= 40799
684 const KeyType initMinKey = ::KokkosKernels::ArithTraits<KeyType>::max();
686 const KeyType initMinKey = ::Kokkos::ArithTraits<KeyType>::max();
700 #if KOKKOS_VERSION >= 40799
701 const KeyType initMaxKey = ::KokkosKernels::ArithTraits<KeyType>::is_integer ? ::KokkosKernels::ArithTraits<KeyType>::min() : -::KokkosKernels::ArithTraits<KeyType>::max();
703 const KeyType initMaxKey = ::Kokkos::ArithTraits<KeyType>::is_integer ? ::Kokkos::ArithTraits<KeyType>::min() : -::Kokkos::ArithTraits<KeyType>::max();
705 this->init(keys, startingValue, initMinKey, initMaxKey,
706 initMinKey, initMinKey,
false);
709 template <
class KeyType,
class ValueType,
class DeviceType>
712 const Teuchos::ArrayView<const ValueType>& vals)
713 : contiguousValues_(false)
714 , checkedForDuplicateKeys_(false) {
718 host_input_keys_type keys_k(keys.size() == 0 ? NULL : keys.getRawPtr(),
720 host_input_vals_type vals_k(vals.size() == 0 ? NULL : vals.getRawPtr(),
722 #if KOKKOS_VERSION >= 40799
723 const KeyType initMinKey = ::KokkosKernels::ArithTraits<KeyType>::max();
725 const KeyType initMinKey = ::Kokkos::ArithTraits<KeyType>::max();
739 #if KOKKOS_VERSION >= 40799
740 const KeyType initMaxKey = ::KokkosKernels::ArithTraits<KeyType>::is_integer ? ::KokkosKernels::ArithTraits<KeyType>::min() : -::KokkosKernels::ArithTraits<KeyType>::max();
742 const KeyType initMaxKey = ::Kokkos::ArithTraits<KeyType>::is_integer ? ::Kokkos::ArithTraits<KeyType>::min() : -::Kokkos::ArithTraits<KeyType>::max();
744 this->init(keys_k, vals_k, initMinKey, initMaxKey);
747 template <
class KeyType,
class ValueType,
class DeviceType>
749 init(
const keys_type& keys,
750 ValueType startingValue,
753 KeyType firstContigKey,
754 KeyType lastContigKey,
755 const bool computeInitContigKeys) {
756 using Kokkos::subview;
757 using Kokkos::ViewAllocateWithoutInitializing;
758 using Teuchos::TypeNameTraits;
759 typedef typename std::decay<decltype(keys.extent(0))>::type size_type;
761 const char prefix[] =
"Tpetra::Details::FixedHashTable: ";
763 const offset_type numKeys =
static_cast<offset_type
>(keys.extent(0));
765 #if KOKKOS_VERSION >= 40799
766 const offset_type theMaxVal = ::KokkosKernels::ArithTraits<offset_type>::max();
768 const offset_type theMaxVal = ::Kokkos::ArithTraits<offset_type>::max();
770 const size_type maxValST =
static_cast<size_type
>(theMaxVal);
771 TEUCHOS_TEST_FOR_EXCEPTION(keys.extent(0) > maxValST, std::invalid_argument, prefix <<
"The "
773 << keys.extent(0) <<
" does not fit in "
775 << TypeNameTraits<offset_type>::name() <<
", whose "
777 << theMaxVal <<
". This means that it is not possible to "
778 "use this constructor.");
780 TEUCHOS_TEST_FOR_EXCEPTION(static_cast<unsigned long long>(numKeys) >
781 #
if KOKKOS_VERSION >= 40799
782 static_cast<unsigned long long>(::KokkosKernels::ArithTraits<ValueType>::max()),
784 static_cast<unsigned long long>(::Kokkos::ArithTraits<ValueType>::max()),
786 std::invalid_argument,
787 "Tpetra::Details::FixedHashTable: The number of "
789 << numKeys <<
" is greater than the maximum representable "
791 #
if KOKKOS_VERSION >= 40799
792 << ::KokkosKernels::ArithTraits<ValueType>::max() <<
". "
794 << ::Kokkos::ArithTraits<ValueType>::max() <<
". "
796 "This means that it is not possible to use this constructor.");
797 TEUCHOS_TEST_FOR_EXCEPTION(numKeys > static_cast<offset_type>(INT_MAX), std::logic_error, prefix <<
"This class currently only works when the number of keys is <= INT_MAX = " << INT_MAX <<
". If this is a problem for you, please talk to the Tpetra "
800 const bool buildInParallel =
801 FHT::worthBuildingFixedHashTableInParallel<execution_space>();
812 if (computeInitContigKeys) {
826 auto keys_h = Kokkos::create_mirror_view_and_copy(Kokkos::HostSpace(),
828 firstContigKey_ = keys_h[0];
832 lastContigKey_ = firstContigKey_ + 1;
838 for (offset_type k = 1; k < numKeys; ++k) {
839 if (lastContigKey_ != keys_h[k]) {
847 firstContigKey_ = firstContigKey;
848 lastContigKey_ = lastContigKey;
851 offset_type startIndex;
853 initMinKey = std::min(initMinKey, firstContigKey_);
854 initMaxKey = std::max(initMaxKey, lastContigKey_);
855 startIndex =
static_cast<offset_type
>(lastContigKey_ - firstContigKey_);
860 const offset_type theNumKeys = numKeys - startIndex;
861 const offset_type size = hash_type::getRecommendedSize(theNumKeys);
862 #ifdef HAVE_TPETRA_DEBUG
863 TEUCHOS_TEST_FOR_EXCEPTION(
864 size == 0 && numKeys != 0, std::logic_error,
865 "Tpetra::Details::FixedHashTable constructor: "
866 "getRecommendedSize("
867 << numKeys <<
") returned zero, "
868 "even though the number of keys "
869 << numKeys <<
" is nonzero. "
870 "Please report this bug to the Tpetra developers.");
871 #endif // HAVE_TPETRA_DEBUG
873 subview(keys, std::pair<offset_type, offset_type>(startIndex, numKeys));
880 typedef typename ptr_type::non_const_type counts_type;
881 counts_type counts(
"Tpetra::FixedHashTable::counts", size);
888 typename keys_type::host_mirror_type theKeysHost;
895 if (buildInParallel) {
896 FHT::CountBuckets<counts_type, keys_type> functor(counts, theKeys, size);
897 using range_type = Kokkos::RangePolicy<execution_space, offset_type>;
898 const char kernelLabel[] =
"Tpetra::Details::FixedHashTable CountBuckets";
900 using key_type =
typename keys_type::non_const_value_type;
901 Kokkos::pair<int, key_type> err;
902 Kokkos::parallel_reduce(kernelLabel, range_type(0, theNumKeys),
904 TEUCHOS_TEST_FOR_EXCEPTION(err.first != 0, std::logic_error,
905 "Tpetra::Details::FixedHashTable "
906 "constructor: CountBuckets found a key "
907 << err.second <<
" that "
908 "results in an out-of-bounds hash value.");
910 Kokkos::parallel_for(kernelLabel, range_type(0, theNumKeys), functor);
913 Kokkos::HostSpace hostMemSpace;
914 theKeysHost = Kokkos::create_mirror_view(theKeys);
917 auto countsHost = Kokkos::create_mirror_view(hostMemSpace, counts);
919 for (offset_type k = 0; k < theNumKeys; ++k) {
920 using key_type =
typename keys_type::non_const_value_type;
921 const key_type key = theKeysHost[k];
923 using hash_value_type =
typename hash_type::result_type;
924 const hash_value_type hashVal = hash_type::hashFunc(key, size);
925 TEUCHOS_TEST_FOR_EXCEPTION(hashVal < hash_value_type(0) ||
926 hashVal >= hash_value_type(countsHost.extent(0)),
928 "Tpetra::Details::FixedHashTable "
929 "constructor: Sequential CountBuckets found a key "
931 <<
" that results in an out-of-bounds hash value.");
933 ++countsHost[hashVal];
942 execution_space().fence();
945 typename ptr_type::non_const_type ptr(
"Tpetra::FixedHashTable::ptr", size + 1);
961 if (buildInParallel) {
965 if (!buildInParallel || debug) {
966 Kokkos::HostSpace hostMemSpace;
967 auto counts_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, counts);
968 auto ptr_h = Kokkos::create_mirror_view(hostMemSpace, ptr);
970 #ifdef KOKKOS_ENABLE_SERIAL
971 Kokkos::Serial hostExecSpace;
973 Kokkos::DefaultHostExecutionSpace hostExecSpace;
974 #endif // KOKKOS_ENABLE_SERIAL
982 for (offset_type i = 0; i < size; ++i) {
983 if (ptr_h[i + 1] != ptr_h[i] + counts_h[i]) {
987 TEUCHOS_TEST_FOR_EXCEPTION(bad, std::logic_error,
988 "Tpetra::Details::FixedHashTable "
989 "constructor: computeOffsetsFromCounts gave an incorrect "
997 execution_space().fence();
1001 typedef typename val_type::non_const_type nonconst_val_type;
1002 nonconst_val_type val(ViewAllocateWithoutInitializing(
"Tpetra::FixedHashTable::pairs"),
1006 typedef FHT::FillPairs<
typename val_type::non_const_type, keys_type,
1007 typename ptr_type::non_const_type>
1009 typename functor_type::value_type result(initMinKey, initMaxKey);
1011 const ValueType newStartingValue = startingValue +
static_cast<ValueType
>(startIndex);
1012 if (buildInParallel) {
1013 functor_type functor(val, counts, ptr, theKeys, newStartingValue,
1014 initMinKey, initMaxKey);
1015 typedef Kokkos::RangePolicy<execution_space, offset_type> range_type;
1016 Kokkos::parallel_reduce(
"Tpetra::Details::FixedHashTable::FillPairs", range_type(0, theNumKeys), functor, result);
1018 Kokkos::HostSpace hostMemSpace;
1019 auto counts_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, counts);
1020 auto ptr_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, ptr);
1021 auto val_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, val);
1022 for (offset_type k = 0; k < theNumKeys; ++k) {
1023 typedef typename hash_type::result_type hash_value_type;
1024 const KeyType key = theKeysHost[k];
1025 if (key > result.maxKey_) {
1026 result.maxKey_ = key;
1028 if (key < result.minKey_) {
1029 result.minKey_ = key;
1031 const ValueType theVal = newStartingValue +
static_cast<ValueType
>(k);
1032 const hash_value_type hashVal = hash_type::hashFunc(key, size);
1035 const offset_type count = counts_h[hashVal];
1036 --counts_h[hashVal];
1038 result.success_ =
false;
1041 const offset_type curPos = ptr_h[hashVal + 1] - count;
1042 val_h[curPos].first = key;
1043 val_h[curPos].second = theVal;
1062 minKey_ = result.minKey_;
1063 maxKey_ = result.maxKey_;
1067 template <
class KeyType,
class ValueType,
class DeviceType>
1068 void FixedHashTable<KeyType, ValueType, DeviceType>::
1069 init(
const host_input_keys_type& keys,
1070 const host_input_vals_type& vals,
1072 KeyType initMaxKey) {
1074 const offset_type numKeys =
static_cast<offset_type
>(keys.extent(0));
1075 #if KOKKOS_VERSION >= 40799
1076 TEUCHOS_TEST_FOR_EXCEPTION(static_cast<unsigned long long>(numKeys) > static_cast<unsigned long long>(::KokkosKernels::ArithTraits<ValueType>::max()),
1078 TEUCHOS_TEST_FOR_EXCEPTION(static_cast<unsigned long long>(numKeys) > static_cast<unsigned long long>(::Kokkos::ArithTraits<ValueType>::max()),
1080 std::invalid_argument,
1081 "Tpetra::Details::FixedHashTable: The number of "
1083 << numKeys <<
" is greater than the maximum representable "
1085 #
if KOKKOS_VERSION >= 40799
1086 << ::KokkosKernels::ArithTraits<ValueType>::max() <<
".");
1088 << ::Kokkos::ArithTraits<ValueType>::max() <<
".");
1090 TEUCHOS_TEST_FOR_EXCEPTION(numKeys > static_cast<offset_type>(INT_MAX), std::logic_error,
1092 "Details::FixedHashTable: This class currently only works when the number "
1093 "of keys is <= INT_MAX = "
1094 << INT_MAX <<
". If this is a problem for you"
1095 ", please talk to the Tpetra developers.");
1102 const offset_type size = hash_type::getRecommendedSize(numKeys);
1103 #ifdef HAVE_TPETRA_DEBUG
1104 TEUCHOS_TEST_FOR_EXCEPTION(
1105 size == 0 && numKeys != 0, std::logic_error,
1106 "Tpetra::Details::FixedHashTable constructor: "
1107 "getRecommendedSize("
1108 << numKeys <<
") returned zero, "
1109 "even though the number of keys "
1110 << numKeys <<
" is nonzero. "
1111 "Please report this bug to the Tpetra developers.");
1112 #endif // HAVE_TPETRA_DEBUG
1120 Kokkos::HostSpace hostMemSpace;
1121 typename ptr_type::non_const_type ptr(
"Tpetra::FixedHashTable::ptr", size + 1);
1122 auto ptr_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, ptr);
1126 using Kokkos::ViewAllocateWithoutInitializing;
1127 typedef typename val_type::non_const_type nonconst_val_type;
1128 nonconst_val_type val(ViewAllocateWithoutInitializing(
"Tpetra::FixedHashTable::pairs"),
1130 auto val_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, val);
1133 for (offset_type k = 0; k < numKeys; ++k) {
1134 const typename hash_type::result_type hashVal =
1135 hash_type::hashFunc(keys[k], size);
1137 ++ptr_h[hashVal + 1];
1147 for (offset_type i = 0; i < size; ++i) {
1148 ptr_h[i + 1] += ptr_h[i];
1153 typename ptr_type::non_const_type::host_mirror_type curRowStart(
"Tpetra::FixedHashTable::curRowStart", size);
1156 FHT::FillPairsResult<KeyType> result(initMinKey, initMaxKey);
1157 for (offset_type k = 0; k < numKeys; ++k) {
1158 typedef typename hash_type::result_type hash_value_type;
1159 const KeyType key = keys[k];
1160 if (key > result.maxKey_) {
1161 result.maxKey_ = key;
1163 if (key < result.minKey_) {
1164 result.minKey_ = key;
1166 const ValueType theVal = vals[k];
1167 if (theVal > maxVal_) {
1170 if (theVal < minVal_) {
1173 const hash_value_type hashVal = hash_type::hashFunc(key, size);
1175 const offset_type offset = curRowStart[hashVal];
1176 const offset_type curPos = ptr_h[hashVal] + offset;
1177 if (curPos >= ptr_h[hashVal + 1]) {
1178 result.success_ =
false;
1180 val_h[curPos].first = key;
1181 val_h[curPos].second = theVal;
1182 ++curRowStart[hashVal];
1186 TEUCHOS_TEST_FOR_EXCEPTION(!result.success_, std::logic_error,
1187 "Tpetra::Details::FixedHashTable::"
1188 "init: Filling the hash table failed! Please report this bug to the "
1189 "Tpetra developers.");
1197 minKey_ = result.minKey_;
1198 maxKey_ = result.maxKey_;
1202 template <
class KeyType,
class ValueType,
class DeviceType>
1205 if (!checkedForDuplicateKeys_) {
1206 hasDuplicateKeys_ = checkForDuplicateKeys();
1207 checkedForDuplicateKeys_ =
true;
1209 return hasDuplicateKeys_;
1212 template <
class KeyType,
class ValueType,
class DeviceType>
1215 const offset_type size = this->getSize();
1219 if (size == 0 || this->numPairs() == 0) {
1222 typedef FHT::CheckForDuplicateKeys<ptr_type, val_type> functor_type;
1223 functor_type functor(val_, ptr_);
1225 typedef Kokkos::RangePolicy<execution_space, offset_type> range_type;
1226 Kokkos::parallel_reduce(
"Tpetra::Details::FixedHashTable::CheckForDuplicateKeys", range_type(0, size), functor, hasDupKeys);
1227 return hasDupKeys > 0;
1231 template <
class KeyType,
class ValueType,
class DeviceType>
1235 std::ostringstream oss;
1236 oss <<
"FixedHashTable<"
1237 << Teuchos::TypeNameTraits<KeyType>::name() <<
","
1238 << Teuchos::TypeNameTraits<ValueType>::name() <<
">: "
1239 <<
"{ numKeys: " << val_.extent(0)
1240 <<
", tableSize: " << this->getSize() <<
" }";
1244 template <
class KeyType,
class ValueType,
class DeviceType>
1247 const Teuchos::EVerbosityLevel verbLevel)
const {
1250 using Teuchos::OSTab;
1251 using Teuchos::rcpFromRef;
1252 using Teuchos::TypeNameTraits;
1253 using Teuchos::VERB_DEFAULT;
1254 using Teuchos::VERB_EXTREME;
1255 using Teuchos::VERB_LOW;
1256 using Teuchos::VERB_NONE;
1261 Teuchos::EVerbosityLevel vl = verbLevel;
1262 if (vl == VERB_DEFAULT) vl = VERB_LOW;
1264 if (vl == VERB_NONE) {
1266 }
else if (vl == VERB_LOW) {
1267 out << this->description() << endl;
1269 out <<
"FixedHashTable:" << endl;
1271 OSTab tab1(rcpFromRef(out));
1277 out <<
"Template parameters:" << endl;
1279 OSTab tab2(rcpFromRef(out));
1280 out <<
"KeyType: " << TypeNameTraits<KeyType>::name() << endl
1281 <<
"ValueType: " << TypeNameTraits<ValueType>::name() << endl;
1284 const offset_type tableSize = this->getSize();
1285 const offset_type numKeys = val_.extent(0);
1287 out <<
"Table parameters:" << endl;
1289 OSTab tab2(rcpFromRef(out));
1290 out <<
"numKeys: " << numKeys << endl
1291 <<
"tableSize: " << tableSize << endl;
1294 if (vl >= VERB_EXTREME) {
1295 out <<
"Contents: ";
1296 if (tableSize == 0 || numKeys == 0) {
1297 out <<
"[]" << endl;
1299 out <<
"[ " << endl;
1301 OSTab tab2(rcpFromRef(out));
1302 for (offset_type i = 0; i < tableSize; ++i) {
1303 OSTab tab3(rcpFromRef(out));
1305 for (offset_type k = ptr_[i]; k < ptr_[i + 1]; ++k) {
1306 out <<
"(" << val_[k].first <<
"," << val_[k].second <<
")";
1307 if (k + 1 < ptr_[i + 1]) {
1335 #if defined(HAVE_TPETRA_INST_SERIAL) || defined(HAVE_TPETRA_INST_OPENMP)
1336 #if defined(HAVE_TPETRA_INST_INT_INT)
1337 #define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT(LO, GO, NODE) \
1338 template class Details::FixedHashTable<GO, LO, typename NODE::device_type>;
1340 #define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT(LO, GO, NODE) \
1341 template class Details::FixedHashTable<GO, LO, typename NODE::device_type>; \
1342 template class Details::FixedHashTable<LO, LO, typename NODE::device_type>;
1345 #define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT(LO, GO, NODE) \
1346 template class Details::FixedHashTable<GO, LO, typename NODE::device_type>; \
1347 template class Details::FixedHashTable<GO, LO, Kokkos::HostSpace::device_type>; \
1348 template class Details::FixedHashTable<LO, LO, Kokkos::HostSpace::device_type>;
CheckForDuplicateKeys(const pairs_view_type &pairs, const offsets_view_type &ptr)
Constructor.
Parallel reduce functor for filling the FixedHashTable, and computing the min and max keys...
FillPairs(const pairs_view_type &pairs, const counts_view_type &counts, const offsets_view_type &ptr, const keys_view_type &keys, const typename pair_type::second_type startingValue, const key_type initMinKey, const key_type initMaxKey)
Constructor that takes initial min and max key values.
KOKKOS_INLINE_FUNCTION void init(value_type &dst) const
Set the initial value of the reduction result.
KOKKOS_DEFAULTED_FUNCTION FixedHashTable()=default
Default constructor; makes an empty table.
static KOKKOS_INLINE_FUNCTION result_type hashFunc(const argument_type &, const offset_type &)
The hash function.
KOKKOS_INLINE_FUNCTION void operator()(const size_type &i) const
Do this for every entry of keys_.
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.
ResultType result_type
Type of the return value of the hash function.
Parallel for functor for counting "buckets" in the FixedHashTable.
static bool debug()
Whether Tpetra is in debug mode.
bool success_
Whether fill succeeded (it can only fail on a bug)
KeyType maxKey_
The current maximum key.
void deep_copy(MultiVector< DS, DL, DG, DN > &dst, const MultiVector< SS, SL, SG, SN > &src)
Copy the contents of the MultiVector src into dst.
The hash function for FixedHashTable.
KOKKOS_INLINE_FUNCTION void operator()(const size_type &i, value_type &dst) const
Debug reduce version of above operator().
Declare and define the functions Tpetra::Details::computeOffsetsFromCounts and Tpetra::computeOffsets...
std::string description() const
Implementation of Teuchos::Describable interface.
KOKKOS_INLINE_FUNCTION void operator()(const size_type &i, value_type &dst) const
Parallel loop body; do this for every entry of keys_.
FillPairs(const pairs_view_type &pairs, const counts_view_type &counts, const offsets_view_type &ptr, const keys_view_type &keys, const typename pair_type::second_type startingValue)
Constructor.
KOKKOS_INLINE_FUNCTION void init(value_type &dst) const
Set the initial value of the reduction result.
bool hasDuplicateKeys()
Whether the table has any duplicate keys.
CountBuckets(const counts_view_type &counts, const keys_view_type &keys, const size_type size)
Constructor.
KOKKOS_INLINE_FUNCTION void init(value_type &dst) const
Set the initial value of the reduction result.
Functor for checking whether a FixedHashTable has one or more duplicate entries.
KOKKOS_INLINE_FUNCTION void join(value_type &dst, const value_type &src) const
Combine two intermediate reduction results.
OffsetsViewType::non_const_value_type computeOffsetsFromCounts(const ExecutionSpace &execSpace, const OffsetsViewType &ptr, const CountsViewType &counts)
Compute offsets from counts.
KeyType minKey_
The current minimum key.
Reduction result for FillPairs functor below.
KOKKOS_INLINE_FUNCTION void operator()(const size_type &i, value_type &dst) const
Parallel loop body.
Kokkos::View< const KeyType *, Kokkos::LayoutLeft, device_type > keys_type
Type of a 1-D Kokkos::View (array) used to store keys.
Declaration of Tpetra::Details::Behavior, a class that describes Tpetra's behavior.