SimdSet

Set implementation that is well suited for small sets and simple items.

Uses SSE instructions to compare multiple elements simultaneously, but has linear time complexity.

Note: Only works on x86_64. Does NOT add GC ranges. Do not store pointers in this container unless they are also stored somewhere else.

struct SimdSet(T, Allocator = Mallocator)
version(D_InlineAsm_X86_64)
struct SimdSet (
T
Allocator = Mallocator
) if (
T.sizeof == 1 ||
T.sizeof == 2
||
T.sizeof == 4
||
T.sizeof == 8
) {
this(this);
this();
this(Allocator allocator);
~this();
bool contains(T item);
bool insert(T item);
bool remove(T item);
auto opSlice();
size_t length();
}
struct SimdSet(T)

Constructors

this this(): No default construction if an allocator must be provided.
this this(Allocator allocator): Use the given allocator for allocations.

Destructor

~this ~this(): Undocumented in source.

Postblit

this(this) this(this): Undocumented in source.

Members

Functions

contains bool contains(T item)
insert bool insert(T item): Inserts the given item into the set.
length size_t length()
opSlice auto opSlice(): Slice operator
remove bool remove(T item): Removes the given item from the set.

Parameters

T: the element type
Allocator: the allocator to use. Defaults to Mallocator.

Examples

import std.string : format;

void testSimdSet(T)()
{
	SimdSet!T set;
	assert(set.insert(1));
	assert(set.length == 1);
	assert(set.contains(1));
	assert(!set.insert(1));
	set.insert(0);
	set.insert(20);
	assert(set.contains(1));
	assert(set.contains(0));
	assert(!set.contains(10));
	assert(!set.contains(50));
	assert(set.contains(20));
	foreach (T i; 28 .. 127)
		set.insert(i);
	foreach (T i; 28 .. 127)
		assert(set.contains(i), "%d".format(i));
	foreach (T i; 28 .. 127)
		assert(set.remove(i));
	assert(set.length == 3, "%d".format(set.length));
	assert(set.contains(0));
	assert(set.contains(1));
	assert(set.contains(20));
	assert(!set.contains(28));
}

testSimdSet!ubyte();
testSimdSet!ushort();
testSimdSet!uint();
testSimdSet!ulong();
testSimdSet!byte();
testSimdSet!short();
testSimdSet!int();
testSimdSet!long();