Сейчас на форуме: ManHunter, rmn, _MBK_, tyns777, UniSoft (+10 невидимых)

 eXeL@B —› Программирование —› fast_copy и fast_xor
Посл.ответ Сообщение

Ранг: 101.0 (ветеран), 344thx
Активность: 1.15↘0
Статус: Участник

 Создано: 19 апреля 2012 22:48
· Личное сообщение · #1

Приветствую сишников!

Есть вот такой код (написан мной):
Code:
  1. void table_fast_xor(unsigned int *table1, unsigned int *table2)
  2. {
  3.          unsigned int i;
  4.          // use pxor for xoring tables;
  5.          for (i = 0; i < 16; i++) {
  6.                  // cor 16 bytes
  7.                  _mm_store_si128(
  8.                         reinterpret_cast<__m128i *>(&table1[i * 4]),
  9.                         _mm_xor_si128(
  10.                               *reinterpret_cast<__m128i *>(&table1[i * 4]),
  11.                               *reinterpret_cast<__m128i *>(&table2[i * 4])
  12.                         )
  13.                  );
  14.          }
  15. }

На вход подаются две таблицы по 256 байт. Требуется запилить код, который как можно быстрее суммирует их между собой (понятное дело логическое сложние по модулю 2).

Правильно ли это решение с точки зрения скорости работы? Или обычный xor будет быстрее?

Есть и еще одна задача, инициализация таблицы из rainbow таблицы, но об этом позже.




Ранг: 533.6 (!), 232thx
Активность: 0.45↘0
Статус: Uploader
retired

 Создано: 19 апреля 2012 22:55
· Личное сообщение · #2

Эта ф-ия используется в каком-то большом цикле? Если нет, то и оптимизация не нужна.

-----
Лучше быть одиноким, но свободным © $me

Ранг: 101.0 (ветеран), 344thx
Активность: 1.15↘0
Статус: Участник

 Создано: 19 апреля 2012 22:59
· Личное сообщение · #3

Перебор 2^32 симметричных ключей армы, этап подготовки буффера для md5 хэша, используемого в качестве ключа для алгоритма TEA.

Запил rainbow таблиц на моем ноуте занимает 10 часов. Хочу полностью избавиться от всех операций умножения.



Ранг: 590.6 (!), 408thx
Активность: 0.36↘0.18
Статус: Модератор

 Создано: 19 апреля 2012 23:02
· Личное сообщение · #4

развернуть цикл и объявить функцию inline.

-----
старый пень

| Сообщение посчитали полезным: drone

Ранг: 101.0 (ветеран), 344thx
Активность: 1.15↘0
Статус: Участник

 Создано: 19 апреля 2012 23:24
· Личное сообщение · #5

r_e
Что-то типа такого?
Code:
  1. #define XOR_SI128(A, B, OFFSET) ( \
  2.          _mm_store_si128( \
  3.                  reinterpret_cast<__m128i *>(A + OFFSET), \
  4.                  _mm_xor_si128( \
  5.                         *reinterpret_cast<__m128i *>(A + OFFSET), \
  6.                         *reinterpret_cast<__m128i *>(B + OFFSET) \
  7.                  )))
  8. void __inline table_fast_xor(unsigned char *table1, unsigned char *table2)
  9. {
  10.          // use pxor for xoring tables;
  11.          XOR_SI128(table1, table2, 0);
  12.          XOR_SI128(table1, table2, 16);
  13.          XOR_SI128(table1, table2, 32);
  14.          XOR_SI128(table1, table2, 48);
  15.          XOR_SI128(table1, table2, 64);
  16.          XOR_SI128(table1, table2, 80);
  17.          XOR_SI128(table1, table2, 96);
  18.          XOR_SI128(table1, table2, 112);
  19.          XOR_SI128(table1, table2, 128);
  20.          XOR_SI128(table1, table2, 144);
  21.          XOR_SI128(table1, table2, 160);
  22.          XOR_SI128(table1, table2, 176);
  23.          XOR_SI128(table1, table2, 192);
  24.          XOR_SI128(table1, table2, 208);
  25.          XOR_SI128(table1, table2, 224);
  26.          XOR_SI128(table1, table2, 240);
  27. }

