200-600x slower Dlang performance with nested foreach loop

[methonash]

On Sunday, 31 January 2021 at 00:53:05 UTC, Steven Schveighoffer 
wrote:
> I'd suggest trying it in reverse. If you have the sequence 
> "cba", "ba", "a", then determining "a" is in "ba" is probably 
> cheaper than determining "a" is in "cba".

I have user requirements that this application track string IDs 
that get collapsed under parents. To minimize/simplify array 
concatenations, I figured that going in descending order might 
make those operations less expensive.

Though I think this is also worth trying.

> Are you still convinced that it's possible to do it in under 2 
> seconds? That would seem a huge discrepancy. If not, what 
> specifically are you looking for in terms of performance?

Good question. As a sanity check, at some point this past week, I 
re-wrote everything in a single contained Perl program, and 
running that program on the dataset I've shared above took well 
over 2 hours of wall time.

Considering that the index() function in Perl is pre-compiled, I 
imagine that Dlang running 4-5x faster is a pretty good speed 
boost, as it may only be benefiting from the speed of compiled 
loops over interpreted loops.

What confuses me, at this point, is this: I originally wrote the 
D code using foreach in this style:

foreach( i, ref parentString; strings )
{
     foreach( j, ref childString; strings[ i + 1 .. $ ] )
     {
         // ...
     }
}

Essentially, the value of j printed to stdout should always be 
larger than the value of i. Yet, when running in the above style, 
the values of j reported to stdout inevitably become smaller than 
i, suggesting that the loop is somehow traversing backwards. How 
can this be explained?