c++ - компилятор - rust хабр




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

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

uint8_t MyArray[10000000];

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

  • 0 или 1 для 95% всех случаев,
  • 2 в 4% случаев,
  • от 3 до 255 в остальных 1% случаев?

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

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


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

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

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


Глядя на это, вы можете разделить ваши данные, например:

  • набор битов, который индексируется и представляет значение 0 (здесь было бы полезно использовать std :: vector)
  • набор битов, который индексируется и представляет значение 1
  • std :: vector для значений 2, содержащий индексы, которые ссылаются на это значение
  • карта для других значений (или std :: vector>)

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

Это сэкономит вам память для этого случая, хотя в худшем случае будет хуже. Вам также понадобится больше ресурсов процессора для поиска.

Обязательно измеряйте!


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

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


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

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

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


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

  • проверьте результат 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% случаев. Конечно, как обычно, если это хорошая идея или нет, зависит от множества других условий, поэтому единственный ответ - экспериментировать с реальным использованием.


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

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

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

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

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


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

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


Простая возможность, которая приходит на ум, - это сохранить сжатый массив из 2 битов на значение для общих случаев и разделенный 4 байта на значение (24 бита для индекса исходного элемента, 8 бит для фактического значения, поэтому (idx << 8) | value) ) отсортированный массив для остальных.

Когда вы ищите значение, вы сначала делаете поиск в массиве 2bpp (O (1)); если вы найдете 0, 1 или 2, это значение, которое вы хотите; если вы найдете 3, это означает, что вы должны искать его во вторичном массиве. Здесь вы выполните бинарный поиск, чтобы найти интересующий вас индекс, сдвинутый влево на 8 (O (log (n) с небольшим n, так как это должно быть 1%), и извлеките значение из 4- байт вещь

std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;

uint8_t lookup(unsigned idx) {
    // extract the 2 bits of our interest from the main array
    uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
    // usual (likely) case: value between 0 and 2
    if(v != 3) return v;
    // bad case: lookup the index<<8 in the secondary array
    // lower_bound finds the first >=, so we don't need to mask out the value
    auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
    // some coherency checks
    if(ptr == sec_arr.end()) std::abort();
    if((*ptr >> 8) != idx) std::abort();
#endif
    // extract our 8-bit value from the 32 bit (index, value) thingie
    return (*ptr) & 0xff;
}

void populate(uint8_t *source, size_t size) {
    main_arr.clear(); sec_arr.clear();
    // size the main storage (round up)
    main_arr.resize((size+3)/4);
    for(size_t idx = 0; idx < size; ++idx) {
        uint8_t in = source[idx];
        uint8_t &target = main_arr[idx>>2];
        // if the input doesn't fit, cap to 3 and put in secondary storage
        if(in >= 3) {
            // top 24 bits: index; low 8 bit: value
            sec_arr.push_back((idx << 8) | in);
            in = 3;
        }
        // store in the target according to the position
        target |= in << ((idx & 3)*2);
    }
}

Для такого массива, как тот, который вы предложили, для первого массива это должно быть 10000000/4 = 2500000 байт, плюс для второго массива 10000000 * 1% * 4 B = 400000 байт; следовательно, 2900000 байт, т. е. менее одной трети исходного массива, а наиболее часто используемая часть хранится в памяти вместе, что должно быть хорошо для кэширования (может даже соответствовать L3).

Если вам требуется более 24-битная адресация, вам нужно настроить «вторичное хранилище»; тривиальный способ его расширения состоит в том, чтобы иметь массив указателей из 256 элементов для переключения 8 верхних битов индекса и пересылки в 24-битный индексированный отсортированный массив, как указано выше.

Быстрый тест

#include <algorithm>
#include <vector>
#include <stdint.h>
#include <chrono>
#include <stdio.h>
#include <math.h>

using namespace std::chrono;

/// XorShift32 generator; extremely fast, 2^32-1 period, way better quality
/// than LCG but fail some test suites
struct XorShift32 {
    /// This stuff allows to use this class wherever a library function
    /// requires a UniformRandomBitGenerator (e.g. std::shuffle)
    typedef uint32_t result_type;
    static uint32_t min() { return 1; }
    static uint32_t max() { return uint32_t(-1); }

    /// PRNG state
    uint32_t y;

    /// Initializes with seed
    XorShift32(uint32_t seed = 0) : y(seed) {
        if(y == 0) y = 2463534242UL;
    }

    /// Returns a value in the range [1, 1<<32)
    uint32_t operator()() {
        y ^= (y<<13);
        y ^= (y>>17);
        y ^= (y<<15);
        return y;
    }

    /// Returns a value in the range [0, limit); this conforms to the RandomFunc
    /// requirements for std::random_shuffle
    uint32_t operator()(uint32_t limit) {
        return (*this)()%limit;
    }
};

struct mean_variance {
    double rmean = 0.;
    double rvariance = 0.;
    int count = 0;

    void operator()(double x) {
        ++count;
        double ormean = rmean;
        rmean     += (x-rmean)/count;
        rvariance += (x-ormean)*(x-rmean);
    }

    double mean()     const { return rmean; }
    double variance() const { return rvariance/(count-1); }
    double stddev()   const { return std::sqrt(variance()); }
};

std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;

uint8_t lookup(unsigned idx) {
    // extract the 2 bits of our interest from the main array
    uint8_t v = (main_arr[idx>>2]>>(2*(idx&3)))&3;
    // usual (likely) case: value between 0 and 2
    if(v != 3) return v;
    // bad case: lookup the index<<8 in the secondary array
    // lower_bound finds the first >=, so we don't need to mask out the value
    auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx<<8);
#ifdef _DEBUG
    // some coherency checks
    if(ptr == sec_arr.end()) std::abort();
    if((*ptr >> 8) != idx) std::abort();
#endif
    // extract our 8-bit value from the 32 bit (index, value) thingie
    return (*ptr) & 0xff;
}

