I have a c++ application using libcuckoo library , there is a global var OrderRefMap like following

cuckoohash_map<std::string, int, CityHasher<std::string>> OrderRefMap ;

one thread do OrderRefMap.insert quite fast , another thread do OrderRefMap.erase quite fast , too,
I think libcuckoo is high-performance concurrency hash library , means I should not worry to use lock
in inserting and erasing , so I just code like :

Thread1 :
OrderRefMap.insert( s , 100 ) ;
Thread2 :
OrderRefMap.erase( s ) ;

no need to use lock like

Thread1 :
pthread_spin_lock(&orderspinlock) ;
OrderRefMap.insert( s , 100 ) ;
pthread_spin_unlock(&orderspinlock) ;
Thread2 :
pthread_spin_lock(&orderspinlock) ;
OrderRefMap.erase( s ) ;
pthread_spin_unlock(&orderspinlock) ;

Am I correct ?!

something appears to be amiss.

iam@shaman:~/Repositories/growt/extern/libcuckoo$ uname -a
Linux shaman 3.13.0-109-generic #156-Ubuntu SMP Wed Feb 8 16:09:17 UTC 2017 x86_64 x86_64 x86_64 GNU/Linux
iam@shaman:~/Repositories/growt/extern/libcuckoo/build$ cmake --version
cmake version 3.6.0

CMake suite maintained and supported by Kitware (kitware.com/cmake).

But following your build instructions does not provoke much

iam@shaman:~/Repositories/growt/extern/libcuckoo$ mkdir build
iam@shaman:~/Repositories/growt/extern/libcuckoo$ cd build/
iam@shaman:~/Repositories/growt/extern/libcuckoo/build$ cmake -DCMAKE_INSTALL_PREFIX=../install -DCMAKE_BUILD_EXAMPLES=1 -DCMAKE_BUILD_TESTS=1 ..
-- The CXX compiler identification is GNU 4.9.4
-- Check for working CXX compiler: /usr/bin/c++
-- Check for working CXX compiler: /usr/bin/c++ -- works
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Looking for C++ include pthread.h
-- Looking for C++ include pthread.h - found
-- Looking for pthread_create
-- Looking for pthread_create - not found
-- Check if compiler accepts -pthread
-- Check if compiler accepts -pthread - yes
-- Found Threads: TRUE
-- Configuring done
-- Generating done
CMake Warning:
  Manually-specified variables were not used by the project:

    CMAKE_BUILD_EXAMPLES
    CMAKE_BUILD_TESTS


-- Build files have been written to: /home/iam/Repositories/growt/extern/libcuckoo/build
iam@shaman:~/Repositories/growt/extern/libcuckoo/build$ make all
iam@shaman:~/Repositories/growt/extern/libcuckoo/build$ make install
Install the project...
-- Install configuration: "Release"
-- Up-to-date: /home/iam/Repositories/growt/extern/libcuckoo/install/include/libcuckoo/city_hasher.hh
-- Up-to-date: /home/iam/Repositories/growt/extern/libcuckoo/install/include/libcuckoo/cuckoohash_config.hh
-- Up-to-date: /home/iam/Repositories/growt/extern/libcuckoo/install/include/libcuckoo/cuckoohash_map.hh
-- Up-to-date: /home/iam/Repositories/growt/extern/libcuckoo/install/include/libcuckoo/cuckoohash_util.hh
-- Up-to-date: /home/iam/Repositories/growt/extern/libcuckoo/install/include/libcuckoo/libcuckoo_lazy_array.hh
iam@shaman:~/Repositories/growt/extern/libcuckoo/build$ make tests
iam@shaman:~/Repositories/growt/extern/libcuckoo/build$

First of all, thank you for sharing this code with us, and for the C++ templates; I'm looking forward to playing around with this more in the near future. I wanted to share a minor problem I encountered with one of the examples in hope of sparing others some unnecessary frustration.

Problem:
In examples/count_freq.cc, the update function called by upsert will insert "1" upon the first encounter of a key, but will not update the counter's value on the subsequent occurrences of that key.

Test Environment:
Ubuntu x64 w/ gcc 4.8.4-2ubuntu1~14.04, and on OSX LLVM 6.1.0 (clang-602.0.53).

Issue:
The update function in count_freq.cc (as provided) is:

auto updatefn = [](const size_t& num) { return num+1; };

The value returned by updatefn is equal to num+1, but the function doesn't change the actual value of num, and is precluded from doing so by the const declaration.

If I change the definition to

auto updatefn = [](size_t& num) {num++; return num;};  // (losing the const, explicitly incrementing the counter)

then the program seems to execute as expected on both Ubuntu and on OSX.
(FWIW, I also get a ton of gcc -Wshadow warnings under Ubuntu gcc once I make this change, but none under Xcode clang.)

move_to_bucket() looks to be called when performing cuckoo rehashing (cuckoopath_move()), and also during fast resize (cuckoo_fast_double()).

It moves elements from one slot to another, sets the first slot's occupied_ bit to 0, but does not call the destructor on the moved-from element. This "don't call destructors" behaviour looks to be asserted in test_resize.cc.

Do I have this right? If so, I think failing to call destructors is wrong and a resource leak -- e.g. consider a class that doesn't have a move constructor and gets copied instead.

Hello
I am going to use libcuckoo concurrent hash map in my application. Its multi threaded application with thread pool. Few clarificaaitons

1. Do i need to take care of allocating object before i pass to insert ? I allocate object then I will be taking car of deal locating that too
2. What's the maximum limit this libcuckoo can support, i mean in terms of no of keys along with its respective object. My object size is around 112 bytes. And ideally at anytime each key will hold just one entry corresponding to its object.
   During multiple threads execution, if multiple threads are updating the similary key e.g key is 4431 , with different objects? What will happen ?

Neo

I noticed this note in the README about future-master:

This update also contains a number of small but important performance and correctness improvements.

Could you mention the correctness improvements? What behavior in the existing master branch is not "correct"?

I was trying to debug my own code and faced with this error.
If I compile in debug mode with _GLIBCXX_DEBUG enabled, it throws an error during hash table insertion, when it causes expansion. I managed to reproduce it with "count_freq.cc" example:

First, i've changed line 18 to

typedef cuckoohash_map<KeyType, size_t> Table;

and commented out line 15 to ease the building process. I compile it with:

g++ count_freq.cc -I../src/ -pthread -std=c++11 -g -Og -D_GLIBCXX_DEBUG -o count_freq

and when I run the binary, it terminates with:

/usr/include/c++/5.3.1/debug/array:152:error: attempt to subscript container with out-of-bounds index 1, but container only holds 1 elements.

However, the non-debug version seems to be running fine. I'm using GCC version 5.3.1, fedora linux 4.4.9-300.

For example, I have a cuckoomp<string, shared_ptr<class>> mp;

I have to update like this:

void my_update (int num) {
    shared_ptr<class> p(new class);
    auto fn = [num](shared_ptr<class>& p){ ***  };
    mp.upsert(key, fn, p);
}

The problem is, every time when my_update is invoked, it new a class, even though this class might not be used. How can I avoid this?

I have the following 2 libcuckoo in my machine :

1. 186405 Apr 7 2016 libcuckoo-master.zip
2. 217549 Dec 20 07:51 libcuckoo-master.zip

The following compile and run fine at Apr 7 version but failed at Dec 20 version :

#include <libcuckoo/cuckoohash_map.hh>
#include <libcuckoo/city_hasher.hh>

template <>
class CityHasher<char*> {
public:
size_t operator()(const char* ptr) const {
return CityHash64((const char*) ptr, strlen(ptr));
}
};
struct charptrcompare
{
bool operator()(char* p1,char* p2){
return strcmp( p1 , p2 ) == 0 ;
}
} ;
cuckoohash_map<char*,int,CityHasher<char*>,charptrcompare> StkidMap ;

int main() {
char x[8]={0} ,y[8]={0},z[8]={0} ;

strcpy(x,"Marx") ;
strcpy(y,"Mary") ;
strcpy(z,"Marz") ;

StkidMap.insert( x , 100 ) ;
StkidMap.insert( y , 100 ) ;
StkidMap.insert( z , 100 ) ;

char x1[8]={0}  ;
int i ;
strcpy(x1,"Marz") ;
if( StkidMap.find(x1,i) )
    printf("1...YES\n") ;
strcpy(x1,"MarR") ;
if( StkidMap.find(x1,i) )
    printf("2...YES\n") ;
strcpy(x1,"Mary") ;
if( StkidMap.find(x1,i) )
    printf("3...YES\n") ;

}

compile by g++ --std=c++11 -O2 test2.cpp -lcityhash -o test2.exe
using Apr 7 libcuckoo in g++ (GCC) 4.8.3 compile fine
using Dec 20 libcuckoo in g++ (GCC) 4.8.5 compile error .

May I know how to avoid compile error in my test source ?!

It looks like current upsert only passes one parameters to update_fn, and this parameter is the value of the corresponding key in the hash table, like : upsert(key, upsert_fn, cur_num); If I wanna pass cur_num to upsert_fn, how can I do that ?

It seems there is no operator [] in current libcuckoo. But our code uses [] that is supported in the old version of libcuckoo. How can I keep my code unchanged if I use current version of libcuckoo?

C++14 added heterogeneous comparison lookup to std::map. This allows us to have a map where the key type is std::string, but use a const char * in our lookup, avoiding the construction of a temporary string object.

I'd like for cuckoohash_map::upsert() to support something similar. Let me have a cuckoohash_map with std::string as the key, but pass const char * as the key argument of upsert(), such that a conversion from const char * to std::string is only done if the key needs to be inserted into the table.

Right now for performance reasons I'm using const char * as my key, but it means the caller of my API must ensure the string is valid for the lifetime of the entry in the table, which it doesn't know.

Is it ok (fast) to use string as the key ? or I need to use integer and manually hash the string to integer.

The current read_thread function looks for the same key repeatedly rather than searching the series of keys.

The

ASSERT_EQ(table.find(*begin, v), in_table) 

should be switched to

ASSERT_EQ(table.find(*it, v), in_table);

At the moment the hashmap can only increase its memory consumption. Would it be possible to release allocated memory when the size() decreases or when clear() is called?

Hi,
My job needs to build a large size hashtable (size>1 billion), then I modify Line 20 as "const size_t total_inserts = 1000000000;" in examples/count_freq.cc, and it reports "std::bad_alloc". So Does it support such a concurrent hashtable in count frequency task? Looking forward to hearing from you.
Regards,
Shelson

