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

[Daniel Kozak]

On Sat, Jan 20, 2024 at 2:11 PM Renato via Digitalmars-d-learn <
digitalmars-d-learn at puremagic.com> wrote:

> Wow, fantastic feedback from lots of people, thanks so much!
> ...
>
> > evilrat:
> > There is another important difference, i quickly looked up D
> > associative array implementation and the search looks like
> > nlog(n) complexity with plain loop iteration of hashes, whereas
> > rust's implementation is using "swisstable" algorithm
> > implementation that has packed SIMD optimized lookups, this is
> > likely where the 3x speed difference comes from.
>
> I am not using the default hash implementation in Rust (which is
> hashbrown as you've found out). That's too slow (because it's
> ddos secure - still Java's hash also is and it's still faster). I
> had to replace that with a library called `ahash`.
>
> If you're interested in knowing more about that, please [read my
> blog
> post](https://renato.athaydes.com/posts/how-to-write-fast-rust-code)
> about optimising the Rust code.
>
> So, no, that's not where the difference is coming from... in
> fact, I am using a faster hashing function in D.
>
> You can [see my custom hashing function
> here](
> https://github.com/renatoathaydes/prechelt-phone-number-encoding/commit/d1fa1b77ad928f7d536728fba11f2d69b4afe7e3).
> This function is not good for the general purpose case, but it's probably
> as good as it gets for this problem (see my int128 trick in a previous post
> on this thread to understand why). I did try a few variations of hashing
> before settling on this one... Rust, if anything, is at a disadvantage here.
>

And here you are wrong, it is the hashing when the slowdown comes. It is
not only about the speed of hashing function. It is about the quality of
hashing functiuon for this particular problem and it is about how hashing
table (associative array) is implemented.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.puremagic.com/pipermail/digitalmars-d-learn/attachments/20240120/78036ae6/attachment.htm>