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

[Renato]

On Saturday, 13 January 2024 at 23:20:32 UTC, Sergey wrote:
> On Saturday, 13 January 2024 at 19:35:57 UTC, Renato wrote:
>> On Saturday, 13 January 2024 at 17:00:58 UTC, Anonymouse wrote:
>>> On Saturday, 13 January 2024 at 12:55:27 UTC, Renato wrote:
>>>> [...]
>> I will have to try it... I thought that `BigInt` was to blame 
>> for the slowness (from what I could read from the trace logs), 
>> but after replacing that with basically a byte array key (see 
>> [commit 
>> here](https://github.com/renatoathaydes/prechelt-phone-number-encoding/commit/0e9025b9aacdcfef5a2649be4cc82b9bc607fd6c)) it barely improved. It's still much slower than Common Lisp and very, very far from Java and Rust.
>
> In the repo is hard to find the proper version.
> I've checked the Rust from master branch and it looks a bit 
> different from D implementation..

I explicitly linked to the Rust implementation in my question:

>  the [Rust 
> solution](https://github.com/renatoathaydes/prechelt-phone-number-encoding/blob/fastest-implementations-print-or-count/src/rust/phone_encoder/src/main.rs) uses approx. the same algorithm as used in CL and D, but instead of BigInt, it uses a Vec<u8> as key

Can you be more specific about which part of the Rust 
implementation is not roughly equivalent to the D 
implementation?? There are obvious differences in style and 
syntax, but I hope that it's mostly equivalent algorithm-wise.

But to clarify: the branch where the fastest solutions are is 
called `fastest-implementations-print-or-count`.

The D branches with my alternative implementations are all called 
`dlang-*`.

>
> I would suggest to rewrite in the same way as Rust implemented.
> Probably you would like to try:
> * do not use BigInt from std. It could be quite slow. Try to 
> use GMP library from Dub instead

Right, but as I posted above, even using a byte-array just like 
in Rust, the performance was still very bad (but around 2x faster 
than using BigInt).

Also, using GMP is always suggested to me, but I can't accept 
that because my goal is not to use C libraries to achieve the 
fastest speed (which I could do by using C or FFI in any other 
language), it's to use D (and the other languages) to solve my 
problem in an idiomatic way.

I [ended up using 
`Int128`](https://github.com/renatoathaydes/prechelt-phone-number-encoding/commit/98dcbcf1c77d1ded3406cc03af9026e126df5b2d) (the problem description requires more than i64, but int128 is enough), which grealy improved performance over my D baseline AND on the byte-array solution.

> * don't do "idup" every time
> * instead of byLine, try byLineCopy

`idup` is necessary because the strings are stored in a Map after 
the iteration ends. Anyway, I replaced that with `byLineCopy` and 
it became sligthtly slower.

> * instead of "arr ~= data" try to use Appender 
> (https://dlang.org/library/std/array/appender.html)

I was worried about `~=` allocating too much, though IIUC it 
shouldn't be a problem the way I used it... in any case, I 
[replaced it with 
`Appender`](https://github.com/renatoathaydes/prechelt-phone-number-encoding/commit/f1364d0897f1f37882f1d39b92c16b84b1abdc31) and the performance was completely unchanged - which is good as I think it means I used `~=` correctly to avoid overallocation (or I messed up using `Appender` :D - pls have a look).

> * also you could try to use splitter 
> (https://dlang.org/library/std/algorithm/iteration/splitter.html) to lazily process each part of the data

This is not necessary because that would only affect the time 
spent loading the dictionary, which is the faster part of the 
problem... nearly all of the time is spent looking for solutions 
instead.

> * isLastDigit function has many checks, but I think it could be 
> implemented easier in a Rust way

The Rust solution uses sum types for that, but that had a very 
minor effect on the overall performance (though in Rust, that's 
"cleaner" to use anyway)... I know D does have SumType in the 
stdlib, but I thought it is not as "zero cost" as in Rust, and 
because both variants wrap a String, it's awkward to use that... 
so I instead tried using a struct like this:

```d
struct WordOrDigit {
     string value;
     bool isDigit;
}
```

You can check [the commit 
here](https://github.com/renatoathaydes/prechelt-phone-number-encoding/commit/0f6b4ce83373c46b14b5bb40c53bb0e2d0905e66).

This change made the code slightly slower.

> * also consider to use functions from Range (filter, map) as 
> you use it in Rust, instead of using for loops

Why would for loops be slower? Or you're just saying I should 
make the D code nicer?

Anyway, thanks for the suggestions!


On Sunday, 14 January 2024 at 08:33:24 UTC, Anonymouse wrote:
> On Saturday, 13 January 2024 at 23:20:32 UTC, Sergey wrote:
>> I would suggest to rewrite in the same way as Rust implemented.
>> Probably you would like to try:
>> [...]
>
> I would strongly argue for profiling first instead of 
> optimising based on conjecture. If you profile you have solid 
> evidence on what is actually slow. If you're very good at 
> analysing D, well-educated hypotheses *may* be enough, until 
> they suddenly aren't and you will have spent a lot of time on 
> the wrong problem.

Totally agree. I will spend some time on my Linux machine to see 
if I can get more useful profiling data.

## Current Performance

For now, with the int128 change from BigInt, the code is about 4x 
faster than before, but on larger problems, it's still scaling 
very badly compared to other languages (this suggests there's 
still some "exponential growth" going on, which should not happen 
as the problem is not exponential).

```
Proc,Memory(bytes),Time(ms)
===> ./rust
./rust,23252992,59
./rust,23420928,263
./rust,23412736,1025
./rust,7069696,8661
===> src/d/dencoder
src/d/dencoder,11268096,72
src/d/dencoder,23781376,938
src/d/dencoder,23818240,4443
src/d/dencoder,10723328,134703
```

On the bright side: D is using almost as little memory as Rust, 
which is orders of magnitude better than the other, usual GC 
languages.