Arhn - архитектура программирования

Самый быстрый способ преобразовать 8 последовательных байтов в полубайты (закодированные в 32-битное целое число)

Байты без знака, и все они меньше 16, поэтому их можно поместить в откусывание. В настоящее время я перемещаю байты в цикле и & их с помощью 0xf:

pub fn compress(offsets: [u8; 8]) -> u32 {
    let mut co: u32 = 0;

    for (i, o) in offsets.iter().enumerate() {
        co |= ((*o as u32) & 0xf ) << (i * 4);
    }
    co
}

Компилятор уже сделал хорошую оптимизацию:

https://godbolt.org/z/NEpC64

Но, может быть, можно немного покрутить или использовать SIMD-команды с u64, чтобы уменьшить количество операций?

rust bit-manipulation
10.12.2019

Ответы:


1

С ящиком bitintr вы можете использовать pext:

bitintr::bmi2::pext(x, 0x0f0f0f0f0f0f0f0f)

Однако это быстро только на процессорах Intel. AMD Ryzen реализует BMI2, но его pext работает очень медленно.

Вот альтернатива только с нормальным кодом:

pub fn compress(offsets: [u8; 8]) -> u32 {
    let mut x = u64::from_le_bytes(offsets);
    x = (x | (x >> 4)) & 0x00FF00FF00FF00FF;
    x = (x | (x >> 8)) & 0x0000FFFF0000FFFF;
    x = (x | (x >> 16));
    x as u32
}

Шаги делают это:

start:         0x0a0b0c0d0e0f0g0h
x | (x >> 4):  0x0aabbccddeeffggh
& mask:        0x00ab00cd00ef00gh
x | (x >> 8):  0x00ababcdcdefefgh
& mask:        0x0000abcd0000efgh
x | (x >> 16): 0x0000abcdabcdefgh
as u32:                0xabcdefgh
10.12.2019
  • Ваш нормальный код прекрасен, и мне нравится иллюстрация шагов, чтобы увидеть, как биты перетекают из одной позиции в другую. 10.12.2019
  • Действительно ли любой из них быстрее, чем то, что предоставил OP? В вопросе требуется самое быстрое решение, поэтому я ожидаю увидеть какой-нибудь тест, подтверждающий неявное утверждение, что они быстрые (или, по крайней мере, быстрее). 10.12.2019
  • @Shepmaster pext - это 3-тактная инструкция на Intel, по сути непревзойденная, пока не появится более специализированная инструкция. А вот на AMD плохо. Это также опровергает существование самого быстрого способа сделать это: относительные скорости различных подходов зависят от аппаратного обеспечения. Так что, если мы буквально воспримем название ОП, ответа нет. 10.12.2019
  • Спасибо, решения, по крайней мере, намного короче (относительно количества инструкций кода операции) 11.12.2019
  • Было бы еще интересно, если реализация AMD pext быстрее, чем независимая от архитектуры версия, есть ли дополнительная информация о том, как она реализована? К сожалению, у меня нет процессора AMD для этого. 11.12.2019
  • @PhilippMildenberger Согласно тестам, проведенным uops_info, это похоже на микрокодированный цикл, основанный на битах маски. , генерируя 8 мкопераций на установленный бит, что требует около 4,5 дополнительных циклов на установленный бит (также есть некоторые накладные расходы, поэтому маска = 0 уже медленная, и могут возникать дробные циклы, потому что это обратная пропускная способность). Я тоже не могу это проверить, но по оценке 32 бита должно быть около 145-150 циклов. Это более чем в десять раз хуже, чем ваша оригинальная версия. 11.12.2019
    • Новые материалы
    Коллекции публикаций по глубокому обучению
    Последние пару месяцев я создавал коллекции последних академических публикаций по различным подполям глубокого обучения в моем блоге https://amundtveit.com - эта публикация дает обзор 25..
    Представляем: Pepita
    Фреймворк JavaScript с открытым исходным кодом Я знаю, что недостатка в фреймворках JavaScript нет. Но я просто не мог остановиться. Я хотел написать что-то сам, со своими собственными..
    Советы по коду Laravel #2
    1-) Найти // You can specify the columns you need // in when you use the find method on a model User::find(‘id’, [‘email’,’name’]); // You can increment or decrement // a field in..
    Работа с временными рядами спутниковых изображений, часть 3 (аналитика данных)
    Анализ временных рядов спутниковых изображений для данных наблюдений за большой Землей (arXiv) Автор: Рольф Симоэс , Жильберто Камара , Жильберто Кейрос , Фелипе Соуза , Педро Р. Андраде ,..
    3 способа решить квадратное уравнение (3-й мой любимый) -
    1. Методом факторизации — 2. Используя квадратичную формулу — 3. Заполнив квадрат — Давайте поймем это, решив это простое уравнение: Мы пытаемся сделать LHS,..
    Создание VR-миров с A-Frame
    Виртуальная реальность (и дополненная реальность) стали главными модными терминами в образовательных технологиях. С недорогими VR-гарнитурами, такими как Google Cardboard , и использованием..
    Демистификация рекурсии
    КОДЕКС Демистификация рекурсии Упрощенная концепция ошеломляющей О чем весь этот шум? Рекурсия, кажется, единственная тема, от которой у каждого начинающего студента-информатика..