ios - 为基于 ARM 的设备优化 C 代码

Question

最近，我偶然发现一个面试问题，需要编写针对 ARM，尤其是 iPhone 优化的代码:

Write a function which takes an array of char (ASCII symbols) and find the most frequent character.

char mostFrequentCharacter(char* str, int size)

The function should be optimized to run on dual-core ARM-based processors, and an infinity amount of memory.

从表面上看，问题本身看起来非常简单，这是我脑海中浮现的函数的简单实现:

#define RESULT_SIZE 127

inline int set_char(char c, int result[])
{
    int count = result[c];
    result[c] = ++count;
    return count;
}

char mostFrequentChar(char str[], int size)
{
    int result[RESULT_SIZE] = {0};

    char current_char;
    char frequent_char = '\0';

    int current_char_frequency = 0;
    int char_frequency = 0;

    for(size_t i = 0; i<size; i++)
    {
        current_char = str[i];
        current_char_frequency = set_char(current_char, result);

        if(current_char_frequency >= char_frequency)
        {
            char_frequency = current_char_frequency;
            frequent_char = current_char;
        }
    }

    return frequent_char;
}

首先，我做了一些基本的代码优化；我将每次迭代计算最频繁的字符的代码移至额外的 for 循环，并显着提高了速度，而不是评估以下代码块 size次

if(current_char_frequency >= char_frequency)
{
    char_frequency = current_char_frequency;
    frequent_char = current_char;
}

我们可以在O(RESULT_SIZE)中找到最常见的字符，其中RESULT_SIZE == 127。

char mostFrequentCharOpt1(char str[], int size)
{
    int result[RESULT_SIZE] = {0};

    char frequent_char = '\0';

    int current_char_frequency = 0;
    int char_frequency = 0;

    for(int i = 0; i<size; i++)
    {
        set_char(str[i], result);
    }

    for(int i = 0; i<RESULT_SIZE; i++)
    {
        current_char_frequency = result[i];

        if(current_char_frequency >= char_frequency)
        {
            char_frequency = current_char_frequency;
            frequent_char = i;
        }
    }

    return frequent_char;
}

基准测试:iPhone 5s

size = 1000000
iterations = 500

// seconds = 7.842381
char mostFrequentChar(char str[], int size)

// seconds = 5.905090
char mostFrequentCharOpt1(char str[], int size)

平均而言，mostFrequentCharOpt1 的工作速度比基本实现快约 24%。

类型优化

ARM 内核寄存器的长度为 32 位。因此，将所有类型为 char 的局部变量更改为类型为 int 可以防止处理器在每次赋值后执行额外的指令来计算局部变量的大小。

注意:ARM64 提供 31 个寄存器 (x0-x30)，其中每个寄存器都是 64 位宽，并且还具有 32 位形式 (w0-w30)。因此，无需执行任何特殊操作即可对 int 数据类型进行操作。 infocenter.arm.com - ARMv8 Registers

在比较汇编语言版本中的函数时，我注意到 ARM 使用 int 类型和 char 类型的方式之间存在差异。 ARM 使用 LDRB 指令加载字节，使用 STRB 指令将字节存储到内存中的各个字节中。因此，在我看来，LDRB 比 LDR 慢一点，因为 LDRB 每次访问内存并加载到寄存器时都会进行零扩展。换句话说，我们不能只是将一个字节加载到 32 位寄存器中，我们应该将字节转换为字。

基准测试:iPhone 5s

size = 1000000
iterations = 500

// seconds = 5.905090
char mostFrequentCharOpt1(char str[], int size)

// seconds = 5.874684
int mostFrequentCharOpt2(char str[], int size)

将 char 类型更改为 int 并没有让我在 iPhone 5s 上显着提高速度，相比之下，在 iPhone 4 上运行相同的代码却得到了不同的结果:

基准测试:iPhone 4

size = 1000000
iterations = 500

// seconds = 28.853877
char mostFrequentCharOpt1(char str[], int size)

// seconds = 27.328955
int mostFrequentCharOpt2(char str[], int size)

循环优化

接下来，我进行了循环优化，其中，我不是递增 i 值，而是递减它。

before    
for(int i = 0; i<size; i++) { ... }

after
for(int i = size; i--) { ... }

再次通过比较汇编代码，我可以清楚地区分这两种方法。

