www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - How to work with hashmap from memutils properly?

reply Sergey <kornburn yandex.ru> writes:
Could someone help with memutils library?
It seems (based on some posts in 2018) that memutils is one of 
the fastest hashmap in Dlang world (if you know it is not - 
please help me find the fastest hashmap realisation).

I've made some benchmarks with the same code for regular AA, 
ikod-container and memutils. And the last one gave the different 
results. In the realisation is used the same operations: get, 
put, in.
The master version (compiled locally) is used, because last 
version available in dub is broken (issue already in the github 
since August 2021).

Can someone help to find out how to make it works?
Because there is no any kind of documetation for this package at 
all :(

Code could be found here: 
https://github.com/cyrusmsk/lang_benchmark/tree/main/lru/source/d_comparison/mem

PS it seems that almost all realisations of hashmap/dict/AA in D 
very slow :(
Feb 10 2022
parent reply Siarhei Siamashka <siarhei.siamashka gmail.com> writes:
On Thursday, 10 February 2022 at 20:39:45 UTC, Sergey wrote:


 Code could be found here: 
 https://github.com/cyrusmsk/lang_benchmark/tree/main/lru/source/d_comparison/mem


Is this an attempt to implement a high performance solution for 
the Benchmarks Game's LRU problem in D language?


 PS it seems that almost all realisations of hashmap/dict/AA in 
 D very slow :(


Looks like your code that you are bolting on top of 
hashmap/dict/AA is very slow. Some major improvements are 
possible.

Though this strange benchmark is testing performance of an LRU 
with ... wait for it ... 10 elements, which makes using 
hashmap/dict/AA a completely ridiculous idea. You can try to test 
this code as a replacement for your LRU class:

```D
struct LRU(KT, VT)
{
     private int _size;
     private Tuple!(KT, VT)[] a;

     this(int size)
     {
         _size = size;
     }

     protected Tuple!(bool, VT) get(KT key)
     {
         foreach (i ; 0 .. a.length)
         {
             if (a[i][0] == key)
             {
                 auto tmp = a[i];
                 foreach (j ; i + 1 .. a.length)
                     a[j - 1] = a[j];
                 a.back = tmp;
                 return tuple(true, a.back[1]);
             }
         }
         return tuple(false, cast(VT) 0);
     }

     protected void put(KT key, VT value)
     {
         foreach (i ; 0 .. a.length)
         {
             if (a[i][0] == key)
             {
                 foreach (j ; i + 1 .. a.length)
                     a[j - 1] = a[j];
                 a.back = tuple(key, value);
                 return;
             }
         }
         if (a.length < _size)
         {
             a ~= tuple(key, value);
             return;
         }
         // FIXME: use ring buffer and this copy loop won't be 
necessary
         foreach (j ; 1 .. a.length)
             a[j - 1] = a[j];
         a.back = tuple(key, value);
     }
}
```
It can be further tuned for better performance if necessary.
Feb 10 2022
next sibling parent reply Sergey <kornburn yandex.ru> writes:
On Friday, 11 February 2022 at 02:43:24 UTC, Siarhei Siamashka 
wrote:

 On Thursday, 10 February 2022 at 20:39:45 UTC, Sergey wrote:


 Code could be found here: 
 https://github.com/cyrusmsk/lang_benchmark/tree/main/lru/source/d_comparison/mem


 Is this an attempt to implement a high performance solution for 
 the Benchmarks Game's LRU problem in D language?


Yes. There is no D version there. And I'm just curious how fast 
is D in those problems.


 It can be further tuned for better performance if necessary.


Thank you for your version.
It is interesting finding about the size of the LRU. Already seen 
your comment in the benchmark github.

Though version with memutils still not working :)

What is also interesting - it is quite different results based 
not only for size of cache, but also the number of iterations.

P.S. surprised to see you here. I've seen your participation in 
contests at codeforces - there are much smaller D-community)
Feb 11 2022
parent reply Siarhei Siamashka <siarhei.siamashka gmail.com> writes:
On Friday, 11 February 2022 at 19:04:41 UTC, Sergey wrote:

 Is this an attempt to implement a high performance solution 
 for the Benchmarks Game's LRU problem in D language?


 Yes. There is no D version there. And I'm just curious how fast 
 is D in those problems.


Dlang (LDC), Crystal, Rust and C++ (Clang) all can generate 
equally fast code. That's because they are using the same LLVM 
backend for generating code. If you encounter a significant 
performance difference, then there has to be a good reason for 
that. And figuring out what exactly causes this difference allows 
to fix the under-performing code in most cases.

A better question is how much effort is required to reach _peak_ 
performance using each of these programming languages? Or how 
much effort is required to reach _good enough_ performance?

Let's look at the benchmark results from that site:
* https://programming-language-benchmarks.vercel.app/d-vs-rust
* 
https://programming-language-benchmarks.vercel.app/crystal-vs-rust
* https://programming-language-benchmarks.vercel.app/d-vs-crystal

It may seem like Rust is kinda winning there. But is it a faster 
language? Or did some people just invest a lot of their time into 
creating better Rust code for these benchmarks? This time is not 
tracked and not compared for different languages, while it's 
probably the most important metric.

My personal opinion is that both Dlang and Crystal primarily 
focus on developer convenience and rapid development. Rust 
focuses on extreme safety at the expense of developer 
convenience. C++ is neither safe nor convenient, but at least 
it's fast and has excellent backward compatibility with the old 
code.

Does it make sense to spend time on improving D code on that 
benchmark site and reach performance parity with the other 
languages? I don't know.


 It is interesting finding about the size of the LRU. Already 
 seen your comment in the benchmark github.


Yes, I took a look and their initial implementation of the LRU 
benchmark for Crystal was initially written by somebody, who is 
apparently not very fluent with the language. This was difficult 
for me to ignore, so I had an impulse to fix it and this 
escalated into a kind of Rust vs. Crystal performance duel.

Now the size of the LRU cache has been changed to something more 
reasonable in that benchmark and hash tables are back in the game 
:-) You can try to contribute your D code to this benchmark site 
and then work on making it faster.


 Though version with memutils still not working :)


