标签: optimization

这是一段看似非常特殊的C++代码.出于某种奇怪的原因,奇迹般地对数据进行排序使得代码几乎快了六倍.

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster.
    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) …

以下是构建链接的两种方法,其唯一目的是运行JavaScript代码.哪个更好,在功能,页面加载速度,验证目的等方面？

function myJsFunc() {
    alert("myJsFunc");
}

<a href="#" onclick="myJsFunc();">Run JavaScript Code</a>

要么

function myJsFunc() {
    alert("myJsFunc");
}

 <a href="javascript:void(0)" onclick="myJsFunc();">Run JavaScript Code</a>

优化SQLite很棘手.C应用程序的批量插入性能可以从每秒85次插入到每秒超过96,000次插入!

背景:我们使用SQLite作为桌面应用程序的一部分.我们有大量的配置数据存储在XML文件中,这些数据被解析并加载到SQLite数据库中,以便在初始化应用程序时进行进一步处理.SQLite非常适合这种情况,因为它速度快,不需要专门配置,数据库作为单个文件存储在磁盘上.

理由: 最初我对我所看到的表现感到失望.事实证明,SQLite的性能可能会有很大差异(对于批量插入和选择),具体取决于数据库的配置方式以及如何使用API​​.弄清楚所有选项和技术是什么并不是一件小事,所以我认为创建这个社区wiki条目以与Stack Overflow读者分享结果是谨慎的,以便为其他人节省相同调查的麻烦.

实验:我不是简单地谈论一般意义上的性能提示(即"使用事务!"),而是认为最好编写一些C代码并实际测量各种选项的影响.我们将从一些简单的数据开始:

• 多伦多市完整交通时间表的28 MB TAB分隔文本文件(约865,000条记录)
• 我的测试机器是运行Windows XP的3.60 GHz P4.
• 该代码使用Visual C++ 2005 编译为"Release",带有"Full Optimization"(/ Ox)和Favor Fast Code(/ Ot).
• 我正在使用SQLite"Amalgamation",直接编译到我的测试应用程序中.我碰巧遇到的SQLite版本有点旧(3.6.7),但我怀疑这些结果与最新版本相当(如果你不这么想请发表评论).

我们来写一些代码吧!

代码:一个简单的C程序,它逐行读取文本文件,将字符串拆分为值,然后将数据插入SQLite数据库.在代码的这个"基线"版本中,创建了数据库,但我们实际上不会插入数据:

/*************************************************************
    Baseline code to experiment with SQLite performance.

    Input data is a 28 MB TAB-delimited text file of the
    complete Toronto Transit System schedule/route info
    from http://www.toronto.ca/open/datasets/ttc-routes/

**************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include "sqlite3.h"

#define INPUTDATA "C:\\TTC_schedule_scheduleitem_10-27-2009.txt"
#define DATABASE "c:\\TTC_schedule_scheduleitem_10-27-2009.sqlite"
#define …

我正在寻找最快的方法来确定一个long值是否是一个完美的正方形(即它的平方根是另一个整数):

1. 我通过使用内置Math.sqrt() 函数以简单的方式完成了它,但我想知道是否有办法通过将自己限制为仅整数域来更快地完成它.
2. 维护查找表是不切实际的(因为大约有2 ^31.5个整数,其平方小于2 ⁶³).

这是我现在正在做的非常简单直接的方式:

public final static boolean isPerfectSquare(long n)
{
  if (n < 0)
    return false;

  long tst = (long)(Math.sqrt(n) + 0.5);
  return tst*tst == n;
}

_{注意:我在许多Project Euler问题中使用此函数.因此,没有其他人必须维护此代码.而这种微优化实际上可以产生影响,因为部分挑战是在不到一分钟的时间内完成每个算法,并且在某些问题中需要将此函数调用数百万次.}

我尝试过不同的问题解决方案:

• 经过详尽的测试后,我发现0.5不需要添加Math.sqrt()的结果,至少在我的机器上没有.
• 的快速逆平方根增快,但它给了不正确的结果对于n> = 410881.然而,所建议BobbyShaftoe,我们可以使用FISR劈对于n <410881.
• 牛顿的方法慢了一点Math.sqrt().这可能是因为Math.sqrt()使用类似牛顿方法的东西,但在硬件中实现,因此它比Java快得多.此外,牛顿的方法仍然需要使用双打.
• 一个修改过的牛顿方法,它使用了一些技巧,只涉及整数数学,需要一些黑客来避免溢出(我希望这个函数适用于所有正64位有符号整数),并且它仍然比它慢Math.sqrt().
• 二进制斩甚至更慢.这是有道理的,因为二进制斩波平均需要16遍才能找到64位数的平方根.
• 根据John的测试,or在C++中使用语句比使用语句更快switch,但在Java和C#中,or和之间似乎没有区别switch.
• 我还尝试制作一个查找表(作为64个布尔值的私有静态数组).然后or我会说,而不是开关或声明if(lookup[(int)(n&0x3F)]) { test } else return false; …

大多数拥有CS学位的人肯定会知道Big O代表什么.它可以帮助我们衡量算法的实际效率(如何),如果你知道你试图解决的问题属于哪个类别,你可以弄清楚是否仍然可以挤出那么少的额外性能.¹

但我很好奇,你如何计算或近似算法的复杂性？

¹ _{但正如他们所说,不要过度,过早优化是所有邪恶的根源,没有正当理由的优化也应该得到这个名称.}

我为Project Euler Q14编写了这两个解决方案,在汇编和C++中.它们是用于测试Collat​​z猜想的相同蛮力方法.装配解决方案与组装

nasm -felf64 p14.asm && gcc p14.o -o p14

C++是用.编译的

g++ p14.cpp -o p14

部件, p14.asm

section .data
    fmt db "%d", 10, 0

global main
extern printf

section .text

main:
    mov rcx, 1000000
    xor rdi, rdi        ; max i
    xor rsi, rsi        ; i

l1:
    dec rcx
    xor r10, r10        ; count
    mov rax, rcx

l2:
    test rax, 1
    jpe even

    mov rbx, 3
    mul rbx
    inc rax
    jmp c1

even:
    mov rbx, 2 …

如何在现代x86-64 Intel CPU上实现每个周期4个浮点运算(双精度)的理论峰值性能？

据我所知,SSE 需要三个周期,add而mul大多数现代Intel CPU需要五个周期才能完成(参见例如Agner Fog的"指令表").由于流水线操作,add如果算法具有至少三个独立的求和,则每个周期可以获得一个吞吐量.因为打包addpd和标量addsd版本都是如此,并且SSE寄存器可以包含两个,double每个周期的吞吐量可以高达两个触发器.

此外,似乎(虽然我没有看到任何适当的文档)add并且mul可以并行执行,给出每个周期四个触发器的理论最大吞吐量.

但是,我无法使用简单的C/C++程序复制该性能.我最好的尝试导致大约2.7个翻牌/周期.如果有人可以贡献一个简单的C/C++或汇编程序,它可以表现出非常高兴的峰值性能.

我的尝试:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/time.h>

double stoptime(void) {
   struct timeval t;
   gettimeofday(&t,NULL);
   return (double) t.tv_sec + t.tv_usec/1000000.0;
}

double addmul(double add, double mul, int ops){
   // Need to initialise differently otherwise compiler might optimise away
   double sum1=0.1, sum2=-0.1, sum3=0.2, sum4=-0.2, sum5=0.0;
   double mul1=1.0, mul2= 1.1, mul3=1.2, mul4= 1.3, …

这个网站上已经存在很多性能问题,但是我发现几乎所有这些都是特定于问题且相当狭窄的问题.几乎所有人都重复这些建议,以避免过早优化.

我们假设:

• 代码已经正常工作
• 所选择的算法对于问题的情况已经是最佳的
• 已经测量了代码,并且已经隔离了违规的例程
• 所有优化尝试也将被测量,以确保它们不会使事情变得更糟

我在这里寻找的是在一个关键算法中挤出最后几个百分点的策略和技巧,除此之外别无他法.

理想情况下,尝试使答案语言不可知,并在适用的情况下指出建议策略的任何缺点.

我将使用我自己的初步建议添加回复,并期待Stack Overflow社区可以想到的任何其他内容.

使用反射,如何使用最少的代码获得使用C#3.0/.NET 3.5实现接口的所有类型,并最大限度地减少迭代？

这就是我想要重写的内容:

foreach (Type t in this.GetType().Assembly.GetTypes())
    if (t is IMyInterface)
        ; //do stuff

比较两个double或两个float值的最有效方法是什么？

简单地这样做是不正确的:

bool CompareDoubles1 (double A, double B)
{
   return A == B;
}

但是像这样:

bool CompareDoubles2 (double A, double B) 
{
   diff = A - B;
   return (diff < EPSILON) && (-diff < EPSILON);
}

似乎浪费处理.

有谁知道更聪明的浮动比较器？