Non generic Skip List implementation in C++

Question

Edit: This code was reworked and repostetd under a new question: Non generic Skip List implementation in C++ Version 2

To sharpen my C++ skills I tried to implement a skip list.

I was quite happy when it finally seemed to work correctly. Unfortunately, the implementation is kinda slow. When I run the main were I randomly insert / erase a map and my skip list, it's always like twice as slow as the map (I tried it with Visual Studio 2017 in Release).

I wonder what can be improved to get the big performance gain. I suspect the use of vector in the skipnode and the random number generator. I wonder if there's a faster way to flip a coin to establish the levels. I would also appreciate it if you have any other suggestions to improve the code.

One Note: I know it should be normally generic with templates. But first I want to make the code good before in the next step make it generic for any type.

skiplist.h

#ifndef SKIP_LIST_GUARD
#define SKIP_LIST_GUARD

#include <iostream>
#include <random>
#include <functional>
#include <vector>
#include <utility>
#include <exception>

namespace Skiplist {

    struct Skipnode {
        Skipnode(int key, int val, int lvl);
        std::pair<int, int> kv;     //first key, second value
        std::vector <Skipnode*> next;
    };

    class Skiplist {
    public:
        Skiplist()
            :maxlvl{ 0 }, head{ nullptr }, m_mt(std::random_device()())
        {
        }

        ~Skiplist();

        void insert(int key, int val);
        bool erase(int key);                //search for an element and erase it from the skip list
        Skipnode* find(int key) const;          //find element by key and return the value

        int size() const;
        int get_maxlvl() const { return maxlvl; }

        void print() const;
        void debug_print() const;
    private:
        bool next_level()  
            //flips a coin if true goes up one lvl
            // with every layer the chance is half so 1 = 50% 2 = 25% etc.....
        {
            std::uniform_int_distribution<int> dist(0, 1);
            return dist(m_mt);
        }

        Skipnode* head;     //element before first element
        int maxlvl;         // maximum level the nodes have reached so far
        std::mt19937 m_mt;  //random generator member
    };

    int get_random(int min, int max);
}
#endif

skiplist.cpp

#include "skiplist.h"

namespace Skiplist {

    Skipnode::Skipnode(int key, int val, int lvl)
    {
        kv = std::make_pair(key, val);
        for (int i = 0; i < lvl; ++i)       //build all pointers for the lvl
            next.push_back(nullptr);
        next.shrink_to_fit();               //to not waste space
    }

    Skiplist::~Skiplist()
    {
        if (head == nullptr) return;

        Skipnode* currpos = head;   //start on head

        while (currpos->next[0] != nullptr) {
            Skipnode* lastpos = currpos;
            currpos = currpos->next[0];
            delete lastpos;
        }
        delete currpos;         //delete last element
    }

    void Skiplist::insert(int key, int val)
    {
        //calculate max height of new node
        int new_node_lvl = 0;
        do {
            ++new_node_lvl;
            if (new_node_lvl == (maxlvl + 1)) {         //new node can maximum grow by one lvl;
                ++maxlvl;
                if (maxlvl == 1) {                      //case first row needs to be created;
                    head = new Skipnode(0, 0, 0);       //make a empty head
                }
                head->next.push_back(nullptr);
                head->next.shrink_to_fit();             //to not waste to much space
                break;
            }
        } while (next_level());     //flip coin. every time it is true go to the next lvl

        Skipnode* new_node = new Skipnode(key,val,new_node_lvl);    //create new node
        int currlvl = maxlvl - 1;                                   //start on highest lvl

        Skipnode* currpos = head;       //start on head

        while (true) {
            if (currpos->next[currlvl] == nullptr || currpos->next[currlvl]->kv.first > key) {
                if (currlvl < new_node->next.size()){       //if node will be on this lvl. Install node on it
                    new_node->next[currlvl] = currpos->next[currlvl];
                    currpos->next[currlvl] = new_node;
                }
                --currlvl;      // go to the next lvl
                if (currlvl < 0)
                    break;
                continue;
            }
            currpos = currpos->next[currlvl];
        }
    }

