Могут ли компиляторы когда-либо оптимизировать переменные, чтобы они занимали меньше байта пространства?

Question

Я думаю о действительно гранулированной оптимизации кода для случая, когда перечисляемые типы хранятся в массиве или в таблице sh.

У меня есть массив перечислений животных, где каждое перечисление имеет 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, мы можем Избегайте ветвления полностью. Конечно, мы отказываемся от случая раннего отклонения, который бы нас спас, ну, на самом деле, это немного сложно сказать, я думаю, вам нужно рассмотреть биномиальное распределение по общей вероятности того, что любое данное значение будет другим. Но преимущество состоит в том, что вы полностью исключили ветвление, и многие современные компиляторы и архитектуры поддерживают 128-битные and операции, поэтому эта операция может быть действительно очень быстрой . Вы все еще на O (n) усложняете время для наихудшего и среднего случая, но вы потенциально сокращаете число итераций в 16 раз (16-значное and с 128-битным логическим арифметическим c, предполагая, что компилятор знает, что он делает, и обычно это делает), и полностью исключает риск ошибочных прогнозов.

Теперь реальный вопрос двоякий, хотя оба вопроса действительно являются различными приложениями одного и того же вопроса о том, является ли компилятор оптимизирует значения суббайтов, чтобы использовать меньше места. Один , вы бы использовали в 2 раза больше места для хранения data из-за переопределения enum для использования одного бита на значение вместо лога (значений), предполагая постоянное количество категорий перечисления (все еще интересующийся кстати, если есть правильное название для этих категорий). Два , возможно, вы могли бы получить 32-кратное ускорение, если компилятор знает, что вы используете только первые 4 бита каждого Animal, что позволяет использовать 32-значные and с 128-битной логической арифметикой c

Answer 1

Большинство архитектур поддерживают только 128-битное И через SIMD, и в этом случае они обычно также поддерживают сравнение для равенства в упакованных байтах / int16 / int32. например, x86 pcmpeqb/w/d/q.

Вы можете И вместе сравнить результаты и проверить в конце (строки кэша или целого массива), что каждый элемент вашего вектора SIMD имеет "true" ", т. е. каждый элемент массива соответствует первому элементу.

Вы можете сделать это на упакованных 2-битных полях, выполнив битовую трансляцию, чтобы дублировать первое 2-битное поле для всех остальных пар. в байтах и ​​в байтовой передаче, что в целом вектор SIMD (например, AVX2 vpbroadcastb, или в C intrinsics _mm_set1_epi8). Сравнение на равенство все еще работает в этом случае для упакованных 2-битных или 4-битных полей, хотя для загрузки + pcmpeqb с другим reg + pand может потребоваться пара дополнительных входных мопов на 16-байтовый вектор по сравнению с просто pand с операндом источника памяти. Тем не менее, разрешение на вдвое более плотном представлении компенсирует это на большинстве процессоров, особенно когда вы рассматриваете возможность сократить объем кэш-памяти в два раза. перенумерация для вас, или упаковка массива перечислений для хранения двух элементов nibble на байт.

Определенно нет текущих компиляторов C; язык (и ABI для языка) слишком сильно определяют ширину типов и макеты данных, и обычно компилятору не стоит тратить время на поиск редких случаев, когда структура данных полностью закрыта для функции и полностью реструктурировать работу типов .

(Более того, компилятору Writers времени обычно не стоит пытаться писать код, который может безопасно / правильно выполнять крупные высокоуровневые преобразования, которые отличают макет данных в памяти от исходного кода говорит, что полная оптимизация массива, безусловно, сделана, но я не видел, как это делают C компиляторы. Изменение типа *)

Но, конечно, это возможно в теории, особенно в отличие от языков C, где enum не определяет , как вещи нумеруются автоматически. (В C, который четко определен: начинайте с нуля и увеличивайте на 1, если вы не переопределите его, например, enum foo { a = 1<<0, b = 1<<1, ... };

Скомпилированные языки с опережением времени будут нацелены на ABI, который определен для платформы (например, x86-64 System V ABI при компиляции для x86-64 GNU / Linux). Это позволяет коду из разных компиляторов и разных версий / настроек оптимизации одного и того же компилятора вызывать друг друга.

Наличие enum в качестве функции arg или возвращаемого значения делает его частью ABI, для не static функций (то есть тех, которые могут быть вызваны из отдельно скомпилированного кода Таким образом, кроме оптимизации во время соединения (и встраивания), компиляторы не имеют выбора в отношении представления данных через границы не встроенных функций. (За исключением иногда с межпроцедурной оптимизацией, иногда включаемой оптимизацией во время соединения через источник файлы.)

Также имейте в виду, что компиляторы C обычно заботятся о том, чтобы быть полезными для низкоуровневого системного программирования, включая int извлечение с помощью аппаратного обеспечения или возможность отображения файлов карты памяти. Если это может произойти, то представления данных становятся видимыми извне. Это причина, почему компиляторы не захотят делать упаковку данных, которая изменяет способ хранения массива. Трудно доказать (кроме локального, чей адрес никогда не выходит за пределы функции), что ничто иное не может заботиться о расположении данных массива.

---

Атомность / потокобезопасность для изменения смежных элементов массива

C / C ++ гарантирует, что разные потоки могут изменять разные объекты, не мешая друг другу. (поскольку C11 / C ++ 11 представили модель памяти с поддержкой потоков).

Сюда входят смежные элементы char array[] или enum foo array[]. Каждый элемент массива является отдельным объектом. (А также является частью всего объекта массива). Модель памяти C ++ и условия гонки на массивах символов и Может ли современное оборудование x86 не хранить в памяти ни одного байта? (может, так может каждый ISA с инструкциями для хранения байтов)

На однопоточном языке или на языке без такой гарантии, да, теоретически у вас может быть реализация, которая упаковывает перечисления в суббайтовые поля.

Интересный факт: в C ++ std::vector<bool> требуется специализация на упакованном растровом шаблоне ( полезная структура данных, к сожалению, исторический выбор класса для предоставления его через ). Это делает небезопасным одновременное выполнение vbool[1] = false и vbool[2] = false различными потоками, в отличие от других std::vector, где это безопасно.

---

Если вы хотите эту оптимизацию, вы обычно написать самому в источнике