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

[H. S. Teoh]

On Tue, Jan 16, 2024 at 09:15:19PM +0000, Renato via Digitalmars-d-learn wrote:
> On Tuesday, 16 January 2024 at 20:34:48 UTC, H. S. Teoh wrote:
> > On Tue, Jan 16, 2024 at 12:28:49PM -0800, H. S. Teoh via
> > Digitalmars-d-learn wrote: [...]
> > > Anyway, I've fixed the problem, now my program produces the exact
> > > same output as Renato's repo. Code is posted below.
> > [...]
> > 
> 
> Great, I ran the benchmarks for you :)
> 
> I had to change how you accept arguments, even though you did "the
> right thing" using `getopt`, the solutions should just take a `count`
> or `print` argument first...

Oops, haha :-P


> Anyway, here's your result:
> 
> ```
> ===> ./rust
> ./rust,24133632,25
> ./rust,24739840,130
> ./rust,24477696,536
> ./rust,25247744,1064
> ./rust,8175616,6148
> ./rust,8306688,8315
> ===> src/d/dencoder
> src/d/dencoder,46055424,43
> src/d/dencoder,96337920,146
> src/d/dencoder,102350848,542
> src/d/dencoder,102268928,1032
> src/d/dencoder,40206336,99936
> ^C
> ```
> 
> It took too long with the `count` option, so I had to abort before the
> last run ended... there's probably some bug there, otherwise the Trie
> runs very fast, as I had expected.
[...]

Do you have the problematic data file handy?  I'd like to look into any
potential bugs.

Also, the profiler revealed that a lot of time was spent in the GC and
in small allocations.  The cause is in all likelihood the .format() call
for each found match, and array append being used for the recursive
calls. Getting rid of the .format ought to speed it up a bit. Will try
that now...


T

-- 
If the comments and the code disagree, it's likely that *both* are wrong. -- Christopher