toobiased/growt

This is a header only library offering a variety of dynamically growing concurrent hash tables. That all work by dynamically migrating the current table once it gets too full.

growt's Issues

Let UpdateFunction decide to cancel update after seeing current data

Hey Tobias, first thanks a lot for your work on this library!

I noted you made extensive experiments in your paper regarding the performance under contention for a subset of keys (ie. Zipf distributed keys). In the particular case where one wants to count the occurrence of the keys in some dataset, contention can be reduced by using statistical counters (e.g. Dice et. al. "Scalable statistics counters."). Such counters provide a tradeoff between statistical guarantees about the accurateness of a count versus the number of writes necessary to the counter. In the concurrent case the number of writes is the number of CAS operations. For more contended counters, the probability of requiring a write during counter increment decreases.

The increment opreation of such counter is quite simple to implement:

  void inc(uint32_t random) {
    while (true) {
      double seenT = threshold.load();
      if (random > seenT) {
        return;
      }
      bool overflow = (seenT < (a + 1.0));
      double newT = seenT * probFactor;
      if (overflow) newT = (double)MaxInt;

      if (std::atomic_compare_exchange_weak(&threshold, &seenT, newT)) {
        return;
      }
    }
  }

Based on a random number, either an update of the stored value is performed or the stored value is left as it is. In case of CAS failure the operation is retried.

It would be very useful, to store such statistical counters as values in a concurrent hash map. However, in the current implementation, whenever update or insertOrUpdate is called, CAS will be executed. The UpdateFunction has no option to cancel the update.

I believe only few changes would be required to make this work though.

1. UpdateFunction must return bool to indicate if the update shall be cancelled or not
2. In TAtomic::execute (for SimpleElement) and atomicUpdate (for MarkableElement) check the return value of UpdateFunction and skip the CIS if false is returned (still indicating that the update was successful).

Would you suggest any other / better solution? Would you welcome a contribution to the library to implement this feature?

Unrelated: Your paper describes a strategy to support complex key and value types. Do you have any plans to support it for growt? I have a use-case for complex keys (strings) and if it is feasible without too many changes, would be happy to use / adapt growt for that.

Building with TBB

Hello 👋

I've been trying to build this project with GROWT_BUILD_TBB=ON and I cannot seem to be able to do it (log file).
I noticed the latest commit on CMakeLists.txt is titled Disable TBB stuff, is TBB still supported, along with the related functionalities?

When trying to compile without the flag, it works without issues.

Cheers

Including headers causes compilation failure

When I ran into your manuscript on arxiv, I was quite excited by your results and wanted to try your tables, but I am unable to build any files including either definitions.h or tsxdefinitions.h. The only difference between this and a branch of our project which is building as expected is the include line. tsxdefinitions seems to die much sooner.

It outputs:

In file included from growt/data-structures/tsxdefinitions.h:18:0,
                 from lib/db.h:6,
                 from lib/db.cpp:1:
growt/data-structures/simpleelement.h:24:18: warning: ISO C++ does not support ‘__int128’ for ‘type name’ [-Wpedantic]
 using int128_t = __int128;
                  ^~~~~~~~
In file included from growt/data-structures/tsxdefinitions.h:19:0,
                 from lib/db.h:6,
                 from lib/db.cpp:1:
growt/data-structures/markableelement.h:28:18: warning: ISO C++ does not support ‘__int128’ for ‘type name’ [-Wpedantic]
 using int128_t = __int128;
                  ^~~~~~~~
growt/data-structures/markableelement.h: In member function ‘int128_t& growt::MarkableElement::as128i()’:
growt/data-structures/markableelement.h:152:37: warning: ISO C++ does not support ‘__int128’ for ‘type name’ [-Wpedantic]
 { return *reinterpret_cast<__int128 *>(this); }
                                     ^
