Обобщение кода Radix Sort uint64_t от 32 бит MSB и 48 бит MSB до 40 бит сортировки MSB - PullRequest
Новая
       41

Обобщение кода Radix Sort uint64_t от 32 бит MSB и 48 бит MSB до 40 бит сортировки MSB

1 голос
/ 04 февраля 2020

Можно ли обобщить этот код сортировки Radix для просмотра только 40 старших значащих битов данных uint64_t?

Обобщение 32-битного кода сортировки от пользователя RGCLGR на 48 и 64 бита и сравнение сортировки uint64_t [36M] для 64, 48 и 32 бит: 

Time=  3.130 sec = 20.342%, RADIX_SORT_UINT64_REG, hits=4, 0.782 sec each
Time=  2.336 sec = 15.180%, RADIX_SORT_UINT64_48R, hits=4, 0.584 sec each
Time=  1.540 sec = 10.007%, RADIX_SORT_UINT64_32R, hits=4, 0.385 sec each

Это подтверждает ожидаемую линейность между отсортированными битами и временем сортировки.

Мне нужно отсортировать сотни uint64_t [] только по 34 наиболее значимым битам. Сортировка с 48 старшими битами работает, но сортировка только по 40 битам занимает ~ 5/6. Это может сократить время 58-секундной нагрузки до 48-секундного испытания для пользователя.

Разница между кодом 32-разрядного MSB и кодом 48-разрядного MS в основном незначительная вариация, за исключением одного кодового сегмента:

сортировка по основному сегменту 32-битового кода mIndex [0, 1, 2, 3] : 

for (i = 0; i < count; i++) {       /* radix sort */
    u = pData[i];
    pTemp[mIndex[3][(u >> 32) & 0xff]++] = u;
}
for (i = 0; i < count; i++) {
    u = pTemp[i];
    pData[mIndex[2][(u >> 40) & 0xff]++] = u;
}
for (i = 0; i < count; i++) {
    u = pData[i];
    pTemp[mIndex[1][(u >> 48) & 0xff]++] = u;
}
for (i = 0; i < count; i++) {
    u = pTemp[i];
    pData[mIndex[0][(u >> 56) & 0xff]++] = u;
}

48-битный сегмент добавляет этот код для обработки mIndex [4, 5]: 

for (i = 0; i < count; i++) {       /* radix sort */
    u = pData[i];
    pTemp[mIndex[5][(u >> 16) & 0xff]++] = u;
}
for (i = 0; i < count; i++) {       
    u = pTemp[i];
    pData[mIndex[4][(u >> 24) & 0xff]++] = u;
}

Преобразование в полную 64-битную сортировку добавляет аналогичный код для работы с матричными индексами [ 6, 7]

Можно ли даже добавить mIndex [4] для создания сортировки 40 MSB?
Массив pData используется с четными индексами mIndex.
Массив pTemp используется с нечетным Индексы mIndex.

Этот метод ограничен обобщением только для четного числа байтов?

======================== ==========

Полный код для сортировки uint64 [] по 32 старшим значащим битам: 

// From code submitted by on stackoverflow.com rcgldr, Nov 3 2017
void radix_sort_r64_32(uint64_t *pData, uint64_t *pTemp, size_t count,    
EV_TIME_STR *tsa)
{
    size_t mIndex[4][256] = { 0 };      /* index matrix */
size_t * pmIndex;                   /* ptr to row of matrix */
size_t i, j, m, n;
uint64_t u;
if(tsa)  time_event(E_RADIX_SORT_UINT64_32R, tsa, E_TIME_EVENT, 1, 0);  

for (i = 0; i < count; i++) {       /* generate histograms */
    u = pData[i];
    mIndex[3][(u >> 32) & 0xff]++;
    mIndex[2][(u >> 40) & 0xff]++;
    mIndex[1][(u >> 48) & 0xff]++;
    mIndex[0][(u >> 56) & 0xff]++;
}

for (j = 0; j < 4; j++) {           /* convert to indices */
    pmIndex = mIndex[j];
    n = 0;
    for (i = 0; i < 256; i++) {
        m = pmIndex[i];
        pmIndex[i] = n;
        n += m;
    }
}

for (i = 0; i < count; i++) {       /* radix sort */
    u = pData[i];
    pTemp[mIndex[3][(u >> 32) & 0xff]++] = u;
}
for (i = 0; i < count; i++) {
    u = pTemp[i];
    pData[mIndex[2][(u >> 40) & 0xff]++] = u;
}
for (i = 0; i < count; i++) {
    u = pData[i];
    pTemp[mIndex[1][(u >> 48) & 0xff]++] = u;
}
for (i = 0; i < count; i++) {
    u = pTemp[i];
    pData[mIndex[0][(u >> 56) & 0xff]++] = u;
}
}  // End Radix_Sort_R64_32().

========== ============

И разница между 32-битной и 48-битной версиями сортировки: 

diff ~/tmp/radix.sort.32.c    ~/tmp/radix.sort.48.c
< < void radix_sort_r64_32(uint64_t *pData, uint64_t *pTemp, size_t count,
< ---
< > void radix_sort_r64_48(uint64_t *pData, uint64_t *pTemp, size_t count,
< 
< <     size_t mIndex[4][256] = { 0 };      /* index matrix */
< ---
< >     size_t mIndex[6][256] = { 0 };      /* index matrix */
< 
< <       if(tsa)  time_event(E_RADIX_SORT_UINT64_32R, tsa, E_TIME_EVENT, 1, 0);  
< ---
< >       if(tsa)  time_event(E_RADIX_SORT_UINT64_48R, tsa, E_TIME_EVENT, 1, 0);  
< 
< ---
< >         mIndex[5][(u >> 16) & 0xff]++;  // B2
< >         mIndex[4][(u >> 24) & 0xff]++;  // B3
< 
< <     for (j = 0; j < 4; j++) {           /* convert to indices */
< ---
< >     for (j = 0; j < 6; j++) {           /* convert to indices */
< 
< >         pTemp[mIndex[5][(u >> 16) & 0xff]++] = u;
< >     }
< >     for (i = 0; i < count; i++) {       /* radix sort */
< >         u = pTemp[i];
< >         pData[mIndex[4][(u >> 24) & 0xff]++] = u;
< >     }
< >     for (i = 0; i < count; i++) {       /* radix sort */
< >         u = pData[i];
< 44c56
< < }  // End Radix_Sort_R64_32().
< ---
< > }  // End Radix_Sort_R64_48().

Краткое описание уникальных различий: 

Unique lines from "~/tmp/radix.sort.32.c":
  02) void radix_sort_r64_32(uint64_t *pData, uint64_t *pTemp, size_t count,
  05) size_t mIndex[4][256] = { 0 };      /* index matrix */
  19) for (j = 0; j < 4; j++) {           /* convert to indices */

Unique lines from "~/tmp/radix.sort.48.c":
  01) void radix_sort_r64_48(uint64_t *pData, uint64_t *pTemp, size_t count,
  04) size_t mIndex[6][256] = { 0 };      /* index matrix */
  14) mIndex[5][(u >> 16) & 0xff]++;  // B2
  15) mIndex[4][(u >> 24) & 0xff]++;  // B3
  22) for (j = 0; j < 6; j++) {           /* convert to indices */
  34) pTemp[mIndex[5][(u >> 16) & 0xff]++] = u;
  38) pData[mIndex[4][(u >> 24) & 0xff]++] = u;
...