Thread overview | ||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
May 16, 2016 My ACCU 2016 keynote video available online | ||||
---|---|---|---|---|
| ||||
Uses D for examples, showcases Design by Introspection, and rediscovers a fast partition routine. It was quite well received. https://www.youtube.com/watch?v=AxnotgLql0k Andrei |
May 16, 2016 Re: My ACCU 2016 keynote video available online | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On 5/16/2016 6:46 AM, Andrei Alexandrescu wrote: > Uses D for examples, showcases Design by Introspection, and rediscovers a fast > partition routine. It was quite well received. > https://www.youtube.com/watch?v=AxnotgLql0k https://www.reddit.com/r/programming/comments/4jlkhv/accu_2016_keynote_by_andrei_alexandrescu/ |
May 16, 2016 Re: My ACCU 2016 keynote video available online | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On Monday, 16 May 2016 at 13:46:11 UTC, Andrei Alexandrescu wrote:
> Uses D for examples, showcases Design by Introspection, and rediscovers a fast partition routine. It was quite well received. https://www.youtube.com/watch?v=AxnotgLql0k
>
> Andrei
Great! Your talks are always pushedFront in my view queue 😊
Did you manage to recruit any new D liutenants 😉
|
May 16, 2016 Re: My ACCU 2016 keynote video available online | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On Monday, 16 May 2016 at 13:46:11 UTC, Andrei Alexandrescu wrote:
> Uses D for examples, showcases Design by Introspection, and rediscovers a fast partition routine. It was quite well received. https://www.youtube.com/watch?v=AxnotgLql0k
>
> Andrei
Funny, useful, advertises the best parts of D very well.
|
May 17, 2016 Re: My ACCU 2016 keynote video available online | ||||
---|---|---|---|---|
| ||||
Posted in reply to QAston | On 05/16/2016 05:45 PM, QAston wrote:
> On Monday, 16 May 2016 at 13:46:11 UTC, Andrei Alexandrescu wrote:
>> Uses D for examples, showcases Design by Introspection, and
>> rediscovers a fast partition routine. It was quite well received.
>> https://www.youtube.com/watch?v=AxnotgLql0k
>>
>> Andrei
>
> Funny, useful, advertises the best parts of D very well.
Thanks. And of course on reddit there's the Slaves Chorus of Nabucco chiming in right on cue how it could be done in C++. -- Andrei
|
May 18, 2016 Re: My ACCU 2016 keynote video available online | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On 16 May 2016 at 23:46, Andrei Alexandrescu via Digitalmars-d-announce <digitalmars-d-announce@puremagic.com> wrote: > Uses D for examples, showcases Design by Introspection, and rediscovers a fast partition routine. It was quite well received. https://www.youtube.com/watch?v=AxnotgLql0k > > Andrei This isn't the one you said you were going to "destroy concepts" is it? At dconf, you mentioned a talk for release on some date I can't remember, and I got the impression you were going to show how C++'s concepts proposal was broken, and ideally, propose how we can nail it in D? |
May 19, 2016 Re: My ACCU 2016 keynote video available online | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On Monday, 16 May 2016 at 13:46:11 UTC, Andrei Alexandrescu wrote: > Uses D for examples, showcases Design by Introspection, and rediscovers a fast partition routine. It was quite well received. https://www.youtube.com/watch?v=AxnotgLql0k > > Andrei Nice presentation. The code applying the sentinel optimization assumes mutability of the input. That needs to be checked for. That's fine for partition because that is assumed to be in-place. But for other algorithms it's not so obvious. It's sad that the optimization works only for non-const input. It is in conflict with the advice to make input const if the function doesn't change it. This makes the optimization less likely to be applicable. One might though relax the const requirement to mean "the input is identical at return of the function to its beginning". But that's a different story, I'll guess. Coming up with another implementation might also work, using chain or so. But typically the sentinel optimization assumes mutability. I didn't get the idea behind sentinels for sparse dot product. I picked the smallest of the last elements (so you need bidirectional ranges) and fix up as needed. For gdc I get a speedup (baseline over new implementation) of 1.2 in best case and >1.0 in worst case. On average it's about 1.1 I would say. I expected more. How would you approach sentinels with the sparse dot product. Can you elaborate the idea from the video? I didn't get it. The base line (dot1 in the graphs) is the straightforward version --- size_t i,j = 0; double sum = 0; while (i < a.length && j < b.length) { if (a[i].index < b[j].index) i++; else if (a[i].index > b[j].index) j++; else { assert(a[i].index == b[j].index); sum += a[i].value * b[j].value; i++; j++; } } return sum; --- BTW the effects vary greatly for different compilers. For example with dmd the optimized version is slowest. The baseline is best. Weird. With gdc the optimized is best and gdc's code is always faster than dmd's code. With ldc it's really strange. Slower than dmd. I assume I'm doing something wrong here. Used compiler flags dmd v2.071.0 -wi -dw -g -O -inline -release -noboundscheck gdc (crosstool-NG 203be35 - 20160205-2.066.1-e95a735b97) 5.2.0 -Wall -g -O3 -fomit-frame-pointer -finline-functions -frelease -fno-bounds-check -ffast-math ldc (0.15.2-beta2) based on DMD v2.066.1 and LLVM 3.6.1 -wi -dw -g -O3 -enable-inlining -release -boundscheck=off Am I missing some flags? I uploaded my plots. - running time https://www.scribd.com/doc/312951947/Running-Time - speed up https://www.scribd.com/doc/312951964/Speedup *Disclaimer* I hope most of this makes sense but take it with a grain of salt. Jens PS It seems the mailinglist interface does not work. I cannot send replies anymore via mail. I wrote Brad Roberts but no answer yet. |
May 19, 2016 Re: My ACCU 2016 keynote video available online | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On 5/16/16 9:46 AM, Andrei Alexandrescu wrote: > Uses D for examples, showcases Design by Introspection, and rediscovers > a fast partition routine. It was quite well received. > https://www.youtube.com/watch?v=AxnotgLql0k This talk took a big gambit and it seems to have worked well. Per https://www.youtube.com/channel/UCJhay24LTpO1s4bIZxuIqKw/videos?sort=p&view=0&flow=grid, "There's Treasure Everywhere" is the most watched talk of the ACCU 2016 conference with 5276 views with a large margin (next 1874, median 339). Andrei |
May 19, 2016 Re: My ACCU 2016 keynote video available online | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jens Müller | On 5/19/16 4:12 AM, Jens Müller wrote: > The code applying the sentinel optimization assumes mutability of > the input. That needs to be checked for. Indeed. As I mentioned after discussing find, I didn't worry about those checks assuming they were obvious. > That's fine for partition > because that is assumed to be in-place. But for other algorithms it's > not so obvious. It's sad that the optimization works only for > non-const input. Several optimizations only apply to mutable data. Others apply to immutable data. It's the way things go. > I didn't get the idea behind sentinels for sparse dot product. I picked the > smallest of the last elements (so you need bidirectional ranges) and fix > up as > needed. For gdc I get a speedup (baseline over new implementation) of > 1.2 in > best case and >1.0 in worst case. On average it's about 1.1 I would say. I > expected more. How would you approach sentinels with the sparse dot > product. Can > you elaborate the idea from the video? I didn't get it. That's the idea - to only need to bounds check on one of the three possibilities. What test data did you use? 10%-20% win on dot product is significant because for many algorithms dot product is a kernel and dominates everything else. For those any win goes straight to the bottom line. > The base line (dot1 in the graphs) is the straightforward version > > --- > size_t i,j = 0; > double sum = 0; > while (i < a.length && j < b.length) > { > if (a[i].index < b[j].index) i++; > else if (a[i].index > b[j].index) j++; > else > { > assert(a[i].index == b[j].index); > sum += a[i].value * b[j].value; > i++; > j++; > } > } > return sum; > --- That does redundant checking. There's a better baseline: --- 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. > BTW the effects vary greatly for different compilers. > For example with dmd the optimized version is slowest. The baseline is > best. Weird. With gdc the optimized is best and gdc's code is always > faster than dmd's code. With ldc it's really strange. Slower than dmd. I > assume I'm doing something wrong here. > > Used compiler flags > dmd v2.071.0 > -wi -dw -g -O -inline -release -noboundscheck > gdc (crosstool-NG 203be35 - 20160205-2.066.1-e95a735b97) 5.2.0 > -Wall -g -O3 -fomit-frame-pointer -finline-functions -frelease > -fno-bounds-check -ffast-math > ldc (0.15.2-beta2) based on DMD v2.066.1 and LLVM 3.6.1 > -wi -dw -g -O3 -enable-inlining -release -boundscheck=off > > Am I missing some flags? These look reasonable. > I uploaded my plots. > - running time https://www.scribd.com/doc/312951947/Running-Time > - speed up https://www.scribd.com/doc/312951964/Speedup What is dot2? Could you please redo the experiments with the modified code as well? Thanks! Andrei |
May 19, 2016 Re: My ACCU 2016 keynote video available online | ||||
---|---|---|---|---|
| ||||
Posted in reply to Manu | On 5/18/16 7:42 AM, Manu via Digitalmars-d-announce wrote:
> On 16 May 2016 at 23:46, Andrei Alexandrescu via
> Digitalmars-d-announce <digitalmars-d-announce@puremagic.com> wrote:
>> Uses D for examples, showcases Design by Introspection, and rediscovers a
>> fast partition routine. It was quite well received.
>> https://www.youtube.com/watch?v=AxnotgLql0k
>>
>> Andrei
>
> This isn't the one you said you were going to "destroy concepts" is it?
> At dconf, you mentioned a talk for release on some date I can't
> remember, and I got the impression you were going to show how C++'s
> concepts proposal was broken, and ideally, propose how we can nail it
> in D?
That's the one - sorry to disappoint :o). -- Andrei
|
Copyright © 1999-2021 by the D Language Foundation