Intel TSX simple benchmark

tsx.cpp

#include <atomic>
#include <chrono>
#include <immintrin.h>
#include <iostream>
#include <thread>

struct Node {
    Node * prev{};
    Node * next{};
};

static std::atomic<int> op_cnt{};
static std::atomic<int> ls_len{};

static std::atomic<int> failed{};

static Node head{};
static Node * phead = &head;

constexpr int kOps = 1000000;
constexpr int kLen = 1000;

static void work() {
    while (op_cnt.fetch_add(1) < kOps) {
        Node * cursor = phead;
        int random_run = rand() % kLen;
        for (int i = 1; i < random_run; ++i) {
            if (cursor->next == nullptr) {
                break;
            } else {
                cursor = cursor->next;
            }
        }

        if (ls_len.fetch_add(1) > kLen) {
            ls_len.fetch_sub(1);

            // delete node
            unsigned int status = _xbegin();
            if (status == _XBEGIN_STARTED) {
                if ((cursor->prev == nullptr || cursor->prev->next == cursor) &&
                    (cursor->next == nullptr || cursor->next->prev == cursor) &&
                    phead != cursor) {
                    if (cursor->prev != nullptr) {
                        cursor->prev->next = cursor->next;
                    }
                    if (cursor->next != nullptr) {
                        cursor->next->prev = cursor->prev;
                    }
                    cursor->prev = cursor;
                    cursor->next = nullptr;
                    _xend();

                    ls_len.fetch_sub(1);
                } else {
                    _xabort(6);
                }
            } else {
                failed.fetch_add(1);
            }
        } else {
            // add node
            Node * new_node = new Node;

            unsigned int status = _xbegin();
            if (status == _XBEGIN_STARTED) {
                if ((cursor->prev == nullptr || cursor->prev->next == cursor) &&
                    (cursor->next == nullptr || cursor->next->prev == cursor)) {
                    new_node->prev = cursor->prev;
                    new_node->next = cursor;
                    if (cursor->prev != nullptr) {
                        cursor->prev->next = new_node;
                    }
                    cursor->prev = new_node;
                    if (phead == cursor) {
                        phead = new_node;
                    }
                    _xend();
                } else {
                    _xabort(7);
                }
            } else {
                ls_len.fetch_sub(1);
                failed.fetch_add(1);
            }
        }
    }
}

static void workSingleThread() {
    while (op_cnt.fetch_add(1) < kOps) {
        Node * cursor = phead;
        int random_run = rand() % kLen;
        for (int i = 1; i < random_run; ++i) {
            if (cursor->next == nullptr) {
                break;
            } else {
                cursor = cursor->next;
            }
        }

        if (ls_len.fetch_add(1) > kLen) {
            ls_len.fetch_sub(2);
            if (cursor->prev != nullptr) {
                cursor->prev->next = cursor->next;
            }
            if (cursor->next != nullptr) {
                cursor->next->prev = cursor->prev;
            }
            cursor->prev = cursor;
            cursor->next = nullptr;
        } else {
            // add node
            Node * new_node = new Node;
            new_node->prev = cursor->prev;
            new_node->next = cursor;
            if (cursor->prev != nullptr) {
                cursor->prev->next = new_node;
            }
            cursor->prev = new_node;
            if (phead == cursor) {
                phead = new_node;
            }
        }
    }
}

#define TIME_START auto start = std::chrono::high_resolution_clock::now()
#define TIME_END auto end = std::chrono::high_resolution_clock::now()
#define PRINT_TIME(name) \
std::cout << name " took " << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() << " milliseconds" << std::endl

int main() {
    srand(time(nullptr));

    TIME_START;
    auto a = std::thread(work);
    auto b = std::thread(work);
    a.join();
    b.join();
    TIME_END;
    PRINT_TIME("TSX linked list insert");

    std::cout << "failed " << failed << std::endl;

    // check correctness
    std::cout << ls_len << std::endl;
    Node * cursor = phead;
    for (int i = 0; i < ls_len.load(); ++i) {
        if (cursor->next == nullptr) {
            exit(8);
        }
        if (cursor->prev != nullptr && cursor->prev->next != cursor) {
            exit(9);
        }
        if (cursor->next != nullptr && cursor->next->prev != cursor) {
            exit(10);
        }
        cursor = cursor->next;
    }
    return 0;
}