growt/data-structures/markableelement.h: In member function ‘const int128_t& growt::MarkableElement::as128i() const’:
growt/data-structures/markableelement.h:155:43: warning: ISO C++ does not support ‘__int128’ for ‘type name’ [-Wpedantic]
 { return *reinterpret_cast<const __int128 *>(this); }
                                           ^
In file included from growt/data-structures/tsxdefinitions.h:26:0,
                 from lib/db.h:6,
                 from lib/db.cpp:1:
growt/data-structures/growtable.h: At global scope:
growt/data-structures/growtable.h:280:2: warning: extra ‘;’ [-Wpedantic]
 };
  ^
growt/data-structures/growtable.h:292:2: warning: extra ‘;’ [-Wpedantic]
 };
  ^
In file included from lib/db.h:6:0,
                 from lib/db.cpp:1:
growt/data-structures/tsxdefinitions.h:30:99: error: ‘E’ was not declared in this scope
 template<class HashFct = std::hash<typename SimpleElement::Key>, class Allocator = std::allocator<E> >
                                                                                                   ^
growt/data-structures/tsxdefinitions.h:30:100: error: template argument 1 is invalid
 template<class HashFct = std::hash<typename SimpleElement::Key>, class Allocator = std::allocator<E> >
                                                                                                    ^
make: *** [lib/db.o] Error 1

From definitions.h, I get the following errors:

