Важная информация
Показано с 1 по 7 из 7

Тема: Чтение из памяти в обратном порядке

  1. #1 Чтение из памяти в обратном порядке 
    Новичок
    Регистрация
    17.10.2015
    Сообщений
    6
    Сказал(а) спасибо
    0
    Поблагодарили 0 раз(а) в 0 сообщениях
    Представьте ситуацию: сравниваются два массива WORD. Количество элементов в массивах фиксировано и равно 16. Массивы могут находится в памяти совсем рядом, а могут быть разнесены на большое расстояние (до 2 Гб). Сравнение идёт не просто так, а:
    - 0-й элемент первого массива сравнивается с 31-м элементом второго;
    - 1-й эл. первого с 30-м эл. второго;
    - 2-й эл. первого с 29-м эл второго;
    - и т.д.
    Получается, что первый массив читается из ОЗУ по-порядку, а второй в обратном порядке.
    Если нужно не просто сравнить элемент первого массива с эл. второго, а ещё сначала как-то этот элемент преобразовать, то у процессора появляется возможность заранее подгрузить следующий эл. первого массива в кэш ещё до самой проверки. А вот со вторым массивом, как я понимаю, такого не может произойти, т.к. подгружаться заранее в кэш будут байты с больших адресов.

    Как заставить процессор загрузить в кэш весь второй массив сразу и даст ли это хоть какое-то ускорение выполнения?

    Ниже конкретный код, в котором эта ситуация возникает. Он отличается от описания выше, но в целом, смысл такой-же. В R11 и R12 адреса "массивов" (на самом деле адреса 256-битных переменных). Точки с запятой разделяют команды и не являются началом комментария.
    Код :
            MOV EAX,[R11+00] ; ROL EAX,16 ; XOR EAX,[R12+28] ; JNZ @N1neN2s1
            MOV EAX,[R11+04] ; ROL EAX,16 ; XOR EAX,[R12+24] ; JNZ @N1neN2s1
            MOV EAX,[R11+08] ; ROL EAX,16 ; XOR EAX,[R12+20] ; JNZ @N1neN2s1
            MOV EAX,[R11+12] ; ROL EAX,16 ; XOR EAX,[R12+16] ; JNZ @N1neN2s1
            MOV EAX,[R11+16] ; ROL EAX,16 ; XOR EAX,[R12+12] ; JNZ @N1neN2s1
            MOV EAX,[R11+20] ; ROL EAX,16 ; XOR EAX,[R12+08] ; JNZ @N1neN2s1
            MOV EAX,[R11+24] ; ROL EAX,16 ; XOR EAX,[R12+04] ; JNZ @N1neN2s1
            MOV EAX,[R11+28] ; ROL EAX,16 ; XOR EAX,[R12+00] ; JZ  @N1eqN2
    Ответить с цитированием  
     

  2. #2  
    Супер модератор Аватар для >Quiet Snow<
    Регистрация
    11.04.2011
    Адрес
    Планета земля
    Сообщений
    3,931
    Сказал(а) спасибо
    1,842
    Поблагодарили 982 раз(а) в 840 сообщениях
    Записей в блоге
    1
    Как заставить процессор загрузить в кэш весь второй массив сразу
    Как загрузить, хз, даст ли прирост - даст почти в два раза, а то и больше.
    Код в кеш загрузить можно, например попробуйте перед кодом jmp short на следующую инструкцию,
    это сбросит кеш инструкций(на новых процах хз, работает ли).
    Насчёт данных не знаю, сходите на WASM форум, почитайте там статейки матёрых, авось получится.
    И да, если найдёте решение - напишите сюда.
    Обучение прикладному программированию(по skype), качественно, недорого, 18+, вопросы в личку.
    «Если вы ничего не сделаете, я уверяю вас, ничего и не произойдёт» © Жак Фреско
    Ограниченно модерирую.
    Ответить с цитированием  
     

  3. #3  
    Новичок
    Регистрация
    17.10.2015
    Сообщений
    6
    Сказал(а) спасибо
    0
    Поблагодарили 0 раз(а) в 0 сообщениях
    Немного покопался с разных статьях. Нашёл информацию о том, что данных из ОЗУ в кэш загружаются обычно пачками по 64 байта, выровненными на 64. Если так, то код из первого поста никак не улучшить. Если второй массив весь умещается в такой выровненный на 64 блок из 64х байт, то при чтении последнего элемента массива, весь массив будет загружен в кэш. А если массив размазан на два блока, то в любом случае (для полного сравнения) придётся эти два блока загружать полностью из памяти.

    Зато удалось переделать код так, чтобы выиграть до 6.2% времени выполнения:
    Assembler Code:
    1.  
    2.         MOVAPS  XMM0,[R11]
    3.         MOVAPS  XMM1,[R12+$10]
    4.         pshufd  xmm0,xmm0,$4E
    5.         pshufhw xmm0,xmm0,$1B
    6.         pshuflw xmm0,xmm0,$1B
    7.         XORPS   xmm0,xmm1
    8.         PTEST   xmm0,xmm0
    9.         JNZ     @N1neN2s1
    10.         MOVAPS  XMM0,[R11+$10]
    11.         MOVAPS  XMM1,[R12]
    12.         pshufd  xmm0,xmm0,$4E
    13.         pshufhw xmm0,xmm0,$1B
    14.         pshuflw xmm0,xmm0,$1B
    15.         XORPS   xmm0,xmm1
    16.         PTEST   xmm0,xmm0
    17.         JZ      @N1eqN2
    18.   @N1neN2s1:                        // [R11]^s1 <> [R12]


    Выигрыш 6% получается только на массивах, которые по результату сравнения будут признаны эквивалентными. На случайно заполненных массивах разницы в скорости нет. На частично эквивалентных разница 0..6%
    Ответить с цитированием  
     

  4. #4  
    Супер модератор Аватар для >Quiet Snow<
    Регистрация
    11.04.2011
    Адрес
    Планета земля
    Сообщений
    3,931
    Сказал(а) спасибо
    1,842
    Поблагодарили 982 раз(а) в 840 сообщениях
    Записей в блоге
    1
    чтобы выиграть до 6.2% времени выполнения
    Это слабый выигрыш. Не похоже, что что-то там вообще кешируется. Если ваша прога и данные закешируются,
    вы гарантированно получите существенно большую производительность. Полтора-два раза на каких-либо
    "чистых" операциях.
    Обучение прикладному программированию(по skype), качественно, недорого, 18+, вопросы в личку.
    «Если вы ничего не сделаете, я уверяю вас, ничего и не произойдёт» © Жак Фреско
    Ограниченно модерирую.
    Ответить с цитированием  
     

  5. #5  
    Новичок
    Регистрация
    17.10.2015
    Сообщений
    6
    Сказал(а) спасибо
    0
    Поблагодарили 0 раз(а) в 0 сообщениях
    Потестил ещё на одной и той же паре "массивов" в цикле. В этом случае получается, что вся работа идёт только в кэше, а из памяти данные читаются 1 раз на первой итерации цикла.
    Выигрыш по времени:
    на паре эквивалентных массивов 51.5%
    на паре массивов, которые были эквивалентны, но в первом массиве инвертирован бит в 0-м или в 1-м элементе -11.1%
    =//= 2-м или в 3-м элементе 0.033%
    =//= 4-м или в 5-м элементе 15.9%
    =//= 6-м или в 7-м элементе 25.5%
    =//= 8-м или в 9-м элементе 34%
    =//= 10-м или в 11-м элементе 41%
    =//= 12-м или в 13-м элементе 46%
    =//= 14-м или в 15-м элементе 51.5%
    на случайно заполненных массивах 0.033%

    Честно говоря, не могу объяснить, почему на случайных выходит одинаковая скорость, а на инвертированном бите в 0-м или 1-м элементе выходит замедление. Вроде как должно одинаково получаться.
    Ответить с цитированием  
     

  6. #6  
    Супер модератор Аватар для >Quiet Snow<
    Регистрация
    11.04.2011
    Адрес
    Планета земля
    Сообщений
    3,931
    Сказал(а) спасибо
    1,842
    Поблагодарили 982 раз(а) в 840 сообщениях
    Записей в блоге
    1
    на паре эквивалентных массивов 51.5%
    Уже ближе к истине, во всех остальных случаях у вас судя по всему идут кеш промахи.
    Вообще от данных зависеть не должно. Если только исходя из них не происходит ветвления.

    В этом случае получается, что вся работа идёт только в кэше
    Как вы это определили?
    Обучение прикладному программированию(по skype), качественно, недорого, 18+, вопросы в личку.
    «Если вы ничего не сделаете, я уверяю вас, ничего и не произойдёт» © Жак Фреско
    Ограниченно модерирую.
    Ответить с цитированием  
     

  7. #7  
    Новичок
    Регистрация
    17.10.2015
    Сообщений
    6
    Сказал(а) спасибо
    0
    Поблагодарили 0 раз(а) в 0 сообщениях
    Цитата Сообщение от >Quiet Snow< Посмотреть сообщение
    Как вы это определили?
    Я конечно не на 100% уверен. Просто между чтениями из ОЗУ проходит совсем мало времени, исполняется мало инструкций. Незачем выгружать из кэша два сравниваемых массива.
    В первом варианте, когда получилось 6% я специально, чтобы уменьшить влияние кэша и сравнивать только методы сравнения, делал два массива "массивов" размером по 1000000*32 байта и сравнивал каждую пару по 1 разу. Если для моего процессора верно, что размер линии кэша 64 байта, то обращения к ОЗУ происходили 2x500000..2x500001 раз

    Цитата Сообщение от Алексей Смолин Посмотреть сообщение
    Честно говоря, не могу объяснить, почему на случайных выходит одинаковая скорость, а на инвертированном бите в 0-м или 1-м элементе выходит замедление. Вроде как должно одинаково получаться.
    Нашёл, почему так. Функция генерации случайных массивов заполняла их хоть и случайно, но наиболее приближённо к тому виду, который должен обрабатываться в программе. В 0-м и в 15-м элементах массивов все биты были выключены.
    Последний раз редактировалось Алексей Смолин; 10.11.2015 в 20:52.
    Ответить с цитированием  
     

Информация о теме
Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Похожие темы

  1. Загрузка DLL из памяти
    от stabud в разделе FreeBasic
    Ответов: 1
    Последнее сообщение: 05.01.2013, 12:57
  2. Получение памяти в DOS из COM программы.
    от Абадябер в разделе Assembler
    Ответов: 11
    Последнее сообщение: 28.11.2011, 21:51
  3. Ответов: 1
    Последнее сообщение: 03.06.2011, 04:15
Ваши права
  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •