set_bench.md

Add

from lpython import i32

def test_set_add():
    s1: set[i32] = {0}
    i: i32
    total: i32 = 10000000

    # https://en.wikipedia.org/wiki/Lehmer_random_number_generator
    # Precomputed parameters for Schrage's method
    M: i32 = 0x7fffffff
    A: i32 = 48271
    Q: i32 = M // A  # 44488
    R: i32 = M % A   # 3399
    div: i32
    rem: i32
    s: i32
    t: i32
    x: i32 = M - 1  # co-prime with M

    for i in range(0, total):
        s1.add(x)

        div = x // Q
        rem = x % Q
        s = rem * A
        t = div * R
        x = s - t
        if x < 0:
            x += M

    assert len(s1) >= total

test_set_add()

def test_set_add():
    s1 = {0}
    total = 10000000

    M = 0x7fffffff
    A = 48271
    Q = M // A
    R = M % A
    x = M - 1

    for i in range(0, total):
        s1.add(x)
        div = x // Q
        rem = x % Q
        s = rem * A
        t = div * R
        x = s - t
        if x < 0:
            x += M

    assert len(s1) >= total

test_set_add()

#include <unordered_set>
#include <cassert>

void test_set_add() {
    std::unordered_set<int32_t> s1 = {0};
    uint32_t i;
    uint32_t total = 10000000;

	const uint32_t M = 0x7fffffff;
	const uint32_t A = 48271;
	const uint32_t Q = M / A;
	const uint32_t R = M % A;
    int32_t x = M - 1;
    int32_t div, rem, s, t;

    for(i = 0; i < total; i++) {
        s1.insert(x);

        div = x / Q;
        rem = x % Q;
        s = rem * A;
        t = div * R;
        x = s - t;
        if (x < 0) {
            x += M;
        }
    }

    assert(s1.size() >= total);
}

int main() {
    test_set_add();
}

Compiler	Time (user + sys) [s]	Relative
Lpython	0.64	1.0
Lpython --fast	0.56	0.88
g++	6.25	9.77
g++ -O3 -funroll-loops -ffast-math	4.00	6.25
g++ ModuloHash	5.68	8.88
g++ -O3 -funroll-loops -ffast-math ModuloHash	4.03	6.30
Python 3.10.2	2.92	4.57

Add and Remove

from lpython import i32

def test_set():
    s1: set[i32] = {0}
    i: i32
    total: i32 = 10000000

    M: i32 = 0x7fffffff
    A: i32 = 48271
    Q: i32 = M // A
    R: i32 = M % A
    div: i32
    rem: i32
    s: i32
    t: i32
    x: i32 = M - 1

    for i in range(0, total):
        s1.add(x)
        div = x // Q
        rem = x % Q
        s = rem * A
        t = div * R
        x = s - t
        if x < 0:
            x += M

    assert len(s1) == total + 1

    x = M - 1

    for i in range(0, total):
        s1.remove(x)
        div = x // Q
        rem = x % Q
        s = rem * A
        t = div * R
        x = s - t
        if x < 0:
            x += M

    s1.remove(0)

    assert len(s1) == 0

test_set()

def test_set():
    s1 = {0}
    total = 10000000

    M = 0x7fffffff
    A = 48271
    Q = M // A
    R = M % A
    x = M - 1

    for i in range(0, total):
        s1.add(x)
        div = x // Q
        rem = x % Q
        s = rem * A
        t = div * R
        x = s - t
        if x < 0:
            x += M

    assert len(s1) == total + 1

    x = M - 1

    for i in range(0, total):
        s1.remove(x)
        div = x // Q
        rem = x % Q
        s = rem * A
        t = div * R
        x = s - t
        if x < 0:
            x += M

    s1.remove(0)

    assert len(s1) == 0

test_set()

#include <unordered_set>
#include <cassert>

uint32_t total = 10000000;

struct ModuloHash {
    size_t operator() (int32_t elem) const
    {
        return elem % total;
    }
};

void test_set() {
    std::unordered_set<int32_t> s1 = {0};
    uint32_t i;

	const uint32_t M = 0x7fffffff;
	const uint32_t A = 48271;
	const uint32_t Q = M / A;
	const uint32_t R = M % A;
    int32_t x = M - 1;
    int32_t div, rem, s, t;

    for(i = 0; i < total; i++) {
        s1.insert(x);
        div = x / Q;
        rem = x % Q;
        s = rem * A;
        t = div * R;
        x = s - t;
        if (x < 0) {
            x += M;
        }
    }

    assert(s1.size() == total + 1);

    x = M - 1;

    for(i = 0; i < total; i++) {
        s1.erase(x);
        div = x / Q;
        rem = x % Q;
        s = rem * A;
        t = div * R;
        x = s - t;
        if (x < 0) {
            x += M;
        }
    }

    s1.erase(0);

    assert(s1.size() == 0);
}

