Re: Help optimize D solution to phone encoding problem: extremely slow performace.
On Sunday, 14 January 2024 at 17:11:27 UTC, Renato wrote: If anyone can find any flaw in my methodology or optmise my code so that it can still get a couple of times faster, approaching Rust's performance, I would greatly appreciate that! But for now, my understanding is that the most promising way to get there would be to write D in `betterC` style?! I've added port from Rust in the PR comment. Can you please check this solution? Most probably it need to be optimized with profiler. Just interesting how close-enough port will work.
Re: Socket handle leak and active handle warning with Vibe-D
On Saturday, 13 January 2024 at 20:49:54 UTC, bomat wrote: I am still getting this in 2024 and vibe.d 0.9.7: ``` Warning: 1 socket handles leaked at driver shutdown. ``` I was wondering if maybe someone has new info on this... There should be a version you can enable that tells you where that socket handle was allocated. That might give you a further clue as to why it's not closed when the system shuts down. I think the program tells you which version to enable when this happens, but if not, let me know and I'll find it. -Steve
Re: Non-blocking keyboard input
On Sunday, 14 January 2024 at 13:41:26 UTC, Joe wrote: This does not actually work on my computer. It still blocks. Adam is no longer using mainstream D, and apparently not posting on this forum. I suggest you try to contact him via the arsd github page: https://github.com/adamdruppe/arsd -Steve
Re: Help optimize D solution to phone encoding problem: extremely slow performace.
On Sunday, 14 January 2024 at 10:02:58 UTC, Jordan Wilson wrote: On Saturday, 13 January 2024 at 11:03:42 UTC, Renato wrote: I like to use a phone encoding problem to determine the strenghtness and weaknesses of programming languages because this problem is easy enough I can write solutions in any language in a few hours, but complex enough to exercise lots of interesting parts of the language. [...] Hello Renato, This seems to be quite a lot of calls: ``` Timer frequency unknown, Times are in Megaticks Num TreeFuncPer CallsTimeTimeCall 1920496437613756 0 pure nothrow ref @trusted immutable(char)[][] core.internal.array.appending._d_arrayappendcTX!(immutable(char)[][], immutable(char)[])._d_arrayappendcTX(scope return ref immutable(char)[][], ulong) 1920492489573474 0 @safe void dencoder.printTranslations(immutable(char)[][][dencoder.Key], dencoder.ISolutionHandler, immutable(char)[], immutable(char)[], immutable(char)[][]) ``` This is when using the `words-quarter.txt` input (the `dictionary.txt` input seems to finish much faster, although still slower than `java`/`rust`). I also used only 100 phone numbers as input. My final observation is that `words-quarter.txt` contains some 1-letter inputs, (for example, `i` or `m`)...this may result in a large number of encoding permutations, which may explain the high number of recursion calls? Jordan The characteristics of the dictionary impact the number of solutions greatly. I explored this in my blog post about [Common Lisp, Part 2](https://renato.athaydes.com/posts/revenge_of_lisp-part-2). The fact there's a ridiculous amount of function calls is why this problem can take minutes even without having to allocate much memory or print anything. ** I've managed to improve the D code enough that it is now faster than Common Lisp and the equivalent algorithm in Java.** It took some profiling to do that, though... thanks to @Anonymouse for the suggestion to use Valgrind... with that, I was able to profile the code nicely (Valgrind works nicely with D, it doesn't even show mangled names!). Here's what I did. First: the solution using int128 was much faster than the BigInt solution, as I had already mentioned. But when profiling that, it was clear that for the problems with a very large number of solutions, GC became a problem: ``` 23,044,096,944 (100.0%) PROGRAM TOTALS Ir file:function 7,079,878,197 (30.72%) ???:core.internal.gc.impl.conservative.gc.Gcx.mark!(false, true, true).mark(core.internal.gc.impl.conservative.gc.Gcx.ScanRange!(false).ScanRange) [/home/renato/programming/experiments/prechelt-phone-number-encoding/dencoder-int128] 2,375,100,857 (10.31%) ???:dencoder.printTranslations(immutable(char)[][][std.int128.Int128], dencoder.ISolutionHandler, immutable(char)[], immutable(char)[], immutable(char)[][])'2 [/home/renato/programming/experiments/prechelt-phone-number-encoding/dencoder-int128] 1,971,210,820 ( 8.55%) ???:_aaInX [/home/renato/programming/experiments/prechelt-phone-number-encoding/dencoder-int128] 1,922,961,924 ( 8.34%) ???:_d_arraysetlengthT [/home/renato/programming/experiments/prechelt-phone-number-encoding/dencoder-int128] 1,298,747,622 ( 5.64%) ???:core.int128.mul(core.int128.Cent, core.int128.Cent) [/home/renato/programming/experiments/prechelt-phone-number-encoding/dencoder-int128] 1,134,644,706 ( 4.92%) ???:core.internal.gc.bits.GCBits.setLocked(ulong) [/home/renato/programming/experiments/prechelt-phone-number-encoding/dencoder-int128] 849,587,834 ( 3.69%) ???:core.internal.gc.impl.conservative.gc.Gcx.smallAlloc(ulong, ref ulong, uint, const(TypeInfo)) [/home/renato/programming/experiments/prechelt-phone-number-encoding/dencoder-int128] 827,407,988 ( 3.59%) ./string/../sysdeps/x86_64/multiarch/memmove-vec-unaligned-erms.S:__memcpy_avx_unaligned_erms [/usr/lib/x86_64-linux-gnu/libc.so.6] 688,845,027 ( 2.99%) ./string/../sysdeps/x86_64/multiarch/memset-vec-unaligned-erms.S:__memset_avx2_unaligned_erms [/usr/lib/x86_64-linux-gnu/libc.so.6] 575,415,884 ( 2.50%) ???:_DThn16_4core8internal2gc4impl12conservativeQw14ConservativeGC6qallocMFNbmkMxC8TypeInfoZSQDd6memory8BlkInfo_ [/home/renato/programming/experiments/prechelt-phone-number-encoding/dencoder-int128] 562,146,592 ( 2.44%) ???: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,
Re: Non-blocking keyboard input
On Wednesday, 27 December 2023 at 13:27:53 UTC, Adam D Ruppe
wrote:
On Wednesday, 27 December 2023 at 05:07:04 UTC, Joe wrote:
??? Surely there there is
a one liner library solution for this?
It is not one line because it needs a bit of setup (and
teardown, but the objects' destructors do that for you) but it
is close:
http://arsd-official.dpldocs.info/arsd.terminal.html#single-key
`input.getch` waits for a single line, but you can use
`if(input.kbhit())` to see if it would block before calling it.
This shouldn't be hard... yet it is.
Better be careful, the mods are out in force deleting posts
this week that tell the hard truth. But yeah, the stdlib in D
has very little activity:
https://github.com/dlang/phobos/graphs/contributors?
So you can't expect much from it. My arsd libs provide a broad
set of functionality missing from it: stuff like this
terminal/console stuff, window creation, basic guis, web
servers, etc.
If you want to try them, you can use it from the dub system,
but I recommend just `git clone
https://github.com/adamdruppe/arsd.git` in your working
directory then import what you want and use `dmd -i` to
automatically include them in the build.
This does not actually work on my computer. It still blocks.
int itr = 0;
for(;;)
{
itr++;
writeln("1. closeKBThread = ", closeKBThread, ", iter = ",
itr);
if (closeKBThread) return;
string op = "";
string istr = "";
while (!closeKBThread)
{
writeln("2. ", input.kbhit(), " ",
closeKBThread);
if (input.kbhit())
{
istr ~= input.getch(false);
break;
}
}
writeln("final istr = ", istr);
1. closeKBThread = false, iter = 1
2. false false
2. false false
2. false false
2. false false
final istr = f
1. closeKBThread = false, iter = 2
2. false false < now blocking
All this is just junk of me trying to figure out what was going
on, but literally input.kbhit blocks after the first run(which
really means it's always blocking)
My original code was
while(true)
{
if (input.kbhit()) { istr ~= input.getch(); break; }
}
and I've been trying all kinds of stuff to figure out what was
going on but I believe it is the kbhit function itself. It calls
getch(true) and blocks on that as if I were just using getch
itself.
The issue is the same, the code does not block then after I hit a
key and it goes through an iteration of the outside loop it then
blocks waiting for the next input.
Re: Help optimize D solution to phone encoding problem: extremely slow performace.
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 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. I
Re: Help optimize D solution to phone encoding problem: extremely slow performace.
On Saturday, 13 January 2024 at 11:03:42 UTC, Renato wrote: I like to use a phone encoding problem to determine the strenghtness and weaknesses of programming languages because this problem is easy enough I can write solutions in any language in a few hours, but complex enough to exercise lots of interesting parts of the language. [...] Hello Renato, This seems to be quite a lot of calls: ``` Timer frequency unknown, Times are in Megaticks Num TreeFuncPer CallsTimeTimeCall 1920496437613756 0 pure nothrow ref @trusted immutable(char)[][] core.internal.array.appending._d_arrayappendcTX!(immutable(char)[][], immutable(char)[])._d_arrayappendcTX(scope return ref immutable(char)[][], ulong) 1920492489573474 0 @safe void dencoder.printTranslations(immutable(char)[][][dencoder.Key], dencoder.ISolutionHandler, immutable(char)[], immutable(char)[], immutable(char)[][]) ``` This is when using the `words-quarter.txt` input (the `dictionary.txt` input seems to finish much faster, although still slower than `java`/`rust`). I also used only 100 phone numbers as input. My final observation is that `words-quarter.txt` contains some 1-letter inputs, (for example, `i` or `m`)...this may result in a large number of encoding permutations, which may explain the high number of recursion calls? Jordan
Re: Help optimize D solution to phone encoding problem: extremely slow performace.
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.
