Оптимизация переупорядочения битов

Question

У меня есть функция C# ядра, которую я пытаюсь ускорить. Предложения, касающиеся безопасного или небезопасного кода, одинаково приветствуются. Вот метод:

public byte[] Interleave(uint[] vector) 
{ 
    var byteVector = new byte[BytesNeeded + 1]; // Extra byte needed when creating a BigInteger, for sign bit. 
    foreach (var idx in PrecomputedIndices) 
    { 
     var bit = (byte)(((vector[idx.iFromUintVector] >> idx.iFromUintBit) & 1U) << idx.iToByteBit); 
     byteVector[idx.iToByteVector] |= bit; 
    } 
    return byteVector; 
} 

PrecomputedIndices представляет собой массив из следующего класса:

class Indices 
{ 
    public readonly int iFromUintVector; 
    public readonly int iFromUintBit; 
    public readonly int iToByteVector; 
    public readonly int iToByteBit; 

    public Indices(int fromUintVector, int fromUintBit, int toByteVector, int toByteBit) 
    { 
     iFromUintVector = fromUintVector; 
     iFromUintBit = fromUintBit; 
     iToByteVector = toByteVector; 
     iToByteBit = toByteBit; 
    } 
} 

Целью метода Interleave является копирование бит из массива uints в массив байтов. Я предварительно вычислил индекс источника и целевого массива, а также номер источника и целевого бита и сохранил их в объектах индексов. Ни один из двух соседних битов в источнике не будет смежным в целевом объекте, чтобы исключить определенные оптимизации. Чтобы дать вам представление о масштабе, проблема, над которой я работаю, имеет около 4200 измерений, поэтому «вектор» имеет 4 200 элементов. Значения в векторе варьируются от нуля до двенадцати, поэтому мне нужно использовать только четыре бита для хранения их значений в массиве байтов, поэтому мне нужно 4,200 х 4 = 16 800 бит данных или 2,100 байта вывода на вектор. Этот метод будет называться миллионы раз. Он потребляет примерно треть времени в большей процедуре, которую мне нужно оптимизировать.

ОБНОВЛЕНИЕ 1: изменение «указателей» на структуру и сжатие нескольких типов данных, так что объект был всего лишь восемью байтами (int, короткий и два байта) уменьшил процент времени выполнения от 35% до 30%.

Answer 1

Этих важные части моего пересмотренным реализации идея почерпнутой из комментаторов:

1) Преобразования объекта структуры, термоусадочные типов данных для небольших Интсов, и переставляет так, что объект должен соответствовать в 64 -битных значение, которое лучше для 64-битной машине:

struct Indices 
{ 
    /// <summary> 
    /// Index into source vector of source uint to read. 
    /// </summary> 
    public readonly int iFromUintVector; 

    /// <summary> 
    /// Index into target vector of target byte to write. 
    /// </summary> 
    public readonly short iToByteVector; 

    /// <summary> 
    /// Index into source uint of source bit to read. 
    /// </summary> 
    public readonly byte iFromUintBit; 

    /// <summary> 
    /// Index into target byte of target bit to write. 
    /// </summary> 
    public readonly byte iToByteBit; 

    public Indices(int fromUintVector, byte fromUintBit, short toByteVector, byte toByteBit) 
    { 
     iFromUintVector = fromUintVector; 
     iFromUintBit = fromUintBit; 
     iToByteVector = toByteVector; 
     iToByteBit = toByteBit; 
    } 
} 

2) сортировать PrecomputedIndices так, что я пишу каждый целевой байт и бит в порядке возрастания, что улучшает доступ кэш-памяти:

Comparison<Indices> sortByTargetByteAndBit = (a, b) => 
    { 
     if (a.iToByteVector < b.iToByteVector) return -1; 
     if (a.iToByteVector > b.iToByteVector) return 1; 
     if (a.iToByteBit < b.iToByteBit) return -1; 
     if (a.iToByteBit > b.iToByteBit) return 1; 
     return 0; 
    }; 
    Array.Sort(PrecomputedIndices, sortByTargetByteAndBit); 

3) Unroll петли так, чтобы в целом целевые байты собраны на один раз, уменьшая количество раз, получить доступ к целевому массиву:

public byte[] Interleave(uint[] vector) 
{ 
    var byteVector = new byte[BytesNeeded + 1]; // An extra byte is needed to hold the extra bits and a sign bit for the BigInteger. 
    var extraBits = Bits - BytesNeeded << 3; 
    int iIndex = 0; 
    var iByte = 0; 
    for (; iByte < BytesNeeded; iByte++) 
    { 
     // Unroll the loop so we compute the bits for a whole byte at a time. 
     uint bits = 0; 
     var idx0 = PrecomputedIndices[iIndex]; 
     var idx1 = PrecomputedIndices[iIndex + 1]; 
     var idx2 = PrecomputedIndices[iIndex + 2]; 
     var idx3 = PrecomputedIndices[iIndex + 3]; 
     var idx4 = PrecomputedIndices[iIndex + 4]; 
     var idx5 = PrecomputedIndices[iIndex + 5]; 
     var idx6 = PrecomputedIndices[iIndex + 6]; 
     var idx7 = PrecomputedIndices[iIndex + 7]; 
     bits = (((vector[idx0.iFromUintVector] >> idx0.iFromUintBit) & 1U)) 
      | (((vector[idx1.iFromUintVector] >> idx1.iFromUintBit) & 1U) << 1) 
      | (((vector[idx2.iFromUintVector] >> idx2.iFromUintBit) & 1U) << 2) 
      | (((vector[idx3.iFromUintVector] >> idx3.iFromUintBit) & 1U) << 3) 
      | (((vector[idx4.iFromUintVector] >> idx4.iFromUintBit) & 1U) << 4) 
      | (((vector[idx5.iFromUintVector] >> idx5.iFromUintBit) & 1U) << 5) 
      | (((vector[idx6.iFromUintVector] >> idx6.iFromUintBit) & 1U) << 6) 
      | (((vector[idx7.iFromUintVector] >> idx7.iFromUintBit) & 1U) << 7); 
     byteVector[iByte] = (Byte)bits; 
     iIndex += 8; 
    } 
    for (; iIndex < PrecomputedIndices.Length; iIndex++) 
    { 
     var idx = PrecomputedIndices[iIndex]; 
     var bit = (byte)(((vector[idx.iFromUintVector] >> idx.iFromUintBit) & 1U) << idx.iToByteBit); 
     byteVector[idx.iToByteVector] |= bit; 
    } 
    return byteVector; 
} 

-Вырезать функцию от взятия до 35% от времени выполнения до 30% времени выполнения (экономия 14%).

2 Не ускоряйте функцию вверх, но допустимо # 3.

3 Отрежьте функцию от 30% времени исполнения до 19,6%, а еще 33% экономии.

Общая экономия: 44%!