    bool Skiplist::erase(int key)
    {
        Skipnode* currpos = head;       //start on head
        int currlvl = maxlvl - 1;       //start on highest lvl

        while (currlvl >=0) {
            if (currpos->next[currlvl] == nullptr) {
                --currlvl;
                continue;
            }
            else if (currpos->next[currlvl]->kv.first > key) {
                --currlvl;
                continue;
            }
            else if (currpos->next[currlvl]->kv.first == key) {     //key found on current lvl
                --currlvl;                                          //go down first before link is deleted
                if(currlvl+1 !=0)
                    currpos->next[currlvl+1] = currpos->next[currlvl+1]->next[currlvl+1];   //take out pointer of found element from list
                else {                      //case end 
                    Skipnode* keynode = currpos->next[currlvl+1];
                    currpos->next[currlvl+1] = currpos->next[currlvl + 1]->next[currlvl + 1];
                    delete keynode;

                    if (head->next[maxlvl - 1] == nullptr  && maxlvl >1) {  //no nodes on highest lvl 
                        head->next.pop_back();                              //delete empty lvl
                        --maxlvl;
                    }
                    return true;
                }
                continue;
            }
            currpos = currpos->next[currlvl];
        }
        return false;
    }

    Skipnode* Skiplist::find(int key) const
        //find element by key and return value
    {
        Skipnode* currpos = head;       //start on head
        int currlvl = maxlvl - 1;       //start on highest lvl

        while (true) {
            if (currpos->next[currlvl] == nullptr || (currlvl > 0 && currpos->next[currlvl]->kv.first >= key)) {
                --currlvl;
                if (currlvl < 0)
                    return nullptr;                         //element was not found;
                continue;
            }

            if (currlvl == 0 && currpos->next[currlvl]->kv.first == key) {      // element found
                currpos = currpos->next[currlvl];
                return currpos;
            }
            currpos = currpos->next[currlvl];
        }
        return nullptr;
    }

    int Skiplist::size() const
    {
        if (head == nullptr) return 0;      //special case nothing is build yet

        int sz = 0;

        Skipnode* currpos = head;

        if (currpos->next.empty())
            return sz;

        while (currpos->next[0] != nullptr) {
            ++sz;
            currpos = currpos->next[0];
        }
        return sz;
    }

    void Skiplist::print() const
        //prints out all elements
    {
        Skipnode* currpos = head;

        while (currpos != nullptr) {
            if(currpos != head)
                std::cout << currpos->kv.first<<"/"<< currpos->kv.second << " ";
            currpos = currpos->next[0];
        }
        std::cout << "\n";
    }

    void Skiplist::debug_print() const
        //messy debug routine to print with all available layers
    {
        Skipnode* currpos = head;

        int currlvl = currpos->next.size() - 1;
        currpos = currpos->next[currlvl];

        if (head->next[0] == nullptr)
            return;

        while (currlvl >= 0) {
            std::cout << "lvl: " << currlvl << "\t";

            Skipnode* lastpos = head;

            while (currpos != nullptr) {

                if (currlvl > 0) {
                    int void_count = 0;
                    while (lastpos != nullptr && lastpos->kv.first != currpos->kv.first) {
                        lastpos = lastpos->next[0];
                        ++void_count;
                    }

                    for (int i = 0; i < void_count-1; ++i)
                        std::cout << "-/-- ";
                }
                if(currpos != head)
                    std::cout << currpos->kv.first << "/" << currpos->kv.second << " ";
                currpos = currpos->next[currlvl];
            }
            std::cout << "\n";
            --currlvl;
            currpos = head;
        }
        std::cout << "\n";
    }

