avr-gcc：二分搜索与线性搜索

Question

我正在使用如下线性搜索来搜索存储在程序内存中的一些长度约为 30-200 的结构数组：

Glyph getGlyph(Font font, uint16_t code) {
    for (size_t i = 0; i < font.length; i++) {
        if (pgm_read_word(&font.glyphs[i].code) == code) {
            static Glyph glyph;
            memcpy_P(&glyph, &font.glyphs[i], sizeof (Glyph));
            
            return glyph;
        }
    }
    
    // return question mark if unknown code point
    return getGlyph(font, 0x003f);
}

假设我正确地阅读了反汇编代码，每次迭代有 20 条指令，据我所知，其中 3 条指令相当昂贵：

brcc

、

brne

和

rjmp

。

只是评估是否可以更高效地完成此操作，我实现了二分搜索：

Glyph getGlyph(Font font, uint16_t code) {
    
    // https://en.wikipedia.org/wiki/Binary_search_algorithm
    int16_t l = 0;
    int16_t r = font.length - 1;
    
    while (l <= r) {
        uint8_t m = (l + r) / 2;
        uint16_t c = pgm_read_word(&font.glyphs[m].code);
        if (c < code) {
            l = m + 1;
        } else if (c > code) {
            r = m - 1;
        } else {
            // found code point, get and return glyph
            static Glyph glyph;
            memcpy_P(&glyph, &font.glyphs[m], sizeof (Glyph));
            
            return glyph;
        }
    }
    
    // return question mark if unknown code point
    return getGlyph(font, 0x003f);
}

这导致反汇编中每次迭代需要 35 条指令，其中 5 条我认为相当昂贵：

brlt

、

brcc

(2x) 和

rjmp

(2x)。

鉴于数组相当短，我认为二分搜索的好处不是很多，并且可能会通过增加的复杂性来补偿？

尝试对此进行基准测试是否值得或是否有意义？

Answer 1

这个程序有很多大瓶颈，它们不一定与搜索本身有关。要解决这些问题，您需要进行代码审查：

• 为什么要按值传递结构等？即使在结构很小的情况下，这对于 8 个 Bit 来说也是极其低效的。

• 当您返回字形时，首先将其从某处（闪存）复制到

  static

  变量（.bss）中，然后再次将其复制到函数调用堆栈上，最后在调用者中再次复制它。当您只返回一个指向原始项目的

  const

  指针时，这是非常低效的，或者如果这些需要在运行时修改，只需复制它 once - 可能仍然返回一个

  const

  指针并且让调用者复制数据。

  （可能需要使用一些哈佛架构调整来直接访问闪存数据 - 无论您的编译器使用什么来处理该数据，“PROGMEM”宏或类似的宏。）

• 避免不必要的大计数器和索引。如果您不打算超过值 255，则不要使用

  uint16_t

  。而且几乎从不使用

  size_t

  ，这将是 32 苦，因此速度非常慢。

• 递归函数几乎不应该在任何上下文中使用，当然也不应该在嵌入式系统中使用。该部分必须重写为循环 - 我什至不明白你为什么要使用递归。

• 使用标准库

  bsearch

  不一定比手动推出自己的版本慢很多。用示波器进行基准测试。

• 一般来说，二分查找对于 8 比特来说是一个相当不错的算法。我们无需担心分支或对齐，只需担心生成的原始指令量。另一方面，您实际上选择了仍在生产中最慢的 CPU 之一，所以为什么要担心性能。

总的来说，我认为选择现代 MCU（例如 Cortex M）会让您受益匪浅。用 C 语言对旧的 8 位进行编程实际上非常困难，而且很容易出错。 AVR 是 90 年代的技术，没有太多理由再使用它们了。