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

[ryuukk_]

On Friday, 19 January 2024 at 13:40:39 UTC, Renato wrote:
> 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
> ```

You do hash map lookup for every character in D, it's slow, 
whereas in Rust you do it via pattern matching, java does the 
same, pattern matching


Yet another reason to advocate for pattern matching in D and 
switch as expression