Ранг: 101.0 (ветеран), 344thx
Активность: 1.15↘0
Статус: Участник

 Создано: 20 апреля 2012 00:45
· Личное сообщение · #6

Теперь fast_copy:
Code:
  1. void copy_table(unsigned int *tmp_table, unsigned int *rnd_table, int index)
  2. {        
  3.          size_t count = 100000000 - index, remind_count;
  4.          if (count > 256) count = 256;
  5.          remind_count = 256 - count;
  6.          __m128i *dst = reinterpret_cast<__m128i *>(tmp_table);
  7.          __m128i *src = reinterpret_cast<__m128i *>(&rnd_table[index]);
  8.          while (count >= 16) {
  9.                  // fast memory copy
  10.                  *dst++ = *src++;
  11.                  count -= 16;
  12.          }
  13.          memcpy(reinterpret_cast<void *>(dst), reinterpret_cast<void *>(src), count);
  14.          if (remind_count) {
  15.                  dst = reinterpret_cast<__m128i *>(tmp_table + 256 - remind_count);
  16.                  src = reinterpret_cast<__m128i *>(&rnd_table[0]);
  17.                  while (remind_count >= 16) {
  18.                         // fast memory copy
  19.                         *dst++ = *src++;
  20.                         remind_count -= 16;
  21.                  }
  22.                  memcpy(reinterpret_cast<void *>(dst), reinterpret_cast<void *>(src), remind_count);
  23.          }
  24. }

Код явно плохой, но интересно услышать в какую сторону идти с позиции оптимизации.

Дело в том, что массив случайных чисел представляет собой циклическую группу. Хранится она в виде массива 0, rand(0), rand(rand(0)), ... Всего 100 000 000 значений. Нам нужно 256 последовательных чисел этого массива. Если же наш индекс указывает ближе к концу этого массива, получается что надо скопировать 256 - N чисел с конца массива и N чисел с начала массива. Таким образом имеем неизвестный размер блока (N может быть ноль в хорошем случае, или чем угодно в плохом).

Какие мысли?



Ранг: 20.8 (новичок), 7thx
Активность: 0.01↗0.02
Статус: Участник

 Создано: 20 апреля 2012 01:04 · Поправил: int_256
· Личное сообщение · #7

memcpy в последних реализациях использует xmm регистры --> Link <-- Смысла нет особо выдумывать свою реализацию memcpy



Ранг: 101.0 (ветеран), 344thx
Активность: 1.15↘0
Статус: Участник

 Создано: 20 апреля 2012 01:11
· Личное сообщение · #8

Специально глянул msvcr100 memcpy. Ни одной SSE инструкции.




Ранг: 337.6 (мудрец), 224thx
Активность: 0.21↘0.1
Статус: Участник
born to be evil

 Создано: 20 апреля 2012 01:30
· Личное сообщение · #9

int
http://fastcode.sourceforge.net/FastcodeFileDownloads/MoveBV941.zip

-----
От многой мудрости много скорби, и умножающий знание умножает печаль

Ранг: 101.0 (ветеран), 344thx
Активность: 1.15↘0
Статус: Участник

 Создано: 20 апреля 2012 01:54
· Личное сообщение · #10

ajax
Хороший код, только я задолбаюсь это в человеческий вид (в смысле "красивый" С) переводить. Но в принципе юзабельно. Логически получается, что чуть ли не единственный разумный вариант. Базируясь на размере блока определять switch'ом какую последовательность инструкций использовать. Учитывая, что максимальный размер блока не такой большой (256 двойных слов), можно переделать под конкретный рассматриваемый случай с развертыванием циклов. Хотя конечно, если кто знает готовый аналог на сях, хочется использовать его, чтобы не изобретать велосипед. Задача очень тривиальная.



