Почему скорость битовых операций отличается в 1000 раз?

Question

[floppa322]

В данном цикле для каждого из элементов исходного массива, каждый бит байта этого массива засисывается в переменную bit 2-мя разными способами, отличие в скорости примерно в 1000 раз. Моё предположение заключается в том, что массив MASKS вытесняется из кэша процессора (что маловероятно), в то время, как переменная MASK - нет. Есть ли у кого-то ещё какие-либо предположения, в чём дело ?

final byte[] MASKS =
        {
            (byte) 0b1000_0000, // 0
            (byte) 0b0100_0000, // 1
            (byte) 0b0010_0000, // 2
            (byte) 0b0001_0000, // 3
            (byte) 0b0000_1000, // 4
            (byte) 0b0000_0100, // 5
            (byte) 0b0000_0010, // 6
            (byte) 0b0000_0001, // 7
        };
final  byte MASK = (byte) 0b1000_0000;
int BYTE_COUNT = 2_000_000_000;

byte[] bytes = new byte[BYTE_COUNT];
byte bit;

double start = System.nanoTime();

for (int i = 0; i < BYTE_COUNT; ++i)
{
        byte currentByte = bytes[i];
         for (int j = 0; j < 8; ++j)
            {
                bit = (byte) (currentByte & MASKS[j]); // Elapsed time 6.2994273

//                bit = (byte) ((currentByte << j) & MASK); // Elapsed time 0.0054073
            }
}

double elapsedTime = (System.nanoTime() - start) / 1e9;
System.out.println("Elapsed time " + elapsedTime);

Comments

[Adamos]

Какое там невлезание в кэш, при таком-то размере данных?
Скорее компилятор просто выкинул за ненадобностью строчки с присвоением значений нигде больше не используемым переменным, а потом и оба опустевших цикла. Так что во втором случае вы просто получаете время отработки вызова nanoTime.

[floppa322]

Adamos, заменил последнюю строчку, чтобы не выкидывал

System.out.println("Elapsed time " + elapsedTime + ". Bit value " + bit);

Результаты 0.1656177 и 12.4750856 в пользу строчки, где используется битовый сдвиг. Всё равно разница почти в 100 раз

[floppa322]

Adamos, вообще, попробовал просто оставить строчку
bit = MASKS[j];

По времени получилось ~12 сек, т.е. +- то же

Answer 1

[Wataru]

Скорее всего, обращение к массиву тормозит. Там, видимо, еще и проверки на попадание в границы массива происходят.

Если вы место обращения к массиву будете делать currentByte & (1 << (7-j)), то должно работать почти также быстро.

P.s. и вообще у вас какой-то странный выбор порядка битов. Обычно сдвигают вправо, к младшему биту. Тогда вместо маски будет тупо 0x1.

Comments

[floppa322]

Ага, спасибо, нашёл
https://en.wikipedia.org/wiki/Bounds-checking_elim...

[floppa322]

В общем, переписал на С++, где нет этой проверки получилось

bit = currentByte & MASKS[j]; // Elapsed time = 2362 milliseconds.
bit = (currentByte << j) & MASK;  // Elapsed time = 2574 milliseconds.

Всё же вариант с предзаготовленными масками на каждый случай, без сдвига, оказался на 10% быстрее :)

[Wataru]

bakdurak, Я думаю, у вас от запуска к запуску погрешность будет больше этих несчастных 212ms.

[floppa322]

Wataru, там внешний цикл ещё есть, среднее считает ))

[Wataru]

bakdurak, И все равно. По-запускайте еще несколько раз, посмотрите, есть ли разброс.

[res2001]

bakdurak, Разверните вручную этот цикл for (int j = 0; j < 8; ++j)
Т.е. просто запишите 8 операций, маску указывайте константой, а не из массива и не сдвигом.
Это будет самый быстрый вариант, имхо.
Вообще компилятор может и сам это сделать, при каком-то уровне оптимизации, но тут не угадаешь.

PS: Что у вас в задаче этот участок кода настолько критичен? Я бы не стал заморачиваться с его оптимизацией в принципе - так как на одиночных операциях тут прирост производительности в оптимизированной версии мизерный.

[floppa322]

Wataru, в общем прогнал каждый раз по 10-15

uint8_t MASKS[] =
    {
        0b10000000, // 0
        0b01000000, // 1
        0b00100000, // 2
        0b00010000, // 3
        0b00001000, // 4
        0b00000100, // 5
        0b00000010, // 6
        0b00000001, // 7
    };
    uint8_t MASK = 0b10000000;
    int BYTE_COUNT = 60000000;
    int ROUND_COUNT = 10;

    uint8_t* bytes = new uint8_t [BYTE_COUNT];
    uint8_t bit = -1;

    double timeAccumulator = 0;
    for (int k = 0; k < ROUND_COUNT; ++k)
    {
        std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();

        for (int i = 0; i < BYTE_COUNT; ++i)
        {
            uint8_t currentByte = bytes[i];
            for (int j = 0; j < 8; ++j)
            {
//                bit = currentByte & MASKS[j]; // Elapsed time = 708.4 milliseconds. Bit value: ☺ (+- 6 millis)

                bit = (currentByte << j) & MASK;  // Elapsed time = 763.5 milliseconds. Bit value: А (+- 6 millis)
            }
        }

        std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();

        double timeMillis = std::chrono::duration_cast<std::chrono::milliseconds>(end - begin).count();
        timeAccumulator += timeMillis;
    }

    std::cout
            << "Elapsed time = "
            << timeAccumulator / ROUND_COUNT
            << " milliseconds. Bit value: "
            << bit
            << std::endl;

Всё же с предзаготовленными масками и без сдвига оплучается на 7-8% быстрее

[floppa322]

res2001, да нет, не критичен, просто изначально интересно стало откуда такая разница ). А в итоге оказалось, что она составляет около 10%

[Wataru]

bakdurak, Может тут в бенчмарке так и получается, из-за того, что все в кеше. Но вообще говоря, обращение к массиву должно быть медленнее сдвига. Вообще, качественные бенчмарки - дело сложное. По уму вам надо написать 2 функции и проверять их через, допустим, gbenchmark.

[res2001]

bakdurak, Кстати, есть шанс, что компилятор вообще выкинет цикл for (int j = 0; j < 8; ++j).
И оставит от него в лучшем случае последнюю итерацию. А если будет совсем молодец, то выкинет и верхний цикл то же.
По уму вам нужно делать bit += ..., что бы у компилятора не было повода что-то выкинуть из кода.

[floppa322]

Wataru, ну, вообще да, во-первых ему, когда он с массивом имеет дело, нужно вычислять оффсеты для него, а во-вторых, в нём данных в 8 раз больше, чем в той переменной, следовательно вероятность вытеснения из кэша больше

[floppa322]

res2001, я там поправил, теперь результат переменной bit в логировании в консоль используется, поэтому не должен выкинуть

[res2001]

bakdurak,

не должен выкинуть

Я читал коменты. Да там все верно написано.
Вот только в дополнение к написанному в bit у вас сейчас простое присваивание, а следовательно на выходе из цикла имеет значение только последняя итерация. Если я это увидел, то и компилятор то же увидет :)
И вывод переменной в конце тут не поможет - вам надо каким-то образом использовать значения всех итераций цикла bit += - самый простой вариант это сделать.

[floppa322]

res2001, а, ок, понял, чуть позже проверю