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.
