www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Is D slow?

reply Honey <honey pot.com> writes:
Hi guys,

I wrote a toy benchmark in C++ [1] and tried to literally 
translate it to D [2].

The results are quite disappointing. What seems particularly 
strange to me is that -boundscheck=off leads to a performance 
decrease.

Am I missing anything?

// $ clang++ -std=c++1z -O3 cmp-bench.cpp
// $ time ./a.out
// 501
//
// real 0m2.777s
// user 0m2.774s
// sys  0m0.004s
//
//
// $ clang++ --version
// clang version 4.0.0 (tags/RELEASE_400/final)
// Target: x86_64-unknown-linux-gnu
// Thread model: posix
// InstalledDir: /usr/bin

// $ ldc2 -O3 -release cmp-bench.d
// $ time ./cmp-bench
// 501
//
// real	0m5.257s
// user	0m5.224s
// sys	0m0.000s
//
//
// $ ldc2 -O3 -release -boundscheck=off cmp-bench.d
// $ time ./cmp-bench
// 501
//
// real	0m11.083s
// user	0m11.083s
// sys	0m0.000s
//
//
// $ ldc2 --version
// LDC - the LLVM D compiler (1.2.0):
//   based on DMD v2.072.2 and LLVM 4.0.0
//   built with DMD64 D Compiler v2.074.0
//   Default target: x86_64-unknown-linux-gnu
//   Host CPU: haswell

[1] C++ Insertion Sort - https://dpaste.dzfl.pl/74fdb92a0579
[2] D Insertion Sort   - https://dpaste.dzfl.pl/b97a1fca1546
Jun 09
next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 6/9/17 12:21 PM, Honey wrote:
 Hi guys,

 I wrote a toy benchmark in C++ [1] and tried to literally translate it
 to D [2].
Wow, so that's how D code would look like if it were C++ :)
 The results are quite disappointing. What seems particularly strange to
 me is that -boundscheck=off leads to a performance decrease.
That doesn't make much sense, but I'm not an ldc2 user. However, it does note in the help that -release disables bounds checks already. I did replicate that issue on my box, and mucking around with the implementation didn't help. In answer to the subject, no D is not slow. However, it's quite possible that std.algorithm.bringToFront is slower than std::rotate, or SortedRange.upperBound is slower than std::upper_bound, or both. I don't think it's a design issue per se, probably more of an implementation issue. -Steve
Jun 09
next sibling parent =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 06/09/2017 11:32 AM, Steven Schveighoffer wrote:

 In answer to the subject, no D is not slow. However, it's quite possible
 that std.algorithm.bringToFront is slower than std::rotate, or
 SortedRange.upperBound is slower than std::upper_bound, or both.
That was exactly my conclusion. I found this C++ article which may point at a similar implementation issue in Phobos: https://stackoverflow.com/questions/21160875/why-is-stdrotate-so-fast Ali
Jun 09
prev sibling next sibling parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 6/9/17 2:32 PM, Steven Schveighoffer wrote:

 In answer to the subject, no D is not slow. However, it's quite possible
 that std.algorithm.bringToFront is slower than std::rotate, or
 SortedRange.upperBound is slower than std::upper_bound, or both. I don't
 think it's a design issue per se, probably more of an implementation issue.
https://issues.dlang.org/show_bug.cgi?id=17485 -Steve
Jun 09
prev sibling next sibling parent reply Honey <honey pot.com> writes:
On Friday, 9 June 2017 at 18:32:06 UTC, Steven Schveighoffer 
wrote:
 Wow, so that's how D code would look like if it were C++ :)
Well, I cannot (and did not try to) hide where I am coming from. ;-)
 The results are quite disappointing. What seems particularly 
 strange to
 me is that -boundscheck=off leads to a performance decrease.
That doesn't make much sense, but I'm not an ldc2 user. However, it does note in the help that -release disables bounds checks already.
Sounds like a bug, then.
 I did replicate that issue on my box, and mucking around with 
 the implementation didn't help.

 In answer to the subject, no D is not slow. However, it's quite 
 possible that std.algorithm.bringToFront is slower than 
 std::rotate, or SortedRange.upperBound is slower than 
 std::upper_bound, or both. I don't think it's a design issue 
 per se, probably more of an implementation issue.
