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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017
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 2017