# vebtree 0.13.0

A library for van Emde Boas tree

To use this package, run the following command in your project's root directory:

This repository contains a Van Emde Boas tree written in D. It operates on unique integer keys.

See

and

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. MIT Press, 2009. ISBN 978-0-262-53305-8. Chapter 20: The van Emde Boas tree, pp. 531–560.

The idea of bit operations at leaf level was taken from the C++ implementation found at http://www.keithschwarz.com/interesting/code/van-emde-boas-tree/

Example usage:

``````import vebtree;

enum baseSize(T : A!s, alias A, int s) = s;

void main()
{
import std.random : unpredictableSeed, uniform;

/*
The creation could be long, if number generated by unpredictableSeed is large,
but the example works even for (1UL << 32) - 1
*/
auto root = vebRoot(unpredictableSeed); // create the tree structure.
const rndNum = uniform(0, root.universe); // ... and some data

import std.math : nextPow2;
assert(root.capacity == (root.universe - 1).nextPow2);

root.insert(rndNum);
assert(root.prev(rndNum) == size_t.max);
assert(root.next(rndNum) == size_t.max);
assert(root.front == root.back);
assert(root.length == 1);
auto root2 = root.dup;
root2.remove(rndNum);
assert(root2.empty);
assert(root2.length == 0);
assert(rndNum in root);
assert(root == root());
assert(root[].front == 0);
assert(root[].back == root.universe);

import std.range : isBidirectionalRange;
static assert(isBidirectionalRange!(typeof(root[])));

root.universe < baseSize!(typeof(root)) ? assert(root.isLeaf) : assert(!root.isLeaf);
foreach(el; root) assert(el == rndNum);
}
``````

An evaluation of the library shows very good performace compared to the Phobos Red-Black tree and the TTree of EMSI containers.

The evaluation was done with the following code:

``````/+
// dub.json
"dependencies" :
{
"vebtree" : "~>0.12.0",
"emsi_containers": "~>0.8.0-alpha.11"
}

// dub.selections.json
{
"fileVersion": 1,
"versions": {
"emsi_containers": "0.8.0-alpha.12",
"mir-core": "0.2.1",
"stdx-allocator": "2.77.5",
"vebtree": {"path":"../../Libs/vebtree"}
}
}
+/

import containers.ttree;
import std.container.rbtree;
import containers.slist;
import std.container.slist;
import containers.unrolledlist;
import std.experimental.allocator;
import std.experimental.allocator.building_blocks.allocator_list;
import std.experimental.allocator.building_blocks.region;
import std.experimental.allocator.mallocator;
import std.datetime.stopwatch;
import std.stdio;
import vebtree;

// For fun: change this number and watch the effect it has on the execution time
alias Allocator = AllocatorList!(a => Region!Mallocator(1024 * 16), Mallocator);

enum NUMBER_OF_ITEMS = 1_000_000;

auto testEMSIContainer(alias Container, string ContainerName, size_t number_of_items = NUMBER_OF_ITEMS)()
{
Allocator allocator;
auto c = Container!(uint, typeof(&allocator))(&allocator);

foreach (i; 0 .. number_of_items)
c.insert(cast(uint)i);
}

auto testPhobosContainer(alias Container, string ContainerName, size_t number_of_items = NUMBER_OF_ITEMS)()
{
static if (is(Container!uint == class))
auto c = new Container!uint();
else
Container!uint c;

foreach (i; 0 .. number_of_items)
c.insert(cast(uint)i);
}

auto testVebTree(string ContainerName, size_t number_of_items = NUMBER_OF_ITEMS, size_t base = 0)()
{
static if(!base)
{
auto c = vebRoot(number_of_items);
}
else
{
auto c = vebRoot!base(number_of_items);
}

foreach (i; 0 .. number_of_items)
c.insert(i);
}

shared Duration[size_t] results;
shared string[size_t] identifiers;

import std.format : format;

enum funid(T : A!s, alias A, Args...) = format!"%s : %d"(Args[0], Args[1]);

void main()
{
import std.parallelism : parallel;
import std.range : iota;

import std.datetime.stopwatch : benchmark;

uint repeats = 10;
enum maxBaseSize = 24;
void function()[maxBaseSize * 5] testFunctions;

import std.range;

static foreach(_; 1 .. maxBaseSize + 1)
{
testFunctions[0 + (_ - 1) * 5] = &testEMSIContainer!(TTree, "TTree", 1UL << _);
identifiers[0 + (_ - 1) * 5] = format!"%s : %d"("TTree", 1UL << _);

testFunctions[1 + (_ - 1) * 5] = &testPhobosContainer!(RedBlackTree, "RedBlackTree", 1UL << _);
identifiers[1 + (_ - 1) * 5] = format!"%s : %d"("RedBlackTree", 1UL << _);

testFunctions[2 + (_ - 1) * 5] = &testPhobosContainer!(std.container.slist.SList, "Phobos SList", 1UL << _);
identifiers[2 + (_ - 1) * 5] = format!"%s : %d"("Phobos SList", 1UL << _);

testFunctions[3 + (_ - 1) * 5] = &testEMSIContainer!(containers.slist.SList, "EMSI SList", 1UL << _);
identifiers[3 + (_ - 1) * 5] = format!"%s : %d"("EMSI SList", 1UL << _);

testFunctions[4 + (_ - 1) * 5] = &testVebTree!("VEBtree", 1UL << _);
identifiers[4 + (_ - 1) * 5] = format!"%s : %d"("VEBtree", 1UL << _);
}

foreach(i, _; parallel(testFunctions[]))
{
results[i] = benchmark!(_)(repeats)[0]/repeats;
}

foreach(i; testFunctions.length.iota)
{
Duration dur = results[i];
writeln(identifiers[i], " : ", dur);
}

auto results_local = benchmark!(
testEMSIContainer!(TTree, "TTree"),
testPhobosContainer!(RedBlackTree, "RedBlackTree"),
testPhobosContainer!(std.container.slist.SList, "Phobos SList"),
testEMSIContainer!(containers.slist.SList, "EMSI SList"),
testVebTree!("VEBtree")
)(repeats);

writeln("TTree : ", NUMBER_OF_ITEMS, " : ", results_local[0]/repeats);
writeln("RedBlackTree : ", NUMBER_OF_ITEMS, " : ", results_local[1]/repeats);
writeln("Phobos SList : ", NUMBER_OF_ITEMS, " : ", results_local[2]/repeats);
writeln("EMSI SList : ", NUMBER_OF_ITEMS, " : ", results_local[3]/repeats);
writeln("VEBtree : ", NUMBER_OF_ITEMS, " : ", results_local[4]/repeats);
}
``````

Measurements taken on a Intel(R) Core(TM) i7 CPU @ 2.60GHz with 16GB of memory. Compiled with dub run --build=release --compiler=ldc2

The tree can be expanded to contain all key up to uint max. The construction lasts appropriate time for this, however, all operations remain fast.

Author: Alexander Orlov, sascha.orlov@gmail.com

• Registered by Alexander Orlov
• 0.13.0 released 5 months ago
• Sandman83/vebtree
• BSL-1.0
Authors:
• Alexander Orlov
Dependencies:
none
Versions:
 0.13.0 2019-Jul-08 0.12.2 2019-Jul-08 0.12.1 2019-Feb-12 0.12.0 2019-Feb-05 0.11.1 2018-Nov-10