Любая оптимизация для произвольного доступа в очень большом массиве, когда значение в 95% случаев равно 0 или 1?

Question

Есть ли какая-либо возможная оптимизация для произвольного доступа на очень большом массиве (в настоящее время я использую uint8_t, и я спрашиваю, что лучше)

uint8_t MyArray[10000000];

когда значение в любой позиции в массиве равно

• 0 или 1 для 95% всех случаев,
• 2 в 4% дел,
• между 3 и 255 in другие 1% случаев?

Итак, есть ли что-нибудь лучше, чем массив uint8_t, который можно использовать для этого? Должен быть как можно более быстрый цикл по всему массиву в случайном порядке, и это очень сильно влияет на пропускную способность ОЗУ, поэтому при наличии нескольких потоков, делающих это одновременно для разных массивов, в настоящее время вся пропускная способность ОЗУ быстро насыщается.

Я спрашиваю, поскольку такой большой массив (10 МБ) кажется очень неэффективным, когда на самом деле известно, что почти все значения, кроме 5%, будут либо 0, либо 1. Так что, когда 95% всех значений в массиве на самом деле потребуется только 1 бит вместо 8 бит, это уменьшит использование памяти почти на порядок. Такое ощущение, что должно быть более эффективное решение для памяти, которое значительно уменьшило бы требуемую для этого пропускную способность ОЗУ и, как следствие, значительно ускорило бы произвольный доступ.

Answer 1

Давным-давно, я просто помню ...

В университете мы получили задачу ускорить программу трассировки лучей, которая должна снова и снова считывать алгоритмы из буферных массивов. Друг сказал мне, чтобы всегда использовать чтения RAM, которые кратны 4Bytes. Поэтому я изменил массив с шаблона [x1, y1, z1, x2, y2, z2, ..., xn, yn, zn] на шаблон [x1, y1, z1,0, x2, y2, z2 , 0, ..., хп, уп, гп, 0]. Значит я добавляю пустое поле после каждой трехмерной координаты. После некоторого тестирования производительности: это было быстрее. Итак, короткая история: Считайте кратные 4 байта из вашего массива из ОЗУ и, возможно, также из правильной начальной позиции, так что вы читаете небольшой кластер, в котором находится искомый индекс, и читаете искомый индекс из этого маленького кластера в процессоре. (В вашем случае вам не нужно вставлять поля заполнения, но концепция должна быть ясной)

Может быть, и другие кратные могут быть ключевыми в более новых системах.

Я не знаю, сработает ли это в вашем случае, поэтому, если это не сработает: Извините. Если это сработает, я был бы рад услышать о результатах некоторых тестов.

PS: Да, и если есть какой-либо шаблон доступа или близлежащие индексы доступа, вы можете повторно использовать кэшированный кластер.

PPS: Возможно, множитель был больше похож на 16Bytes или что-то в этом роде, это слишком давно, я точно помню.

Answer 2

Я не очень знаком с C, но в C ++ вы можете использовать unsigned char для представления целого числа в диапазоне 0 - 255.

По сравнению с обычным int (опять же, я из мира Java и C ++ ), в котором 4 байта (32 бита) ) требуется, беззнаковый символ требует 1 байт (8 бит). поэтому он может уменьшить общий размер массива на 75%.

Answer 3

Я добавлю к ответу @ o11c , так как его формулировка может быть немного запутанной.Если мне нужно сжать последний бит и цикл процессора, я бы сделал следующее.

Мы начнем с построения сбалансированного бинарного дерева поиска, которое содержит 5% «что-то еще» случаев,Для каждого поиска вы быстро обходите дерево: у вас есть 10000000 элементов: 5% из которых находится в дереве: следовательно, структура данных дерева содержит 500000 элементов.Пройдя по времени O (log (n)), вы получите 19 итераций.Я не эксперт в этом, но я думаю, что есть некоторые реализации с эффективным использованием памяти.Давайте предположим:

• Сбалансированное дерево, чтобы можно было рассчитать позицию поддерева (индексы не нужно хранить в узлах дерева).Точно так же куча (структура данных) хранится в линейной памяти.
• 1 байтовое значение (от 2 до 255)
• 3 байта для индекса (10000000 занимает 23 бита, что соответствует 3 байта)

Итого, 4 байта: 500000 * 4 = 1953 кБ.Подходит для кеша!

Для всех остальных случаев (0 или 1) вы можете использовать битовый вектор.Обратите внимание, что вы не можете пропустить 5% других случаев для произвольного доступа: 1,19 МБ.

Комбинация этих двух использует приблизительно 3 099 МБ.Используя эту технику, вы сэкономите в 3,08 раза больше памяти.

Однако, это не превзойдет ответ @ Matteo Italia (который использует 2,76 МБ), а жаль.Есть ли что-нибудь, что мы можем сделать дополнительно?Наиболее ресурсоемкая часть - это 3 байта индекса в дереве.Если бы мы смогли уменьшить это значение до 2, мы бы сэкономили 488 КБ, а общее использование памяти составило бы: 2,622 МБ, что меньше!

