為什麼C++中的整數數組搜索循環比Java慢?




performance visual-c++ (2)

主要區別是循環展開。

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::FindDuplicateN[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)

我有用C ++和Java編寫的相同程序。 對於C ++,我使用的是VS 2019和使用Eclipse 2019-03的Java。

這是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.0293s

對此有任何想法,可能是什麼原因? 為什麼Java佔用41.876秒而CPP佔用64.0293秒?


由於矢量化不容易進行,因此大部分時間都花在循環控制上。
由於使用 #pragma GCC unroll N 在內循環上 #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)







visual-c++