khizmax/libcds

Skip List Map Usage

Closed this issue · 4 comments

jarulraj commented

In the container cds::container::SkipListMap<cds::gc::nogc, KeyType, ValueType, skip_list_map_traits> skip_list_map_t, is it possible for insert to fail even when the key does not exist ?

I ran a multi-threaded insert workload (4 threads), and it looks like some of the insert operations fail even when the key does not exist (~30%).

khizmax commented

It should not be. If so it is a bug.Can you provide your testcase?

jarulraj commented 
class SkipListMap<uint32_t, uint32_t, std::less<uint32_t>> test_skip_list_map;

const std::size_t base_scale = 1000;
const std::size_t max_scale_factor = 10000;

// INSERT HELPER FUNCTION
void InsertTest(size_t scale_factor, uint64_t thread_itr) {

  uint32_t base = thread_itr * base_scale * max_scale_factor;
  uint32_t tuple_count = scale_factor * base_scale;

  for (uint32_t tuple_itr = 1; tuple_itr <= tuple_count; tuple_itr++) {
    uint32_t tuple_offset = base + tuple_itr;

    auto status = test_skip_list_map.Insert(tuple_offset, tuple_offset);
    EXPECT_TRUE(status);
  }

}

// Test multithreaded functionality
TEST_F(SkipListMapTest, MultithreadedTest) {

  // Parallel Test
  size_t num_threads = 4;
  size_t scale_factor = 10;

  std::vector<std::thread> thread_group;

  // Uses thread group
  LaunchParallelTest(num_threads, InsertTest, scale_factor);
}

Here are some links to the source code:

Test case : https://github.com/cmu-db/peloton/blob/cds/test/container/skip_list_map_test.cpp#L93
Include : https://github.com/cmu-db/peloton/blob/cds/src/include/container/skip_list_map.h
Source : https://github.com/cmu-db/peloton/blob/cds/src/container/skip_list_map.cpp

We are using version 2.1.0 on a Linux x86_64 machine with gcc 4.9.3.

khizmax commented

I'm not quite sure but lines 37-41 in https://github.com/cmu-db/peloton/blob/cds/src/include/container/skip_list_map.h are suspicious:

  struct skip_list_map_traits: public cds::container::skip_list::traits {
    typedef KeyComparator compare;  // suspicious for me
    typedef KeyComparator less;
};

In libcds, compare predicate has high priority than less.

Further, you declare SkipList with std::less. Here std::less is used as compare that is wrong.
compare( Key const& a, Key const& b) returns (like std::string::compare):

  • -1 if a < b
  • 0 if a == b
  • 1 if a > b

Please, try to comment line 38: https://github.com/cmu-db/peloton/blob/cds/src/include/container/skip_list_map.h#L38