lib/db.o: In function `growt::SimpleElement::CAS(growt::SimpleElement&, growt::SimpleElement const&)':
db.cpp:(.text+0xf5): undefined reference to `__sync_bool_compare_and_swap_16'
lib/db.o: In function `growt::SimpleElement::atomicDelete(growt::SimpleElement const&)':
db.cpp:(.text+0x123): undefined reference to `__sync_bool_compare_and_swap_16'
lib/db.o: In function `growt::MarkableElement::atomicDelete(growt::MarkableElement const&)':
db.cpp:(.text+0x173): undefined reference to `__sync_bool_compare_and_swap_16'
collect2: error: ld returned 1 exit status
make: *** [taxmap] Error 1
make: *** Waiting for unfinished jobs....
src/mapmake.o: In function `growt::successful(growt::ReturnCode)':
mapmake.cpp:(.text+0xff0): multiple definition of `growt::successful(growt::ReturnCode)'
lib/db.o:db.cpp:(.text+0x0): first defined here
src/mapmake.o: In function `growt::SimpleElement::SimpleElement()':
mapmake.cpp:(.text+0x1000): multiple definition of `growt::SimpleElement::SimpleElement()'
lib/db.o:db.cpp:(.text+0x10): first defined here
src/mapmake.o: In function `growt::SimpleElement::SimpleElement()':
mapmake.cpp:(.text+0x1000): multiple definition of `growt::SimpleElement::SimpleElement()'
lib/db.o:db.cpp:(.text+0x10): first defined here
src/mapmake.o: In function `growt::SimpleElement::SimpleElement(unsigned long, unsigned long)':
mapmake.cpp:(.text+0x1010): multiple definition of `growt::SimpleElement::SimpleElement(unsigned long, unsigned long)'
lib/db.o:db.cpp:(.text+0x20): first defined here
src/mapmake.o: In function `growt::SimpleElement::SimpleElement(unsigned long, unsigned long)':
mapmake.cpp:(.text+0x1010): multiple definition of `growt::SimpleElement::SimpleElement(unsigned long, unsigned long)'
lib/db.o:db.cpp:(.text+0x20): first defined here
src/mapmake.o: In function `growt::SimpleElement::SimpleElement(growt::SimpleElement const&&)':
mapmake.cpp:(.text+0x1020): multiple definition of `growt::SimpleElement::SimpleElement(growt::SimpleElement const&&)'
lib/db.o:db.cpp:(.text+0x30): first defined here
src/mapmake.o: In function `growt::SimpleElement::SimpleElement(growt::SimpleElement const&&)':
mapmake.cpp:(.text+0x1020): multiple definition of `growt::SimpleElement::SimpleElement(growt::SimpleElement const&&)'
lib/db.o:db.cpp:(.text+0x30): first defined here
src/mapmake.o: In function `growt::SimpleElement::SimpleElement(growt::SimpleElement const&)':
mapmake.cpp:(.text+0x1030): multiple definition of `growt::SimpleElement::SimpleElement(growt::SimpleElement const&)'
lib/db.o:db.cpp:(.text+0x40): first defined here
src/mapmake.o: In function `growt::SimpleElement::SimpleElement(growt::SimpleElement const&)':
mapmake.cpp:(.text+0x1030): multiple definition of `growt::SimpleElement::SimpleElement(growt::SimpleElement const&)'
lib/db.o:db.cpp:(.text+0x40): first defined here
src/mapmake.o: In function `growt::SimpleElement::operator=(growt::SimpleElement const&)':
mapmake.cpp:(.text+0x1040): multiple definition of `growt::SimpleElement::operator=(growt::SimpleElement const&)'
lib/db.o:db.cpp:(.text+0x50): first defined here
src/mapmake.o: In function `growt::SimpleElement::isEmpty() const':
mapmake.cpp:(.text+0x1050): multiple definition of `growt::SimpleElement::isEmpty() const'
lib/db.o:db.cpp:(.text+0x60): first defined here
src/mapmake.o: In function `growt::SimpleElement::isDeleted() const':
mapmake.cpp:(.text+0x1060): multiple definition of `growt::SimpleElement::isDeleted() const'
lib/db.o:db.cpp:(.text+0x70): first defined here
src/mapmake.o: In function `growt::SimpleElement::isMarked() const':
mapmake.cpp:(.text+0x1080): multiple definition of `growt::SimpleElement::isMarked() const'
lib/db.o:db.cpp:(.text+0x90): first defined here
src/mapmake.o: In function `growt::SimpleElement::compareKey(unsigned long const&) const':
mapmake.cpp:(.text+0x1090): multiple definition of `growt::SimpleElement::compareKey(unsigned long const&) const'
lib/db.o:db.cpp:(.text+0xa0): first defined here
src/mapmake.o: In function `growt::SimpleElement::atomicMark(growt::SimpleElement&)':
mapmake.cpp:(.text+0x10a0): multiple definition of `growt::SimpleElement::atomicMark(growt::SimpleElement&)'
lib/db.o:db.cpp:(.text+0xb0): first defined here
src/mapmake.o: In function `growt::SimpleElement::getKey() const':
mapmake.cpp:(.text+0x10b0): multiple definition of `growt::SimpleElement::getKey() const'
lib/db.o:db.cpp:(.text+0xc0): first defined here
src/mapmake.o: In function `growt::SimpleElement::getData() const':
mapmake.cpp:(.text+0x10c0): multiple definition of `growt::SimpleElement::getData() const'
lib/db.o:db.cpp:(.text+0xd0): first defined here
src/mapmake.o: In function `growt::SimpleElement::CAS(growt::SimpleElement&, growt::SimpleElement const&)':
mapmake.cpp:(.text+0x10d0): multiple definition of `growt::SimpleElement::CAS(growt::SimpleElement&, growt::SimpleElement const&)'
lib/db.o:db.cpp:(.text+0xe0): first defined here
src/mapmake.o: In function `growt::SimpleElement::atomicDelete(growt::SimpleElement const&)':
mapmake.cpp:(.text+0x10f0): multiple definition of `growt::SimpleElement::atomicDelete(growt::SimpleElement const&)'
lib/db.o:db.cpp:(.text+0x100): first defined here
src/mapmake.o: In function `growt::SimpleElement::as128i()':
mapmake.cpp:(.text+0x1120): multiple definition of `growt::SimpleElement::as128i()'
lib/db.o:db.cpp:(.text+0x130): first defined here
src/mapmake.o: In function `growt::SimpleElement::as128i() const':
mapmake.cpp:(.text+0x1130): multiple definition of `growt::SimpleElement::as128i() const'
lib/db.o:db.cpp:(.text+0x140): first defined here
src/mapmake.o: In function `growt::MarkableElement::atomicDelete(growt::MarkableElement const&)':
mapmake.cpp:(.text+0x1140): multiple definition of `growt::MarkableElement::atomicDelete(growt::MarkableElement const&)'
lib/db.o:db.cpp:(.text+0x150): first defined here
src/mapmake.o: In function `growt::SimpleElement::CAS(growt::SimpleElement&, growt::SimpleElement const&)':
mapmake.cpp:(.text+0x10e5): undefined reference to `__sync_bool_compare_and_swap_16'
src/mapmake.o: In function `growt::SimpleElement::atomicDelete(growt::SimpleElement const&)':
mapmake.cpp:(.text+0x1113): undefined reference to `__sync_bool_compare_and_swap_16'
src/mapmake.o: In function `growt::MarkableElement::atomicDelete(growt::MarkableElement const&)':
mapmake.cpp:(.text+0x1163): undefined reference to `__sync_bool_compare_and_swap_16'
lib/db.o: In function `growt::SimpleElement::CAS(growt::SimpleElement&, growt::SimpleElement const&)':
db.cpp:(.text+0xf5): undefined reference to `__sync_bool_compare_and_swap_16'
lib/db.o: In function `growt::SimpleElement::atomicDelete(growt::SimpleElement const&)':
db.cpp:(.text+0x123): undefined reference to `__sync_bool_compare_and_swap_16'
lib/db.o:db.cpp:(.text+0x173): more undefined references to `__sync_bool_compare_and_swap_16' follow
collect2: error: ld returned 1 exit status
make: *** [mapmake] Error 1

Now, the tsx might die sooner because I may not have transactional memory on these Xeon R processors. This is with gcc6.2.1 on RedHat.

Edit: Adding -latomic and -lgcc_s and -lgcc seem to have eliminated the undefineed __sync_bool_compare_and_swap_16s, but I still am encountering the multiple definitions. Maybe a static declaration is needed?

Any idea why that might be?

Thanks!

utils/hash/murmur3_hash.hpp includes non-existent MurmurHash3.cpp

utils/hash/murmur3_hash.hpp has a line #include "MurmurHash3.cpp", but the compiler can't find this file, and I don't see it in the utils repo either.

Clear hash map / erase all elements

Is there a fast way to delete all elements of a growable or non-growable hash map without freeing its memory?

Missing size function

Your table does not implement a .size() function. This is a major issue, preventing widespread adoption.

Not compiling under clang 12

Unfortunately, the project does not compile due to some constexpr violations for the _mapper type in base_linear.hpp as seen below:

/home/user/build/project/libs/growt/./data-structures/base_linear.hpp:1160:19: error: constexpr if condition is not a constant expression
    if constexpr (_mapper.cyclic_mapping)
                  ^~~~~~~~~~~~~~~~~~~~~~

I got this behavior for both clang 12 and 10.

find not working for 0 value and above 0xfffffffffffffff (15 bytes)

Hi,
I am using

template<typename KeyType, typename ValueStorage>
using GrowtConcurrentHashtable = typename growt::table_config<KeyType, ValueStorage,
                                                              utils_tm::hash_tm::crc_hash, growt::AlignedAllocator<>,
                                                              hmod::growable>::table_type;

With KeyType=uint64_t ValueStorage=int8_t

When I insert value 0 or value above 0xfffffffffffffff and right after I call find with the value I get that the value is not present.
I could not find the root cause for this, any idea what is wrong?

Thanks

TBB is a Prerequisite to include table_config.hpp

The README indicates that grow can be used all on its own without any third part libraries. However, data-structures/table_config.hpp includes data-structures/element_types/complex_slot.hpp, which includes tbb/scalable_allocator.h. TBB must be installed to use growt's hash map.

utils/hash/murmur2_hash.hpp compiler error

Ubuntu 18.04. clang++ 12.0.1.

In my project I add #include "utils/hash/murmur2_hash.hpp" and I see this error at compile time:

/home/xander/dev/my_model/../growt/utils/hash/murmur2_hash.hpp:75:31: error: member reference base
type 'const long' is not a structure or union
        return MurmurHash64A(k.data(), k.size(), seed);
                             ~^~~~~
/home/xander/dev/my_model/../growt/data-structures/base_linear.hpp:245:63: note: in instantiation o
f function template specialization 'utils_tm::hash_tm::murmur2_hash::operator()<long>' requested here
    inline size_type h    (const key_type & k) const { return _hash(k); }
                                                              ^
/home/xander/dev/my_model/../growt/data-structures/base_linear.hpp:1189:23: note: in instantiation
of member function 'growt::base_linear<growt::base_linear_config<growt::complex_slot<long, std::shared_
ptr<ccmydata::MyBook>, true>, utils_tm::hash_tm::murmur2_hash, growt::GenericAlignedAllocator
<char, 128>, false, false, false>>::h' requested here
    size_type htemp = h(k);
                      ^
/home/xander/dev/my_model/../growt/data-structures/base_linear.hpp:1071:24: note: in instantiation
of member function 'growt::base_linear<growt::base_linear_config<growt::complex_slot<long, std::shared_
ptr<ccmydata::MyBook>, true>, utils_tm::hash_tm::murmur2_hash, growt::GenericAlignedAllocator
<char, 128>, false, false, false>>::insert_unsafe' requested here
                target.insert_unsafe(curr);
                       ^
/home/xander/dev/my_model/../growt/data-structures/strategies/estrat_async.hpp:294:22: note: in ins
tantiation of member function 'growt::base_linear<growt::base_linear_config<growt::complex_slot<long, s
td::shared_ptr<ccmydata::MyBook>, true>, utils_tm::hash_tm::murmur2_hash, growt::GenericAlign
edAllocator<char, 128>, false, false, false>>::migrate' requested here
        n += source->migrate(*target, temp,
                     ^
/home/xander/dev/my_model/../growt/data-structures/strategies/estrat_async.hpp:269:5: note: in inst
antiation of member function 'growt::estrat_async<growt::migration_table_data<growt::migration_table<gr
owt::base_linear<growt::base_linear_config<growt::complex_slot<long, std::shared_ptr<ccmydata::MyBook>, true>, utils_tm::hash_tm::murmur2_hash, growt::GenericAlignedAllocator<char, 128>, false, fa
lse, false>>, workerstrat, exclstrat>>>::local_data_type::blockwise_migrate' requested here
    blockwise_migrate(curr, next);//,

The error is similar when I compile with g++ 10.3.0:

In file included from /home/xander/dev/my_model/../growt/utils/default_hash.hpp:41,                                 from /home/xander/dev/my_model/../growt/data-structures/base_linear.hpp:24,
                 from /home/xander/dev/my_model/../growt/data-structures/table_config.hpp:15,                       from /home/xander/dev/my_model/pymydata/pymydata/MyWebsocketClient.h:21,
                 from /home/xander/dev/my_model/pymydata/pymydata/DataFeed.cc:11:          /home/xander/dev/my_model/../growt/utils/hash/murmur2_hash.hpp: In instantiation of ‘uint64_t util$
_tm::hash_tm::murmur2_hash::operator()(const Type&) const [with Type = long int; uint64_t = long unsig$ed int]’:
/home/xander/dev/my_model/../growt/data-structures/base_linear.hpp:245:68:   required from ‘growt:$
base_linear<Config>::size_type growt::base_linear<Config>::h(const key_type&) const [with Config = gro$
t::base_linear_config<growt::complex_slot<long int, std::shared_ptr<ccmydata::MyBook>, true,
tbb::scalable_allocator<void> >, utils_tm::hash_tm::murmur2_hash, growt::GenericAlignedAllocator<char,
128>, false, false, false>; growt::base_linear<Config>::size_type = long unsigned int; growt::base_lin$
ar<Config>::key_type = long int]’
/home/xander/dev/my_model/../growt/data-structures/base_linear.hpp:825:23:   required from ‘growt:$
base_linear<Config>::iterator growt::base_linear<Config>::find(const key_type&) [with Config = growt::$
ase_linear_config<growt::complex_slot<long int, std::shared_ptr<ccmydata::MyBook>, true, tbb$
:scalable_allocator<void> >, utils_tm::hash_tm::murmur2_hash, growt::GenericAlignedAllocator<char, 128$
, false, false, false>; growt::base_linear<Config>::iterator = growt::base_linear_iterator<growt::base$
linear<growt::base_linear_config<growt::complex_slot<long int, std::shared_ptr<ccmydata::MyB$
ok>, true, tbb::scalable_allocator<void> >, utils_tm::hash_tm::murmur2_hash, growt::GenericAlignedAllo$
ator<char, 128>, false, false, false> >, false>; growt::base_linear<Config>::key_type = long int]’
/home/xander/dev/my_model/../growt/data-structures/migration_table.hpp:818:103:   required from ‘g$
owt::migration_table_handle< <template-parameter-1-1> >::iterator growt::migration_table_handle< <temp$
ate-parameter-1-1> >::find(const key_type&) [with migration_table_data = growt::migration_table_data<g$
owt::migration_table<growt::base_linear<growt::base_linear_config<growt::complex_slot<long int, std::s$
ared_ptr<ccmydata::MyBook>, true, tbb::scalable_allocator<void> >, utils_tm::hash_tm::murmur$
_hash, growt::GenericAlignedAllocator<char, 128>, false, false, false> >, growt::table_config<long int$
 std::shared_ptr<ccmydata::MyBook>, utils_tm::hash_tm::murmur2_hash, growt::GenericAlignedAl$
ocator<char, 128>, hmod::growable, hmod::deletion>::workerstrat, growt::table_config<long int, std::sh$
red_ptr<ccmydata::MyBook>, utils_tm::hash_tm::murmur2_hash, growt::GenericAlignedAllocator<c$
ar, 128>, hmod::growable, hmod::deletion>::exclstrat> >; growt::migration_table_handle< <template-para$
eter-1-1> >::iterator = growt::migration_table_iterator<growt::migration_table_handle<growt::migration$
table_data<growt::migration_table<growt::base_linear<growt::base_linear_config<growt::complex_slot<lon$
 int, std::shared_ptr<ccmydata::MyBook>, true, tbb::scalable_allocator<void> >, utils_tm::ha$
h_tm::murmur2_hash, growt::GenericAlignedAllocator<char, 128>, false, false, false> >, growt::table_co$
fig<long int, std::shared_ptr<ccmydata::MyBook>, utils_tm::hash_tm::murmur2_hash, growt::Gene
ricAlignedAllocator<char, 128>, hmod::growable, hmod::deletion>::workerstrat, growt::table_config<long
int, std::shared_ptr<ccmydata::MyBook>, utils_tm::hash_tm::murmur2_hash, growt::GenericAligne
dAllocator<char, 128>, hmod::growable, hmod::deletion>::exclstrat> > >, false>; growt::migration_table_
handle< <template-parameter-1-1> >::key_type = long int]’
/home/xander/dev/my_model/pymydata/pymydata/MyWebsocketClient.h:105:32:   required from he
re
/home/xander/dev/my_model/../growt/utils/hash/murmur2_hash.hpp:75:32: error: request for member ‘da
ta’ in ‘k’, which is of non-class type ‘const long int’
   75 |         return MurmurHash64A(k.data(), k.size(), seed);
      |                              ~~^~~~
/home/xander/dev/my_model/../growt/utils/hash/murmur2_hash.hpp:75:42: error: request for member ‘si
ze’ in ‘k’, which is of non-class type ‘const long int’
   75 |         return MurmurHash64A(k.data(), k.size(), seed);
      |                                        ~~^~~~