mostFrequentCharOpt2                                              |      mostFrequentCharOpt3
0x10001250c <+88>:  ldr    w8, [sp, #28] ; w8 = i                 |      0x100012694 <+92>:  ldr    w8, [sp, #28]                                             ; w8 = i
0x100012510 <+92>:  ldr    w9, [sp, #44] ; w9 = size              |      0x100012698 <+96>:  sub    w9, w8, #1 ; w9 = i - 1                                           
0x100012514 <+96>:  cmp    w8, w9 ; if i<size                     |      0x10001269c <+100>: str    w9, [sp, #28] ; save w9 to memmory
0x100012518 <+100>: b.ge   0x100012548 ; if true => end loop      |      0x1000126a0 <+104>: cbz    w8, 0x1000126c4 ; compare w8 with 0 and if w8 == 0 => go to 0x1000126c4
0x10001251c <+104>: ... set_char start routine                    |      0x1000126a4 <+108>: ... set_char start routine
...                                                               |      ...
0x100012534 <+128>: ... set_char end routine                      |      0x1000126bc <+132>: ... set_char end routine
0x100012538 <+132>: ldr    w8, [sp, #28] ; w8 = i                 |      0x1000126c0 <+136>: b      0x100012694 ; back to the first line
0x10001253c <+136>: add    w8, w8, #1 ; i++                       |      0x1000126c4 <+140>: ...
0x100012540 <+140>: str    w8, [sp, #28] ; save i to $sp+28       |      
0x100012544 <+144>: b      0x10001250c ; back to the first line   |      
0x100012548 <+148>: str    ...                                    |      

这里，代替从内存访问 size 并将其与 i 变量进行比较，其中 i 变量递增，我们只是将 i 减 0x1，并将存储 i 的寄存器与 0 进行比较。

基准测试:iPhone 5s

size = 1000000
iterations = 500

// seconds = 5.874684
char mostFrequentCharOpt2(char str[], int size) //Type optimization

// seconds = 5.577797
char mostFrequentCharOpt3(char str[], int size) //Loop otimization

线程优化

准确地阅读问题至少可以让我们多一个优化。此行..优化为在基于 ARM 的双核处理器上运行... 特别是，删除了使用 pthread 或 gcd 优化代码的提示。

int mostFrequentCharThreadOpt(char str[], int size)
{
    int s;
    int tnum;
    int num_threads = THREAD_COUNT; //by default 2
    struct thread_info *tinfo;

    tinfo = calloc(num_threads, sizeof(struct thread_info));

    if (tinfo == NULL)
        exit(EXIT_FAILURE);

    int minCharCountPerThread = size/num_threads;
    int startIndex = 0;

    for (tnum = num_threads; tnum--;)
    {
        startIndex = minCharCountPerThread*tnum;

        tinfo[tnum].thread_num = tnum + 1;
        tinfo[tnum].startIndex = minCharCountPerThread*tnum;
        tinfo[tnum].str_size = (size - minCharCountPerThread*tnum) >= minCharCountPerThread ? minCharCountPerThread : (size - minCharCountPerThread*(tnum-1));
        tinfo[tnum].str = str;

        s = pthread_create(&tinfo[tnum].thread_id, NULL,
                           (void *(*)(void *))_mostFrequentChar, &tinfo[tnum]);
        if (s != 0)
            exit(EXIT_FAILURE);
    }

    int frequent_char = 0;
    int char_frequency = 0;
    int current_char_frequency = 0;

    for (tnum = num_threads; tnum--; )
    {
        s = pthread_join(tinfo[tnum].thread_id, NULL);
    }

    for(int i = RESULT_SIZE; i--; )
    {
        current_char_frequency = 0;

        for (int z = num_threads; z--;)
        {
            current_char_frequency += tinfo[z].resultArray[i];
        }

        if(current_char_frequency >= char_frequency)
        {
            char_frequency = current_char_frequency;
            frequent_char = i;
        }
    }

    free(tinfo);

    return frequent_char;
}

基准测试:iPhone 5s

size = 1000000
iterations = 500

// seconds = 5.874684
char mostFrequentCharOpt3(char str[], int size) //Loop optimization

// seconds = 3.758042
// THREAD_COUNT = 2
char mostFrequentCharThreadOpt(char str[], int size) //Thread otimization

注意:mostFrequentCharThreadOpt 在 iPhone 4 上的运行速度比mostFrequentCharOpt2 慢。

基准测试:iPhone 4

size = 1000000
iterations = 500

// seconds = 25.819347
char mostFrequentCharOpt3(char str[], int size) //Loop optimization

// seconds = 31.541066
char mostFrequentCharThreadOpt(char str[], int size) //Thread otimization

问题

mostFrequentCharOpt3 和mostFrequentCharThreadOpt 的优化程度如何，换句话说:是否有其他方法可以优化这两种方法？

Source code

Answer 1

好吧，您可以尝试以下方法，我不能 100% 说出什么对您的情况有效，但根据经验，如果您关闭所有可能的优化，并查看事实上，即使循环优化也对你有用:你的编译器相当 NumPy 。

这稍微取决于您的 THREAD_COUNT，您说默认为 2，但如果您 100% 为 2，您可能可以腾出一些时间。您知道您工作的平台，如果速度是你的首要任务，就不要无缘无故地让任何东西变得动态。

如果THREAD == 2，则num_threads是不必要的变量，可以删除。

int minCharCountPerThread = size/num_threads;

许多讨论有关位移位的主题的旧方法，请尝试一下:

int minCharCountPerThread = size >> 1; //divide by 2

您可以尝试的下一件事是展开循环:多个循环仅使用两次，如果大小不是问题，为什么不删除循环方面呢？这确实是您应该尝试的事情，看看会发生什么，以及它是否对您有用。我见过案例循环展开效果很好，我见过案例循环展开会减慢我的代码速度。

最后一件事:如果signed/int，请尝试使用unsigned数字(除非您确实需要签名)。众所周知，某些技巧/指令仅适用于无符号变量。