Дополнительный условный оператор делает программу быстрее
После прочтения Почему обрабатывать отсортированный массив быстрее, чем несортированный?, Я добавил еще один тест в основной цикл. Кажется, что этот дополнительный тест делает программу быстрее.
int main()
{
// Generate data
const unsigned arraySize = 32768;
int data[arraySize];
for (unsigned c = 0; c < arraySize; ++c)
data[c] = std::rand() % 256;
//Don't sort the array
//std::sort(data, data + arraySize);
// Test
clock_t start = clock();
long long sum = 0;
for (unsigned i = 0; i < 100000; ++i)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
//With this additional test, execution becomes faster
if (data[c] < 128)
sum += data[c];
}
}
double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << std::endl;
std::cout << "sum = " << sum << std::endl;
}
Я получаю около 4,2 с с дополнительным тестом и 18 с без дополнительного теста.
Разве дополнительный тест не должен замедлять программу, а не ускорять ее?
Решение
Из-за этого конкретный дополнительный тест, эквивалентный код этого:
for (unsigned i = 0; i < 100000; ++i)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
if (data[c] >= 128)
sum += data[c];
//With this additional test, execution becomes faster
if (data[c] < 128)
sum += data[c];
}
}
становится так:
for (unsigned i = 0; i < 100000; ++i)
{
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
sum += data[c];//because exactly one condition is guaranteed to be
//true in each iteration (in your code)!
//the equivalent is as if there is no condition at all!
}
}
вот почему это становится быстрее.
Это из-за необычный дополнительный тест и идентичный тело, компилятор может оптимизировать код, удаляя if условия. Когда ты один ifто компилятор не может этого сделать.
Попробуйте написать это:
sum -= data[c]; //the body is not identical anymore!
в одном из if состояние. Я уверен, что компилятор не быть в состоянии оптимизировать код. Теперь он должен генерировать более медленный машинный код.
Обратите внимание, что внешний цикл может быть полностью опущен, хотя он не сильно зависит от дополнительного теста:
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
sum += 100000 * data[c];
}
или это:
// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
sum += data[c];
}
sum = 100000 * sum; //multiple once!
Другие решения
Других решений пока нет …