Thank you for confirming the results and your factual explanation notwithstanding my pointed question. ;-) Maybe I was expecting too much given Andrei's performance oriented talks. I realize that the conceptual groundwork is more important than a concrete implementation that can be easily improved. However, I think that real world out-of-the-box performance - particularly with respect to toy examples (since those are small enough to be literally translated) - is important for prospects to gain confidence in buying into D. At the current state, at least for such benchmarks, I think, I should not rely on standard library facilities. Unfortunately, that does not increase my confidence.
Jun 09
next sibling parent Honey <honey pot.com> writes:
On Friday, 9 June 2017 at 19:29:35 UTC, Honey wrote:
 Unfortunately, that does not increase my confidence.
I should add that, nevertheless, I very much appreciate and respect D and its community. Great work! :-)
Jun 09
prev sibling next sibling parent Laeeth Isharc <laeethnospam nospam.laeeth.com> writes:
On Friday, 9 June 2017 at 19:29:35 UTC, Honey wrote:
 On Friday, 9 June 2017 at 18:32:06 UTC, Steven Schveighoffer 
 wrote:
 Wow, so that's how D code would look like if it were C++ :)
Well, I cannot (and did not try to) hide where I am coming from. ;-)
 The results are quite disappointing. What seems particularly 
 strange to
 me is that -boundscheck=off leads to a performance decrease.
That doesn't make much sense, but I'm not an ldc2 user. However, it does note in the help that -release disables bounds checks already.
Sounds like a bug, then.
 I did replicate that issue on my box, and mucking around with 
 the implementation didn't help.

 In answer to the subject, no D is not slow. However, it's 
 quite possible that std.algorithm.bringToFront is slower than 
 std::rotate, or SortedRange.upperBound is slower than 
 std::upper_bound, or both. I don't think it's a design issue 
 per se, probably more of an implementation issue.
Thank you for confirming the results and your factual explanation notwithstanding my pointed question. ;-) Maybe I was expecting too much given Andrei's performance oriented talks. I realize that the conceptual groundwork is more important than a concrete implementation that can be easily improved. However, I think that real world out-of-the-box performance - particularly with respect to toy examples (since those are small enough to be literally translated) - is important for prospects to gain confidence in buying into D. At the current state, at least for such benchmarks, I think, I should not rely on standard library facilities. Unfortunately, that does not increase my confidence.
Real world and toy are mutually exclusive categories, and I am not sure the empirical evidence is consistent with your perspective that it is what prospects need to see before exploring D, though that is an interesting perspective. I highly recommend Weka.io talks if you would like to see how one larger D user has found performance in practice. If you are expecting a perfectly finished glossy product then I don't think that - at least in the current year - D will be necessarily for you. Polish improves every year, but it's not the principal focus of the community currently. It's more the opposite - pay the price up front in different ways and reap the returns again and again over time.
Jun 09
prev sibling next sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 06/09/2017 12:29 PM, Honey wrote:

 I think, I should not rely on standard library facilities.
I think you hit a Phobos function with particularly bad performance (which can be improved). Phobos is not a slow library in general. Ali
Jun 09
parent reply Honey <honey pot.com> writes:
On Friday, 9 June 2017 at 20:27:58 UTC, Ali Çehreli wrote:
 On 06/09/2017 12:29 PM, Honey wrote:

 I think, I should not rely on standard library facilities.
I think you hit a Phobos function with particularly bad performance (which can be improved). Phobos is not a slow library in general.
What I meant to say is: the comparison would have been less biased if I had written the complete algorithm without relying on different standard library abstractions (iterators vs. ranges).
Jun 09
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 06/09/2017 03:46 PM, Honey wrote:
 On Friday, 9 June 2017 at 20:27:58 UTC, Ali Çehreli wrote:
 On 06/09/2017 12:29 PM, Honey wrote:

 I think, I should not rely on standard library facilities.
I think you hit a Phobos function with particularly bad performance (which can be improved). Phobos is not a slow library in general.
What I meant to say is: the comparison would have been less biased if I had written the complete algorithm without relying on different standard library abstractions (iterators vs. ranges).
You would get the exact performance if you implemented e.g. with pointers. Your test has been very valuable for exposing an embarrassing performance issue. :) Ali
Jun 09
parent reply Honey <honey pot.com> writes:
On Friday, 9 June 2017 at 23:10:28 UTC, Ali Çehreli wrote:
 You would get the exact performance if you implemented e.g. 
 with pointers. Your test has been very valuable for exposing an 
 embarrassing performance issue. :)
