为什么整数数组搜索循环在C++比Java慢?

2022-09-01 15:48:38

我有用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中的相同输入所花费的时间。

在爪哇:

所需时间为:499999 41.876秒

在CPP中:

启用优化并处于发布模式后,

输出为:499999
用时间:64.0293s

对此有什么想法,可能是什么原因?为什么Java需要41.876秒,而CPP需要64.0293秒?


答案 1

由于矢量化不容易发生,因此大部分时间都花在了循环控制上。
由于使用了内部环路,这有助于调查,环路展开提供了OP结果的解释。#pragma GCC unroll N

我获得这些平均结果(控制台从计时中排除):

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

编辑:这些测试在输入大小 = 100'000 的情况下运行,如原始问题中所示(之后更改为 500'000)


答案 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::FindDuplicateNaive@25 (line 6)

  0x00007f13a5113f64: cmp     %ebx,%ecx
  0x00007f13a5113f66: je      0x7f13a5113fcb    ;*if_icmpne
                                                ; - FindDuplicate::FindDuplicateNaive@26 (line 6)

  0x00007f13a5113f68: movsxd  %edx,%rdi
  0x00007f13a5113f6b: mov     0x14(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::FindDuplicateNaive@25 (line 6)

  0x00007f13a5113f6f: cmp     %ebx,%ecx
  0x00007f13a5113f71: je      0x7f13a5113fc9    ;*if_icmpne
                                                ; - FindDuplicate::FindDuplicateNaive@26 (line 6)

  0x00007f13a5113f73: mov     0x18(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::FindDuplicateNaive@25 (line 6)

  0x00007f13a5113f77: cmp     %ebx,%ecx
  0x00007f13a5113f79: je      0x7f13a5113fed    ;*if_icmpne
                                                ; - FindDuplicate::FindDuplicateNaive@26 (line 6)

  0x00007f13a5113f7b: mov     0x1c(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::FindDuplicateNaive@25 (line 6)

  0x00007f13a5113f7f: cmp     %ebx,%ecx
  0x00007f13a5113f81: je      0x7f13a5113ff2    ;*if_icmpne
                                                ; - FindDuplicate::FindDuplicateNaive@26 (line 6)

  0x00007f13a5113f83: mov     0x20(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::FindDuplicateNaive@25 (line 6)

  0x00007f13a5113f87: cmp     %ebx,%ecx
  0x00007f13a5113f89: je      0x7f13a5113ff7    ;*if_icmpne
                                                ; - FindDuplicate::FindDuplicateNaive@26 (line 6)

  0x00007f13a5113f8b: mov     0x24(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::FindDuplicateNaive@25 (line 6)

  0x00007f13a5113f8f: cmp     %ebx,%ecx
  0x00007f13a5113f91: je      0x7f13a5113ffc    ;*if_icmpne
                                                ; - FindDuplicate::FindDuplicateNaive@26 (line 6)

  0x00007f13a5113f93: mov     0x28(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::FindDuplicateNaive@25 (line 6)

  0x00007f13a5113f97: cmp     %ebx,%ecx
  0x00007f13a5113f99: je      0x7f13a5114001    ;*if_icmpne
                                                ; - FindDuplicate::FindDuplicateNaive@26 (line 6)

  0x00007f13a5113f9b: mov     0x2c(%rsi,%rdi,4),%ebx  ;*iaload
                                                ; - FindDuplicate::FindDuplicateNaive@25 (line 6)

  0x00007f13a5113f9f: cmp     %ebx,%ecx
  0x00007f13a5113fa1: je      0x7f13a5114006    ;*if_icmpne
                                                ; - FindDuplicate::FindDuplicateNaive@26 (line 6)

  0x00007f13a5113fa3: add     $0x8,%edx         ;*iinc
                                                ; - FindDuplicate::FindDuplicateNaive@33 (line 5)

  0x00007f13a5113fa6: cmp     %r8d,%edx
  0x00007f13a5113fa9: jl      0x7f13a5113f60    ;*if_icmpge
                                                ; - FindDuplicate::FindDuplicateNaive@17 (line 5)

推荐