Do you suspect that it's a bug in 
https://github.com/etcimon/memutils ? I never heard about this 
library before. But associative arrays are important enough and 
it's reasonable to expect a decent implementation in the standard 
library without having to use some third-party magic sauce for 
that.
Feb 16 2022
parent reply ikod <igor.khasilev gmail.com> writes:
On Wednesday, 16 February 2022 at 10:31:38 UTC, Siarhei Siamashka 
wrote:

 On Friday, 11 February 2022 at 19:04:41 UTC, Sergey wrote:

 Is this an attempt to implement a high performance solution 
 for the Benchmarks Game's LRU problem in D language?


 Yes. There is no D version there. And I'm just curious how 
 fast is D in those problems.




Sorry for late question - I can't find page with benchmark 
results, can you please share url?

Thanks
Feb 16 2022
parent Sergey <kornburn yandex.ru> writes:
On Wednesday, 16 February 2022 at 13:37:28 UTC, ikod wrote:

 On Wednesday, 16 February 2022 at 10:31:38 UTC, Siarhei 
 Siamashka wrote:

 On Friday, 11 February 2022 at 19:04:41 UTC, Sergey wrote:

 Is this an attempt to implement a high performance solution 
 for the Benchmarks Game's LRU problem in D language?


 Yes. There is no D version there. And I'm just curious how 
 fast is D in those problems.




 Sorry for late question - I can't find page with benchmark 
 results, can you please share url?

 Thanks


Hi. I'm not sure which results did you mean..
Official page with LRU (and great implementation in Crystal from 
Siarhei) is here: 
https://programming-language-benchmarks.vercel.app/problem/lru

Results with my version in D is here:
https://github.com/cyrusmsk/lang_benchmark/tree/main/lru/bin

But the code is not the same that used in original 
implementation. To speed-up the D solution I thought to play 
around with  safe and  nogc.. but currently no time for that..

Btw ikod packages was used instead of built-in AA. And I've made 
the version with memutils - but unfortunately it is the slowest 
one.
Mar 04 2022
prev sibling parent Era Scarecrow <rtcvb32 yahoo.com> writes:
On Friday, 11 February 2022 at 02:43:24 UTC, Siarhei Siamashka 
wrote:

 Though this strange benchmark is testing performance of an LRU 
 with ... wait for it ... 10 elements, which makes using 
 hashmap/dict/AA a completely ridiculous idea.


  Hmmm... if it's static data i can see maybe a enum hashmap with 
keynames, and then it resolved at compile-time to fixed values 
maybe (*for AA*).

  I remember for a C project i faked a hashmap/AA by having sorted 
key/value pairs and then doing a binary lookup. I also have a D 
static-AA i made which will make an array large enough for all 
the statically known values at compile-time, though i don't know 
if anyone uses it.

  Regardless, 10 items really is a bad test size; Big enough to 
show it might be working but not big enough for performance tests 
(*at least with 2Ghz+ computers today; Maybe on a Pi where you 
can drop it to 30Mhz then you could get somewhat useful results 
from a smaller dataset*).
Feb 11 2022