I can confirm that, after changing implementation to the following, performance is on par. It is not immediatetly clear to me how r[r[0 .. i].getTransitionIndex!Less(r[i]) .. i + 1] would look like if written idiomatically. size_t getTransitionIndex(alias test, Range, V)(Range r, V v) if (isRandomAccessRange!Range && hasLength!Range) { size_t first = 0; size_t count = r.length; while (count > 0) { immutable step = count / 2; immutable it = first + step; if (!test(v, r[it])) { first = it + 1; count -= step + 1; } else { count = step; } } return first; } void rotateRight(Range)(Range r) if (hasLength!Range && isRandomAccessRange!Range && hasSlicing!Range) { auto t = r[$ - 1]; foreach_reverse (i; 0 .. r.length - 1) { r[i + 1] = r[i]; } r[0] = t; } void insertionSort(alias Less, Range)(Range r) if (hasLength!Range && isRandomAccessRange!Range && hasSlicing!Range) { foreach (i; 1 .. r.length) { rotateRight(r[r[0 .. i].getTransitionIndex!Less(r[i]) .. i + 1]); } }
Jun 10
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 6/10/17 5:00 AM, Honey wrote:
 On Friday, 9 June 2017 at 23:10:28 UTC, Ali Çehreli wrote:
 You would get the exact performance if you implemented e.g. with
 pointers. Your test has been very valuable for exposing an
 embarrassing performance issue. :)
I can confirm that, after changing implementation to the following, performance is on par. It is not immediatetly clear to me how r[r[0 .. i].getTransitionIndex!Less(r[i]) .. i + 1] would look like if written idiomatically.
I wrote it like this, which confirms that it's indeed bringToFront (I tried your getTransitionIndex function, but that didn't change timings at all): void insertionSort(alias Less, Range)(Range r) if (hasLength!Range && isRandomAccessRange!Range && hasSlicing!Range) { foreach (immutable i; 1 .. r.length) { auto ubElem = i - r[0 .. i].assumeSorted!Less.upperBound(r[i]).length; r[ubElem .. i+1].rotateRight; } } On my mac, it's completing in about 4.4 seconds, whereas the C++ version completes in around 3. Optimized your rotateRight a bit to get better performance when we can use memmove: void rotateRight(Range)(Range r) if (hasLength!Range && isRandomAccessRange!Range && hasSlicing!Range) { auto t = r[$ - 1]; static if(isDynamicArray!Range) { import core.stdc.string; memmove(r.ptr + 1, r.ptr, (r.length - 1) * r[0].sizeof); } else { foreach_reverse (i; 0 .. r.length - 1) { r[i + 1] = r[i]; } } r[0] = t; } Brings it to exactly c++ performance :) I'll update the bug report. -Steve
Jun 10
parent Honey <honey pot.com> writes:
On Saturday, 10 June 2017 at 10:59:24 UTC, Steven Schveighoffer 
wrote:
 I wrote it like this, which confirms that it's indeed 
 bringToFront (I tried your getTransitionIndex function, but 
 that didn't change timings at all):

 void insertionSort(alias Less, Range)(Range r)
 if (hasLength!Range && isRandomAccessRange!Range && 
 hasSlicing!Range)
 {
     foreach (immutable i; 1 .. r.length)
     {
         auto ubElem = i - r[0 .. 
 i].assumeSorted!Less.upperBound(r[i]).length;
         r[ubElem .. i+1].rotateRight;
     }
 }
Taking the length of upperBound is a great move! ;-)
 On my mac, it's completing in about 4.4 seconds, whereas the 
 C++ version completes in around 3.
On my machine, I am getting the same performance even without resorting to memmove. Using getTransitionIndex directly, however, leads to a neglectable improvement (about 2.7 vs. 2.8 seconds), here.
Jun 10
prev sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 6/9/17 3:29 PM, Honey wrote:
 On Friday, 9 June 2017 at 18:32:06 UTC, Steven Schveighoffer wrote:
 Wow, so that's how D code would look like if it were C++ :)
Well, I cannot (and did not try to) hide where I am coming from. ;-)
hehe this was meant more as a dig at C++ syntax and not you, I totally understand the reason you did it that way. Just to show you what I meant, I changed your code to eliminate the functors completely, the main function now looks like this: foreach (i; 0 .. N) { insertionSort!((a, b) => lt(a, b))(v); insertionSort!((a, b) => lt(b, a))(v); } I'm sure there's also a way to reduce the initialization of the array to a few lines (or maybe even one?), but didn't have time to think about it.
 I did replicate that issue on my box, and mucking around with the
 implementation didn't help.

 In answer to the subject, no D is not slow. However, it's quite
 possible that std.algorithm.bringToFront is slower than std::rotate,
 or SortedRange.upperBound is slower than std::upper_bound, or both. I
 don't think it's a design issue per se, probably more of an
 implementation issue.
