[llvm-bugs] [Bug 30404] New: bubble sort flakiness

[via llvm-bugs]

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

            Bug ID: 30404
           Summary: bubble sort flakiness
           Product: Test Suite
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: QMTest
          Assignee: unassignedbugs at nondot.org
          Reporter: evstupac at gmail.com
                CC: llvm-bugs at lists.llvm.org
    Classification: Unclassified

The test performance differs 2 times when test:
SingleSource/Benchmarks/Stanford/Bubblesort.c is compiled with

-O2 -march=core-avx2 -mllvm -unroll-runtime-epilog=true (bad case)
and
-O2 -march=core-avx2 -mllvm -unroll-runtime-epilog=false (good case)

Attached assemblies from current compiler:
bs_epil.s
bs_prol.s
and assembly from hottest loop:
bs_epil_loop.s
bs_prol_loop.s

The code looks very similar and with some assembly modifications I was able to
make hottest loops identical keeping the same performance gap (2 times).

Deeper analysis uncovered that hottest loop (99% of execution time) mostly
consist of memory and code stalls:

while ( i<top ) {    
    if ( sortlist[i] > sortlist[i+1] ) {
        j = sortlist[i];
        sortlist[i] = sortlist[i+1];
        sortlist[i+1] = j;
    }
    i=i+1;
}

sortlist is randomly filled array. That way comparison in the loop is
completely unpredictable. The same we could say about stores. The distance
between branches is very short (the same about memory accesses).
This makes the test very sensitive to code shifts and memory accesses order and
distance.

https://reviews.llvm.org/D24593
Contains a patch to the test that makes it not code/memory sensitive (and
therefore more stable) without significant performance difference (from good
case).

-- 
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/20160915/75d9c6f1/attachment.html>