200-600x slower Dlang performance with nested foreach loop

[mw]

On Tuesday, 26 January 2021 at 21:55:47 UTC, mw wrote:
> On Tuesday, 26 January 2021 at 17:40:36 UTC, methonash wrote:
>> foreach( i, ref pStr; sortedArr )
>> {
>>     foreach( j, ref cStr; sortedArr[ i + 1 .. $ ] )
>>     {
>>         if( indexOf( pStr, cStr ) > -1 )
>>         {
>>             // ... yourInnerOp
>>         }
>>     }
>> }
>>
>> Before adding the code excerpt above, the Dlang program was 
>> taking ~1 second on an input file containing approx. 64,000 
>> strings.
>
> What's the typical length of your strings?

Actually, I think it's reasonable given your algo:

Your algo (double-loop) is O(n^2), n = 64,000

so the loop will run n^2 = 4,096,000,000 i.e 4G

Suppose your CPU is 2GHz, and suppose each loop operation take 
just 1 machine cycle (very unlikely), this algo will take 2 
seconds.

However, string searching i.e `indexOf`, or `yourInnerLoop` can 
easily take hundreds of cycles, let's suppose it's 100 machine 
cycles (still a very low estimate), then the algo will take ~200 
seconds = ~3.3 minutes.

If you want, you can try to rewrite your algo in Java or Python, 
and compare the run time with the Dlang version.