My ACCU 2016 keynote video available online
Jens Müller via Digitalmars-d-announce
digitalmars-d-announce at puremagic.com
Thu May 19 14:36:09 PDT 2016
On Thursday, 19 May 2016 at 12:04:31 UTC, Andrei Alexandrescu
wrote:
> On 5/19/16 4:12 AM, Jens Müller wrote:
>
> ---
> if (a.length == 0 || b.length == 0)
> return 0;
> const amax = a.length - 1, bmax = b.length - 1;
> size_t i,j = 0;
> double sum = 0;
> for (;;)
> {
> if (a[i].index < b[j].index) {
> if (i++ == amax) break;
> }
> else if (a[i].index > b[j].index) {
> bumpJ: if (j++ == bmax) break;
> }
> else
> {
> assert(a[i].index == b[j].index);
> sum += a[i].value * b[j].value;
> if (i++ == amax) break;
> goto bumpJ;
> }
> }
> return sum;
> ---
>
> Then if you add the sentinel you only need the bounds tests in
> the third case.
I'm not seeing it. Let me explain.
Consider the input a = [1] and b = [2, 3] (I only write the
indices). The smallest back index is 1, i.e., a.back is the
chosen sentinel. Now I assume that we set b.back to a.back
restoring it after the loop. Now in the case a[i].index <
b[j].index I have to check whether a[i].index == a.back.index to
break because otherwise i is incremented (since a[i].index = 1
and b[j].index = 2, for i = 0 and j = 0 respectively). In the
last case I only check a[i].index == a.back.index, since this
implies b[j].index == a.back.index.
So in sum I have two bounds tests. But I think this is not what
you are thinking of.
This does not look right.
Here are the plots for the implementations.
https://www.scribd.com/doc/313204510/Running-Time
https://www.scribd.com/doc/313204526/Speedup
dot1 is my baseline, which is indeed worse than your baseline
(dot2). But only on gdc. I choose dot2 as the baseline for
computing the speedup. dot3 is the sentinel version.
I removed the code to optimize for large gaps. Because it is only
confusing. I may generate some benchmark data with larger gaps
later to see whether it is worthwhile for such data.
It looks much more regular now (ldc is still strange).
Jens
More information about the Digitalmars-d-announce
mailing list