int main() {
    test_set();
}

Compiler	Time (user + sys) [s]	Relative
Lpython	1.23	1.0
Lpython --fast	1.19	0.97
g++	8.83	7.18
g++ -O3 -funroll-loops -ffast-math	5.91	4.80
g++ ModuloHash	8.29	6.74
g++ -O3 -funroll-loops -ffast-math ModuloHash	6.02	4.90
Python 3.10.2	4.44	3.61

set_bench_str.md

Strings

Linear Probing implementation

from lpython import i32

def test_set():
    s1: set[str] = {'0'}
    i: i32
    total: i32 = 10000000

    M: i32 = 0x7fffffff
    A: i32 = 48271
    Q: i32 = M // A
    R: i32 = M % A
    div: i32
    rem: i32
    s: i32
    t: i32
    x: i32 = M - 1

    for i in range(0, total):
        s1.add(str(x))
        div = x // Q
        rem = x % Q
        s = rem * A
        t = div * R
        x = s - t
        if x < 0:
            x += M

    assert len(s1) == total + 1

    x = M - 1

    for i in range(0, total):
        s1.remove(str(x))
        div = x // Q
        rem = x % Q
        s = rem * A
        t = div * R
        x = s - t
        if x < 0:
            x += M

    s1.remove('0')

    assert len(s1) == 0

test_set()

def test_set():
    s1 = {'0'}
    total = 10000000

    M = 0x7fffffff
    A = 48271
    Q = M // A
    R = M % A
    x = M - 1

    for i in range(0, total):
        s1.add(str(x))
        div = x // Q
        rem = x % Q
        s = rem * A
        t = div * R
        x = s - t
        if x < 0:
            x += M

    assert len(s1) == total + 1

    x = M - 1

    for i in range(0, total):
        s1.remove(str(x))
        div = x // Q
        rem = x % Q
        s = rem * A
        t = div * R
        x = s - t
        if x < 0:
            x += M

    s1.remove('0')

    assert len(s1) == 0

test_set()

#include <unordered_set>
#include <string>
#include <cassert>

uint32_t total = 10000000;

struct PolynomialRollingHash {
    size_t operator() (const std::string& key) const
    {
        const uint64_t p = 31;
        const uint64_t m = 100000009;
        uint64_t hash_value = 0;
        uint64_t p_pow = 1;
        for (char c : key) {
            hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
            p_pow = (p_pow * p) % m;
        }
        return hash_value % total;
    }
};

void test_set() {
    std::unordered_set<std::string> s1 = {"0"};
    uint32_t i;

	const uint32_t M = 0x7fffffff;
	const uint32_t A = 48271;
	const uint32_t Q = M / A;
	const uint32_t R = M % A;
    int32_t x = M - 1;
    int32_t div, rem, s, t;

    for(i = 0; i < total; i++) {
        s1.insert(std::to_string(x));
        div = x / Q;
        rem = x % Q;
        s = rem * A;
        t = div * R;
        x = s - t;
        if (x < 0) {
            x += M;
        }
    }

    assert(s1.size() == total + 1);

    x = M - 1;

    for(i = 0; i < total; i++) {
        s1.erase(std::to_string(x));
        div = x / Q;
        rem = x % Q;
        s = rem * A;
        t = div * R;
        x = s - t;
        if (x < 0) {
            x += M;
        }
    }

    s1.erase("0");

    assert(s1.size() == 0);
}

int main() {
    test_set();
}

Compiler	Time (user + sys) [s]	Relative
Lpython	6.13	1.0
Lpython (Separate Chaining)	6.20	1.01
Lpython --fast	6.20	1.01
Lpython --fast (Separate Chaining)	5.89	0.96
g++	10.34	1.69
g++ -O3 -funroll-loops -ffast-math	7.55	1.23
g++ PolynomialRollingHash	11.33	1.85
g++ -O3 -funroll-loops -ffast-math PolynomialRollingHash	8.09	1.32
Python 3.10.2	6.25	1.02