<div dir="auto"><div><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Dne so 20. 1. 2024 21:21 uživatel Renato via Digitalmars-d-learn <<a href="mailto:digitalmars-d-learn@puremagic.com">digitalmars-d-learn@puremagic.com</a>> napsal:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Saturday, 20 January 2024 at 19:45:19 UTC, Daniel Kozak wrote:<br>
> On Sat, Jan 20, 2024 at 2:11 PM Renato via Digitalmars-d-learn <br>
> < <a href="mailto:digitalmars-d-learn@puremagic.com" target="_blank" rel="noreferrer">digitalmars-d-learn@puremagic.com</a>> wrote:<br>
><br>
>> Wow, fantastic feedback from lots of people, thanks so much! <br>
>> ...<br>
>><br>
>> > evilrat:<br>
>> > There is another important difference, i quickly looked up D<br>
>> > associative array implementation and the search looks like<br>
>> > nlog(n) complexity with plain loop iteration of hashes, <br>
>> > whereas<br>
>> > rust's implementation is using "swisstable" algorithm<br>
>> > implementation that has packed SIMD optimized lookups, this <br>
>> > is<br>
>> > likely where the 3x speed difference comes from.<br>
>><br>
>> I am not using the default hash implementation in Rust (which <br>
>> is hashbrown as you've found out). That's too slow (because <br>
>> it's ddos secure - still Java's hash also is and it's still <br>
>> faster). I had to replace that with a library called `ahash`.<br>
>><br>
>> If you're interested in knowing more about that, please [read <br>
>> my blog <br>
>> post](<a href="https://renato.athaydes.com/posts/how-to-write-fast-rust-code" rel="noreferrer noreferrer" target="_blank">https://renato.athaydes.com/posts/how-to-write-fast-rust-code</a>) about optimising the Rust code.<br>
>><br>
>> So, no, that's not where the difference is coming from... in <br>
>> fact, I am using a faster hashing function in D.<br>
>><br>
>> You can [see my custom hashing function<br>
>> here](<br>
>> <a href="https://github.com/renatoathaydes/prechelt-phone-number-encoding/commit/d1fa1b77ad928f7d536728fba11f2d69b4afe7e3" rel="noreferrer noreferrer" target="_blank">https://github.com/renatoathaydes/prechelt-phone-number-encoding/commit/d1fa1b77ad928f7d536728fba11f2d69b4afe7e3</a>).<br>
>> This function is not good for the general purpose case, but <br>
>> it's probably<br>
>> as good as it gets for this problem (see my int128 trick in a <br>
>> previous post<br>
>> on this thread to understand why). I did try a few variations <br>
>> of hashing<br>
>> before settling on this one... Rust, if anything, is at a <br>
>> disadvantage here.<br>
>><br>
><br>
> And here you are wrong, it is the hashing when the slowdown <br>
> comes. It is not only about the speed of hashing function. It <br>
> is about the quality of hashing functiuon for this particular <br>
> problem and it is about how hashing table (associative array) <br>
> is implemented.<br>
<br>
I've explained why this function is almost a perfect hash <br>
function for this problem (there will be almost no collisions <br>
except for very large inputs where the shift-left will <br>
"overflow", and even then the probability of collisions should be <br>
very low). If you're going to claim I'm wrong, you must show <br>
exactly where I'm wrong, and preferrably you should provide a <br>
faster implementation. I will even accept a theoretical <br>
explanation if you can give one. What I will not accept, is for <br>
you to call me "wrong" just because you say so. That's childish <br>
behaviour and uncalled for on a technical discussion.<br></blockquote></div></div><div dir="auto"><br></div><div dir="auto"><br></div><div dir="auto">If you provided info that hash is perfect, than I am sorry. I have probably missed that in this thread my fault. Than I will need to looked into this more carefully and do much more than just assumption.</div><div dir="auto"><div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
</blockquote></div></div></div>