相关疑难解决方法(0)

摘要

在处理大型文本文件时,我遇到了以下(意外)性能下降,我无法解释.我对这个问题的目标是:

• 了解导致下面描述的减速的原因
• 了解如何快速初始化大型非原始数组

问题

• 数组包含非基本引用项
  • 不是int[],但MyComplexType[]
  • MyComplexType 是一个类,而不是结构
  • MyComplexType包含一些string属性
• 数组已预先分配
• 数组很大
• 如果在未分配给阵列的情况下创建和使用项目,则程序很快
• 如果创建了一个项目然后将其分配给数组项,则程序会显着减慢
  • 我希望数组项目赋值是一个简单的引用赋值,但是根据我在下面的测试程序的结果,这似乎不是这种情况

测试程序

考虑以下C#程序:

namespace Test
{
    public static class Program
    {
        // Simple data structure
        private sealed class Item
        {
            public Item(int i)
            {
                this.Name = "Hello " + i;
                //this.Name = "Hello";
                //this.Name = null;
            }
            public readonly string Name;
        }

        // Test program
        public static void Main()
        {
            const int length …

我试图找到我最近在stackoverflow上发布的程序的效率.

如何有效地删除给定另一个向量的向量中的元素

为了比较我的代码与其他答案的效率,我正在使用chrono对象.

这是检查运行时效率的正确方法吗？

如果没有,那么请用一个例子来建议一种方法.

Coliru代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <chrono>
#include <ctime>
using namespace std;

void remove_elements(vector<int>& vDestination, const vector<int>& vSource) 
{
    if(!vDestination.empty() && !vSource.empty())
    {
        for(auto i: vSource) {
            vDestination.erase(std::remove(vDestination.begin(), vDestination.end(), i), vDestination.end());
        }
    }
}

int main() {
    vector<int> v1={1,2,3};
    vector<int> v2={4,5,6};
    vector<int> v3={1,2,3,4,5,6,7,8,9};
    std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
    remove_elements(v3,v1);
    remove_elements(v3,v2);
    std::chrono::steady_clock::time_point end= std::chrono::steady_clock::now();
    std::cout << "Time difference = " << std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin).count() <<std::endl;
    for(auto i:v3)
        cout << i << endl;
    return …

在比较检查列表是否包含R中的另一个列表时,比较两个函数的效率,我偶然发现了一个有趣的结果.排序大大提高了duplicated矢量大时的效率.这是一个惊喜,因为我从未注意到我自己的工作使用时有相当大的差异duplicated.事实上,对于我每天工作的尺寸,没有区别.注意:

set.seed(1007)
s1 <- sample(10^2, 10^3, replace = TRUE)
s1_sort <- sort(s1)
library(microbenchmark)
microbenchmark(dp=duplicated(s1), dp_sort=duplicated(s1_sort), times=1000)
Unit: microseconds
   expr    min      lq     mean  median      uq      max neval cld
     dp 16.459 16.9425 22.06371 17.2965 22.5050 1541.137  1000   a
dp_sort 17.007 17.5005 25.54953 17.8200 23.3655 1549.198  1000   a

如您所见,向量排序时的时间没有明显差异.然而,在非常大的向量上,结果是非常不同的.注意:

s2 <- sample(10^6, 10^7, replace = TRUE)
s2_sort <- sort(s2)
microbenchmark(dp=duplicated(s2), dp_sort=duplicated(s2_sort), times=100)
Unit: milliseconds
   expr      min       lq     mean   median       uq       max neval cld
     dp 816.6883 847.9231 869.6829 …

我最近在这里阅读了这个问题为什么处理排序数组比未排序数组更快？并且发现答案绝对令人着迷,在处理基于Data的分支时,它完全改变了我对编程的看法.

我目前有一个用C编写的相当基本但功能完备的解释型Intel 8080仿真器,操作的核心是一个256长的交换机案例表,用于处理每个操作码.我最初的想法是,这显然是最快的工作方法,因为操作码编码在整个8080指令集中并不一致,并且解码会增加很多复杂性,不一致性和一次性情况.一个装有预处理器宏的开关盒表非常整洁,易于维护.

不幸的是,在阅读上述帖子之后,我发现我的电脑中的分支预测器绝对没有办法预测开关盒的跳跃.因此,每次切换案例时,必须完全擦除管道,导致几个周期延迟,否则应该是一个非常快速的程序(在我的代码中甚至没有多次乘法).

我相信大多数人都在想"哦,这里的解决方案很简单,转向动态重新编译".是的,这看起来似乎会削减大部分开关盒并大大提高速度.不幸的是,我的主要兴趣是模拟旧的8位和16位时代控制台(这里的英特尔8080只是一个例子,因为它是我最简单的模拟代码),其中保持精确指令的周期和时序对于视频和声音很重要必须根据这些确切的时间进行处理.

当处理这种级别的准确性时,性能成为一个问题,即使对于旧的控制台(例如,查看bSnes).在处理具有长管道的处理器时,是否有任何追索权或者这仅仅是事实？

我发现这个主题为什么处理排序数组比未排序数组更快？.并尝试运行此代码.而且我发现了奇怪的行为.如果我使用-O3优化标志编译此代码,则需要2.98605 sec运行.如果我用-O2它编译1.98093 sec.我尝试在同一环境中的同一台机器上运行此代码几次(5或6),我关闭所有其他软件(chrome,skype等).

gcc --version
gcc (Ubuntu 4.9.2-0ubuntu1~14.04) 4.9.2
Copyright (C) 2014 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

那么请你能解释一下为什么会这样吗？我阅读gcc手册,我看到-O3包括-O2.谢谢你的帮助.

PS添加代码

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

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

    for (unsigned …

当我写一些需要快速工作的紧密循环时,我常常被关于处理器分支预测将如何表现的想法所困扰.例如,我尽量避免在最内部循环中使用if语句,尤其是结果不一致的结果(比如判断为true或false随机).

我倾向于这样做,因为处理器预先获取指令有一些常见的知识,如果事实证明它错误地预测了一个分支,那么预取是没用的.

我的问题是 - 这真的是现代处理器的问题吗？预期分支预测有多好？
可以使用哪些编码模式来使其更好？

(为了讨论起见,假设我超越了"早期优化是所有邪恶的根源"阶段)

这个问题及其答案最近被标记为史诗答案,这让我感到奇怪; 我可以根据CPU分支预测失败来衡量Windows中正在运行的应用程序的性能吗？我知道存在一些静态分析工具,这可能有助于在分支预测情况下优化代码以获得良好性能,并且手动技术可以通过简单地进行更改和重新测试来提供帮助,但我正在寻找一些可以自动化的机制.报告在一段时间内,当Windows应用程序运行时,分支预测失败的总数,我希望Visual C++的一些Profiler工具可以帮助我.

为了这个问题,有问题的应用程序可以使用本机编译器(如Visual C++ for Windows)构建,也可以使用其他本机编译器构建,例如GCC,FreePascal,Delphi或TurboAssembler.可执行文件可能根本没有任何调试信息.我想知道我是否可以检测并计算分支预测失败,可能是通过某些Windows服务(如WMI)读取内部CPU信息,或者可能完全在运行Windows的虚拟化环境中运行,例如使用VirtualBox,然后完全运行虚拟化Windows环境与我的测试应用程序,VirtualBox内部,并进行虚拟CPU的运行时分析.或者其他一些我不知道的技术,因此这个问题.

是的,我用Google搜索.唯一看起来很有希望的是来自AMD的PDF.我们提到了一些非常接近我想做的事情,但似乎是为没有任何操作系统的人在原始评估硬件平台上编写的:

5.1.分行.适用性.条件分支错误预测可能是具有大量决策逻辑的代码中的重要问题.

当选择真或假路径的可能性是随机的或接近50-50分裂时,条件分支可能被错误预测.分支预测硬件不能"学习"模式,并且不能正确预测分支.采集.收集此表中的事件以测量分支预测性能:

分支使用以下公式计算分支的采用率和每个分支的指令数的比率:分支采用率= Taken_branches/Ret_instructions分支采用率= Taken_branches /分支
每个分支的指令= Ret_instructions /分支

更新:我想我可以说我正在寻找一种方法来读取英特尔酷睿i7 PMU模块或其他CPU的等效功能.看起来英特尔VTUNE(来自Adrian的评论)非常接近我的要求.

VBA不会短路

VBA不支持短路 - 显然是因为它只有按位和/或/不等操作.从VBA语言规范:"逻辑运算符是对其操作数执行按位计算的简单数据运算符." 从这个角度来看,使用true = &H1111和设计VBA是有道理的false = &H0000:这样,逻辑语句可以被评估为按位运算.

缺少短路可能会导致问题

1. 性能:在ReallyExpensiveFunction()评估此语句时将始终运行,即使条件左侧的结果不需要

   If IsNecessary() And ReallyExpensiveFunction() Then '... End If

2. 错误:如果MyObj为Nothing,则此条件语句将导致运行时错误,因为VBA仍将尝试检查值 Property

   If Not MyObj Is Nothing And MyObj.Property = 5 Then '... End If

我用来实现短效行为的解决方案是嵌套If的

If cond1 And cond2 Then
    '...
End If

变

If cond1 Then
    If cond2 Then
        '...
    End If
End If

通过这种方式,If语句给出了类似短路的行为,即不打算评估cond2是否cond1存在False.

如果存在Else子句,则会创建重复的代码块

If Not MyObj Is Nothing And MyObj.Property …

我正在搜索关于"C程序如何工作"的博客文章一个月.大多数人都喜欢

1. 编译器会做这些事情
2. 连接器做这些事情
3. 程序被放入内存; 和堆栈,堆等

我想我会先阅读有关编译器如何理解程序流入机器的工作原理.龙书似乎是普遍的首选.但说实话,这太过密集了.我现在还不够好,无法完成所有这些工作.

所以我开始阅读有关硬件的内容.但是,他们也解释了总线,I/O信号,内存结构,编写缓存友好代码等等.但没有适当的例子.

但我仍然无法让自己满意或能够完全想象这个过程.

2个小时前,我决定提出这个问题.(因为我害怕它可能对SO社区,或题外话题或其他可下注的类别没用),而且我没有找到任何与此相关的帖子.有一个关于"编译器如何编译",但答案表明这是一个太宽泛的问题.

我的问题是:

我想知道C程序的工作原理.如果您无法明确告诉我,请将我重定向到另一个网站上的书或其他帖子,以便给我答案.

我在这里,直到得到回复.如果您对此帖有任何建议,请告诉我.这不是我的第一语言,所以请把我所有的句子都当作柔软和礼貌的.

谢谢.

更新:

除了接受的答案外,还有一些非常好的链接以及建议,可以给出部分答案或进一步了解我想要了解的内容.

我有一个C++程序,基本上执行一些矩阵计算.对于这些我使用LAPACK/BLAS并且通常根据平台链接到MKL或ACML.很多这些矩阵计算都在不同的独立矩阵上运行,因此我使用std :: thread来让这些操作并行运行.但是,我注意到在使用更多线程时我没有加速.我将问题追溯到daxpy Blas例程.似乎如果两个线程并行使用此例程,则每个线程花费两倍的时间,即使两个线程在不同的阵列上运行.

我尝试的下一件事是编写一个新的简单方法来执行向量添加以替换daxpy例程.使用一个线程,这个新方法与BLAS例程一样快,但是,当使用gcc进行编译时,它会遇到与BLAS例程相同的问题:并行运行的线程数加倍也会使每个线程需要的时间加倍,所以没有加速.但是,使用英特尔C++编译器时,这个问题就会消失:随着线程数量的增加,单个线程需要的时间是不变的.

但是,我需要在没有英特尔编译器的系统上进行编译.所以我的问题是:为什么gcc没有加速,是否有提高gcc性能的可能性？

我写了一个小程序来演示效果:

// $(CC) -std=c++11 -O2 threadmatrixsum.cpp -o threadmatrixsum -pthread

#include <iostream>
#include <thread>
#include <vector>

#include "boost/date_time/posix_time/posix_time.hpp"
#include "boost/timer.hpp"

void simplesum(double* a, double* b, std::size_t dim);

int main() {

    for (std::size_t num_threads {1}; num_threads <= 4; num_threads++) {
        const std::size_t N { 936 };

        std::vector <std::size_t> times(num_threads, 0);    

        auto threadfunction = [&](std::size_t tid)
        {
            const std::size_t dim { N * N };
            double* pA = new double[dim];
            double* pB = new double[dim];

            for (std::size_t …