[llvm-bugs] [Bug 30628] New: poor unrolling of range-based for loops

[via llvm-bugs]

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

            Bug ID: 30628
           Summary: poor unrolling of range-based for loops
           Product: clang
           Version: 3.9
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: enhancement
          Priority: P
         Component: C++
          Assignee: unassignedclangbugs at nondot.org
          Reporter: matthias.thul at gmail.com
                CC: dgregor at apple.com, llvm-bugs at lists.llvm.org
    Classification: Unclassified

This is not a bug but a suggestion for an improvement. Consider the following
range based for loop:

==========

#include <algorithm>
#include <array>
#include <functional>
#include <random>

const size_t N = 100000;
const unsigned value = 31415926;

template<size_t N>
std::array<unsigned, N> generateData() {
    std::mt19937 randomEngine(0);
    std::array<unsigned, N> data;
    std::generate(data.begin(), data.end(), randomEngine);
    return data;
}

void testRange() {
    auto const data = generateData<N>();
    bool result = true;
    for (unsigned entry : data) {
        if (entry == value) {
            result = false;
            break;
        }
    }
    assert(result);
}

==========

I compiled it with "-std=c++14 -O3" using Clang 3.9. I was expecting the
range-based for loop to be unrolled but this didn't happen. Using "#pragma
unroll 8" before the loop didn't have any effect either.

I was expecting the compiler to essentially generate the same code that it does
for the below two loops, both of which are unrolled automatically 8 times
without the pragma directive.

==========

void testManual() {
    auto data = generateData<N>();
    bool result = true;
    for (size_t i = 0; i < N; i++) {
        if (data[i] == value) {
            result = false;
            break;
        }
    }
    assert(result);
}

void testIterator() {
    auto data = generateData<N>();
    bool result = true;
    for (auto itData = data.begin(); itData != data.end(); ++itData) {
        if (*itData == value) {
            result = false;
            break;
        }
    }
    assert(result);
}

==========

This has an severe effect on performance as you can see from the below
benchmark:

Benchmark                  Time           CPU Iterations
--------------------------------------------------------
benchmarkManual        33175 ns      33135 ns      21015
benchmarkRange         58488 ns      58370 ns      10771
benchmarkIterator      27077 ns      27045 ns      29426

The benchmark was generated using the Google benchmark library and only the
loops but not the array generation were benchmarked.

-- 
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/20161006/ec276a48/attachment-0001.html>