Array.permutations() performance

[ruslansennov]

@jest reported performance degradation of Array.permutations() in vavr:0.9.0. It seems the problem commit is 9e37950e2fa3113cba6fbcd03feebd1fc86ca1e1

Here is (slightly modified for testing) old code:

public static <T> Array<Array<T>> permOld(Array<T> array) {
    if (array.isEmpty()) {
        return Array.empty();
    } else {
        final Array<T> tail = array.tail();
        if (tail.isEmpty()) {
            return Array.of(array);
        } else {
            final Array<Array<T>> zero = Array.empty();
            return array.distinct().foldLeft(zero, (xs, x) -> {
                final Function<Array<T>, Array<T>> prepend = l -> l.prepend(x);
                return xs.appendAll(array.remove(x).permutations().map(prepend));
            });
        }
    }
}

And here is new code:

public static <T> Array<Array<T>> permNew(Array<T> array) {
    if (array.isEmpty()) {
        return Array.empty();
    } else {
        Array<Array<T>> results = Array.empty();
        for (T t : array.distinct()) {
            for (Array<T> ts : array.remove(t).permutations()) {
                results = results.append(Array.of(t).appendAll(ts));
            }
        }
        return results;
    }
}

[ruslansennov]

initial PR: #1325
reverted (not completely) by: #1373

[danieldietrich]

@ruslansennov great thanks!

It came to my mind if something else might also influence the performance. E.g. did the implementation of the following methods change?

• Array.distinct()
• Array.appendAll(Iterable)
• Array.append(T)
• Array.remove(T)

???

Btw - the following part

        final Array<T> tail = array.tail();
        if (tail.isEmpty()) {
            return Array.of(array);
        } else {

could be optimized by

        if (array.size() == 1) {
            return Array.of(array);
        } else {

[ruslansennov]

did the implementation of the following methods change?

I'll check all methods

Btw - the following part <...> could be optimized by <...>

sure :)

[jest]

I thought about implementing permutations using Steinhaus–Johnson–Trotter algoritm (https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm). It is very efficient, as every permutation differs from the previous one by a single swap of two adjacent elements.

Guava has a very nice implementation, in a form of generic Iterator depending on a single swap operation (https://github.com/google/guava/blob/master/guava/src/com/google/common/collect/Collections2.java#L652).

[danieldietrich]

@jest That sounds really nice!!

@ruslansennov However, we should double-check that the basic Array operations do not perform worse than in 2.0.6

[jest]

Looking at my benchmark from the Gitter:

public void bench_dummy_no_permutation(Blackhole bh) {
    Array<Array<Integer>> perms = Iterator.range(0, PERM_NUM).map(i -> {
        Integer elem = arr.get(0);
        return arr.remove(0).append(elem);
    }).toArray();

    bh.consume(perms);
}

and the results:

VavrPermutationTest.bench_dummy_no_permutation  avgt   20   1.894 ± 0.018  ms/op
...
VavrPermutationTest.bench_dummy_no_permutation  avgt   20    2.467 ± 0.018  ms/op

there seems to be 30% increase of time for some combination of add/remove/map operations.

[danieldietrich]

@jest interesting, thanks for the benchmarks. We need to take a look why it changed. We recently added some a priori checks in order to

• return the same instance if possible
• run optimized operations in the empty case

Maybe these checks are responsible for the performance changes. However, it is necessary to do so in order to ensure that essential constraints are valid. The Java converters / views rely on these constraints in order to provide java.util.List impls that behave as expected.

But there is another use-case for separating behavior & structure: The 1.0 version of Vavr will internally be completely refactored. My goal is to compensate some of the down-sides of Java's type system that currently force us to repeat slightly changing method declarations.

We reach this goal by a new kind of code-generator. I call it "inline code generator". Files contains generated regions (as opposed to protected regions), that are filled automatically with redundant code. Maybe we can benefit here also from selecting appropriate algorithms.

[jest]

Thanks. That "inline code generator" would be great to open the decision about performance compromises (e.g. memory-time) to power users that may need them.