    int get_random(int min, int max)
    {
        static std::random_device rd;
        static std::mt19937 mt(rd());
        std::uniform_int_distribution<int> distribution(min, max);
        return distribution(mt);
    }
}

main.cpp

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <ctime>
#include "skiplist.h"

int main()
try {
    constexpr int repeats = 30;
    constexpr int count_of_elements = 5000000;

    std::vector <int> rnd;
    std::map <int, int > mp;

    for (int i = 0; i < repeats; ++i) {

        for (int j = 0; j < count_of_elements; ++j) {   //fill vector with 100.000 unique random elements
            int in = 0;
            while (true) {
                in = Skiplist::get_random(1, std::numeric_limits<int>::max());
                bool twice = false;         
                auto it = mp.find(in);
                if (it == mp.end())
                    break;
            }
            rnd.push_back(in);
            mp.insert(std::make_pair(in,i));
        }

        std::cout << rnd.size() << "\n";

        mp.clear();

        std::cout << '\n';

        //fill map and skiplist and compare
        clock_t begin_sk = clock();
        Skiplist::Skiplist sk;
        for (std::size_t i = 0; i < rnd.size(); ++i)
            sk.insert(rnd[i], i);
        clock_t end_sk = clock();
        std::cout << "skiplist filled.    Time:" << double(end_sk - begin_sk) / CLOCKS_PER_SEC << "\n";

        clock_t begin_sk_d = clock();
        for (std::size_t i = 0; i < rnd.size(); ++i)
            sk.erase(rnd[i]);
        clock_t end_sk_d = clock();
        std::cout << "skiplist deleted. Time:" << double(end_sk_d - begin_sk_d) / CLOCKS_PER_SEC << "\n";

        std::cout << '\n';

        clock_t begin_mp = clock();
        std::map<int, int> mp;
        for (std::size_t i = 0; i < rnd.size(); ++i)
            mp.insert(std::pair<int, int>(rnd[i], i));
        clock_t end_mp = clock();
        std::cout << "map   filled.       Time:" << double(end_mp - begin_mp) / CLOCKS_PER_SEC << "\n";

        clock_t begin_mp_d = clock();
        for (std::size_t i = 0; i < rnd.size(); ++i)
            mp.erase(rnd[i]);
        clock_t end_mp_d = clock();
        std::cout << "map deleted.      Time:" << double(end_mp_d - begin_mp_d) / CLOCKS_PER_SEC << "\n";

        std::cout << '\n';
    }

    std::cin.get();
}
catch (std::runtime_error& e) {
    std::cerr << e.what() << "\n";
    std::cin.get();
}
catch (...) {
    std::cerr << "unknown error\n";
    std::cin.get();
}

You might want to add a description of how a skiplist is supposed to work. From reading the code, I can't seem to wrap my head around what this weird tree structure does and what it tries to accomplish. — hoffmale
– hoffmale, Commented Jun 26, 2018 at 21:08
It's not supprising that a skiplist would be twice as slow as a hashmap for insertions and deletions. A hashmap is O(1) for insertion/deletion and the skiplist is O(n log n) for both. — Peter
– Peter, Commented Jun 26, 2018 at 21:24
@Peter: std::map is tree based, so O(log n) insertion/deletion. Hash map in C++ would be std::unordered_map. Also, I don't get where you take O(n log n) from for skip list insertion/deletion, wikipedia lists O(log n) for average case, O(n) for worst case. — hoffmale
– hoffmale, Commented Jun 26, 2018 at 21:35

indi · Accepted Answer · 2018-06-27 01:41:42Z

`skiplist.h`

#include <iostream>
#include <random>
#include <functional>
#include <vector>
#include <utility>
#include <exception>

A lot of these headers don't need to be in skiplist.h. Including unnecessary headers slows down compilation. Instead, include only what is actually needed in the header, and then include the rest in implementation files.

struct Skipnode {
    // ...
    std::pair<int, int> kv;     //first key, second value

There doesn't really seem to be any reason to group the key and value in a pair as the class is currently written. Perhaps there is a long-term reason for it?

Skiplist()
    :maxlvl{ 0 }, head{ nullptr }, m_mt(std::random_device()())
{
}

It's generally better to use in-class initializers for member variables, rather than initializing them in every constructor. That also helps avoid annoying warnings for reordering members in the initializer list. So this could be simplified to:

Skiplist() = default;

Skipnode* head = nullptr;
int maxlvl = 0;
std::mt19937 m_mt = std::mt19937{std::random_device{}()};

And in fact, since there are no other constructors, you don't have to mention the default constructor at all (but you probably should, since this is not a trivial class, and the default constructor is part of the interface).

bool next_level()  
    //flips a coin if true goes up one lvl
    // with every layer the chance is half so 1 = 50% 2 = 25% etc.....
{
    std::uniform_int_distribution<int> dist(0, 1);
    return dist(m_mt);
}

I wouldn't recommend defining this in the header. It's very much an implementation detail, and I can't see any situation where it will depend on T (when you do finally templatize the class). It doesn't need to be part of the class either - it could serve perfectly well defined statically in the class's implementation file.

Now, here's a little observation about performance, because this function is called in a loop. Right now, for each call of this function, you're basically generating a 32-bit random number, then taking the last bit of it. But... what about the other 31 bits?

You don't need to generate a new random number every time you need a bit, because each call generates 32 of them. You only need to call generate a number when you've exhausted them. Something like this:

bool next_level(std::mt19937& eng)
{
    static auto val = std::mt19937::result_type{0}
    static auto bit = std::mt19937::word_size;

    if (bit >= std::mt19937::word_size)
        val = eng();

    return val & (std::mt19937::result_type{1} << (bit++));
}

This probably isn't the best way to implement it because of the statics, but it gives the gist. A better implementation might be a class that stores val and bit as members.

On the same topic, each skip list object probably doesn't need its own Mersenne Twister. The only place it's used is to do the "next level coin flip". It could be an implementation detail hidden in the spurce file. If you do that, then you can probably get away with a single Twister for all skip lists, instead of one in every object. (If you plan on using this skip list in multithreaded code, you would need to guard the Twister with a mutex, or make it thread local (the former is probably better).) Removing the Twister from the class means you don't need the <random> header.

int get_random(int min, int max);

Why is this in this header?

`skiplist.cpp`

Skipnode::Skipnode(int key, int val, int lvl)
{
    kv = std::make_pair(key, val);
    for (int i = 0; i < lvl; ++i)       //build all pointers for the lvl
        next.push_back(nullptr);
    next.shrink_to_fit();               //to not waste space
}

This could be made much simpler, and much more efficient, by making better use of vector's interface:

Skipnode::Skipnode(int key, int val, int lvl) :
    kv{key, val},
    next(lvl, nullptr)
{}

Repeated push_back() means repeated allocation. You could alleviate the problem by using reserve(), but it's much easier to just construct the vector with the right size and content.

But here is where I want to focus on a deeper conceptual problem with the way you're using vector. vector is not a low-level memory management tool; it is not meant for element-level allocation control. Put bluntly, it doesn't work the way you want it to.

What you do in multiple places in you code is fill the vector - usually with push_back() - and then you do shrink_to_fit() "to not waste space". This is misguided for a number of reasons.

First, shrink_to_fit() does not guarantee that it will actually do what you want it to do. The implementation is free to ignore your request.
Second, if shrink_to_fit() does honour your request, what you end up doing is triggering a reallocation and copy.

So to use the loop in insert() as an example, on each pass through the loop, what happens is:

head->next.push_back(nullptr); will trigger:

a. an allocation of (let's say) head->next.size() * 2

b. copying/moving head->next.size() + 1 elements to the new memory

c. deleting the old memory
head->next.shrink_to_fit(); will trigger:

a. an allocation of (you assume) head->next.size()

b. copying/moving head->next.size() elements to the new memory

c. deleting the old memory

That's two allocations and full copies per level. When you're dealing with millions of elements - as you are in your tests - you can see how this can quickly add up.

Now, you might think that you can fix this by replacing:

head->next.push_back(nullptr);
head->next.shrink_to_fit();

with:

head->next.reserve(head->next.size() + 1);
head->next.push_back(nullptr);

or perhaps simpler:

head->next.resize(head->next.size() + 1, nullptr);

That might work - it will certainly cut your allocations and copies in half. But there's no guarantee that the vector's capacity will equal its size... which is what you're aiming for.

In fact: nothing you can do will guarantee that the vector's capacity will equal it's size.

So you might as well just give up trying to achieve that, because it's slowing your code down.

If saving memory is really an important concern, vector is the wrong tool for the job. You would have to roll your own container. It could have the same interface as vector, but it would guarantee that the capacity equals the size (which would make it much simpler than vector, but also much slower).

If saving memory isn't that important that it's worth rolling your own container, then just use vector, but stop fighting with it. Just let it manage its memory, and don't try to micromanage it. You're actually slowing things down by doing so.

(I will also point out that you're already not micromanaging memory in your erase() function, because you pop_back() but don't shrink_to_fit(). So you're already leaving vector to do its own thing there.)

Skiplist::~Skiplist()
{
    if (head == nullptr) return;

I'm not sure about the way you use a dummy Skipnode as your head. It seems to add a lot of complexity, for virtually no gain.

Rather than head being a Skipnode* that you have to then check for nullptr and manually allocate, and so on, you could just as well have it as a Skipnode (note, not a pointer). But even that is fraught with problems. Right now you're just holding ints, but when you start holding non-trivial objects, having a dummy node could be problematic. It could be especially difficult if you want to allow non-default constructable objects.

It's also worth mentioning that you've defined a destructor, but no copy/move ops, in violation of the rule of three/five. You'll be needing those too.

void Skiplist::insert(int key, int val)
{
    //calculate max height of new node
    int new_node_lvl = 0;
    do {
        ++new_node_lvl;
        if (new_node_lvl == (maxlvl + 1)) {         //new node can maximum grow by one lvl;
            ++maxlvl;
            if (maxlvl == 1) {                      //case first row needs to be created;
                head = new Skipnode(0, 0, 0);       //make a empty head
            }
            head->next.push_back(nullptr);
            head->next.shrink_to_fit();             //to not waste to much space
            break;
        }
    } while (next_level());     //flip coin. every time it is true go to the next lvl

    Skipnode* new_node = new Skipnode(key,val,new_node_lvl);

I've already mentioned issues with that loop and superfluous allocations above. But you also have memory management issues. Even assuming nothing after the last line above can throw, there's still the fact that in the following loop, if you find a duplicate key, you just... "forget" the old node. It never gets deallocated.

while (true) {
    if (// ...
        // ...
        if (currlvl < 0)
            break;
        continue;
    }
    currpos = currpos->next[currlvl];
}

In several places in your code, you abuse continue to restart a loop when structured control elements would work. This is basically equivalent to using goto - it creates spaghetti code. The above loop would be better structured as:

while (true) {
    if (// ...
        // ...
        if (currlvl < 0)
            break;
    }
    else {
        currpos = currpos->next[currlvl];
    }
}

Similarly in the next function:

bool Skiplist::erase(int key)
{
    Skipnode* currpos = head;       //start on head
    int currlvl = maxlvl - 1;       //start on highest lvl

    while (currlvl >=0) {
        if (currpos->next[currlvl] == nullptr) {
            --currlvl;
            continue;
        }
        else if (currpos->next[currlvl]->kv.first > key) {
            --currlvl;
            continue;
        }
        else if (currpos->next[currlvl]->kv.first == key) {     //key found on current lvl
            --currlvl;                                          //go down first before link is deleted
            if(currlvl+1 !=0)
                currpos->next[currlvl+1] = currpos->next[currlvl+1]->next[currlvl+1];   //take out pointer of found element from list
            else {                      //case end 
                // ...
                return true;
            }
            continue;
        }
        currpos = currpos->next[currlvl];
    }

This would be better structured as:

bool Skiplist::erase(int key)
{
    Skipnode* currpos = head;       //start on head
    int currlvl = maxlvl - 1;       //start on highest lvl

    while (currlvl >=0) {
        if (currpos->next[currlvl] == nullptr) {
            --currlvl;
        }
        else if (currpos->next[currlvl]->kv.first > key) {
            --currlvl;
        }
        else if (currpos->next[currlvl]->kv.first == key) {     //key found on current lvl
            --currlvl;                                          //go down first before link is deleted
            if(currlvl+1 !=0)
                currpos->next[currlvl+1] = currpos->next[currlvl+1]->next[currlvl+1];   //take out pointer of found element from list
            else {                      //case end 
                // ...
                return true;
            }
        }
        else {
            currpos = currpos->next[currlvl];
        }
    }

Those are the only functions involved in your tests, so those are the only ones that are causing your performance issues. The rest of the functions in the interface are basically the same - there's not much there that seems in particular need to being specifically reviewed.

Re: shrink_to_fit: If it resizes, the next call to push_back (e.g. because the max_lvl increased) will allocate again. — hoffmale
– hoffmale, Commented Jun 27, 2018 at 4:27
Yes, and the same is true if you reserve size + 1 or resize size + 1 (assuming the vector does what you want in all three cases)... which is why I recommend not doing any of that, and just let the vector handle itself. — indi
– indi, Commented Jun 27, 2018 at 6:58
do you have a suggestion how to not represent the head element by a node? — Sandro4912
– Sandro4912, Commented Jun 27, 2018 at 17:53
Nothing specific because I honestly don't understand the design all that well. But you have multiple levels of "empty", as can be seen in the size() function. You have head == nullptr, then the first (dummy) node's next.empty(), and then you actually start counting nodes. It may be possible to skip that middle step, and have the first node as an actual node, and not just a dummy. — indi
– indi, Commented Jun 27, 2018 at 23:04

Sandro4912 · Accepted Answer · 2018-06-27 18:36:23Z

Now that i try to implement all the mentioned improvements so far i found some additional points the presented code lacks which i want to share:

Comments / Documentation

I have to admit i wrote this code some months ago and now i came back to it to continue its development after making progress in C++. I realize now what was months ago very clear to me is now hard to get again. In short it would be alot better if the algorithm would be better commented. I try now to comment how each function works in detail. I really feel like this is the biggest problem with my whole code.

Returning value of find

Find currently returns a Skipnode. Thats bad because the Skipnode itself should be an implementation detail. I changed this for now to a pointer of the result:

int* Skiplist::find(int key) const

I guess later it would be better to return an iterator when they are added to the class.

Hidding implementation details

Since Skipnode is only an implementation detail it shouldn't be exposed to the user. What if by accident the user uses it and then i want to change the Skipnode representation?

So it should be added into the class as private member:

class Skiplist {
//...
private:

    struct Skipnode {
        Skipnode(int in_key, int in_value, int level);
        int key;
        int value;
        std::vector <Skipnode*> next;
    };

   //...
};

Stack Exchange Network

Non generic Skip List implementation in C++

2 Answers 2

`skiplist.h`

`skiplist.cpp`

You must log in to answer this question.

Linked

Hot Network Questions

Non generic Skip List implementation in C++

2 Answers 2

skiplist.h

skiplist.cpp

You must log in to answer this question.

Linked

Related

Hot Network Questions

`skiplist.h`

`skiplist.cpp`