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

[Siarhei Siamashka]

On Tuesday, 16 January 2024 at 21:15:19 UTC, Renato wrote:
> For the record (I already posted this on GitHub)... here's [my 
> current fastest 
> solution](https://github.com/renatoathaydes/prechelt-phone-number-encoding/blob/dlang-key-hash-incremental/src/d/src/dencoder.d) time using the same algorithm as Rust ...

[...]

> ... what I am really curious about is what the code I wrote is 
> doing wrong that causes it to run 4x slower than Rust despite 
> doing "the same thing"...

It's a GC allocations fest. Things like this make it slow:

```diff
      {
-        string digit = [digits[0]];
+        string digit = digits[0 .. 1];
          words.insertBack(digit);
```

And at the top is the associative array lookup (when profiling 
the handling of the "phones_1_000_000_with_empty.txt" input file):

```
     36.85%  dencoder  dencoder              [.] _aaInX
     12.38%  dencoder  dencoder              [.] void 
dencoder.printTranslations(immutable(char)[][][dencoder.Key], 
dencoder.ISolutionHandler, immutable(char)[], immutable(char)[], 
std.container.array.Array!(immutable(char)[]).Array)
      6.43%  dencoder  dencoder              [.] nothrow @nogc 
scope void core.internal.gc.impl.conservative.gc.Gcx.mark!(false, 
true, 
true).mark(core.internal.gc.impl.conservative.gc.Gcx.ScanRange!(false).ScanRange)
      4.53%  dencoder  dencoder              [.] pure @safe void 
std.algorithm.iteration.FilterResult!(dencoder.main(immutable(char)[][]).__lambda12, immutable(char)[]).FilterResult.popFront()
      4.08%  dencoder  dencoder              [.] 
_d_array_slice_copy
      2.43%  dencoder  dencoder              [.] _d_newarrayU
      2.21%  dencoder  dencoder              [.] shared nothrow 
@nogc @trusted void core.internal.spinlock.SpinLock.lock()
      2.00%  dencoder  dencoder              [.] pure @safe void 
std.array.Appender!(immutable(char)[]).Appender.put!(dchar).put(dchar)
      1.91%  dencoder  dencoder              [.] nothrow void* 
core.internal.gc.impl.conservative.gc.Gcx.smallAlloc(ulong, ref 
ulong, uint, const(TypeInfo))
      1.67%  dencoder  dencoder              [.] 
_DThn16_4core8internal2gc4impl12conservativeQw14ConservativeGC6qallocMFNbmkMxC8TypeInfoZSQDd6memory8BlkInfo_
      1.66%  dencoder  dencoder              [.] pure nothrow 
@nogc scope @trusted ulong 
core.internal.gc.bits.GCBits.setLocked(ulong)
      1.60%  dencoder  dencoder              [.] const pure 
nothrow @trusted ulong object.TypeInfo_Struct.getHash(scope 
const(void*))
      1.53%  dencoder  dencoder              [.] nothrow @safe 
void 
core.internal.util.array.enforceRawArraysConformable(const(char[]), const(ulong), const(void[]), const(void[]), const(bool))
      1.49%  dencoder  dencoder              [.] nothrow void* 
core.internal.gc.impl.conservative.gc.ConservativeGC.runLocked!(core.internal.gc.impl.conservative.gc.ConservativeGC.mallocNoSync(ulong, uint, ref ulong, const(TypeInfo)), core.internal.gc.impl.conservative.gc.mallocTime, core.internal.gc.impl.conservative.gc.numMallocs, ulong, uint, ulong, const(TypeInfo)).runLocked(ref ulong, ref uint, ref ulong, ref const(TypeInfo))
      1.27%  dencoder  dencoder              [.] pure nothrow 
@safe void 
std.array.Appender!(immutable(char)[]).Appender.ensureAddable(ulong)
      0.81%  dencoder  dencoder              [.] pure @property 
@safe dchar 
std.algorithm.iteration.FilterResult!(dencoder.main(immutable(char)[][]).__lambda12, immutable(char)[]).FilterResult.front()
      0.79%  dencoder  dencoder              [.] nothrow @safe 
void core.internal.util.array._enforceNoOverlap(const(char[]), 
ulong, ulong, const(ulong))
      0.74%  dencoder  dencoder              [.] nothrow void 
core.internal.gc.impl.conservative.gc.Pool.setBits(ulong, uint)
      0.73%  dencoder  dencoder              [.] pure @safe void 
std.array.Appender!(immutable(char)[]).Appender.put!(std.algorithm.iteration.FilterResult!(dencoder.main(immutable(char)[][]).__lambda12, immutable(char)[]).FilterResult).put(std.algorithm.iteration.FilterResult!(dencoder.main(immutable(char)[][]).__lambda12, immutable(char)[]).FilterResult)
      0.70%  dencoder  dencoder              [.] pure @safe ulong 
std.range.primitives.walkLength!(std.algorithm.iteration.FilterResult!(dencoder.main(immutable(char)[][]).__lambda12, immutable(char)[]).FilterResult).walkLength(std.algorithm.iteration.FilterResult!(dencoder.main(immutable(char)[][]).__lambda12, immutable(char)[]).FilterResult)
      0.60%  dencoder  dencoder              [.] bool 
dencoder.lastItemIsDigit(std.container.array.Array!(immutable(char)[]).Array)
      0.54%  dencoder  dencoder              [.] _d_newarrayT
[...]
```