Как нам это сделать?Мы должны уменьшить индексирование до 2 байтов.Опять же, 10000000 занимает 23 бита.Нам нужно уронить 7 бит.Мы можем просто сделать это, разделив диапазон 10000000 элементов на 2 ^ 7 (= 128) областей из 78125 элементов.Теперь мы можем построить сбалансированное дерево для каждого из этих регионов, в среднем с 3906 элементами.Выбор правильного дерева выполняется простым делением целевого индекса на 2 ^ 7 (или битовое смещение >> 7).Теперь требуемый индекс для хранения может быть представлен оставшимися 16 битами.Обратите внимание, что есть некоторые издержки для длины дерева, которое необходимо сохранить, но это незначительно.Также обратите внимание, что этот механизм разбиения сокращает необходимое количество итераций для обхода дерева, теперь он сокращается на 7 итераций меньше, поскольку мы отбросили 7 бит: осталось только 12 итераций.

Обратите внимание, что теоретически можно повторитьпроцесс обрезки следующих 8 битов, но для этого потребуется создать 2 ^ 15 сбалансированных деревьев, в среднем ~ 305 элементов.В результате получится 2,143 МБ, всего 4 итерации для обхода дерева, что является значительным ускорением по сравнению с 19 итерациями, с которых мы начали.

В заключение: это лучше, чем 2-битная векторная стратегиянемного использования памяти, но это целая борьба для реализации.Но если это может сделать разницу между подгонкой кеша или нет, возможно, стоит попробовать.

Answer 4

Если данные и доступы равномерно распределены случайным образом, производительность, вероятно, будет зависеть от того, какая часть доступа избегает пропадания кэша внешнего уровня. Оптимизация, которая потребует знания, какой размер массива может быть надежно размещен в кеше. Если ваш кэш достаточно большой, чтобы вместить один байт на каждые пять ячеек, самый простой подход может состоять в том, чтобы один байт содержал пять закодированных базовых трех значений в диапазоне 0-2 (имеется 243 комбинации из 5 значений, так что помещается в байт) вместе с массивом из 10 000 000 байтов, который будет запрашиваться всякий раз, когда значение base-3 указывает на «2».

Если кэш не такой большой, но может вместить один байт на 8 ячеек, то будет невозможно использовать одно байтовое значение для выбора среди всех 6 561 возможных комбинаций восьми значений base-3, но, поскольку Единственный эффект изменения 0 или 1 на 2 - вызвать ненужный поиск, для корректности не потребуется поддержка всех 6 561. Вместо этого можно сосредоточиться на 256 самых «полезных» значениях.

Особенно, если 0 чаще встречается, чем 1, или наоборот, хорошим подходом может быть использование 217 значений для кодирования комбинаций 0 и 1, которые содержат 5 или менее 1, 16 значений для кодирования от xxxx0000 до xxxx1111, от 16 до закодируйте 0000xxxx через 1111xxxx и один для xxxxxxxx. Четыре значения останутся для любого другого использования, которое можно найти. Если данные распределяются случайным образом, как описано, небольшое большинство всех запросов будет попадать в байты, которые содержат только нули и единицы (примерно в 2/3 всех групп из восьми все биты будут равны нулю и единицам, а около 7/8 у них было бы шесть или меньше 1 бит); подавляющее большинство из тех, кто не попадал в байты с четырьмя иксами, и с вероятностью 50% попадут в ноль или единицу. Таким образом, только один из четырех запросов потребует поиска в большом массиве.

Если данные распределены случайным образом, но кэш недостаточно велик для обработки одного байта на восемь элементов, можно попробовать использовать этот подход, когда каждый байт обрабатывает более восьми элементов, но если нет сильного смещения в сторону 0 или к 1, доля значений, которые могут быть обработаны без необходимости поиска в большом массиве, будет уменьшаться по мере увеличения числа, обрабатываемого каждым байтом.

Answer 5

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

Например:

[0, 15000] = 0
[15001, 15002] = 153
[15003, 26876] = 2
[25677, 31578] = 0
...

Это можно сделать с помощью структуры. Вы также можете определить класс, подобный этому, если вам нравится ОО-подход.

class Interval{
  private:
    uint32_t start; // First element of interval
    uint32_t end; // Last element of interval
    uint8_t value; // Assigned value

  public:
    Interval(uint32_t start, uint32_t end, uint8_t value);
    bool isInInterval(uint32_t item); // Checks if item lies within interval
    uint8_t getValue(); // Returns the assigned value
}

Теперь вам просто нужно перебрать список интервалов и проверить, находится ли ваш индекс в одном из них, который в среднем может занимать гораздо меньше памяти, но стоит больше ресурсов ЦП.