void populate(uint8_t *source, size_t size) {
    main_arr.clear(); sec_arr.clear();
    // size the main storage (round up)
    main_arr.resize((size+3)/4);
    for(size_t idx = 0; idx < size; ++idx) {
        uint8_t in = source[idx];
        uint8_t &target = main_arr[idx>>2];
        // if the input doesn't fit, cap to 3 and put in secondary storage
        if(in >= 3) {
            // top 24 bits: index; low 8 bit: value
            sec_arr.push_back((idx << 8) | in);
            in = 3;
        }
        // store in the target according to the position
        target |= in << ((idx & 3)*2);
    }
}

volatile unsigned out;

int main() {
    XorShift32 xs;
    std::vector<uint8_t> vec;
    int size = 10000000;
    for(int i = 0; i<size; ++i) {
        uint32_t v = xs();
        if(v < 1825361101)      v = 0; // 42.5%
        else if(v < 4080218931) v = 1; // 95.0%
        else if(v < 4252017623) v = 2; // 99.0%
        else {
            while((v & 0xff) < 3) v = xs();
        }
        vec.push_back(v);
    }
    populate(vec.data(), vec.size());
    mean_variance lk_t, arr_t;
    for(int i = 0; i<50; ++i) {
        {
            unsigned o = 0;
            auto beg = high_resolution_clock::now();
            for(int i = 0; i < size; ++i) {
                o += lookup(xs() % size);
            }
            out += o;
            int dur = (high_resolution_clock::now()-beg)/microseconds(1);
            fprintf(stderr, "lookup: %10d µs\n", dur);
            lk_t(dur);
        }
        {
            unsigned o = 0;
            auto beg = high_resolution_clock::now();
            for(int i = 0; i < size; ++i) {
                o += vec[xs() % size];
            }
            out += o;
            int dur = (high_resolution_clock::now()-beg)/microseconds(1);
            fprintf(stderr, "array:  %10d µs\n", dur);
            arr_t(dur);
        }
    }

    fprintf(stderr, " lookup |   ±  |  array  |   ±  | speedup\n");
    printf("%7.0f | %4.0f | %7.0f | %4.0f | %0.2f\n",
            lk_t.mean(), lk_t.stddev(),
            arr_t.mean(), arr_t.stddev(),
            arr_t.mean()/lk_t.mean());
    return 0;
}

(код и данные всегда обновляются в моем Bitbucket)

Приведенный выше код заполняет массив элементов 10M случайными данными, распределенными как OP, указанными в их посте, инициализирует мою структуру данных и затем:

  • выполняет случайный поиск 10M элементов с моей структурой данных
  • делает то же самое через оригинальный массив.

