Edmonds algorithm in Koka

[anfelor]

I ported Edmonds Algorithm for computing a maximum cardinality matching for a graph from C++ to Koka and uploaded it to my Github. Aside from some compiler bugs I found, it worked really well: I am amazed that it is possible to write an imperative algorithm in a functional programming language!

Performance is pretty bad so far; even though I probably can't share the instances, here is an overview:

Instance	C++	Koka
queen16_16	0.01s	0.9s
queen27_27	0.02s	12.5s
queen4_4	0.00s	0.02s
lu980	0.01s	1.9s

While the algorithm is exactly the same, I swapped out some datastructures: At a few places I used a list for a stack where the C++ code used a vector and in the find-cycle function I used a list instead of a set. But most of the performance problem seems to be from unnecessary allocations: On some larger instances the Koka code simply allocates all my memory and fails. I will try to fix these leaks; hopefully that pushes the code into the same ballpark as C++.

[anfelor]

I pushed some commits to eliminate uncertainty over the performance problem: First I now use a modified rbtree as a set of integers and I tried to avoid using references and instead have more pure functions. Unfortunately, if anything they made the code a bit slower. It turns out though, that I continued using the executables in gcc-debug even after I started using -O2, so now it at least works on each instance. Still, in the worst case its still 50 times slower! I'll try to nail down the issue by benchmarking my modules individually, but that might take some time.

[daanx]

Ha, this is very interesting! I will take a look soon but would love to study it and see if/how we can improve things.
Note you can use the :set -O2 --showelapsed flags to quickly benchmark from within the interpreter.

[anfelor]

That sounds awesome! I'll see if I can share the test instances with you, so that you can also run the benchmarks. Feel free to ping me if you have any questions about the algorithm: the unshrinking part has some hidden assumptions that are not that obvious from the code.

[anfelor]

You can find instances for testing and replicating my results at http://www.or.uni-bonn.de/lectures/ws18/co_exercises/edmonds_card_matching_graphs.tgz

[anfelor]

The problem is probably entirely due to the implementation of vector:

#include <vector>
int main() {
    size_t n = 10000000;
    std::vector<char> v(n, 'a');
    for(size_t i = 0; i < n; ++i) {
        v.at(i) = 'b';
    }
}

runs in 0,00 - 0,01 seconds on my machine while:

module bench

public fun main() {
    val n = 10000000
    var v := vector(n, 'a')
    for(0, n - 1) fn(i) {
        v[i] := 'b'
    }
}

takes 0,13-0,15 seconds. The same happens when we use Bool/boolean or int/size_t as data for the vector.

[anfelor]

I tried modifying the C++ programm a bit to mimic what Koka does, but that only increased the runtime to 0,03 seconds on average:

#include <vector>
#include <atomic>

int main() {
    long int n = 10000000;
    char a = 'a';
    char b = 'b';
    std::vector<uintptr_t> v(n, (uintptr_t) &a);
    std::vector<uintptr_t>* p = &v;
    std::atomic w(p); // kk_ref_t
    for(long int idx = 0; idx < n; ++idx) {
        size_t i = 0;
        if(idx < 0) {
            i = 0;
        } else {
            i = idx;
        }
        p = std::atomic_load_explicit(&w, std::memory_order_relaxed);
        if(i < p->size()) {
            (*p)[i] = (uintptr_t) &b;
        }
    }
}

[SchrodingerZhu]

vector is actually storing kk\_box\_t which behaves like ptr. but for primitive types, it is specialized to hold the value in place. \-------- Original Message --------

On Jan 12, 2021, 3:04 AM, Anton Felix Lorenzen < ***@***.***> wrote: The problem is probably entirely due to the implementation of vector: ``` #include <vector> int main() { size_t n = 10000000; std::vector<char> v(n, 'a'); for(size_t i = 0; i < n; ++i) { v.at(i) = 'b'; } } ``` runs in 0,00 - 0,01 seconds on my machine while: ``` module bench public fun main() { val n = 10000000 var v := vector(n, 'a') for(0, n - 1) fn(i) { v[i] := 'b' } } ``` takes 0,13-0,15 seconds. The same happens when we use `Bool/boolean` or `int/size_t` as data for the vector. — You are receiving this because you are subscribed to this thread. Reply to this email directly, [view it on GitHub][], or [unsubscribe][].![AEZNMJOD4PIAJBISARKQ7SDSZNDURA5CNFSM4VMIVSL2YY3PNVWWK3TUL52HS4DFWFCGS43DOVZXG2LPNZBW63LNMVXHJKTDN5WW2ZLOORPWSZGOAACDFXQ.gif][]

[view it on GitHub]: #131 (comment) [unsubscribe]: https://github.com/notifications/unsubscribe-auth/AEZNMJMIHX7TTHKEW44JRH3SZNDURANCNFSM4VMIVSLQ [AEZNMJOD4PIAJBISARKQ7SDSZNDURA5CNFSM4VMIVSL2YY3PNVWWK3TUL52HS4DFWFCGS43DOVZXG2LPNZBW63LNMVXHJKTDN5WW2ZLOORPWSZGOAACDFXQ.gif]: https://github.com/notifications/beacon/AEZNMJOD4PIAJBISARKQ7SDSZNDURA5CNFSM4VMIVSL2YY3PNVWWK3TUL52HS4DFWFCGS43DOVZXG2LPNZBW63LNMVXHJKTDN5WW2ZLOORPWSZGOAACDFXQ.gif

[anfelor]

@SchrodingerZhu Where is this specialization happening? I just checked kklib.h and the type signature for kk_ref_vector_assign is static inline kk_unit_t kk_ref_vector_assign(kk_ref_t r, kk_integer_t idx, kk_box_t value, kk_context_t* ctx). So while the index is specialized the value we store in the vector isn't.