Re: How to work with hashmap from memutils properly?
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.
Re: How to work with hashmap from memutils properly?
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
Re: How to work with hashmap from memutils properly?
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.
Re: How to work with hashmap from memutils properly?
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*).
Re: How to work with hashmap from memutils properly?
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)
Re: How to work with hashmap from memutils properly?
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.
How to work with hashmap from memutils properly?
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 :(