Thank you for confirming the results and your factual explanation notwithstanding my pointed question. ;-) Maybe I was expecting too much given Andrei's performance oriented talks. I realize that the conceptual groundwork is more important than a concrete implementation that can be easily improved. However, I think that real world out-of-the-box performance - particularly with respect to toy examples (since those are small enough to be literally translated) - is important for prospects to gain confidence in buying into D.
Well, D is pretty fast, as fast as C++ or C. What I mean is that there is no inherent overhead -- both can produce exactly the same code. However, there are some parts of C/C++ that have been optimized to death. It's one of those things where D's version of rotate probably hasn't had as much scrutiny as C++'s version. We are always looking to improve such things, and more investigation and suggestions are most welcome! It's why I filed the bug report.
 At the current state, at least for such benchmarks, I think, I should
 not rely on standard library facilities. Unfortunately, that does not
 increase my confidence.
Try to find something besides insertion sort to test with I think ;) D is pretty fast at a lot of things, and pleasant to write. You just found one test case that isn't (and we will fix it, I'm sure). -Steve
Jun 09
parent Honey <honey pot.com> writes:
On Friday, 9 June 2017 at 21:11:50 UTC, Steven Schveighoffer 
wrote:
 Just to show you what I meant, I changed your code to eliminate 
 the functors completely, the main function now looks like this:


     foreach (i;  0 .. N)
     {
         insertionSort!((a, b) => lt(a, b))(v);
         insertionSort!((a, b) => lt(b, a))(v);
     }

 I'm sure there's also a way to reduce the initialization of the 
 array to a few lines (or maybe even one?), but didn't have time 
 to think about it.
Thanks for your hints. I'm sure there are many things to improve (also in the C++ version). It should be pretty obvious that my knowledge of D is lacking.
 Well, D is pretty fast, as fast as C++ or C. What I mean is 
 that there is no inherent overhead -- both can produce exactly 
 the same code.
I agree.
 However, there are some parts of C/C++ that have been optimized 
 to death. It's one of those things where D's version of rotate 
 probably hasn't had as much scrutiny as C++'s version. We are 
 always looking to improve such things, and more investigation 
 and suggestions are most welcome! It's why I filed the bug 
 report.
Thank you for filing the bug! bringToFrontImpl does not seem to exploit bidirectional or random access properties.
 Try to find something besides insertion sort to test with I 
 think ;) D is pretty fast at a lot of things, and pleasant to 
 write. You just found one test case that isn't (and we will fix 
 it, I'm sure).
I guess that benchmarking comparison of string tuples will not result in happy faces unless a single-pass version of the comparison function is used.
Jun 09
prev sibling parent reply Era Scarecrow <rtcvb32 yahoo.com> writes:
On Friday, 9 June 2017 at 18:32:06 UTC, Steven Schveighoffer 
wrote:
 Wow, so that's how D code would look like if it were C++ :)
When dipping my toes into C++ to do a quicksort algorithm, I quickly got annoyed I'd have to create all the individual comparison functions rather than just one like in D... Which is one thing I'm seeing from the converted 'toy'. Actually I ended up making an opCmp and then overloading all the individual types to use the opCmp.
Jun 09
parent Ola Fosheim =?UTF-8?B?R3LDuHN0YWQ=?= writes:
On Friday, 9 June 2017 at 19:43:55 UTC, Era Scarecrow wrote:
 On Friday, 9 June 2017 at 18:32:06 UTC, Steven Schveighoffer 
 wrote:
 Wow, so that's how D code would look like if it were C++ :)
When dipping my toes into C++ to do a quicksort algorithm, I quickly got annoyed I'd have to create all the individual comparison functions rather than just one like in D... Which is
Not sure what you mean by that? You only need one in C++. http://en.cppreference.com/w/cpp/utility/functional/less
Jun 11
prev sibling parent reply Johan Engelen <j j.nl> writes:
On Friday, 9 June 2017 at 16:21:22 UTC, Honey wrote:
 What seems particularly strange to me is that -boundscheck=off 
 leads to a performance decrease.
