• bearophile <bearophileHUGS lycos.com> Nov 11 2009
• bearophile <bearophileHUGS lycos.com> Nov 30 2009

bearophile <bearophileHUGS lycos.com> writes:

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

bearophile <bearophileHUGS lycos.com> writes:

It seems I was not fully mad, Clojure designers have had the same idea, see
page 29 of this document (Click on it, don't save as):
http://clojure.googlegroups.com/web/ClojureExperience.pdf

Be well,
bearophile