标题是参考为什么处理排序数组比未排序数组更快？
这也是分支预测效果吗？注意:这里对排序数组的处理速度较慢 !!
请考虑以下代码:
private static final int LIST_LENGTH = 1000 * 1000;
private static final long SLOW_ITERATION_MILLIS = 1000L * 10L;
@Test
public void testBinarySearch() {
Random r = new Random(0);
List<Double> list = new ArrayList<>(LIST_LENGTH);
for (int i = 0; i < LIST_LENGTH; i++) {
list.add(r.nextDouble());
}
//Collections.sort(list);
// remove possible artifacts due to the sorting call
// and rebuild the list from scratch:
list = new ArrayList<>(list);
int nIterations = 0;
long startTime = System.currentTimeMillis(); …我前几天和朋友争论过这两个片段.哪个更快,为什么？
value = 5;
if (condition) {
value = 6;
}
和:
if (condition) {
value = 6;
} else {
value = 5;
}
如果value是矩阵怎么办？
注意:我知道value = condition ? 6 : 5;存在并且我希望它更快,但它不是一个选项.
编辑(工作人员要求,因为问题暂时搁置):
在下面的代码中，我创建了两个具有相同值的列表：一个列表未排序 (s_not)，另一个列表已排序 (s_yes)。这些值由 randint() 创建。我为每个列表运行一些循环并计时。
import random
import time
for x in range(1,9):
r = 10**x # do different val for the bound in randint()
m = int(r/2)
print("For rand", r)
# s_not is non sorted list
s_not = [random.randint(1,r) for i in range(10**7)]
# s_yes is sorted
s_yes = sorted(s_not)
# do some loop over the sorted list
start = time.time()
for i in s_yes:
if i > m:
_ = 1
else:
_ = 1
end = time.time() …为什么这个程序打印"分叉!"4次？
#include <stdio.h>
#include <unistd.h>
int main(void) {
fork() && (fork() || fork());
printf("forked!\n");
return 0;
}
为了说清楚,我不打算在这里使用任何类型的便携性,所以任何将我绑定到某个盒子的解决方案都可以.
基本上,我有一个if语句将99%的时间评估为true,并且我试图剔除每个性能的最后一个时钟,我可以发出某种编译器命令(使用GCC 4.1.2和x86 ISA,如果告诉分支预测器它应该缓存该分支吗？
在阅读了这篇文章后(在StackOverflow上回答)(在优化部分),我想知道为什么条件移动不容易受到分支预测失败的影响.我在一篇关于cond移动的文章中找到了(PDF由AMD提供).在那里,他们声称cond的性能优势.移动.但为什么会这样呢？我没有看到它.在评估ASM指令的时刻,前面的CMP指令的结果尚未知晓.
谢谢.
optimization performance assembly cpu-architecture branch-prediction
我偶然发现了什么.起初我认为这可能是分支错误预测的情况,就像在这种情况下一样,但我无法解释为什么分支错误预测应该导致这种现象.
我在Java中实现了两个版本的Bubble Sort并进行了一些性能测试:
import java.util.Random;
public class BubbleSortAnnomaly {
public static void main(String... args) {
final int ARRAY_SIZE = Integer.parseInt(args[0]);
final int LIMIT = Integer.parseInt(args[1]);
final int RUNS = Integer.parseInt(args[2]);
int[] a = new int[ARRAY_SIZE];
int[] b = new int[ARRAY_SIZE];
Random r = new Random();
for (int run = 0; RUNS > run; ++run) {
for (int i = 0; i < ARRAY_SIZE; i++) {
a[i] = r.nextInt(LIMIT);
b[i] = a[i];
}
System.out.print("Sorting with sortA: ");
long start …在这段代码中:
if (value >= x && value <= y) {
什么时候value >= x和value <= y没有特定模式的情况一样真假,使用&运算符会比使用更快&&吗？
具体来说,我正在考虑如何&&懒惰地评估右侧表达式(即,仅当LHS为真),这意味着条件,而&在此上下文中的Java 保证严格评估两个(布尔)子表达式.值结果是相同的两种方式.
不过,虽然一个>=或<=运营商将使用一个简单的比较指令时,&&必须包括一个分支,该分支是易受分支预测失败 -按本非常著名的问题:为什么快处理有序数组不是一个排序的数组？
因此,强制表达式没有惰性组件肯定会更具确定性,并且不容易受到预测失败的影响.对？
笔记:
if(value >= x && verySlowFunction()).我专注于"足够简单"的RHS表达.if声明).我无法向自己证明这是无关紧要的,而且替代配方可能是更好的例子,比如boolean b = value >= x && value <= y;更新 只是为了解释为什么我感兴趣:我一直在盯着马丁汤普森在他的机械同情博客上撰写的系统,在他来到并谈到 Aeron之后.其中一个关键信息是我们的硬件中包含了所有这些神奇的东西,我们的软件开发人员不幸地无法利用它.别担心,我不打算在我的所有代码上使用///// :-) ...但是这个网站上有很多关于通过删除分支来改进分支预测的问题,并且它发生了对我来说,条件布尔运算符是测试条件的核心.
当然,@ StephenC提出了一个奇妙的观点,即将代码弯曲成奇怪的形状可以使JIT更容易发现常见的优化 - 如果不是现在,那么将来也是如此.并且上面提到的非常着名的问题是特殊的,因为它推动预测复杂性远远超出实际优化. …
java performance processing-efficiency microbenchmark branch-prediction
在C++中,？:运算符比if()... else语句更快？它们在编译代码中有什么区别吗？
我一直试图通过计算一个使用以下代码对数组元素进行扩展和求和的例程来了解在L1缓存与内存中使用数组的影响(我知道我应该将结果缩放为' a'在最后;关键是在循环中同时进行乘法和加法 - 到目前为止,编译器还没有想出要将'a'分解出来):
double sum(double a,double* X,int size)
{
double total = 0.0;
for(int i = 0; i < size; ++i)
{
total += a*X[i];
}
return total;
}
#define KB 1024
int main()
{
//Approximately half the L1 cache size of my machine
int operand_size = (32*KB)/(sizeof(double)*2);
printf("Operand size: %d\n", operand_size);
double* X = new double[operand_size];
fill(X,operand_size);
double seconds = timer();
double result;
int n_iterations = 100000;
for(int i = 0; i < n_iterations; ++i)
{
result = …