Is there an obvious way to synthesize an operation that inspects the state of the stored element and possibly erases it? My first thought would be that update_fn would return a bool to indicate that the entry should be removed as a side effect of the update...

The basic problem I'm trying to deal with is storing a manually reference counted record inside the table. When I decrement the reference count to 0 (via update_fn I would like to have the element removed).

Hello!

I tried to include it multiple times and got a lot of errors.

Please add protections, it implemented with:

#ifndef _FAST_LIBRARY_H
#define _FAST_LIBRARY_H

#endif 

Hi, I'm evaluating libcuckoo for a project and noticed that some of the benchmarks occasionally trip LLVM's ThreadSanitizer. I'm not that familiar with the code, but it looks to me that there's an issue in cuckoopath_move(), where it accesses the buckets_ array without holding any locks.

In my testing, moving the accesses to buckets_ on lines 1170 and 1172 until after the calls to lock_three and lock_two keeps TSAN happy, but I'm not sure if this is the correct fix.

Tested at 1e59598 on OS X 10.12.2; libcuckoo was built in debug mode with -fsanitize=thread, and using Apple LLVM 8.

$ env TSAN_OPTIONS="history_size=7" ./tests/benchmarks/read_insert_throughput --table-capacity 1
...
WARNING: ThreadSanitizer: data race (pid=76330)
  Write of size 8 at 0x7d4000007f10 by thread T14 (mutexes: write M65588):
    #0 std::__1::vector<cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>::Bucket, std::__1::allocator<cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >,4ul>::Bucket> >::__swap_out_circular_buffer(std::__1::__split_buffer<cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>::Bucket, std::__1::allocator<cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>::Bucket>&>&) type_traits:3616 (read_insert_throughput+0x00010000fec7)
    #1 std::__1::vector<cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>::Bucket, std::__1::allocator<cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >,4ul>::Bucket> >::__append(unsigned long) vector:1042 (read_insert_throughput+0x00010000fccd)
    #2 std::__1::vector<cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>::Bucket, std::__1::allocator<cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >,4ul>::Bucket> >::resize(unsigned long) vector:1997 (read_insert_throughput+0x00010000f9ed)
    #3 cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>::cuckoo_fast_double(unsigned long) cuckoohash_map.hh:1708 (read_insert_throughput+0x000100010dc5)
...

  Previous read of size 8 at 0x7d4000007f10 by thread T13:
    #0 cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>::cuckoopath_move(unsigned long, std::__1::array<cuckoohash_map<unsigned int, unsignedint, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>::CuckooRecord, 5ul>&, unsigned long, cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>::BucketContainer<2ul>&) vector:1500 (read_insert_throughput+0x000100011be7)
    #1 cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>::run_cuckoo(cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>::BucketContainer<2ul>&, unsigned long&, unsigned long&) cuckoohash_map.hh:1250 (read_insert_throughput+0x00010001136e)
    #2 cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>::cuckoo_status cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>::cuckoo_insert<unsigned int&, int>(unsigned long, cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>::BucketContainer<2ul>, unsigned int&&&, int&&) cuckoohash_map.hh:1487 (read_insert_throughput+0x0001000109a1)
    #3 bool cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>::cuckoo_insert_loop<unsigned int&, int>(unsigned long, unsigned int&&&, int&&) cuckoohash_map.hh:1535 (read_insert_throughput+0x00010001067d)
    #4 bool cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>::insert<unsigned int&, int>(unsigned int&&&, int&&) cuckoohash_map.hh:513 (read_insert_throughput+0x0001000105e7)
    #5 read_insert_thread<cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul> >::func(cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>&, std::__1::__wrap_iter<unsigned int*>, std::__1::__wrap_iter<unsigned int*>, std::__1::atomic<unsigned long>&, double, unsigned long) test_util.hh:227(read_insert_throughput+0x000100013c89)
    #6 bool cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>::find<unsigned int>(unsigned int const&, unsigned int&) const cuckoohash_map.hh:469 (read_insert_throughput+0x000100014192)
    #7 read_insert_thread<cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul> >::func(cuckoohash_map<unsigned int, unsigned int, DefaultHasher<unsigned int>, std::__1::equal_to<unsigned int>, std::__1::allocator<std::__1::pair<unsigned int const, unsigned int> >, 4ul>&, std::__1::__wrap_iter<unsigned int*>, std::__1::__wrap_iter<unsigned int*>, std::__1::atomic<unsigned long>&, double, unsigned long) test_util.hh:231(read_insert_throughput+0x000100013cbf)
...

Full log is available at: libcuckoo-tsan.txt

Hi all,

If I am correct, the rehashing alway double the bucket size. In practice, if the number of items is slightly larger than power of two, a load factor will be only ~50%, which is a waste of memory. I would like to ask if it is possible that the rehashing can boost the bucket size by a smaller factor, say 1.5 or 1.3, which is more memory-friendly. Thanks.

setKV() declares a static allocator_type variable which may have an exit-time destructor. With appropriate warning settings, Clang will warn you about these, and in a codebase I work on they are a compile error because they're seen as dangerous.

Given that libcuckoo doesn't currently support stateful C++11 allocators anyway, I think you should be able to simply drop the static keyword here.

