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

[ryuukk_]

On Friday, 19 January 2024 at 17:18:36 UTC, evilrat wrote:
> On Friday, 19 January 2024 at 16:55:25 UTC, ryuukk_ wrote:
>>
>> 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
>
> There is another important difference, i quickly looked up D 
> associative array implementation and the search looks like 
> nlog(n) complexity with plain loop iteration of hashes, whereas 
> rust's implementation is using "swisstable" algorithm 
> implementation that has packed SIMD optimized lookups, this is 
> likely where the 3x speed difference comes from.
>
> Tried to look up rust implementation and it is SOOO generic 
> that I was unable to decipher it to find the actual key search 
> and stores.
>
> Anyway here is an interesting article about rust implementation
> https://faultlore.com/blah/hashbrown-tldr/

I'm not talking about the difference between the hashmap 
implementation, but the difference between the algorithm used to 
lookup the characters

https://github.com/renatoathaydes/prechelt-phone-number-encoding/blob/9b1d7f026943841638a2729922cf000b1b3ce655/src/java/Main2.java#L106-L134

vs

https://github.com/renatoathaydes/prechelt-phone-number-encoding/blob/40cd423fc9dd1b1b47f02d8ab66ca03420820e84/src/d/src/dencoder.d#L10-L49


If D had pattern matching and switch as expression, the faster 
method would be:

1. the most obvious choice

2. the fastest by default

3. the most clean

To save from having to write a old-school verbose `switch`, i 
suspect he went with a hashmap, wich is slower in that case, 
hence why i keep advocate for that feature, or i should say, that 
upgrade to `switch`, wich java has adopted, as well as rust:

https://github.com/renatoathaydes/prechelt-phone-number-encoding/blob/40cd423fc9dd1b1b47f02d8ab66ca03420820e84/src/rust/phone_encoder/src/main.rs#L146-L168