Ранг: 101.0 (ветеран), 344thx
Активность: 1.15↘0
Статус: Участник

 Создано: 20 апреля 2012 02:38
· Личное сообщение · #11

Такой вариант еще сделал (на основе Duff's device):
Code:
  1. void fast_memory_copy(unsigned int *dest, unsigned int *source, unsigned long size)
  2. {
  3.          // each 4 points of size are 16 bytes
  4.          unsigned long reminder = size % 4;
  5.          // size in blocks of 16 bytes
  6.          size /= 4;
  7.          __m128i *dst = reinterpret_cast<__m128i *>(dest);
  8.          __m128i *src = reinterpret_cast<__m128i *>(source);
  9.          if (size) {
  10.                  // copy MMX (copy 16 bytes blocks)
  11.                  register unsigned long n = (size + 15) / 16;
  12.                  // copy up to 256 bytes in 1 step of loop
  13.                  switch (size % 16) {
  14.                  case 0:
  15.                         do {
  16.                         // copy 256 elements
  17.                         *dst++ = *src++;
  18.                  case 15:
  19.                         *dst++ = *src++;
  20.                  case 14:
  21.                         *dst++ = *src++;
  22.                  case 13:
  23.                         *dst++ = *src++;
  24.                  case 12:
  25.                         *dst++ = *src++;
  26.                  case 11:
  27.                         *dst++ = *src++;
  28.                  case 10:
  29.                         *dst++ = *src++;
  30.                  case 9:
  31.                         *dst++ = *src++;
  32.                  case 8:
  33.                         *dst++ = *src++;
  34.                  case 7:
  35.                         *dst++ = *src++;
  36.                  case 6:
  37.                         *dst++ = *src++;
  38.                  case 5:
  39.                         *dst++ = *src++;
  40.                  case 4:
  41.                         *dst++ = *src++;
  42.                  case 3:
  43.                         *dst++ = *src++;
  44.                  case 2:
  45.                         *dst++ = *src++;
  46.                  case 1:
  47.                         *dst++ = *src++;
  48.                         } while(--n > 0);
  49.                  }
  50.          }
  51.          int *d = reinterpret_cast<int *>(dst);
  52.          int *s = reinterpret_cast<int *>(src);
  53.          switch(reminder) {
  54.          case 3: *d++ = *s++;
  55.          case 2: *d++ = *s++;
  56.          case 1: *d++ = *s++;
  57.          default: break;
  58.          }
  59. }

P.S. Не проверял ни правильность, ни скорость... Как проверю, отпишусь.




Ранг: 1053.6 (!!!!), 1078thx
Активность: 1.06↘0.81
Статус: Участник

 Создано: 20 апреля 2012 02:58 · Поправил: reversecode
· Личное сообщение · #12

вагон
http://www.gamedev.net/topic/474646-memcpy-using-sse-in-linux/
http://files.rsdn.ru/23380/AMD_block_prefetch_paper.pdf
http://www.gamedev.ru/code/forum/?id=17661&page=2
http://exelab.ru/f/action=vthread&forum=6&topic=15816&page=0
http://www.gamedev.ru/code/forum/?id=62849&page=2

и еще докучи
http://www.hackchina.com/en/r/201332/dmemcpy.cpp__html
https://community.cablelabs.com/svn/OCAPRI/trunk/ri/RI_Stack/thirdparty/DirectFB/src/misc/memcpy.c

а еще лучше компилять Intel C++ Compiler, он умеет оптимизировать



Ранг: 101.0 (ветеран), 344thx
Активность: 1.15↘0
Статус: Участник

 Создано: 20 апреля 2012 03:20
· Личное сообщение · #13

Свою реализацию постом выше исправил (в первой версии ошибка при size < 4), но в итоге возьму вариант MMX от Волка.



Ранг: 72.1 (постоянный), 30thx
Активность: 0.05↘0
Статус: Участник

 Создано: 20 апреля 2012 09:03
· Личное сообщение · #14

Господа, все это замечательно, но по-моему или ассемблер и скорость, или С++ и мучительная оптимизация.



Ранг: 85.4 (постоянный), 51thx
Активность: 0.09↘0
Статус: Участник

 Создано: 20 апреля 2012 09:23
· Личное сообщение · #15

IIRC, были доки от amd по поводу оптимизации, так вот там обсуждались такие алгоритмы




Ранг: 164.6 (ветеран), 65thx
Активность: 0.12↘0
Статус: Участник
Волшебник

 Создано: 20 апреля 2012 10:31 · Поправил: neomant
· Личное сообщение · #16

А что за странные конструкции switch-case?
Не так ли красивше, да и правильнее?
Code:
  1. case 11:
  2. case 10:
  3. case 9:
  4. ...
  5. case 1:
  6.         *dst++ = *src++;

add:
Извиняюсь, не обратил внимания, что между case нет break.

-----
Следуй за белым кроликом

Ранг: 590.6 (!), 408thx
Активность: 0.36↘0.18
Статус: Модератор

 Создано: 20 апреля 2012 10:31
· Личное сообщение · #17

yagello
Для современной вычислительной техники и компиляторов ручная оптимизация имеет смысл когда счет идет на такты. Я так думаю что максимум что получит автор - 2-3% прирост по сравнению с выходом intel c++ opt compiler.

-----
старый пень

Ранг: 590.6 (!), 408thx
Активность: 0.36↘0.18
Статус: Модератор

 Создано: 20 апреля 2012 10:33
· Личное сообщение · #18

neomant
Duff's device - гугль в помощь

-----
старый пень

Ранг: 101.0 (ветеран), 344thx
Активность: 1.15↘0
Статус: Участник

 Создано: 20 апреля 2012 12:12
· Личное сообщение · #19

r_e пишет:
по сравнению с выходом intel c++ opt compiler
Я пока не знаю, что нужно сделать такого, чтобы intel cpp сожрал OpenMP директивы.



Ранг: 590.6 (!), 408thx
Активность: 0.36↘0.18
Статус: Модератор

 Создано: 20 апреля 2012 12:27
· Личное сообщение · #20

int
http://software.intel.com/en-us/articles/how-to-use-intelr-compiler-openmp-compatibility-libraries-on-windows/
?

-----
старый пень


Ранг: 1053.6 (!!!!), 1078thx
Активность: 1.06↘0.81
Статус: Участник

 Создано: 20 апреля 2012 14:03
· Личное сообщение · #21

drone пишет:
IIRC, были доки от amd по поводу оптимизации, так вот там обсуждались такие алгоритмы
reversecode пишет:
http://files.rsdn.ru/23380/AMD_block_prefetch_paper.pdf

| Сообщение посчитали полезным: Dart Sergius


Ранг: 1131.7 (!!!!), 447thx
Активность: 0.67↘0.2
Статус: Участник

 Создано: 22 апреля 2012 06:43
· Личное сообщение · #22

reversecode пишет:
а еще лучше компилять Intel C++ Compiler, он умеет оптимизировать

Угу, умеет.

| Сообщение посчитали полезным: SReg
 eXeL@B —› Программирование —› fast_copy и fast_xor
:: Ваш ответ
Жирный  Курсив  Подчеркнутый  Перечеркнутый  {mpf5}  Код  Вставить ссылку 
:s1: :s2: :s3: :s4: :s5: :s6: :s7: :s8: :s9: :s10: :s11: :s12: :s13: :s14: :s15: :s16:


Максимальный размер аттача: 500KB.
Ваш логин: german1505 » Выход » ЛС
   Для печати Для печати