Vectorized Laziness
bearophile
bearophileHUGS at lycos.com
Wed Nov 11 16:38:41 PST 2009
It seems my idea has not interested people and devs...
The following is a silly little example, works with Tango and Phobos, and on both DMD and LDC the third tabler (VectorizedLazyTabler) is faster...
version (Tango) {
import tango.stdc.stdio: printf;
import tango.stdc.time: CLOCKS_PER_SEC, clock;
} else {
import std.c.stdio: printf;
import std.c.time: CLOCKS_PER_SEC, clock;
}
double myclock() {
return clock() / cast(float)CLOCKS_PER_SEC;
}
const int N = 40_000_000;
// silly generator of the data
struct EvensGenerator {
int i;
int opApply(int delegate(ref int) dg) {
int result;
while (true) {
result = dg(i);
i += 2;
if (result)
break;
}
return result;
}
}
int[] strictTabler(TyGen)(TyGen g) {
auto arr = new int[N];
int i;
foreach (el; g) {
arr[i] = el;
i++;
if (i == N)
break;
}
return arr;
}
struct LazyTabler(TyGen) {
TyGen g;
int opApply(int delegate(ref int) dg) {
int result, i;
foreach (el; g) {
result = dg(el);
if (result)
break;
i++;
if (i == N)
break;
}
return result;
}
}
struct VectorizedLazyTabler(TyGen) {
const BLOCK_SIZE = 1_000;
TyGen g;
int opApply(int delegate(ref int[]) dg) {
int result;
// 'block' can be allocated elsewhere, etc
auto block = new int[BLOCK_SIZE];
for (int nblock; nblock < (N / BLOCK_SIZE); nblock++) {
int i;
foreach (el; g) {
block[i] = el;
i++;
if (i == BLOCK_SIZE)
break;
}
result = dg(block);
if (result)
return result;
}
int rest = N % BLOCK_SIZE;
if (rest) {
int i;
foreach (el; g) {
block[i] = el;
i++;
if (i == rest)
break;
}
block.length = rest;
result = dg(block);
}
return result;
}
}
void main() {
double t0, t1;
long tot;
t0 = myclock();
tot = 0;
foreach (el; strictTabler(EvensGenerator()))
tot += el;
t1 = myclock();
printf("%lld, %.2f\n", tot, t1 - t0);
t0 = myclock();
tot = 0;
auto g2 = LazyTabler!(EvensGenerator)(EvensGenerator());
foreach (el; g2)
tot += el;
t1 = myclock();
printf("%lld, %.2f\n", tot, t1 - t0);
t0 = myclock();
tot = 0;
auto g3 = VectorizedLazyTabler!(EvensGenerator)(EvensGenerator());
foreach (block; g3)
foreach (el; block)
tot += el;
t1 = myclock();
printf("%lld, %.2f\n", tot, t1 - t0);
}
Bye,
bearophile
More information about the Digitalmars-d
mailing list