List.groupBy performance

[eirikm]

List.groupBy is performing really bad compared to the java.util-counterpart.

I've made a testcase to show the magnitude in difference of performance:

package integration.eventstore;

import javaslang.Function1;
import javaslang.collection.HashMap;
import javaslang.collection.List;
import javaslang.collection.Map;
import javaslang.collection.Stream;
import org.junit.Assert;
import org.junit.Test;

import java.util.stream.Collectors;

public class Spike {

    @Test
    public void compare() {
        List<Integer> ns = List.of(100, 1_000, 10_000, 100_000);

        ns.forEach(n -> {
            Stream<Integer> range = Stream.range(1, 10);
            List<Integer> javaslangInts = Stream.repeat(range)
                    .flatMap(is -> is)
                    .take(n)
                    .toList();
            java.util.List<Integer> javaInts = javaslangInts.toJavaList();

            System.out.println("Running group by on " + n + " elements");
            long startJava = System.currentTimeMillis();
            java.util.Map<Integer, java.util.List<Integer>> groupByJava = javaInts.stream().collect(Collectors.groupingBy(i -> i));
            long endJava = System.currentTimeMillis();
            long totalJava = endJava - startJava;
            System.out.println("Total time: ");
            System.out.println("  Java stream: " + totalJava + " ms");

            long startWrapper = System.currentTimeMillis();
            Map<Integer, List<Integer>> groupByWrapper = groupByWrapper(javaslangInts, i -> i);
            long endWrapper = System.currentTimeMillis();
            long totalWrapper = endWrapper - startWrapper;
            System.out.println("  Wrapper: " + totalWrapper + " ms");

            long startJavaslang = System.currentTimeMillis();
            Map<Integer, List<Integer>> groupByJavaslang = javaslangInts.groupBy(i -> i);
            long endJavaslang = System.currentTimeMillis();
            long totalJavaslang = endJavaslang - startJavaslang;
            System.out.println("  Javaslang: " + totalJavaslang + " ms");

            Assert.assertEquals(translateGroupByMap(groupByJava), groupByJavaslang);
            Assert.assertEquals(groupByWrapper, groupByJavaslang);
        });
    }

    public <K, T> Map<K, javaslang.collection.List<T>> groupByWrapper(List<T> list, Function1<T, K> groupByFunc) {
        return translateGroupByMap(list.toJavaStream().collect(Collectors.groupingBy(groupByFunc)));
    }

    public <K, T> Map<K, List<T>> translateGroupByMap(java.util.Map<K, java.util.List<T>> input) {
        return HashMap.ofAll(input).mapValues(l -> List.ofAll(l));
    }
}

A typical result of running this would be:

Running group by on 100 elements
Total time:
Java stream: 6 ms
Wrapper: 21 ms
Javaslang: 7 ms
Running group by on 1000 elements
Total time:
Java stream: 1 ms
Wrapper: 2 ms
Javaslang: 18 ms
Running group by on 10000 elements
Total time:
Java stream: 1 ms
Wrapper: 4 ms
Javaslang: 415 ms
Running group by on 100000 elements
Total time:
Java stream: 7 ms
Wrapper: 21 ms
Javaslang: 28752 ms

kind regards
Eirik Meland

[danieldietrich]

Hi Eirik,

thank you for your investigation. Indeed, Javaslang takes at least quadratic time to group the elements.
We need to understand how Java's Stream is implemented - it seems to me that it is lazy, even the Map that is returned. I will have a look.

Using a wrapper seems to be a viable option!

Greets,
Daniel

[l0rinc]

The problem is mostly that append was used for Stream, instead of prepend and reverse.
Will provide a PR shortly with something like

@Override
default <C> Map<C, Iterator<T>> groupBy(Function<? super T, ? extends C> classifier) {
    Objects.requireNonNull(classifier, "classifier is null");
    if (isEmpty()) {
        return HashMap.empty();
    } else {
        final java.util.Map<C, Collection<T>> results = new java.util.HashMap<>();
        for (T value : this) {
            final C key = classifier.apply(value);
            Collection<T> values = results.get(key);
            if (values == null) {
                values = new ArrayList<T>();
                results.put(key, values);
            }
            values.add(value);
        }
        return HashMap.ofAll(results).map((c, ts) -> Tuple.of(c, List.ofAll(ts).iterator()));
    }
}

which is only <2x slower than the Java impl

[danieldietrich]

Very nice!

[l0rinc]

@eirikm, @danieldietrich, please review :)

[povder]

Hi @danieldietrich! Any reasons why fix for this is not scheduled to be included in a bugfix release?

[danieldietrich]

@povder no - just overseen it. Thanks for the hint!