Help optimize D solution to phone encoding problem: extremely slow performace.

[Renato]

On Friday, 19 January 2024 at 10:15:57 UTC, evilrat wrote:
> On Friday, 19 January 2024 at 09:08:17 UTC, Renato wrote:
>>
>> I forgot to mention: the Java version is using a Trie... and 
>> it consistently beats the Rust numeric algorithm (which means 
>> it's still faster than your D solution), but the Java version 
>> that's equivalent to Rust's implementation is around 3x 
>> slower... i.e. it runs at about the same speed as my current 
>> fastest numeric algorithm in D as well.
>>
>
> Additionally if you comparing D by measuring DMD performance - 
> don't.
> It is valuable in developing for fast iterations, but it lacks 
> many modern optimization techniques, for that we have LDC and 
> GDC.

I tried with DMD again, and yeah, it's much slower.

Here's the [current implementation in 
D](https://github.com/renatoathaydes/prechelt-phone-number-encoding/blob/dlang-key-hash-incremental/src/d/src/dencoder.d), and the roughly [equivalent Rust implementation](https://github.com/renatoathaydes/prechelt-phone-number-encoding/blob/dlang-key-hash-incremental/src/rust/phone_encoder/src/main.rs).

The only "significant" difference is that in Rust, an enum 
`WordOrDigit` is used to represent currently known "words"... I 
[did try using that in 
D](https://github.com/renatoathaydes/prechelt-phone-number-encoding/blob/dlang-int128-word-and-digit/src/d/src/dencoder.d), but it made the algorithm slower.

If you see anything in D that's not as efficient as it should be, 
or somehow "inferior" to what the Rust version is doing , please 
let me know.

Notice that almost all of the time is spent in the for-loop 
inside `printTranslations` (which is misnamed as it doesn't 
necessarily "print" anything, like it did earlier) - the rest of 
the code almost doesn't matter.

Current performance comparison:

```
Proc,Run,Memory(bytes),Time(ms)
===> ./rust
./rust,23920640,31
./rust,24018944,149
./rust,24084480,601
./rust,24248320,1176
./rust,7798784,2958
./rust,7815168,15009
===> src/d/dencoder
src/d/dencoder,14254080,36
src/d/dencoder,24477696,368
src/d/dencoder,24510464,1740
src/d/dencoder,24559616,3396
src/d/dencoder,11321344,6740
src/d/dencoder,11321344,36787
```

So , it's not really 3x slower anymore, here's the "D overhead" 
considering Rust as the baseline:

```
1.161290323
2.469798658
2.895174709
2.887755102
2.278566599
2.450996069
```