编译器是否可以优化变量以使用少于一个字节的空间？

Question

我正在考虑对枚举类型存储在数组或哈希表中的情况进行真正的粒度优化。

我有一系列动物枚举，其中每个枚举可以表示4个不同的类别，Cat，Dog，Fish和Bird（是否有一个枚举类别的名称类型，对吗？）。我需要检查某个范围内的每个值是否相同。这是未优化的方法：

func same([]Animal data, int start, int end) -> Animal or None:
    if (end - start < 0 || end > data.end || start < data.start):  // Bounds checks
        return None
    else if (start == end):                                        // Trivial case
        return data[min_index]
    else:                                                          // Meat & potatoes
        first_value = data[min_index]
        relevant_data = data[min_index:max_index]                      // Slice of relevant parts
        for (value in relevant_data):                                  // Iterate over relevant data
            if value != first_value:                                       // Check if same
                return None                                                // Reject on first non-match
        return first_value                                             // Accept on base case

现在，这很好，最坏和平均的情况是O（n）时间复杂性，但是每次都涉及讨厌的if，我认为这会在编译器级别出现分支错误预测的风险。执行此操作的更优雅的方法是以不同的方式存储data，而不是将其隐式存储为如下形式：

Animal = Enum(
    Cat       // 0b00
    Dog       // 0b01
    Fish      // 0b10
    Bird      // 0b11
)

我们可以使数据代替像这样存储：

Animal = SuperSpecialEnum(
    Cat       // 0b0001
    Dog       // 0b0010
    Fish      // 0b0100
    Bird      // 0b1000
)

然后，我们可以改用以下代码：

func same([]Animal data, int start, int end) -> Animal or None:
    if (end - start < 0 || end > data.end || start < data.start):  // Bounds checks
        return None
    else if (start == end):                                        // Trivial case
        return data[min_index]
    else:                                                          // Thanksgiving
        first_value = data[min_index]
        relevant_data = data[min_index:max_index]                      // Slice of relevant parts

        for (value in relevant_data):                                  // Iterate over relevant data
            first_value &= value                                           // Bitwise and check

        if (first_value == 0b0000):
            return None                                                // Reject on non-match case
        else:
            return first_value                                         // Accept on base case

现在，由于按位first_value &= value，我们可以避免完全分支。当然，我们放弃了可以挽救我们的早期拒绝案例，这实际上很难说，我认为您需要考虑在给定值不同的总体概率上的二项式分布。但是benefit是您完全消除了分支，并且许多现代的编译器和体系结构都支持128位and操作，因此该操作可能会[[真正，非常快]]。对于最坏的情况和平均情况，您的时间复杂度仍为O（n），但是您可能会将迭代次数减少16倍（使用128位布尔运算的16值and，假设编译器知道的操作，并且通常这样做），并完全消除了分支预测错误的风险。现在，真正的问题是双重的，尽管两个问题实际上是同一问题的不同应用程序，该问题涉及编译器是否优化子字节值以使用更少的空间。

一个

，您是否会使用2倍的空间来存储data，因为重新定义了枚举以使用每个值一位而不是log（values）位，并假定枚举类别计数不变（如果存在顺便说一下，这些类别的专有名称）。 Two，如果编译器知道您仅使用每个Animal的前4位，从而允许使用128位布尔运算的32值and，那么您是否有可能获得32倍加速？] >我正在考虑对枚举类型存储在数组或哈希表中的情况进行真正的粒度代码优化。我有一系列的动物枚举，每个枚举都有4个不同的...

Answer 1

大多数架构仅通过SIMD支持128位AND，在那种情况下，它们通常还支持打包字节/ int16 / int32上的相等比较。例如x86 pcmpeqb/w/d/q。

您可以与一些比较结果进行AND运算，并在（高速缓存行或整个数组的最后）检查SIMD向量的每个元素是否都为“ true”，即数组的每个元素都与第一个元素匹配。