On Thu, Apr 01, 2021 at 01:17:15PM -0700, Ali Çehreli via Digitalmars-d-learn wrote:
> On 4/1/21 12:55 PM, H. S. Teoh wrote:
> 
> > - Constructing large arrays by appending 1 element at a time with `~`.  Obviously, this requires many array reallocations and the associated copying
> 
> And that may not be a contributing factor. :) The following program sees just 15 allocations and 1722 element copies for 1 million appending operations:
[...]
> This is because the GC does not allocate if there are unused pages right after the array.

Right, but in a typical program it's unpredictable whether there will be unused pages after the array.


> (However, increasing the element count to 10 million increases allocations slightly to 18 but element copies jump to 8 million.)
[...]

Thanks for the very interesting information; so it looks like most of the time spent is actually in copying array elements than anything else!


T

-- 
Let's eat some disquits while we format the biskettes.

On Thursday, 1 April 2021 at 21:13:18 UTC, H. S. Teoh wrote:
> On Thu, Apr 01, 2021 at 01:17:15PM -0700, Ali Çehreli via Digitalmars-d-learn wrote:
>> [...]
> [...]
>> [...]
>
> Right, but in a typical program it's unpredictable whether there will be unused pages after the array.
>
>
>> [...]
> [...]
>
> Thanks for the very interesting information; so it looks like most of the time spent is actually in copying array elements than anything else!
>
>
> T

Sorting takes longer proportionally though

On Thu, Apr 01, 2021 at 09:16:09PM +0000, Imperatorn via Digitalmars-d-learn wrote:
> On Thursday, 1 April 2021 at 21:13:18 UTC, H. S. Teoh wrote:
[...]
> > Thanks for the very interesting information; so it looks like most of the time spent is actually in copying array elements than anything else!
[...]
> Sorting takes longer proportionally though

I meant that most the time incurred by appending to the array element by element is spent copying elements.

Obviously, sorting will not be as fast as copying array elements.


T

-- 
What do you mean the Internet isn't filled with subliminal messages? What about all those buttons marked "submit"??

On Thursday, 1 April 2021 at 19:55:05 UTC, H. S. Teoh wrote:
> On Thu, Apr 01, 2021 at 07:25:53PM +0000, matheus via Digitalmars-d-learn wrote: [...]
>> Since this is a "Learn" part of the Foruam, be careful with "-boundscheck=off".
>> 
>> I mean for this little snippet is OK, but for a other projects this my be wrong, and as it says here: https://dlang.org/dmd-windows.html#switch-boundscheck
>> 
>> "This option should be used with caution and as a last resort to improve performance. Confirm turning off @safe bounds checks is worthwhile by benchmarking."
> [...]
>
> It's interesting that whenever a question about D's performance pops up in the forums, people tend to reach for optimization flags.  I wouldn't say it doesn't help; but I've found that significant performance improvements can usually be obtained by examining the code first, and catching common newbie mistakes.  Those usually account for the majority of the observed performance degradation.
>
> Only after the code has been cleaned up and obvious mistakes fixed, is it worth reaching for optimization flags, IMO.

This is my experience as well, and not just for D. Pick good algorithms and pay attention to memory allocation. Don't go crazy on the latter. Many people try to avoid GC at all costs, but I don't usually find it necessary to go quite that far. Very often simply reusing already allocated memory does the trick. The blog post I wrote a few years ago focuses on these ideas: https://dlang.org/blog/2017/05/24/faster-command-line-tools-in-d/

--Jon