Interval intervals[INTERVAL_COUNT];
intervals[0] = Interval(0, 15000, 0);
intervals[1] = Interval(15001, 15002, 153);
intervals[2] = Interval(15003, 26876, 2);
intervals[3] = Interval(25677, 31578, 0);
...

uint8_t checkIntervals(uint32_t item)

    for(int i=0; i<INTERVAL_COUNT-1; i++)
    {
        if(intervals[i].isInInterval(item) == true)
        {
            return intervals[i].getValue();
        }
    }
    return DEFAULT_VALUE;
}

Если вы упорядочиваете интервалы по убыванию, вы увеличиваете вероятность того, что искомый элемент будет найден раньше, что еще больше снижает среднее использование памяти и ресурсов ЦП.

Вы также можете удалить все интервалы размером 1. Поместите соответствующие значения в карту и проверяйте их, только если искомый элемент не был найден в интервалах. Это также должно немного повысить среднюю производительность.

Answer 6

Как Мэтс упоминает в своем комментарии-ответе, трудно сказать, что на самом деле является лучшим решением, не зная конкретно , какие у вас есть данные (например, есть ли длинные серии 0 и т. Д.)on) и как выглядит ваш шаблон доступа (означает «случайный» означает «повсеместно» или просто «не строго линейно» или «каждое значение ровно один раз, просто рандомизировано» или ...).

Тем не менее, на ум приходят два механизма:

• Битовые массивы;то есть, если бы у вас было только два значения, вы могли бы тривиально сжать ваш массив в 8 раз;если у вас есть 4 значения (или «3 значения + все остальное»), вы можете сжать с коэффициентом два.Это может не стоить усилий и потребует эталонных тестов, особенно если у вас есть действительно шаблоны произвольного доступа, которые экранируют ваши кеши и, следовательно, вообще не меняют время доступа.
• (index,value) или (value,index) таблицы.То есть, есть одна очень маленькая таблица для случая 1%, может быть одна таблица для случая 5% (которая должна хранить только индексы, поскольку все имеют одинаковое значение), и большой сжатый битовый массив для последних двух случаев.И под «таблицей» я подразумеваю что-то, что позволяет относительно быстро искать;т. е. может быть хеш, бинарное дерево и т. д., в зависимости от того, что у вас есть в наличии и ваши реальные потребности.Если эти подтаблицы вписываются в ваш кэш 1-го / 2-го уровня, вам может повезти.

Answer 7

Если в ваших данных нет закономерностей, маловероятно, что будет какая-либо ощутимая оптимизация скорости или размера, и - если вы нацелены на обычный компьютер - 10 МБ в любом случае не так уж и много.

В ваших вопросах есть два предположения:

1. Данные плохо хранятся, потому что вы не используете все биты
2. Лучшее их хранение сделало бы все быстрее.

Я думаю, что оба эти предположения неверны.В большинстве случаев подходящим способом хранения данных является хранение наиболее естественного представления.В вашем случае это тот, который вы выбрали: байт для числа от 0 до 255. Любое другое представление будет более сложным и, следовательно, при прочих равных условиях, будет медленнее и подвержено ошибкам.Чтобы отклониться от этого общего принципа, вам нужна более веская причина, чем потенциально шесть «потраченных впустую» битов на 95% ваших данных.

Для вашего второго предположения это будет верно, если и только если изменениеразмер массива приводит к значительному уменьшению количества кешейТо, произойдет ли это, может быть определено только путем профилирования рабочего кода, но я думаю, что это вряд ли будет иметь существенное значение.Поскольку в любом случае вы будете получать произвольный доступ к массиву, процессор будет пытаться узнать, какие биты данных следует кэшировать, и сохранить в любом случае.

Answer 8

Вы кратко описали все характеристики распределения вашего массива; бросить массив .

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

Если согласованность имеет значение (выдает то же значениедля того же случайного индекса), рассмотрите возможность использования фильтра Блума и / или хэш-карты для отслеживания повторных попаданий.Если ваш доступ к массиву действительно случайный, это абсолютно не нужно.

Answer 9

Другим вариантом может быть

• , проверить, равен ли результат 0, 1 или 2
• , если нет, сделать обычный поиск

Другими словамичто-то вроде:

unsigned char lookup(int index) {
    int code = (bmap[index>>2]>>(2*(index&3)))&3;
    if (code != 3) return code;
    return full_array[index];
}

, где bmap использует 2 бита на элемент со значением 3, означающим «другое».

Эта структура тривиальна для обновления, использует на 25% больше памяти, нобольшая часть просматривается только в 5% случаев.Конечно, как обычно, если это хорошая идея или нет, зависит от множества других условий, поэтому единственный ответ - экспериментировать с реальным использованием.

Answer 10

В прошлом я использовал хеш-карту в front набора битов.

Это вдвое меньше пробела по сравнению с ответом Маттео, но может быть медленнее, если поиск по «исключениям» идет медленно (т. Е. Есть много исключений).

Однако часто «кеш - король».