(обратите внимание, что в случае последовательного поиска массив всегда выигрывает в огромной мере, так как это самый удобный для кеша поиск, который вы можете сделать)

Эти два последних блока повторяются 50 раз и синхронизируются; в конце вычисляются и печатаются среднее и стандартное отклонение для каждого типа поиска, а также ускорение (lookup_mean / array_mean).

Я скомпилировал приведенный выше код с помощью g ++ 5.4.0 ( -O3 -static , плюс некоторые предупреждения) в Ubuntu 16.04 и запустил его на некоторых машинах; большинство из них работают под управлением Ubuntu 16.04, некоторые из них более старые Linux, некоторые более новые Linux. Я не думаю, что ОС в этом случае должна быть актуальной.

            CPU           |  cache   |  lookup s)   |     array s)  | speedup (x)
Xeon E5-1650 v3 @ 3.50GHz | 15360 KB |  60011 ±  3667 |   29313 ±  2137 | 0.49
Xeon E5-2697 v3 @ 2.60GHz | 35840 KB |  66571 ±  7477 |   33197 ±  3619 | 0.50
Celeron G1610T  @ 2.30GHz |  2048 KB | 172090 ±   629 |  162328 ±   326 | 0.94
Core i3-3220T   @ 2.80GHz |  3072 KB | 111025 ±  5507 |  114415 ±  2528 | 1.03
Core i5-7200U   @ 2.50GHz |  3072 KB |  92447 ±  1494 |   95249 ±  1134 | 1.03
Xeon X3430      @ 2.40GHz |  8192 KB | 111303 ±   936 |  127647 ±  1503 | 1.15
Core i7 920     @ 2.67GHz |  8192 KB | 123161 ± 35113 |  156068 ± 45355 | 1.27
Xeon X5650      @ 2.67GHz | 12288 KB | 106015 ±  5364 |  140335 ±  6739 | 1.32
Core i7 870     @ 2.93GHz |  8192 KB |  77986 ±   429 |  106040 ±  1043 | 1.36
Core i7-6700    @ 3.40GHz |  8192 KB |  47854 ±   573 |   66893 ±  1367 | 1.40
Core i3-4150    @ 3.50GHz |  3072 KB |  76162 ±   983 |  113265 ±   239 | 1.49
Xeon X5650      @ 2.67GHz | 12288 KB | 101384 ±   796 |  152720 ±  2440 | 1.51
Core i7-3770T   @ 2.50GHz |  8192 KB |  69551 ±  1961 |  128929 ±  2631 | 1.85

Результаты ... смешанные!

  1. Вообще, на большинстве этих машин есть какое-то ускорение, или, по крайней мере, они на одном уровне.
  2. Два случая, когда массив действительно превосходит поиск «умной структуры», находятся на машинах с большим количеством кеша и не особенно занятыми: Xeon E5-1650 выше (кеш 15 МБ) - это машина ночной сборки, в настоящий момент довольно простаивающая; Xeon E5-2697 (кэш-память 35 МБ) - это машина для высокопроизводительных вычислений, в том числе и в свободное время. Это имеет смысл, оригинальный массив полностью помещается в их огромный кэш, поэтому компактная структура данных только добавляет сложности.
  3. На противоположной стороне «спектра производительности» - но там, где снова массив немного быстрее, есть скромный Celeron, который питает мой NAS; у него настолько мало кеша, что ни массив, ни «умная структура» не помещаются в нем вообще. Другие машины с достаточно маленьким кешем работают аналогично
  4. К Xeon X5650 следует относиться с некоторой осторожностью - это виртуальные машины на довольно загруженном сервере с двумя сокетами; вполне возможно, что, хотя номинально он имеет приличный объем кеша, во время теста он несколько раз вытесняется совершенно не связанными виртуальными машинами.

Я добавлю к ответу @ 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 МБ.

Комбинация этих двух использует приблизительно 3099 МБ. Используя эту технику, вы сэкономите в 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-битная векторная стратегия превосходит крошечное использование памяти, но это целая борьба за реализацию. Но если это может иметь значение между подгонкой кеша или нет, возможно, стоит попробовать.







memory-bandwidth