vebtree ~master

README

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

See

https://en.wikipedia.org/wiki/Van_Emde_Boas_tree

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.

Copyright: Copyright (c) 2016- Alexander Orlov. All rights reserved.

License: https://opensource.org/licenses/BSL-1.0, BSL License

Author: Alexander Orlov, [email protected]