Portions of libcuckoo pollute the global namespace with un-namespaced symbols, e.g. lazy_array, DEFAULT_SIZE. These symbols should either be namespaced or prefixed with 'libcuckoo_' or similar.

The state_table_ is cuckoohash<std::string, StateCounter*>. Note the value is a pointer StateCounter*. Can I pass the there parameters to StateCounter* as below? If not, how can I pass those parameters?

void StateTableIncrease(std::string& key, int queue_id, int inc = 1) {
    auto inc_fn = [queue_id, inc](StateCounter* counter) {
        counter->Inc(queue_id, inc);
    };
    state_table_.upsert(key, inc_fn, queue_counts_, queue_id, inc);
  }

The constructor of StateCounter is like this:

    StateCounter(int queue_num, int queue_no, int inc)
        : queue_counter(new std::vector<int>(queue_num)) {
      std::cout << "in construction of state counter" << std::endl;
      queue_counter->at(queue_no) = inc;
    }

cuckoo_fast_double() calls vector<Bucket>::resize() to double the size of the table. Bucket stores elements in a std::aligned_storage<> and doesn't define a copy or move constructor -- this means that calling resize() will perform a bitwise copy of table elements, instead of invoking their copy or move constructors.

This is usually okay, but not all types can be moved by bitwise copy, e.g.

class NonRelocatableType {
private:
  char buffer[1024];
  char * pointerToBuffer;
  ...
public:
  NonRelocatableType() : pointerToBuffer(buffer) {}
  ...
};

