[llvm-bugs] [Bug 35502] New: set_union: clang makes code significantly slower by incorrect optimizations.

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=35502

            Bug ID: 35502
           Summary: set_union: clang makes code significantly slower by
                    incorrect optimizations.
           Product: clang
           Version: 5.0
          Hardware: PC
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: -New Bugs
          Assignee: unassignedclangbugs at nondot.org
          Reporter: denis.yaroshevskij at gmail.com
                CC: llvm-bugs at lists.llvm.org

Hi!

I've been doing a small research project, where I needed a version of
set_union, that would be biased to the left range.

Here are two implementations, V6 is the one I wanted to write, V7 is the one I
had to right, in order to stop bad codegen.

https://godbolt.org/g/axVMWr

How it suppose to work (v6):
If I have elements from the second range, I loop between checkSecond and start.
As soon as I get more elements from the left I start falling through the
unrolled loop.

checkSecond is responsible for the whole right range, so it's crucial not to
slow it down. However, this is not what clang does.

If I move my first unrolled iteration to the top of checkSecond (see V7) clang
stops trying to optimize my unrolled loop at the expense of checkSecond, and
the trick works.

The first version is 2-2,5 times slower for some cases and never faster.

Benchmark:
2000 uniformly distributed 64 bit integers.
They are distributed in two vectors.

>From left to right - less integers in the left vector, more integers in the
right vector. (On the very left: - 2000/0, middle - 1000/1000, the very right -
0/2000).

Results: https://plot.ly/~dyaroshev/47/

Compiler: Apple LLVM version 9.0.0 (clang-900.0.38) (I don't know what is the
real clang version this is). At the version 5 assembly is still wrong - see
godbolt.

Compiler options: clang++ --std=c++14 -O3 -Werror -Wall

Benchmmark code:
https://github.com/DenisYaroshevskiy/srt-library/blob/master/other_benchmarks/set_unions_bench.cc

Related bug: https://bugs.llvm.org/show_bug.cgi?id=35499

Best,
Denis.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20171201/97ebca5f/attachment.html>