rillki / humble-benchmarks Goto Github PK

If (in the D code) you change all the doubles to reals you will get 0.131584 instead of 0.1368. This is a pretty bad sign...

I noted in #4 (comment) that there was a lot of work done that was then cancelled out.

So I did this: John-Colvin@0337184 John-Colvin@8b219af which really shows how little work actually depends on the loop variable i.

Which then leads us to #4 (comment). In combination with the commit above, I think it's quite clear that - for a given contingency table - there is a constant (fs[data[0] + data[1]] + fs[data[2] + data[3]] + fs[data[0] + data[2]] + fs[data[1] + data[3]] - fs[data[0] + data[1] + data[2] + data[3]]) that is added n + 1 times where n is the number of iterations, then a pair of indices that sweep down through factorials at a fixed offset to each other (data[2] - data[1]) and a pair that sweep up similarly (offset data[3] - data[0]).

From this it seems evident that there is a way to be found to calculate the a[n]s from #4 (comment) and avoid jumping around in factorials altogether.

I still don't know what fischerExact is 🤣, but I can read code 😄

If you were expecting to call fisherExact many times, you'd be doing a lot of duplicate work. log factorials are such a key thing in stats that I would imagine a "log factorial store" that lazily caches the results, where you can ask for a slice of them or just one-by-one, plus options to clear the cache etc. would be really valuable for performance across a multitude of tasks.

struct LogFactorialCache {
    private static double[] data;

    static void cacheTo(size_t n) {
        size_t oldLength = data.length;
        if (data.length <= n) {
            data.length = n + 1;
            if (oldLength == 0) {
                data[0] = 0;
                oldLength = 1;
            }
            foreach (i; oldLength .. n + 1) {
                data[i] = data[i - 1] + log(i);
            }
        }
    }

    // this is a rubbish function, because you'll never free
    // the memory. Needs redesign.
    static void shrinkTo(size_t n) {
        data.length = n + 1;
    }

    /// for one-off or non-contiguous usage,
    /// slight overhead per access
    static double opIndex(size_t i) {
        cacheTo(i);
        return data[i];
    }

    /// for when you know you want a block of them
    /// and want fast access inside.
    static double[] opSlice(size_t i0, size_t i1) {
        cacheTo(i1);
        return data[i0 .. i1];
    }
}

or something like that. Untested. Of course the same idea applies to other languages, not just D.