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 #if KOKKOS_VERSION >= 40799
781 TEUCHOS_TEST_FOR_EXCEPTION(static_cast<unsigned long long>(numKeys) >
782 static_cast<unsigned long long>(::KokkosKernels::ArithTraits<ValueType>::max()),
783 std::invalid_argument,
784 "Tpetra::Details::FixedHashTable: The number of "
786 << numKeys <<
" is greater than the maximum representable "
788 << ::KokkosKernels::ArithTraits<ValueType>::max() <<
". "
789 "This means that it is not possible to use this constructor.");
791 TEUCHOS_TEST_FOR_EXCEPTION(static_cast<unsigned long long>(numKeys) >
792 static_cast<unsigned long long>(::Kokkos::ArithTraits<ValueType>::max()),
793 std::invalid_argument,
794 "Tpetra::Details::FixedHashTable: The number of "
796 << numKeys <<
" is greater than the maximum representable "
798 << ::Kokkos::ArithTraits<ValueType>::max() <<
". "
799 "This means that it is not possible to use this constructor.");
801 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 "
804 const bool buildInParallel =
805 FHT::worthBuildingFixedHashTableInParallel<execution_space>();
816 if (computeInitContigKeys) {
830 auto keys_h = Kokkos::create_mirror_view_and_copy(Kokkos::HostSpace(),
832 firstContigKey_ = keys_h[0];
836 lastContigKey_ = firstContigKey_ + 1;
842 for (offset_type k = 1; k < numKeys; ++k) {
843 if (lastContigKey_ != keys_h[k]) {
851 firstContigKey_ = firstContigKey;
852 lastContigKey_ = lastContigKey;
855 offset_type startIndex;
857 initMinKey = std::min(initMinKey, firstContigKey_);
858 initMaxKey = std::max(initMaxKey, lastContigKey_);
859 startIndex =
static_cast<offset_type
>(lastContigKey_ - firstContigKey_);
864 const offset_type theNumKeys = numKeys - startIndex;
865 const offset_type size = hash_type::getRecommendedSize(theNumKeys);
866 #ifdef HAVE_TPETRA_DEBUG
867 TEUCHOS_TEST_FOR_EXCEPTION(
868 size == 0 && numKeys != 0, std::logic_error,
869 "Tpetra::Details::FixedHashTable constructor: "
870 "getRecommendedSize("
871 << numKeys <<
") returned zero, "
872 "even though the number of keys "
873 << numKeys <<
" is nonzero. "
874 "Please report this bug to the Tpetra developers.");
875 #endif // HAVE_TPETRA_DEBUG
877 subview(keys, std::pair<offset_type, offset_type>(startIndex, numKeys));
884 typedef typename ptr_type::non_const_type counts_type;
885 counts_type counts(
"Tpetra::FixedHashTable::counts", size);
892 typename keys_type::host_mirror_type theKeysHost;
899 if (buildInParallel) {
900 FHT::CountBuckets<counts_type, keys_type> functor(counts, theKeys, size);
901 using range_type = Kokkos::RangePolicy<execution_space, offset_type>;
902 const char kernelLabel[] =
"Tpetra::Details::FixedHashTable CountBuckets";
904 using key_type =
typename keys_type::non_const_value_type;
905 Kokkos::pair<int, key_type> err;
906 Kokkos::parallel_reduce(kernelLabel, range_type(0, theNumKeys),
908 TEUCHOS_TEST_FOR_EXCEPTION(err.first != 0, std::logic_error,
909 "Tpetra::Details::FixedHashTable "
910 "constructor: CountBuckets found a key "
911 << err.second <<
" that "
912 "results in an out-of-bounds hash value.");
914 Kokkos::parallel_for(kernelLabel, range_type(0, theNumKeys), functor);
917 Kokkos::HostSpace hostMemSpace;
918 theKeysHost = Kokkos::create_mirror_view(theKeys);
921 auto countsHost = Kokkos::create_mirror_view(hostMemSpace, counts);
923 for (offset_type k = 0; k < theNumKeys; ++k) {
924 using key_type =
typename keys_type::non_const_value_type;
925 const key_type key = theKeysHost[k];
927 using hash_value_type =
typename hash_type::result_type;
928 const hash_value_type hashVal = hash_type::hashFunc(key, size);
929 TEUCHOS_TEST_FOR_EXCEPTION(hashVal < hash_value_type(0) ||
930 hashVal >= hash_value_type(countsHost.extent(0)),
932 "Tpetra::Details::FixedHashTable "
933 "constructor: Sequential CountBuckets found a key "
935 <<
" that results in an out-of-bounds hash value.");
937 ++countsHost[hashVal];
946 execution_space().fence();
949 typename ptr_type::non_const_type ptr(
"Tpetra::FixedHashTable::ptr", size + 1);
965 if (buildInParallel) {
969 if (!buildInParallel || debug) {
970 Kokkos::HostSpace hostMemSpace;
971 auto counts_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, counts);
972 auto ptr_h = Kokkos::create_mirror_view(hostMemSpace, ptr);
974 #ifdef KOKKOS_ENABLE_SERIAL
975 Kokkos::Serial hostExecSpace;
977 Kokkos::DefaultHostExecutionSpace hostExecSpace;
978 #endif // KOKKOS_ENABLE_SERIAL
986 for (offset_type i = 0; i < size; ++i) {
987 if (ptr_h[i + 1] != ptr_h[i] + counts_h[i]) {
991 TEUCHOS_TEST_FOR_EXCEPTION(bad, std::logic_error,
992 "Tpetra::Details::FixedHashTable "
993 "constructor: computeOffsetsFromCounts gave an incorrect "
1001 execution_space().fence();
1005 typedef typename val_type::non_const_type nonconst_val_type;
1006 nonconst_val_type val(ViewAllocateWithoutInitializing(
"Tpetra::FixedHashTable::pairs"),
1010 typedef FHT::FillPairs<
typename val_type::non_const_type, keys_type,
1011 typename ptr_type::non_const_type>
1013 typename functor_type::value_type result(initMinKey, initMaxKey);
1015 const ValueType newStartingValue = startingValue +
static_cast<ValueType
>(startIndex);
1016 if (buildInParallel) {
1017 functor_type functor(val, counts, ptr, theKeys, newStartingValue,
1018 initMinKey, initMaxKey);
1019 typedef Kokkos::RangePolicy<execution_space, offset_type> range_type;
1020 Kokkos::parallel_reduce(
"Tpetra::Details::FixedHashTable::FillPairs", range_type(0, theNumKeys), functor, result);
1022 Kokkos::HostSpace hostMemSpace;
1023 auto counts_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, counts);
1024 auto ptr_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, ptr);
1025 auto val_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, val);
1026 for (offset_type k = 0; k < theNumKeys; ++k) {
1027 typedef typename hash_type::result_type hash_value_type;
1028 const KeyType key = theKeysHost[k];
1029 if (key > result.maxKey_) {
1030 result.maxKey_ = key;
1032 if (key < result.minKey_) {
1033 result.minKey_ = key;
1035 const ValueType theVal = newStartingValue +
static_cast<ValueType
>(k);
1036 const hash_value_type hashVal = hash_type::hashFunc(key, size);
1039 const offset_type count = counts_h[hashVal];
1040 --counts_h[hashVal];
1042 result.success_ =
false;
1045 const offset_type curPos = ptr_h[hashVal + 1] - count;
1046 val_h[curPos].first = key;
1047 val_h[curPos].second = theVal;
1066 minKey_ = result.minKey_;
1067 maxKey_ = result.maxKey_;
1071 template <
class KeyType,
class ValueType,
class DeviceType>
1072 void FixedHashTable<KeyType, ValueType, DeviceType>::
1073 init(
const host_input_keys_type& keys,
1074 const host_input_vals_type& vals,
1076 KeyType initMaxKey) {
1078 const offset_type numKeys =
static_cast<offset_type
>(keys.extent(0));
1079 #if KOKKOS_VERSION >= 40799
1080 TEUCHOS_TEST_FOR_EXCEPTION(static_cast<unsigned long long>(numKeys) > static_cast<unsigned long long>(::KokkosKernels::ArithTraits<ValueType>::max()),
1081 std::invalid_argument,
1082 "Tpetra::Details::FixedHashTable: The number of "
1084 << numKeys <<
" is greater than the maximum representable "
1086 << ::KokkosKernels::ArithTraits<ValueType>::max() <<
".");
1088 TEUCHOS_TEST_FOR_EXCEPTION(static_cast<unsigned long long>(numKeys) > static_cast<unsigned long long>(::Kokkos::ArithTraits<ValueType>::max()),
1089 std::invalid_argument,
1090 "Tpetra::Details::FixedHashTable: The number of "
1092 << numKeys <<
" is greater than the maximum representable "
1094 << ::Kokkos::ArithTraits<ValueType>::max() <<
".");
1096 TEUCHOS_TEST_FOR_EXCEPTION(numKeys > static_cast<offset_type>(INT_MAX), std::logic_error,
1098 "Details::FixedHashTable: This class currently only works when the number "
1099 "of keys is <= INT_MAX = "
1100 << INT_MAX <<
". If this is a problem for you"
1101 ", please talk to the Tpetra developers.");
1108 const offset_type size = hash_type::getRecommendedSize(numKeys);
1109 #ifdef HAVE_TPETRA_DEBUG
1110 TEUCHOS_TEST_FOR_EXCEPTION(
1111 size == 0 && numKeys != 0, std::logic_error,
1112 "Tpetra::Details::FixedHashTable constructor: "
1113 "getRecommendedSize("
1114 << numKeys <<
") returned zero, "
1115 "even though the number of keys "
1116 << numKeys <<
" is nonzero. "
1117 "Please report this bug to the Tpetra developers.");
1118 #endif // HAVE_TPETRA_DEBUG
1126 Kokkos::HostSpace hostMemSpace;
1127 typename ptr_type::non_const_type ptr(
"Tpetra::FixedHashTable::ptr", size + 1);
1128 auto ptr_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, ptr);
1132 using Kokkos::ViewAllocateWithoutInitializing;
1133 typedef typename val_type::non_const_type nonconst_val_type;
1134 nonconst_val_type val(ViewAllocateWithoutInitializing(
"Tpetra::FixedHashTable::pairs"),
1136 auto val_h = Kokkos::create_mirror_view_and_copy(hostMemSpace, val);
1139 for (offset_type k = 0; k < numKeys; ++k) {
1140 const typename hash_type::result_type hashVal =
1141 hash_type::hashFunc(keys[k], size);
1143 ++ptr_h[hashVal + 1];
1153 for (offset_type i = 0; i < size; ++i) {
1154 ptr_h[i + 1] += ptr_h[i];
1159 typename ptr_type::non_const_type::host_mirror_type curRowStart(
"Tpetra::FixedHashTable::curRowStart", size);
1162 FHT::FillPairsResult<KeyType> result(initMinKey, initMaxKey);
1163 for (offset_type k = 0; k < numKeys; ++k) {
1164 typedef typename hash_type::result_type hash_value_type;
1165 const KeyType key = keys[k];
1166 if (key > result.maxKey_) {
1167 result.maxKey_ = key;
1169 if (key < result.minKey_) {
1170 result.minKey_ = key;
1172 const ValueType theVal = vals[k];
1173 if (theVal > maxVal_) {
1176 if (theVal < minVal_) {
1179 const hash_value_type hashVal = hash_type::hashFunc(key, size);
1181 const offset_type offset = curRowStart[hashVal];
1182 const offset_type curPos = ptr_h[hashVal] + offset;
1183 if (curPos >= ptr_h[hashVal + 1]) {
1184 result.success_ =
false;
1186 val_h[curPos].first = key;
1187 val_h[curPos].second = theVal;
1188 ++curRowStart[hashVal];
1192 TEUCHOS_TEST_FOR_EXCEPTION(!result.success_, std::logic_error,
1193 "Tpetra::Details::FixedHashTable::"
1194 "init: Filling the hash table failed! Please report this bug to the "
1195 "Tpetra developers.");
1203 minKey_ = result.minKey_;
1204 maxKey_ = result.maxKey_;
1208 template <
class KeyType,
class ValueType,
class DeviceType>
1211 if (!checkedForDuplicateKeys_) {
1212 hasDuplicateKeys_ = checkForDuplicateKeys();
1213 checkedForDuplicateKeys_ =
true;
1215 return hasDuplicateKeys_;
1218 template <
class KeyType,
class ValueType,
class DeviceType>
1221 const offset_type size = this->getSize();
1225 if (size == 0 || this->numPairs() == 0) {
1228 typedef FHT::CheckForDuplicateKeys<ptr_type, val_type> functor_type;
1229 functor_type functor(val_, ptr_);
1231 typedef Kokkos::RangePolicy<execution_space, offset_type> range_type;
1232 Kokkos::parallel_reduce(
"Tpetra::Details::FixedHashTable::CheckForDuplicateKeys", range_type(0, size), functor, hasDupKeys);
1233 return hasDupKeys > 0;
1237 template <
class KeyType,
class ValueType,
class DeviceType>
1241 std::ostringstream oss;
1242 oss <<
"FixedHashTable<"
1243 << Teuchos::TypeNameTraits<KeyType>::name() <<
","
1244 << Teuchos::TypeNameTraits<ValueType>::name() <<
">: "
1245 <<
"{ numKeys: " << val_.extent(0)
1246 <<
", tableSize: " << this->getSize() <<
" }";
1250 template <
class KeyType,
class ValueType,
class DeviceType>
1253 const Teuchos::EVerbosityLevel verbLevel)
const {
1256 using Teuchos::OSTab;
1257 using Teuchos::rcpFromRef;
1258 using Teuchos::TypeNameTraits;
1259 using Teuchos::VERB_DEFAULT;
1260 using Teuchos::VERB_EXTREME;
1261 using Teuchos::VERB_LOW;
1262 using Teuchos::VERB_NONE;
1267 Teuchos::EVerbosityLevel vl = verbLevel;
1268 if (vl == VERB_DEFAULT) vl = VERB_LOW;
1270 if (vl == VERB_NONE) {
1272 }
else if (vl == VERB_LOW) {
1273 out << this->description() << endl;
1275 out <<
"FixedHashTable:" << endl;
1277 OSTab tab1(rcpFromRef(out));
1283 out <<
"Template parameters:" << endl;
1285 OSTab tab2(rcpFromRef(out));
1286 out <<
"KeyType: " << TypeNameTraits<KeyType>::name() << endl
1287 <<
"ValueType: " << TypeNameTraits<ValueType>::name() << endl;
1290 const offset_type tableSize = this->getSize();
1291 const offset_type numKeys = val_.extent(0);
1293 out <<
"Table parameters:" << endl;
1295 OSTab tab2(rcpFromRef(out));
1296 out <<
"numKeys: " << numKeys << endl
1297 <<
"tableSize: " << tableSize << endl;
1300 if (vl >= VERB_EXTREME) {
1301 out <<
"Contents: ";
1302 if (tableSize == 0 || numKeys == 0) {
1303 out <<
"[]" << endl;
1305 out <<
"[ " << endl;
1307 OSTab tab2(rcpFromRef(out));
1308 for (offset_type i = 0; i < tableSize; ++i) {
1309 OSTab tab3(rcpFromRef(out));
1311 for (offset_type k = ptr_[i]; k < ptr_[i + 1]; ++k) {
1312 out <<
"(" << val_[k].first <<
"," << val_[k].second <<
")";
1313 if (k + 1 < ptr_[i + 1]) {
1341 #if defined(HAVE_TPETRA_INST_SERIAL)
1342 #if defined(HAVE_TPETRA_INST_INT_INT)
1343 #define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT(LO, GO, NODE) \
1344 template class Details::FixedHashTable<GO, LO, typename NODE::device_type>;
1346 #define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT(LO, GO, NODE) \
1347 template class Details::FixedHashTable<GO, LO, typename NODE::device_type>; \
1348 template class Details::FixedHashTable<LO, LO, typename NODE::device_type>;
1350 #elif defined(HAVE_TPETRA_INST_OPENMP)
1351 #if defined(HAVE_TPETRA_INST_INT_INT)
1352 #define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT(LO, GO, NODE) \
1353 template class Details::FixedHashTable<GO, LO, typename NODE::device_type>; \
1354 template class Details::FixedHashTable<GO, LO, Kokkos::HostSpace::device_type>;
1356 #define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT(LO, GO, NODE) \
1357 template class Details::FixedHashTable<GO, LO, typename NODE::device_type>; \
1358 template class Details::FixedHashTable<LO, LO, typename NODE::device_type>; \
1359 template class Details::FixedHashTable<GO, LO, Kokkos::Device<Kokkos::Serial, Kokkos::HostSpace>>; \
1360 template class Details::FixedHashTable<LO, LO, Kokkos::Device<Kokkos::Serial, Kokkos::HostSpace>>;
1363 #define TPETRA_DETAILS_FIXEDHASHTABLE_INSTANT(LO, GO, NODE) \
1364 template class Details::FixedHashTable<GO, LO, typename NODE::device_type>; \
1365 template class Details::FixedHashTable<GO, LO, Kokkos::HostSpace::device_type>; \
1366 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.