TimSort

when I am writing a comparator using lamba, java throws out this exception

        at java.util.concurrent.Executors$RunnableAdapter.call(Executors.java:511)
        at java.util.concurrent.FutureTask.run(FutureTask.java:266)
        at java.util.concurrent.ScheduledThreadPoolExecutor$ScheduledFutureTask.access$201(ScheduledThreadPoolExecutor.java:180)
        at java.util.concurrent.ScheduledThreadPoolExecutor$ScheduledFutureTask.run(ScheduledThreadPoolExecutor.java:293)
        at java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1149)
        at java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:624)
        at java.lang.Thread.run(Thread.java:748)
Caused by: java.lang.IllegalArgumentException: Comparison method violates its general contract!
        at java.util.TimSort.mergeLo(TimSort.java:777)
        at java.util.TimSort.mergeAt(TimSort.java:514)
        at java.util.TimSort.mergeCollapse(TimSort.java:441)
        at java.util.TimSort.sort(TimSort.java:245)
        at java.util.Arrays.sort(Arrays.java:1512)
        at java.util.ArrayList.sort(ArrayList.java:1464)
        at java.util.stream.SortedOps$RefSortingSink.end(SortedOps.java:392)
        at java.util.stream.Sink$ChainedReference.end(Sink.java:258)
        at java.util.stream.Sink$ChainedReference.end(Sink.java:258)
        at java.util.stream.AbstractPipeline.copyIntoWithCancel(AbstractPipeline.java:500)
        at java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:486)
        at java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:472)
        at java.util.stream.ReduceOps$ReduceOp.evaluateSequential(ReduceOps.java:708)
        at java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:234)
        at java.util.stream.ReferencePipeline.collect(ReferencePipeline.java:566)

seems like `TimSort` is having a safety check to ensure the Comparator contract, however, it’s not always working.

So this only throws out an issue when running enough times

    @Test
    public void test3() {
        List<Domain> domains = new ArrayList<>();
        for (int i = 0; i < 1_000; i++) {
//            domains.clear();
            domains.add(Domain.builder().val(0.1).name("1").build());
            domains.add(Domain.builder().val(0.5).name("2").build());
            domains.add(Domain.builder().val(1.2).name("3").build());
            domains.add(Domain.builder().val(2.1).name("4").build());
            Collections.shuffle(domains);
            log.info("{}th start sorting {}", i, domains);
            log.info("check sorted {}", domains.parallelStream().sorted((o1, o2) -> {
                        final int diff = (int) (o2.val - o1.val);
                        log.info("check {} - {} = {}", o1, o2, diff);
                        return diff;
                    }).collect(Collectors.toList())
            );
        }

    }
    @Test
    public void test4() {
        List<Domain> domains = new ArrayList<>();
        for (int i = 0; i < 1_000_000; i++) {
//            domains.clear();
            domains.add(Domain.builder().val(0.1).name("1").build());
            domains.add(Domain.builder().val(0.5).name("2").build());
            domains.add(Domain.builder().val(1.2).name("3").build());
            domains.add(Domain.builder().val(2.1).name("4").build());
            Collections.shuffle(domains);
//            log.info("{}th start sorting {}", i, domains);
            log.info("check sorted {}", domains.parallelStream().sorted((o1, o2) -> Double.compare(o2.val, o1.val)).collect(Collectors.toList()).size()
            );
        }

    }
}

@Data
@Builder
class Domain {
    double val;
    String name;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s