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

[H. S. Teoh]

On Thu, Jan 18, 2024 at 04:23:16PM +0000, Renato via Digitalmars-d-learn wrote:
[...]
> Ok, last time I'm running this for someone else :D
> 
> ```
> Proc,Run,Memory(bytes),Time(ms)
> ===> ./rust
> ./rust,23920640,30
> ./rust,24018944,147
> ./rust,24068096,592
> ./rust,24150016,1187
> ./rust,7766016,4972
> ./rust,8011776,46101
> ===> src/d/dencoder
> src/d/dencoder,44154880,42
> src/d/dencoder,51347456,87
> src/d/dencoder,51380224,273
> src/d/dencoder,51462144,441
> src/d/dencoder,18644992,4414
> src/d/dencoder,18710528,43548
> ```

OK, this piqued my interest enough that I decided to install rust using
rustup instead of my distro's package manager.  Here are the numbers I
got for my machine:

===> ./rust
./rust,22896640,35
./rust,22896640,137
./rust,22384640,542
./rust,22896640,1034
./rust,8785920,2489
./rust,8785920,12157
===> src/d/dencoder
src/d/dencoder,1066799104,36
src/d/dencoder,1066799104,72
src/d/dencoder,1066799104,198
src/d/dencoder,1066799104,344
src/d/dencoder,1035292672,2372
src/d/dencoder,1035292672,13867

Looks like we lost out to Rust for larger inputs. :-D  Probably due to
environmental factors (and the fact that std.stdio is slow).  I re-ran
it again and got this:

===> ./rust
./rust,22896640,30
./rust,22896640,131
./rust,22896640,511
./rust,22896640,983
./rust,8785920,3102
./rust,8785920,9912
===> src/d/dencoder
src/d/dencoder,1066799104,36
src/d/dencoder,1066799104,71
src/d/dencoder,1066799104,197
src/d/dencoder,1066799104,355
src/d/dencoder,1035292672,3441
src/d/dencoder,1035292672,9471

Notice the significant discrepancy between the two runs; this seems to
show that the benchmark is only accurate up to about ±1.5 seconds.

Anyway, oddly enough, Java seems to beat Rust on larger inputs.  Maybe
my Java compiler has a better JIT implementation? :-P


> Congratulations on beating Rust :D but remember: you're using a much
> more efficient algorithm! I must conclude that the Rust translation of
> the Trie algorithm would be much faster still, unfortunately (you may
> have noticed that I am on D's side here!).

At this point, it's not really about the difference between languages
anymore; it's about the programmer's skill at optimizing his code.

Traditionally Java is thought to be the slowest, because it runs in a VM
and generally tends to use more heap allocations.  In recent times,
however, JIT and advanced GC implementations have significantly levelled
that out, so you're probably not going to see the difference unless you
hand-tweak your code down to the bare metal.

Surprisingly, at least on my machine, Lisp actually performed the worst.
I'd have thought it would at least beat Java, but I was quite wrong. :-D
Perhaps the Lisp implementation I'm using is suboptimal, I don't know.
Or perhaps modern JVMs have really overtaken Lisp.

Now I'm really curious how a Rust version of the trie algorithm would
perform.  Unfortunately I don't know Rust so I wouldn't be able to write
it myself. (Hint, hint, nudge, nudge ;-)).

As far as the performance of my D version is concerned, I still haven't
squeezed out all the performance I could yet.  Going into this, my
intention was to take the lazy way of optimizing only what the profiler
points out to me, with the slight ulterior motive of proving that a
relatively small amount of targeted optimizations can go a long way at
making the GC a non-problem in your typical D code. ;-)  I haven't
pulled out all the optimization guns at my disposal yet.

If I were to go the next step, I'd split up the impl() function so that
I get a better profile of where it's spending most of its time, and then
optimize that.  My current suspicion is that the traversal of the trie
could be improved by caching intermediate results to eliminate a good
proportion of recursive calls in impl().

Also, the `print` mode of operation is quite slow, probably because
writefln() allocates. (It allocates less than if I had used .format like
I did before, but it nevertheless still allocates.) To alleviate this
cost, I'd allocate an output buffer and write to that, flushing only
once it filled up.

Another thing I could do is to use std.parallelism.parallel to run
searches on batches of phone numbers in parallel. This is kinda
cheating, though, since it's the same algorithm with the same cost,
we're just putting more CPU cores to work. :-P  But in D this is quite
easy to do, often as easy as simply adding .parallel to your outer
foreach loop. In this particular case it will need some additional
refactoring due to the fact that the input is being read line by line.
But it's relatively easy to load the input into a buffer by chunks
instead, and just run the searches on all the numbers found in the
buffer in parallel.


On Thu, Jan 18, 2024 at 04:25:45PM +0000, Renato via Digitalmars-d-learn wrote:
[...]
> BTW here's you main function so it can run on the benchmark:
[...]

Thanks, I've adapted my code accordingly and pushed to my github repo.


T

-- 
This is a tpyo.