Эффективное суммирование N массивов байтов - PullRequest
Новая
       22

Эффективное суммирование N массивов байтов

0 голосов
/ 06 мая 2019

Ниже приведен код для визуализации того, что необходимо сделать. Я ищу решение, которое может сделать это быстрее. Один из них - суммирование массивов с использованием битовых манипуляций (https://stackoverflow.com/a/55945544/4791668).. Интересно, есть ли способ сделать это способом, описанным в ссылке, и одновременно найти среднее значение. 

    var random = new Random();
    byte[] bytes = new byte[20_000_000]; 
    byte[] bytes2 = new byte[20_000_000];

    for (int i = 0; i < bytes.Length; i++)
    {
        bytes[i] = (byte)random.Next(255);
    }

    for (int i = 0; i < bytes.Length; i++)
    {
        bytes2[i] = (byte)random.Next(255);
    }

    //how to optimize the part below
    for (int i = 0; i < bytes.Length; i++)
    {
        bytes[i] = (byte)((bytes[i] + bytes2[i]) / 2);
    }

/////////// Решение, которое необходимо улучшить. Это не делает среднюю часть. 

    var random = new Random();
    byte[] bytes = new byte[20_000_000]; 
    byte[] bytes2 = new byte[20_000_000];

    int Len = bytes.Length >> 3; // >>3 is the same as / 8

    ulong MASK =    0x8080808080808080;
    ulong MASKINV = 0x7f7f7f7f7f7f7f7f;

    //Sanity check
    if((bytes.Length & 7) != 0) throw new Exception("bytes.Length is not a                 multiple of 8");
    if((bytes2.Length & 7) != 0) throw new Exception("bytes2.Length is not a multiple of 8");

    unsafe
    {
//Add 8 bytes at a time, taking into account overflow between bytes
       fixed (byte* pbBytes = &bytes[0])
       fixed (byte* pbBytes2 = &bytes2[0])
       {
          ulong* pBytes = (ulong*)pbBytes;
          ulong* pBytes2 = (ulong*)pbBytes2;
          for (int i = 0; i < Len; i++)
          {
            pBytes[i] = ((pBytes2[i] & MASKINV) + (pBytes[i] & MASKINV)) ^ ((pBytes[i] ^ pBytes2[i]) & MASK);
          } 
       }        
    }

1 Ответ

0 голосов
/ 07 мая 2019

Используя битовую манипуляцию, вы можете вычислить среднее значение байтов параллельно: 

ulong NOLOW = 0xfefefefefefefefe;
unsafe {
    //Add 8 bytes at a time, taking into account overflow between bytes
    fixed (byte* pbBytes = &bytes[0])
    fixed (byte* pbBytes2 = &bytes2[0])
    fixed (byte* pbAns2 = &ans2[0]) {
        ulong* pBytes = (ulong*)pbBytes;
        ulong* pBytes2 = (ulong*)pbBytes2;
        ulong* pAns2 = (ulong*)pbAns2;
        for (int i = 0; i < Len; i++) {
            pAns2[i] = (pBytes2[i] & pBytes[i]) + (((pBytes[i] ^ pBytes2[i]) & NOLOW) >> 1);
        }
    }
}

Я изменил код для хранения в отдельном массиве байтов ans, так как мне нужны исходные массивы для сравнениядва метода.Очевидно, что вы можете сохранить исходное значение bytes[], если хотите.

Это основано на следующей формуле: x+y == (x&y)+(x|y) == (x&y)*2 + (x^y) == (x&y)<<1 + (x^y), что означает, что вы можете вычислить (x+y)/2 == (x&y)+((x^y) >> 1).Поскольку мы знаем, что мы вычисляем 8 байтов за раз, мы можем замаскировать бит младшего разряда из каждого байта, поэтому мы сдвигаем бит 0 для старшего бита каждого байта, когда мы сдвигаем все 8 байтов.

На моем ПК это работает в 2–3 раза быстрее (в 2 раза для более длинных массивов), чем сумма (в байтах).

...