Created
August 12, 2017 14:28
-
-
Save PetarKirov/8d045a7b33fd906ab50d78d6bac42e61 to your computer and use it in GitHub Desktop.
Perf bench for std.bitmanip.BitArray
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
void main() | |
{ | |
import std.algorithm : map, max; | |
import std.datetime : benchmark, to, TickDuration; | |
import std.meta : aliasSeqOf, I = Alias; | |
import std.range : array, iota, roundRobin; | |
import std.random : uniform; | |
import std.stdio : File, writefln; | |
enum evnSizes = [2, 8, 16, 32, 64, 128, 256, 512, 1024, 2 << 12, 2 << 14, 2 << 20]; // , 2 << 22, 2 << 24]; | |
enum oddSizes = evnSizes.map!(x => x - 1); | |
enum sizes = roundRobin(oddSizes, evnSizes).array; | |
auto devnull = File("/dev/null", "w"); | |
foreach (size; sizes[0 .. $]) | |
{ | |
alias rndBool = () => cast(bool)uniform(0, 2); | |
alias generate = (size_t size) => size.iota.map!(x => rndBool()).array; | |
auto val = rndBool(); | |
auto arr1 = generate(size); | |
auto arr2 = arr1.dup; | |
auto bitarr1 = BitArray(arr1); | |
auto bitarr2 = BitArray(arr2); | |
alias toMilis = (TickDuration t) => t.to!(`msecs`, double); | |
alias asArray = (BitArray ba) => ba._ptr[0 .. ba.dim]; | |
auto iterations = max(100, 10_000_000 / size); | |
auto res = benchmark!( | |
() => (bitarr1.opSliceAssign1(val), devnull.rawWrite(bitarr2.I!asArray)), | |
() => (bitarr2.opSliceAssign2(val), devnull.rawWrite(bitarr2.I!asArray))) | |
(iterations); | |
("At [size = %8s | iterations = %8s] opSliceAssign2 was %7.3f times faster -" ~ | |
" %8.3fms (old) vs %8.3fms (new)") | |
.writefln(size, | |
iterations, | |
res[0].length / real(res[1].length), | |
res[0].I!toMilis, | |
res[1].I!toMilis); | |
} | |
} | |
struct BitArray | |
{ | |
import core.bitop : bts, btr, bsf, bt; | |
import core.bitop : btc, bts, btr, bsf, bt; | |
import std.format : FormatSpec; | |
void opSliceAssign1(bool val) | |
{ | |
for (size_t i = 0; i < _len; i++) | |
opIndexAssign(val, i); | |
} | |
void opSliceAssign2(bool val) | |
{ | |
size_t word = val ? size_t(~0) : 0; | |
_ptr[0] = word; | |
if (_len <= bitsPerSizeT) | |
return; | |
_ptr[1 .. fullWords] = val ? ~size_t(0) : 0; | |
if (endBits) _ptr[fullWords] = val? | |
_ptr[fullWords] | endMask : | |
_ptr[fullWords] & ~endMask; | |
} | |
size_t _len; | |
size_t* _ptr; | |
enum bitsPerSizeT = size_t.sizeof * 8; | |
this(bool[] ba) pure nothrow @system | |
{ | |
length = ba.length; | |
foreach (i, b; ba) | |
{ | |
this[i] = b; | |
} | |
} | |
@property size_t length(size_t newlen) pure nothrow @system | |
{ | |
if (newlen != _len) | |
{ | |
size_t olddim = dim; | |
immutable newdim = lenToDim(newlen); | |
if (newdim != olddim) | |
{ | |
// Create a fake array so we can use D's realloc machinery | |
auto b = _ptr[0 .. olddim]; | |
b.length = newdim; // realloc | |
_ptr = b.ptr; | |
} | |
_len = newlen; | |
} | |
return _len; | |
} | |
@property size_t fullWords() const @nogc pure nothrow | |
{ | |
return _len / bitsPerSizeT; | |
} | |
// Number of bits after the last full word | |
@property size_t endBits() const @nogc pure nothrow | |
{ | |
return _len % bitsPerSizeT; | |
} | |
// Bit mask to extract the bits after the last full word | |
@property size_t endMask() const @nogc pure nothrow | |
{ | |
return (size_t(1) << endBits) - 1; | |
} | |
static size_t lenToDim(size_t len) @nogc pure nothrow @safe | |
{ | |
return (len + (bitsPerSizeT-1)) / bitsPerSizeT; | |
} | |
@property size_t dim() const @nogc pure nothrow @safe | |
{ | |
return lenToDim(_len); | |
} | |
bool opIndexAssign(bool b, size_t i) @nogc pure nothrow | |
in | |
{ | |
assert(i < _len); | |
} | |
body | |
{ | |
if (b) | |
bts(_ptr, i); | |
else | |
btr(_ptr, i); | |
return b; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment