相关疑难解决方法(0)

现代x86 CPU将传入的指令流分解为微操作(uops ¹),然后在输入准备就绪时将这些uop 无序调度.虽然基本思路很清楚,但我想了解准备好指令的具体细节,因为它会影响微优化决策.

例如,采取以下玩具循环²:

top:
lea eax, [ecx + 5]
popcnt eax, eax
add edi, eax
dec ecx
jnz top

这基本上实现了循环(具有以下对应关系:) eax -> total, c -> ecx:

do {
  total += popcnt(c + 5);
} while (--c > 0);

通过查看uop细分,依赖链延迟等,我熟悉优化任何小循环的过程.在上面的循环中,我们只有一个携带的依赖链:dec ecx.环路(前三指令lea,imul,add)是开始新鲜每个环一个依赖关系链的一部分.

决赛dec和jne融合.因此,我们总共有4个融合域uop,以及一个仅循环携带的依赖链,延迟为1个周期.因此,基于该标准,似乎循环可以在1个周期/迭代时执行.

但是,我们也应该关注港口压力:

• 在lea能够在端口1和5执行
• popcnt可以在端口1上执行
• 在add可以在端口0,1,5和6执行
• 预测采用jnz在端口6上执行

因此,要进行1次循环/迭代,您几乎需要执行以下操作:

• popcnt 必须在端口1上执行(它可以执行的唯一端口)
• 在lea 必须 …

我有以下 C/C++ 代码片段：

#define ARRAY_LENGTH 666

int g_sum = 0;
extern int *g_ptrArray[ ARRAY_LENGTH ];

void test()
{
    unsigned int idx = 0;

    // either enable or disable the check "idx < ARRAY_LENGTH" in the while loop
    while( g_ptrArray[ idx ] != nullptr /* && idx < ARRAY_LENGTH */ )
    {
        g_sum += *g_ptrArray[ idx ];
        ++idx;
    }

    return;
}

当我使用版本 12.2.0 中的 GCC 编译器编译上述代码时，并选择-Os两种情况：

1. while 循环条件是g_ptrArray[ idx ] != nullptr
2. while 循环条件是g_ptrArray[ idx ] != …

我是指令优化的新手.

我对一个简单的函数dotp进行了简单的分析,该函数用于获取两个浮点数组的点积.

C代码如下:

float dotp(               
    const float  x[],   
    const float  y[],     
    const short  n      
)
{
    short i;
    float suma;
    suma = 0.0f;

    for(i=0; i<n; i++) 
    {    
        suma += x[i] * y[i];
    } 
    return suma;
}

我用昂纳雾在网络上提供的测试框架testp.

在这种情况下使用的数组是对齐的:

int n = 2048;
float* z2 = (float*)_mm_malloc(sizeof(float)*n, 64);
char *mem = (char*)_mm_malloc(1<<18,4096);
char *a = mem;
char *b = a+n*sizeof(float);
char *c = b+n*sizeof(float);

float *x = (float*)a;
float *y = (float*)b;
float *z = (float*)c;

然后我调用函数dotp,n = 2048,repeat …

我一直看到人们声称MOV指令可以在x86中免费,因为寄存器重命名.

对于我的生活,我无法在一个测试用例中验证这一点.每个测试用例我尝试揭穿它.

例如,这是我用Visual C++编译的代码:

#include <limits.h>
#include <stdio.h>
#include <time.h>

int main(void)
{
    unsigned int k, l, j;
    clock_t tstart = clock();
    for (k = 0, j = 0, l = 0; j < UINT_MAX; ++j)
    {
        ++k;
        k = j;     // <-- comment out this line to remove the MOV instruction
        l += j;
    }
    fprintf(stderr, "%d ms\n", (int)((clock() - tstart) * 1000 / CLOCKS_PER_SEC));
    fflush(stderr);
    return (int)(k + j + l);
}

这为循环生成以下汇编代码(随意生成这个你想要的;你显然不需要Visual C++):

LOOP:
    add edi,esi
    mov …

我想将高级语言中的简单循环转换为汇编语言(对于emu8086)说,我有这样的代码:

 for(int x = 0; x<=3; x++)
 {
  //Do something!
 }

要么

 int x=1;
 do{
 //Do something!
 }
 while(x==1)

要么

 while(x==1){
 //Do something
 }

我如何在emu8086中执行此操作？

当我尝试测量算术运算的执行时间时，我遇到了非常奇怪的行为。包含for循环体中具有一个算术运算的循环的代码块总是比相同的代码块执行得慢，但在for循环体中具有两个算术运算。这是我最终测试的代码：

#include <iostream>
#include <chrono>

#define NUM_ITERATIONS 100000000