(Example taken from https://github.com/facebook/folly/blob/master/folly/docs/Traits.md)

I think Bucket should probably declare a move constructor that moves occupied slots using std::move.

In cuckoo_insert_loop, we forward the value to cuckoo_insert, but if we resize and try again, we'll be re-forwarding the value, which won't actually work on values that have been moved. We need to find a way to support perfect forwarding and still be able to retry the insert when the table is full.

root@srinidhi-laptop:/home/srinidhi/msearch/libcuckoo/tests# make
g++ -DHAVE_CONFIG_H -I. -I.. -I.. -O4 -DNDEBUG -std=c++0x -Wall -MT insert_throughput.o -MD -MP -MF .deps/insert_throughput.Tpo -c -o insert_throughput.o insert_throughput.cc
insert_throughput.cc:53:11: error: expected nested-name-specifier before ‘KType’
insert_throughput.cc:53:11: error: using-declaration for non-member at class scope
insert_throughput.cc:53:17: error: expected ‘;’ before ‘=’ token
insert_throughput.cc:53:17: error: expected unqualified-id before ‘=’ token
insert_throughput.cc:95:17: error: ‘KType’ was not declared in this scope
insert_throughput.cc:95:22: error: template argument 1 is invalid
insert_throughput.cc:95:22: error: template argument 2 is invalid
insert_throughput.cc: In constructor ‘InsertEnvironment::InsertEnvironment()’:
insert_throughput.cc:66:15: error: invalid types ‘int[int]’ for array subscript
insert_throughput.cc:69:19: error: invalid types ‘int[size_t {aka unsigned int}]’ for array subscript
insert_throughput.cc:69:35: error: invalid types ‘int[const size_t {aka const unsigned int}]’ for array subscript
insert_throughput.cc:70:25: error: invalid types ‘int[const size_t {aka const unsigned int}]’ for array subscript
insert_throughput.cc:70:41: error: ‘KType’ was not declared in this scope
insert_throughput.cc:78:48: error: ‘KType’ was not declared in this scope
insert_throughput.cc:79:39: error: request for member ‘begin’ in ‘((InsertEnvironment)this)->InsertEnvironment::keys’, which is of non-class type ‘int’
insert_throughput.cc:80:39: error: request for member ‘begin’ in ‘((InsertEnvironment)this)->InsertEnvironment::keys’, which is of non-class type ‘int’
insert_throughput.cc: In function ‘void InsertThroughputTest(InsertEnvironment)’:
insert_throughput.cc:102:11: error: expected nested-name-specifier before ‘KType’
insert_throughput.cc:102:11: error: ‘KType’ has not been declared
insert_throughput.cc:102:17: error: expected ‘;’ before ‘=’ token
insert_throughput.cc:102:17: error: expected primary-expression before ‘=’ token
insert_throughput.cc:102:39: error: expected ‘(’ before ‘;’ token
insert_throughput.cc:108:44: error: ‘KType’ was not declared in this scope
insert_throughput.cc: In function ‘void InsertThroughputTest(InsertEnvironment) [with T = cuckoohash_mapstd::basic_string<char, unsigned int>]’:
insert_throughput.cc:152:33: instantiated from here
insert_throughput.cc:108:9: error: request for member ‘begin’ in ‘env->InsertEnvironment<cuckoohash_map<std::basic_string, unsigned int> >::keys’, which is of non-class type ‘int’
insert_throughput.cc:108:9: error: request for member ‘begin’ in ‘env->InsertEnvironment<cuckoohash_map<std::basic_string, unsigned int> >::keys’, which is of non-class type ‘int’
insert_throughput.cc: In function ‘void InsertThroughputTest(InsertEnvironment) [with T = cuckoohash_map<unsigned int, unsigned int>]’:
insert_throughput.cc:156:33: instantiated from here
insert_throughput.cc:108:9: error: request for member ‘begin’ in ‘env->InsertEnvironment<cuckoohash_map<unsigned int, unsigned int> >::keys’, which is of non-class type ‘int’
insert_throughput.cc:108:9: error: request for member ‘begin’ in ‘env->InsertEnvironment<cuckoohash_map<unsigned int, unsigned int> >::keys’, which is of non-class type ‘int’
make: ** [insert_throughput.o] Error 1

Hi! Thank you very much! for this Concurrent Container (open-source and free). It has very good references. The only 'competitor' that I know is Junction...

I am a newbie. I have a doubt :-?

I have two threads.
In thread 1 the map is iterated and the element are shown/printed (read only). I am using lock_table().

In thread 2 the map is iterated. A condition is evaluated for each element. If the condition is true, the element must be removed.

Well How can i do this? :-(

If i use the lock_table() in thread 2, there are a deadlock.

//THREAD 1

auto lt = m_manager.m_mapadeconexiones.lock_table();
for (const auto& it : lt)
{
   SHOW(it->second);
}

//THREAD 2

auto lt = m_mapadeconexiones.lock_table();

auto it = lt.begin();
while (it != lt.end())
{

if (CONDITION_FOR_REMOVING (it->second)))
{
    m_mapadeconexiones.erase(it->first); //<------ DEADLOCK!!!
}
else
{
++it;
}
}

is it a mistaken approach to the problem/solution?
Thanks for the help! A sample will be incredible. :-}

DJuego

I admit creating such a small hash map is kind of uncommon.

The problem is in reserve_calc(). When capacity is too small,

log2((double)n / (double)SLOT_PER_BUCKET)

gives you a negative number and subsequently new_hashpower is really large.

Hi,

Easy to reproduce:

in count_freq.cc (by the way, the readme page calls that count_freq.cpp):

create a very broken hash function that always returns the same value. Like:

template <class Key>
class brokenHasher {
public:
    size_t operator()(const Key& k) const {
        return 1;
    }
};

template <>
class brokenHasher<std::string> {
public:
    size_t operator()(const std::string& k) const {
        return 1;
    }
};

And adapt the map:

typedef cuckoohash_map<KeyType, size_t, brokenHasher<KeyType> > Table;

then to make it simple, set

const size_t thread_num = 1;
const size_t total_inserts = 10;

Compile and run. Memory goes out the roof at iteration 8 and the exception is thrown.
It breaks in cuckoo_insert_loop, after the expansion.

Now this code is a bit over my head, so I am not able to propose a solution, but I could bet it is the patch for issue #17 that provoked this.

I wrote a simple program to test concurrent insert. However, it seems that the first thread launched always fails to insert keys into the table successfully. See code below. (Note: the spin lock is only to keep the console output from getting garbled when the individual threads print which keys were inserted. The issue remains even without the lock on cout).

#include <iostream>
#include <vector>
#include <atomic>
#include <thread>

#include "libcuckoo/cuckoohash_map.hh"

#define N 4
#define NUM_THREADS 4

using namespace std;

class SpinLock
{
public:
    void lock()
    {
        while(lck.test_and_set(memory_order_acquire)){}
    }
    void unlock()
    {
        lck.clear(memory_order_release);
    }

private:
    atomic_flag lck = ATOMIC_FLAG_INIT;
};

SpinLock coutLock;

void add_to_map(cuckoohash_map<int, int> * mm, const int keyStart, const int keyEnd, const int tid){

    for(int key=keyStart;key<keyEnd;++key){

        auto tmp = mm->insert(key,tid);
        if(tmp){
            coutLock.lock();
            cout << "key: " << key << " inserted" << endl;
            coutLock.unlock();
        }
    }    
}


int main() {

    int Nbefore, Nafter;
    vector<std::thread> threads;

    //create an unordered map, and reserve enough space to avoid a rehash
    cuckoohash_map<int, int>my_map;
    my_map.reserve(NUM_THREADS*N);

    //count number of buckets to make sure that a rehash didn't occur
    Nbefore=my_map.bucket_count();

    // Clear hash table and launch NUM_THREADS threads.  Thread k adds keys k*N through (k+1)*N-1 to the hash table, all with associated value = k.
    my_map.clear();
    for(int threadID=0;threadID<NUM_THREADS;++threadID){
        threads.emplace_back(add_to_map,&my_map,threadID*N,(threadID+1)*N,threadID);
    }

    // Wait for the threads to finish
    for(int threadID=0;threadID<NUM_THREADS;++threadID){
        threads[threadID].join();
    }

    //count number of buckets to make sure that a rehash didn't occur
    Nafter=my_map.bucket_count();

    cout << "Number of buckets before adding elements: " << Nbefore <<endl;
    cout << "Number of buckets after  adding elements: " << Nafter  << " <--- same as above, so rehash didn't occur" <<endl;

    //see if any keys are missing
    for(int key=0;key<NUM_THREADS*N;++key){

        if(!my_map.find(key)){
            cout << "key " << key << " not found!" << endl;

        }
    }

    return 0;
}

A representative output would be:

key: 12 inserted
key: 0 inserted
key: 13 inserted
key: 8 inserted
key: 4 inserted
key: 14 inserted
key: 5 inserted
key: 15 inserted
key: 6 inserted
key: 7 inserted
key: 9 inserted
key: 1 inserted
key: 10 inserted
key: 2 inserted
key: 11 inserted
key: 3 inserted
Number of buckets before adding elements: 65536
Number of buckets after  adding elements: 65536 <--- same as above, so rehash didn't occur
key 0 not found!
key 1 not found!
key 2 not found!
key 3 not found!

Changing N or NUM_THREADS has the same effect: the keys inserted by the first (and only the first) thread are never successfully found later.

It is entirely possible I am doing something wrong or have interpreted the concurrent functionality incorrectly. If so, I would appreciate if you could point out my mistake.

The table is like this : <string, int> . There is function foo that lookups the table with a key. If there is a record matching the key, foo decrease the value by 1. If the value is 0, foo delete the record.

I see there is a update_fn(key, fn) where fn can be defined to update the value. But how can I delete the record using fn ?

Any ideas why this might be thrown? Clang and GCC builds work fine, but we'd like to use libcuckoo with icpc.

icpc -DPACKAGE_NAME="libcuckoo-tests" -DPACKAGE_TARNAME="libcuckoo-tests" -DPACKAGE_VERSION="1.0" -DPACKAGE_STRING="libcuckoo-tests\ 1.0" -DPACKAGE_BUGREPORT="" -DPACKAGE_URL="" -DPACKAGE="libcuckoo-tests" -DVERSION="1.0" -DSTDC_HEADERS=1 -DHAVE_SYS_TYPES_H=1 -DHAVE_SYS_STAT_H=1 -DHAVE_STDLIB_H=1 -DHAVE_STRING_H=1 -DHAVE_MEMORY_H=1 -DHAVE_STRINGS_H=1 -DHAVE_INTTYPES_H=1 -DHAVE_STDINT_H=1 -DHAVE_UNISTD_H=1 -DHAVE_DLFCN_H=1 -DLT_OBJDIR=".libs/" -DHAVE_PTHREAD_PRIO_INHERIT=1 -DHAVE_PTHREAD=1 -I. -O3 -DNDEBUG -pthread -pthread -std=gnu++11 -MT insert_throughput.o -MD -MP -MF .deps/insert_throughput.Tpo -c -o insert_throughput.o insert_throughput.cc
/usr/include/c++/5.3.0/functional(78): error: class "cuckoohash_map<KeyType2, ValType={uint32_t={unsigned int}}, DefaultHasher, std::equal_to, std::allocator<std::pair<const KeyType2, ValType={uint32_t={unsigned int}}>>, 4UL>" has no member "result_type"
{ typedef typename _Functor::result_type result_type; };

In the document, it was said that: "Its interface resembles that of STL's unordered_map but does contain some important differences.", but no detail was mentioned.

I am migrating some code from STL's unordered_map to libcucko's cuckoohash_map. Just in case I misunderstand something, can you clarify?

Thank you in advance,
Ying

Has any one compiled the latest lib-cuckoo on windows? If yes, please do share the steps ?

Johnson

The document said that for find_fn, the fn should implement operator () that should not modify the contents of the value. Could you give an example for that? For example, there is a cuckoohash<string, class* > mp, I have a Get(string& key, int& count) like this:

int Get(string& key, int& count) {
    auto fn = [&count,](const StateCounter*& sc) { count += sc->Get(100); };
    mp.find_fn(key, fn);
    return count;
} 

The above example is not supposed to work. How should I implement the opertator() function to make it work?

Won't cuckoopath_search break with noncopyable keys (like std::unique_ptr) when it tries to copy the key into the CuckooRecord? It currently compiles, so maybe it's doing something bad, like a move assignment into the cuckoo record. Currently we only need the key to determine if the key got deleted or overwritten in between the path search and the moving, so maybe there's another way to detect that without storing the key explicitly.

When you do an upsert, first we try an update, then an insert if the update fails. But when doing the insert, we don't need to scan the whole bucket to check for duplicates, because we just tried doing an update. So ideally the insert would just look for a free slot in either of the buckets and return immediately.

libcuckoo tags the definitions of the cacheint and spinlock classes with alignas(64)/__attribute__((aligned(64))), presumably to avoid false sharing. However it goes on to use these classes in containers like std::vector and lazy_array. AFAIK the std::vector from libstdc++ or MSVC will not respect the alignment of its containing elements, and lazy_array doesn't seem to either. The alignas here ensures that elements are spaced 64-bytes apart, but doesn't ensure they're aligned on 64-byte boundaries.

You may want to consider writing a custom allocator that has support for over-aligned allocations and using it for these containers. The aligned_allocator_adaptor from Boost gives an example.

Hello
I am thinking of using libcuckoohash map in my c++ applicaiton.
Seeking few advice before i get fully plunged into it.
I am designing some real time streaming application where i am hashmapping few data depending upon the unique keys.
So its like from my main thread, i am creating the libcuckoo hashmap like

typedef cuckoohash_map<unsigned int, myObjectStruct > cuckooTable;
cuckooTable *cuckooTableHashMap = NULL;
cuckooTableHashMap = new cuckooTable;

and then sharing cuckooTableHashMap instance with all the 24 threads, now each 24 threads at any second are streaming the data , and i am also inserting the data using the unique key after parsing the streaming data.
so lets consider a thread T1() -> parses the streamed data and extracts the unique key and then tries inserting the object on that extracted key using this code like below

if (!pMAP->find(uID, tempObject)){
  if (pMAP->insert(imei, tempObject1)){
  prtinf("Inserted");   
}
}
else
pMAP->update(uID, tempObject)

now also exactly at same time T4() thread, is also doing the same thing, in that thread it parses the data and found the same key and try inserting using the same above code only. in my poc , i have not considered of taking care of any lock and etc. Should I ?
Is that approach is fine ?

Johnson Neo

Have you considered implementing writing to and reading from disk?

I've been looking for a high-performance concurrent hash table for scientific computing applications, and have been using https://github.com/attractivechaos/klib, which is not threadsafe, because serializing khash with fundamental keys and values is relatively trivial, in spite of the performance cost of only allowing one thread to update the table.

Libcuckoo has been great for use in online applications, and it'd be nice to be able to use it for offline applications as well. I imagine others might find persistence useful.

I haven't actually tested this, but the assumption here about the thread local hazard_pointer:

    // Note that this variable can be safely shared between different
    // cuckoohash_map instances, since multiple operations cannot occur
    // simultaneously in one thread.

can be violated if key_equal accesses a cuckoohash_map with the same template instantiation, since eqfn() is called in some routines that are run after the hazard pointer is set. I believe the same is true of hasher since hashed_key() is called under similar circumstances. Since the hazard pointer is used to determine whether it's safe to free the TableInfo, it seems like this can cause use after free.

If I am right, and this can cause memory unsafety (and I might not be), it seems like an easy way to mitigate it without losing much performance would be to always assert that *hazard_pointer is null before you set it to ti. While this might be annoying since I can think of legitimate reasons you might want to check a hash table in an equality predicate, it's probably better than the alternative (potential silent memory corruption). I'd also document this behavior somewhere.

please advise?

foo.cpp:

#include <libcuckoo/cuckoohash_map.hh>
#include <libcuckoo/city_hasher.hh>

typedef cuckoohash_map<int, int> Map;
Map map;

$ g++ -Wall -fPIC -std=c++11 -shared -o foo.so foo.cpp
$ LD_PRELOAD=./foo.so someprocess
$ symbol lookup error: ./foo.so: undefined symbol: _ZN14cuckoohash_mapIiiSt4hashIiESt8equal_toIiEE6Bucket13key_allocatorE

Hello, folks!

I'm developing connection tracking toolkit and trying to replace std::map with mutexes with libcuckoo.

But unfortunately it slightly faster, my std::map version have performance about 400 kpps. libcuckoo could achieve about 800 kpps.

My workload pattern: 4 threads and random src/ip/ports which used as key:

    if (packet_direction == OUTGOING or packet_direction == INCOMING) {
        std::string connection_tracking_hash_string = convert_ip_as_uint_to_string(current_packet.dst_ip) + "_" + convert_ip_as_uint_to_string(current_packet.src_ip) + "_" +
            convert_ip_as_uint_to_string(current_packet.source_port) + "_" + convert_ip_as_uint_to_string(current_packet.destination_port) + "_" + convert_ip_as_uint_to_string(current_packet.protocol) + "_";
            get_direction_name(packet_direction);

        map_element temp_element;

        if (flow_tracking_table_new_generation.find(connection_tracking_hash_string, temp_element)) {
            // found!

        } else {
            // not found, create it
            flow_tracking_table_new_generation.insert(connection_tracking_hash_string, temp_element);       
        }
    }

Could you recommend anything for me?

We've been using libcuckoo happily for a while now but we've noticed recently that our builds are quite large (unit test executables > 20MB, builds > 1.4GB), and we're getting a huge number of libcuckoo and city_hash symbols. I don't think that we're doing anything unusual with libcuckoo.

Is this expected or is this a surprise? Is there a workaround that you could suggest? I can provide any debugging information necessary.

It would be nice to be able to leave standard unordered_map code intact, like:

for (auto itr = map.cbegin(); itr != map.cend(); ++itr) { doStuff(); }

Right now we have to change the above to use the .is_end() function.

Even better would be to have support for the BOOST_FOREACH feature of boost.

Would the following be sufficient?
bool operator==(const const_iterator& it) { return index_ == it.index_ && slot_ == it.slot_; }
bool operator!=(const const_iterator& it) { return !this->operator==(it); }

Hi guys,

I'm looking to use nested tables with this library and noticed the memory consumption is high. I want to check if this is expected.

This is the code I ran based on the nested table example. In this case, I am inserting 1000 inner tables.

typedef cuckoohash_map<std::string, std::string> InnerTable;
typedef cuckoohash_map<std::string, std::unique_ptr<InnerTable>> OuterTable;

int main() {
    OuterTable tbl;

    for(int i = 0; i< 1000; i++){
        tbl.insert("bob" + i, std::unique_ptr<InnerTable>(new InnerTable(2)));
    }
    sleep(5);
}

The output from top:

65047 elvin     20   0 2662m 2.6g 1060 S  0.0  4.1   0:01.74  7 ./nested_table 

The memory consumption was 2.6 Gb after all the tables are allocated. That works out to about 2.6 Mb per table. The memory used is similar even if I allocate 1000 outer tables.

I cannot figure out why each empty hashmap requires 2.6 Mb of memory.

Any help on my code or explanation to help me understand is greatly appreciated.

Thanks in advance.

Elvin

Thank you for the quick resolution on the prior issue. Poking around, I'm finding one other concern regarding memory allocation and freeing when the # bucket entries needed is larger than the existing allocation.

Looking at examples/count_freq.cc and src/cuckoohash_map.hh:
If I modify the cuckoohash_map constructor to print out when it is allocating,

explicit cuckoohash_map(size_t n = DEFAULT_SIZE) {
        const size_t hp = reserve_calc(n);
        TableInfo* ptr = get_tableinfo_allocator().allocate(1);
        try {
        fprintf(stderr,"Calling cuckoohash_map with hp %ld\n", hp);  fflush(stderr); // add this line
            get_tableinfo_allocator().construct(ptr, hp);
            table_info.store(ptr);
        } catch (...) {
            get_tableinfo_allocator().deallocate(ptr, 1);
            throw;
        }
    }

and TableInfo() constructor and destructor to show when it is allocating and freeing,

 TableInfo(const size_t hp)
            : hashpower(hp), buckets(hashsize(hp)),
              num_inserts(kNumCores(), 0), num_deletes(kNumCores(), 0) { 
          fprintf(stderr,"allocating 2^ %ld buckets\n", hashpower); fflush(stderr); // add this line
              }

        TableInfo(const TableInfo&) = delete;
        TableInfo(TableInfo&&) = delete;

        ~TableInfo() {
          fprintf(stderr,"de-allocating table with 2^ %ld buckets\n", hashpower); fflush(stderr); // add this line
              }

Then running the count_freq.cc example, I get:
Calling cuckoohash_map with hp 16
allocating 2^ 16 buckets
Calling cuckoohash_map with hp 22
allocating 2^ 22 buckets
2373133380 occurred 3 times.
Table size: 9988385
Bucket count: 4194304
Load factor: 0.595354
de-allocating table with 2^ 22 buckets
de-allocating table with 2^ 16 buckets

It seems as though the initial allocation of 2^16 buckets (DEFAULT_SIZE) doesn't get freed until after the larger allocation gets freed at the end.

If I modify the count_freq.cc map to allocate the full amount needed in the allocation:

int main() {
    Table freq_map(total_inserts);
    freq_map.reserve(total_inserts);

...then I just see one allocation and one deallocation (as expected):
Calling cuckoohash_map with hp 22
allocating 2^ 22 buckets
4255206843 occurred 4 times.
Table size: 8740950
Bucket count: 4194304
Load factor: 0.521001
de-allocating table with 2^ 22 buckets

However, if I comment out the "reserve" line altogether, and leave the Table declaration alone:

int main() {
    Table freq_map;
    //freq_map.reserve(total_inserts);

...then I get:
Calling cuckoohash_map with hp 16
allocating 2^ 16 buckets
Calling cuckoohash_map with hp 17
allocating 2^ 17 buckets
Calling cuckoohash_map with hp 18
allocating 2^ 18 buckets
de-allocating table with 2^ 16 buckets
Calling cuckoohash_map with hp 19
allocating 2^ 19 buckets
de-allocating table with 2^ 17 buckets
Calling cuckoohash_map with hp 20
allocating 2^ 20 buckets
de-allocating table with 2^ 18 buckets
Calling cuckoohash_map with hp 21
allocating 2^ 21 buckets
de-allocating table with 2^ 19 buckets
Calling cuckoohash_map with hp 22
allocating 2^ 22 buckets
de-allocating table with 2^ 20 buckets
2975383928 occurred 3 times.
Table size: 9988404
Bucket count: 4194304
Load factor: 0.595355
de-allocating table with 2^ 22 buckets
de-allocating table with 2^ 21 buckets

I see the (expected) automatic re-allocations occurring, but the older (too-small) allocations don't seem to be getting freed until the yet-next-larger size is re-re-allocated. Freeing always seems to lag re-allocating by an extra steps, seemingly resulting in a lot of extra memory left allocated when the arrays get big and need to dynamically resize.

Is there an explicit call that I should be making or testing to ensure the all the old allocations are freed once the new allocation is made and the old has been copied?

upsert is very useful.

But before calling upsert, a new value has to be created, even the value may be not needed for insert won't happen.

In order to simply the logic and to minimize the memory management, can you provide upsert_fn, such as:

template <typename Updater, typename K, typename Getter>
typename std::enable_if<
std::is_convertible<Updater, updater_type>::value,
void>::type upsert_fn(K&& key, Updater fn, Getter gt);

Thank you in advance,
Ying

I havent use one variable many times becouse it swaped with other varible with null value

example:

typedef cuckoohash_mapstd::string,std::string s_table;
s_table s_sessions;
s_table s_services;

auto updatefn = [](std::string &a){};

std::string *str = new std::string("123");
auto res = s_sessions.upsert(*str, updatefn, cid);
if(!res){

}
else{
// problem here!!!
// *str after upsert or insert swap with other varidable that have null value and string below is
// "STRING: ", but it has to be "STRING: 123"
std::cout << "STRING: " << *str << std::endl;

s_services.insert(*str, 0); // this not working becouse after upsert *str is empty
}