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 :(

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

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

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:

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.

On Friday, 11 February 2022 at 02:43:24 UTC, Siarhei Siamashka wrote:

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

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)

On Friday, 11 February 2022 at 02:43:24 UTC, Siarhei Siamashka wrote:

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).

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

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.

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.

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.

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

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

Thanks

On Wednesday, 16 February 2022 at 13:37:28 UTC, ikod wrote:

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.