On Fri, Apr 02, 2021 at 02:36:21AM +0000, Jon Degenhardt via Digitalmars-d-learn wrote:
> On Thursday, 1 April 2021 at 19:55:05 UTC, H. S. Teoh wrote:
[...]
> > It's interesting that whenever a question about D's performance pops up in the forums, people tend to reach for optimization flags.  I wouldn't say it doesn't help; but I've found that significant performance improvements can usually be obtained by examining the code first, and catching common newbie mistakes.  Those usually account for the majority of the observed performance degradation.
> > 
> > Only after the code has been cleaned up and obvious mistakes fixed, is it worth reaching for optimization flags, IMO.
> 
> This is my experience as well, and not just for D. Pick good algorithms and pay attention to memory allocation. Don't go crazy on the latter. Many people try to avoid GC at all costs, but I don't usually find it necessary to go quite that far. Very often simply reusing already allocated memory does the trick.

I've been saying this for years, the GC is (usually) not evil. It's often quite easy to optimize away the main bottlenecks and any remaining problem becomes not so important anymore.

For example, see this thread:

	https://forum.dlang.org/post/mailman.1589.1415314819.9932.digitalmars-d@puremagic.com

which is continued here (for some reason it was split -- the bad ole
Mailman bug, IIRC):

	https://forum.dlang.org/post/mailman.1590.1415315739.9932.digitalmars-d@puremagic.com


>From a starting point of about 20 seconds total running time, I reduced
it to about 6 seconds by the following fixes:

1) Reduce GC collection frequency: call GC.stop at start of program,
   then manually call GC.collect periodically.

2) Eliminate autodecoding (using .representation or .byChar).

3) Rewrite a hot inner loop using pointers instead of .countUntil.

4) Refactor the code to eliminate a redundant computation from an inner
   loop.

5) Judicious use of .assumeSafeAppend to prevent excessive array
   reallocations.

6) (Not described in the thread, but applied later) Reduce GC load even
   further by reusing an array that was being allocated per iteration in
   an inner loop before.

Of the above, (1), (2), (3), and (5) require only very small code
changes. (4) and (6) were a little more tricky, but were pretty
localised changes that did not take a long time to implement or affect a
lot of code.  They were all implemented in a short span of 2-3 days.

Compare this with outright writing @nogc code, which would require a LOT more time & effort.


> The blog post I wrote a few years ago focuses on these ideas: https://dlang.org/blog/2017/05/24/faster-command-line-tools-in-d/

Very nice, and matches my experience with optimizing D code.


T

-- 
Век живи - век учись. А дураком помрёшь.

On Thursday, 1 April 2021 at 19:38:39 UTC, H. S. Teoh wrote:
> On Thu, Apr 01, 2021 at 04:52:17PM +0000, Nestor via Digitalmars-d-learn wrote: [...]
>>     [...]
>
> Since the length of the array is already known beforehand, you could get significant speedups by preallocating the array:
>
> [...]

First, thanks everyone!

I don't have ldc2 installed so I skipped those suggestions.

I always suspected I was doing something wrong with the random generator. Some how in a test if I put the seed outside the loop I got the same (not)random number but might be a copy-paste error from my side.

Reserved length in an integers list is something I am starting to give great value, thanks for pointing it out.

I feel satisfied with 30-12ms using rdmd I am getting now :)

Thanks again Ali, Teoh, Steven, ag0aep6g, Imperatorn

On 4/1/21 9:01 PM, H. S. Teoh wrote:

> 6) (Not described in the thread, but applied later) Reduce GC load even
>     further by reusing an array that was being allocated per iteration in
>     an inner loop before.

For those who prefer a video description with some accent :) here is how to apply that technique:

  https://www.youtube.com/watch?v=dRORNQIB2wA&t=787s

And here is how to profile[1] the program to see where the allocations occur:

  https://www.youtube.com/watch?v=dRORNQIB2wA&t=630s

Ali

[1] Unfortunately, the profiler has some bugs, which cause segmentation faults in some cases.

02.04.2021 15:06, Ali Çehreli пишет:
> 
> For those who prefer a video description with some accent :) here is how 

What about accent - I'm curious what would you say about this old Russian sketch about English and its dialects (in English, no facebook account required):

https://www.facebook.com/ABBYY.Lingvo/videos/954190547976075

skip first 50 seconds up to English part