Почему цикл поиска целочисленных массивов в C++ медленнее, чем в Java?
У меня одна и та же программа, написанная как на C++, так и на Java. Для C++ я использую VS 2019, а для Java - Eclipse 2019-03.
Вот программа в C++.
#define InputSize 500000
int FindDuplicate::FindDuplicateNaive(int* input, int size)
{
int j;
for (int i = 0; i < size-1; i++)
{
for ( j= i+1; j < size; j++)
{
if (input[i] == input[j])
return input[i];
}
}
return -1;
}
int* FindDuplicate::CreateTestCase(int size)
{
int* output = new int[size];
int i;
for ( i= 0; i < size-1; i++)
{
output[i] = i + 1;
}
output[i] = i;
return output;
}
int main()
{
int* input= FindDuplicate::CreateTestCase(InputSize);
auto start = std::chrono::system_clock::now();//clock start
int output = FindDuplicate::FindDuplicateNaive(input, InputSize);
auto end = std::chrono::system_clock::now();//clock end
cout<<"Output is: "<<output<<endl;
std::chrono::duration<double> elapsed_seconds = end - start;
cout<< "elapsed time: " << elapsed_seconds.count() << "s\n";
}
Вот программа на Java...
public class FindDuplicate {
public static int FindDuplicateNaive(int[] input) {
for (int i = 0; i < input.length - 1; i++) {
for (int j = i + 1; j < input.length; j++) {
if (input[i] == input[j])
return input[i];
}
}
return -1;
}
public static int[] CreateTestCase(int n) {
// 1, 2, 3, 4, 5, 1 = n = 6
int[] output = new int[n];
int i;
for (i = 0; i < n - 1; i++) {
output[i] = i + 1;
}
output[i] = i;
return output;
}
public static void main(String[] args)
{
//Here also args[0] is 5,00,000
int number = Integer.parseInt(args[0]);
int[] input = CreateTestCase(number);
long start = System.currentTimeMillis();
int output = FindDuplicateNaive(input);
long end = System.currentTimeMillis();
System.out.println("Total time taken is: " + (end - start) / 1000.0 + " secs");
System.out.println(output);
}
Вы будете потрясены, узнав, что время, затраченное одной и той же программой, на один и тот же ввод и в C++, и в Java.
В Java:
Время в пути: 41,876 сек.
499999
В CPP:
После включения оптимизации и в режиме релиза,
Выход: 499999
прошедшее время: 64.0293с
Любая мысль об этом, в чем может быть причина? Почему Java занимает 41,876 секунды, а CPP - 64,0293 секунды?
Ответы
Ответ 1
Поскольку векторизация не может быть легко осуществлена, большую часть времени проводят в циклическом управлении.
Благодаря использованию #pragma GCC unroll N во внутреннем цикле, который помогает исследовать, развертывание цикла обеспечивает объяснение результатов OP.
Я получаю эти средние результаты (консоль исключена из сроков):
gcc 8.3, -03, unroll 64 1.63s
gcc 8.3, -03, unroll 32 1.66s
gcc 8.3, -03, unroll 16 1.71s
gcc 8.3, -03, unroll 8 1.81s
gcc 8.3, -03, unroll 4 1.97s
gcc 8.3, -03, unroll 2 2.33s
gcc 8.3, -03, no unroll 3.06s
openjdk 10.0.2 1.93s
редактировать: эти тесты были запущены с InputSize = 100'000, как в исходном вопросе (впоследствии было изменено на 500'000)
Ответ 2
Это не полный ответ, я не могу объяснить, почему на самом деле он работает быстрее в Java, чем C++; но я могу объяснить пару вещей, которые сдерживают производительность вашей версии C++. Пожалуйста, не выбирайте это как правильный ответ, если у кого-то есть реальное объяснение общей разницы в производительности.
Этот ответ был обсужден на мета и согласился, что оставить его как частичный ответ временно является лучшим вариантом.
Первое и самое важное, как уже упоминалось в комментариях, Java-код уже оптимизирован при его тестировании, в то время как в C++ вы должны указать уровень оптимизации в качестве аргумента командной строки (формировать визуальную студию и компилировать как выпуск), и пока это имеет большое значение, в моих тестах Java все еще на вершине (все результаты снизу).
Но я хочу указать на серьезный недостаток в вашем тесте, который может показаться незначительным в данном конкретном случае, поскольку он не имеет большого значения, когда вы смотрите на цифры, но все же важен: операции ввода-вывода добавляют заметные задержки. Для точного сравнения времени выполнения вы должны исключить операции ввода-вывода из вашего таймера на обоих языках. Хотя в этом случае это не имеет большого значения, если один язык выполняет и функцию, и вывод во время работы таймера, а другой выполняет только функцию, что делает весь ваш тест смещенным и бессмысленным.
Чтобы сделать его более эквивалентным версии Java, измените основной C++ на
int main()
{
int* input = FindDuplicate::CreateTestCase(InputSize);
int result;
auto start = std::chrono::system_clock::now(); //clock start
result = FindDuplicate::FindDuplicateNaive(input, InputSize);
auto end = std::chrono::system_clock::now(); //clock end
std::chrono::duration<double> elapsed_seconds = end - start;
cout << "Output is: " << result << endl;
cout << "elapsed time: " << elapsed_seconds.count() << "s\n";
}
Обратите внимание, что по умолчанию консольный ввод/вывод C++ (iostream, cin/cout) даже медленнее, чем мог бы быть, потому что синхронизация с консольным вводом/выводом C (stdio, scanf/printf) позволяет программе не выполнять странные действия. вещи, если используются как cout, так и printf. Здесь вы можете прочитать о производительности cout при выключенной синхронизации. Мало того, что вы использовали ввод-вывод внутри ограничений таймера, вы даже использовали его в режиме наихудшей производительности.
Вот мои результаты, которые, хотя и дают Java преимущество, показывают, сколько различий могут иметь определенные опции компиляции и манипуляции ввода-вывода в C++ (для одного цикла разница в 0,03 с в среднем при отключении синхронизации больше, чем она выглядит). Все значения в секундах являются средними для 10 тестов.
1. Java print in timer 1.52s
2. Java 1.36s
3. C++ debug, cout in timer 11.78s
4. C++ debug 11.73s
5. C++ release, cout in timer 3.32s
6. C++ release cout syncronization off 3.29s
7. C++ release 3.26s
Я хочу, чтобы вы поняли, что из всех этих тестов единственные, из которых имеет смысл сравнение, это 1 с 6 и 2 с 7. Все остальные (3, 4, 5) будут сравниваться независимо от того, сколько раз вы повторяете тест.
Ответ 3
Основным отличием является развертывание циклы.
Java очень умно развернула внутренний цикл, в то время как GCC/clang/MSVC/ICC не развернули его (это пропущенная оптимизация этих компиляторов).
Если вы вручную развернете цикл, вы можете ускорить его, чтобы иметь скорость, аналогичную java-версии, примерно так:
for ( j= i+1; j < size-3; j+=4)
{
if (input[i] == input[j])
return input[i];
if (input[i] == input[j+1])
return input[i];
if (input[i] == input[j+2])
return input[i];
if (input[i] == input[j+3])
return input[i];
}
for (; j < size; j++)
{
if (input[i] == input[j])
return input[i];
}
Для доказательства, вот внутренний цикл версии Java (8x развернуть):
0x00007f13a5113f60: mov 0x10(%rsi,%rdx,4),%ebx ;*iaload
; - FindDuplicate::[email protected] (line 6)
0x00007f13a5113f64: cmp %ebx,%ecx
0x00007f13a5113f66: je 0x7f13a5113fcb ;*if_icmpne
; - FindDuplicate::[email protected] (line 6)
0x00007f13a5113f68: movsxd %edx,%rdi
0x00007f13a5113f6b: mov 0x14(%rsi,%rdi,4),%ebx ;*iaload
; - FindDuplicate::[email protected] (line 6)
0x00007f13a5113f6f: cmp %ebx,%ecx
0x00007f13a5113f71: je 0x7f13a5113fc9 ;*if_icmpne
; - FindDuplicate::[email protected] (line 6)
0x00007f13a5113f73: mov 0x18(%rsi,%rdi,4),%ebx ;*iaload
; - FindDuplicate::[email protected] (line 6)
0x00007f13a5113f77: cmp %ebx,%ecx
0x00007f13a5113f79: je 0x7f13a5113fed ;*if_icmpne
; - FindDuplicate::[email protected] (line 6)
0x00007f13a5113f7b: mov 0x1c(%rsi,%rdi,4),%ebx ;*iaload
; - FindDuplicate::[email protected] (line 6)
0x00007f13a5113f7f: cmp %ebx,%ecx
0x00007f13a5113f81: je 0x7f13a5113ff2 ;*if_icmpne
; - FindDuplicate::[email protected] (line 6)
0x00007f13a5113f83: mov 0x20(%rsi,%rdi,4),%ebx ;*iaload
; - FindDuplicate::[email protected] (line 6)
0x00007f13a5113f87: cmp %ebx,%ecx
0x00007f13a5113f89: je 0x7f13a5113ff7 ;*if_icmpne
; - FindDuplicate::[email protected] (line 6)
0x00007f13a5113f8b: mov 0x24(%rsi,%rdi,4),%ebx ;*iaload
; - FindDuplicate::[email protected] (line 6)
0x00007f13a5113f8f: cmp %ebx,%ecx
0x00007f13a5113f91: je 0x7f13a5113ffc ;*if_icmpne
; - FindDuplicate::[email protected] (line 6)
0x00007f13a5113f93: mov 0x28(%rsi,%rdi,4),%ebx ;*iaload
; - FindDuplicate::[email protected] (line 6)
0x00007f13a5113f97: cmp %ebx,%ecx
0x00007f13a5113f99: je 0x7f13a5114001 ;*if_icmpne
; - FindDuplicate::[email protected] (line 6)
0x00007f13a5113f9b: mov 0x2c(%rsi,%rdi,4),%ebx ;*iaload
; - FindDuplicate::[email protected] (line 6)
0x00007f13a5113f9f: cmp %ebx,%ecx
0x00007f13a5113fa1: je 0x7f13a5114006 ;*if_icmpne
; - FindDuplicate::[email protected] (line 6)
0x00007f13a5113fa3: add $0x8,%edx ;*iinc
; - FindDuplicate::[email protected] (line 5)
0x00007f13a5113fa6: cmp %r8d,%edx
0x00007f13a5113fa9: jl 0x7f13a5113f60 ;*if_icmpge
; - FindDuplicate::[email protected] (line 5)