Strange indeed. `-release` should be synonymous with `-release -boundscheck=off`. Investigating... - Johan
Jun 10
parent reply Johan Engelen <j j.nl> writes:
On Saturday, 10 June 2017 at 11:43:06 UTC, Johan Engelen wrote:
 On Friday, 9 June 2017 at 16:21:22 UTC, Honey wrote:
 What seems particularly strange to me is that -boundscheck=off 
 leads to a performance decrease.
Strange indeed. `-release` should be synonymous with `-release -boundscheck=off`.
Nope it's not. http://www.digitalmars.com/d/archives/digitalmars/D/What_s_the_deal_with_-boundscheck_260237.html
Jun 10
parent reply Honey <honey pot.com> writes:
On Saturday, 10 June 2017 at 11:53:44 UTC, Johan Engelen wrote:
 `-release` should be synonymous with `-release 
 -boundscheck=off`.
Nope it's not. http://www.digitalmars.com/d/archives/digitalmars/D/What_s_the_deal_with_-boundscheck_260237.html
Thank you for clarifying that point. Is it expected that turning off bounds checking can lead to a performance decrease?
Jun 10
parent reply Nicholas Wilson <iamthewilsonator hotmail.com> writes:
On Saturday, 10 June 2017 at 12:16:34 UTC, Honey wrote:
 On Saturday, 10 June 2017 at 11:53:44 UTC, Johan Engelen wrote:
 `-release` should be synonymous with `-release 
 -boundscheck=off`.
Nope it's not. http://www.digitalmars.com/d/archives/digitalmars/D/What_s_the_deal_with_-boundscheck_260237.html
Thank you for clarifying that point. Is it expected that turning off bounds checking can lead to a performance decrease?
Yes, with it on you are doing an "is the index <= the length" for every array access. Now some of them can be elided by the complier when it can prove that the index is always in bounds but it is generally dangerous to do so as it opens up the possibility of buffer overflow.
Jun 10
parent reply Honey <honey pot.com> writes:
On Saturday, 10 June 2017 at 12:23:05 UTC, Nicholas Wilson wrote:
 On Saturday, 10 June 2017 at 12:16:34 UTC, Honey wrote:
 Is it expected that turning off bounds checking can lead to a 
 performance decrease?
Yes, with it on you are doing an "is the index <= the length" for every array access. Now some of them can be elided by the complier when it can prove that the index is always in bounds but it is generally dangerous to do so as it opens up the possibility of buffer overflow.
Are you saying that introducing additional checks enables the optimizer to eliminate more or more costly checks than it could without introducing those additional checks in the first place? Can you give an example?
Jun 10
parent reply Nicholas Wilson <iamthewilsonator hotmail.com> writes:
On Saturday, 10 June 2017 at 12:44:07 UTC, Honey wrote:
 On Saturday, 10 June 2017 at 12:23:05 UTC, Nicholas Wilson 
 wrote:
 On Saturday, 10 June 2017 at 12:16:34 UTC, Honey wrote:
 Is it expected that turning off bounds checking can lead to a 
 performance decrease?
Yes, with it on you are doing an "is the index <= the length" for every array access. Now some of them can be elided by the complier when it can prove that the index is always in bounds but it is generally dangerous to do so as it opens up the possibility of buffer overflow.
Are you saying that introducing additional checks enables the optimizer to eliminate more or more costly checks than it could without introducing those additional checks in the first place? Can you give an example?
My bad I misread the original quote, misread that as performance increase. turning bounds checks off should always result in faster code.
Jun 10
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On Saturday, 10 June 2017 at 13:43:48 UTC, Nicholas Wilson wrote:
 On Saturday, 10 June 2017 at 12:44:07 UTC, Honey wrote:
 On Saturday, 10 June 2017 at 12:23:05 UTC, Nicholas Wilson 
 wrote:
 [...]
Are you saying that introducing additional checks enables the optimizer to eliminate more or more costly checks than it could without introducing those additional checks in the first place? Can you give an example?
My bad I misread the original quote, misread that as performance increase. turning bounds checks off should always result in faster code.
I can confirm on my system, ldc with bounds check off was at least twice as slow as with just -release. Definitely seems like a bug -Steve
Jun 10
parent Nicholas Wilson <iamthewilsonator hotmail.com> writes:
On Saturday, 10 June 2017 at 14:14:53 UTC, Steven Schveighoffer 
wrote:
 I can confirm on my system, ldc with bounds check off was at 
 least twice as slow as with just -release.

 Definitely seems like a bug

 -Steve
Ya, see https://github.com/ldc-developers/ldc/issues/2161
Jun 10