int main()
{
    // Block 1: one operation in loop body
    {
        int64_t x = 0, y = 0;
        auto start = std::chrono::high_resolution_clock::now();

        for (long i = 0; i < NUM_ITERATIONS; i++) {x+=31;}

        auto end = std::chrono::high_resolution_clock::now();
        std::chrono::duration<double> diff = end-start;
        std::cout << diff.count() << " seconds. x,y = " << x << "," << y << std::endl;
    }

    // Block 2: two operations in loop …

我目前正在学习x86汇编语言,并想知道实现循环的更好方法是什么.一种方法是将值移动到ecx寄存器并使用循环指令,另一种方法是使用jmp指令,然后循环体,然后条件跳转最终到循环体的开头.我想第一个将具有更好的可读性,但除此之外,我不知道为什么要使用它.

使用以下代码是否存在任何执行速度差异:

cmp al, 0
je done

以下内容:

or al, al
jz done

我知道JE和JZ指令是相同的,并且使用OR可以提供一个字节的大小改进.但是,我也关心代码速度.逻辑运算符似乎比SUB或CMP更快,但我只是想确定.这可能是规模和速度之间的权衡,或双赢(当然代码将更加不透明).

我们有一个简单的内存吞吐量基准.对于大块内存,它所做的只是重复记忆.

在几台不同的机器上查看结果(针对64位编译),Skylake机器的性能明显优于Broadwell-E,保持OS(Win10-64),处理器速度和RAM速度(DDR4-2133)不变.我们不是说几个百分点,而是大约2个因素.Skylake配置为双通道,Broadwell-E的结果不会因双/三/四通道而异.

任何想法为什么会这样？随后的代码在VS2015的Release中编译,并报告完成每个memcpy的平均时间:

64位:Skylake为2.2ms,Broadwell-E为4.5ms

32位:Skylake为2.2ms,Broadwell-E为3.5ms.

通过利用多个线程,我们可以在四通道Broadwell-E构建上获得更大的内存吞吐量,这很不错,但是看到单线程内存访问的这种巨大差异令人沮丧.为什么差异如此显着的任何想法？

我们还使用了各种基准测试软件,他们验证了这个简单示例所展示的内容 - 单线程内存吞吐量在Skylake上更好.

#include <memory>
#include <Windows.h>
#include <iostream>

//Prevent the memcpy from being optimized out of the for loop
_declspec(noinline) void MemoryCopy(void *destinationMemoryBlock, void *sourceMemoryBlock, size_t size)
{
    memcpy(destinationMemoryBlock, sourceMemoryBlock, size);
}

int main()
{
    const int SIZE_OF_BLOCKS = 25000000;
    const int NUMBER_ITERATIONS = 100;
    void* sourceMemoryBlock = malloc(SIZE_OF_BLOCKS);
    void* destinationMemoryBlock = malloc(SIZE_OF_BLOCKS);
    LARGE_INTEGER Frequency;
    QueryPerformanceFrequency(&Frequency);
    while (true)
    {
        LONGLONG total = 0;
        LONGLONG max = 0;
        LARGE_INTEGER StartingTime, …

我们的服务器生成{c521c143-2a23-42ef-89d1-557915e2323a}-sign.xml日志文件夹中的文件.第一部分是GUID; 第二部分是名称模板.

我想计算具有相同名称模板的文件数.例如,我们有

{c521c143-2a23-42ef-89d1-557915e2323a}-sign.xml
{aa3718d1-98e2-4559-bab0-1c69f04eb7ec}-hero.xml
{0c7a50dc-972e-4062-a60c-062a51c7b32c}-sign.xml

结果应该是

sign.xml,2
hero.xml,1

可能的名称模板的总种类是未知的,可能超过int.MaxValue.

服务器上的文件总数未知,可能超过int.MaxValue.

要求:

最终结果应按名称模板排序.

该工具将运行的服务器是超级关键的.在运行工具之前,我们应该能够告诉内存使用情况(MB)和生成的临时文件数(如果有),并且不知道日志文件夹的任何特征.

我们使用C#语言.

我的想法:

• 对于前5000个文件,计算出现次数,将结果写入Group1.txt.
• 对于第二个5000个文件,计算出现次数,将结果写入Group2.txt.
• 重复,直到处理完所有文件.现在我们有一堆组文件.

然后我合并所有这些组文件.

   Group1.txt     Group2.txt   Group3.txt     Group4.txt   
       \            /            \                /
       Group1-2.txt                Group3-4.txt
                  \                 /
                    Group1-4.txt

Group1-4.txt 是最后的结果.

我和我朋友之间的分歧是我们如何计算事件的数量.

我建议使用字典.文件名模板是关键.设m为分区大小.(在这个例子中它是5000.)然后时间复杂度O(m),空间复杂度O(m).

我的朋友建议对名称模板进行排序,然后在一次传递中对事件进行计数,因为相同的名称模板现在都在一起.时间复杂度O(m log m),空间复杂度O(m).

我们无法说服对方.你们看到这两种方法有什么问题吗？