Comments / Profile of notorca / Habr

HISTORY
The gzip program was originally written by Jean-loup Gailly, licensed under the GNU Public Licence.
Matthew R. Green wrote a simple front end for NetBSD 1.3 distribution media, based on the freely re-distributable redistributable
distributable zlib library. It was enhanced to be mostly feature-compatible with the original GNU gzip
program for NetBSD 2.0.

This implementation of gzip was ported based on the NetBSD gzip, and first appeared in FreeBSD 7.0.

~ uname
Darwin
~ gzip --version
Apple gzip 264.50.1

lorca@defaultvps:$ uname 
Linux
lorca@defaultvps:$ gzip --version
gzip 1.6
Copyright (C) 2007, 2010, 2011 Free Software Foundation, Inc.
Copyright (C) 1993 Jean-loup Gailly.
This is free software.  You may redistribute copies of it under the terms of
the GNU General Public License <http://www.gnu.org/licenses/gpl.html>.
There is NO WARRANTY, to the extent permitted by law.

Written by Jean-loup Gailly.

Look

Быстрое удаление пробелов из строк на процессорах ARM — альтернативный анализ

notorca Jul 27 2017 at 19:40

Вот способ по скорости сопоставимый с версией использующей таблицу на 1Mb но без таблицы. Не очень простой для понимания, но быстрый и без дополнительной памяти

Look

Быстрое удаление пробелов из строк на процессорах ARM

notorca Jul 25 2017 at 18:01

Наконец руки дошли проверить на старом RaspberryPi c armv6(ARM1176JZ-S). Он не суперскалярный, single-issue и поэтому более короткий цикл там работает быстрее.

despace(buffer, N)                      :  9.34 ns per operation
despace_ptr(buffer, N)                  :  8.03 ns per operation

Примечательно так же то, что gcc 7.1.1 не сгенерировал оптимальный код, только clang 4. Gcc почему-то постеснялся использовать

strbhs     r1, [ip]!, #0x1

, а вместо этого сгенерировал 2 инструкции

strbhi     r3, [r2]
addhi      r2, r2, #0x1

Look

Быстрое удаление пробелов из строк на процессорах ARM

notorca Jul 18 2017 at 02:40

В первом варианте запись и сравнение не зависят друг от друга, а зависят только от ldrb. При этом strb из того же регистра, в который идет ldrb может начаться на такт раньше, чем другие инструкции, зависящие от этого регистра.

Во втором случае запись зависит от сравнения, и не может начинаться раньше, чем выполнилось сравнение, которое в свою очередь дожидается результата ldrb. Вот и вся разница, счетчик либо указатель тут не причем.

Оптимизированный вариант neon_despace_branchless не зависит от процента пробелов.

Look

Быстрое удаление пробелов из строк на процессорах ARM

notorca Jul 14 2017 at 01:20

Финальная расстановка точек. Тест на Cortex A7. Результаты по скорости:


despace(buffer, N)                      :  4.21 ns per operation
despace_ptr(buffer, N)                  :  5.25 ns per operation
neon_despace(buffer, N)                 :  3.33 ns per operation
neon_despace_branchless(buffer, N)      :  3.69 ns per operation

Где dspace это:

  size_t i = 0, pos = 0;
  while (i < howmany) {
    const char c = bytes[i++];
    bytes[pos] = c;
    pos += (c > 32 ? 1 : 0);
  }
  return pos;

dspace_ptr:

  char *i = bytes, *pos = bytes;
  const char *end = bytes + howmany;
  while (i < end) {
    register char c = *i++;
    if (c>' ') { *pos++ = c;}
  }
  return pos - bytes;

Как видно из результатов код с меньшим количеством инструкций выполняется медленнее. Подробное объяснение потянет на отдельную статью, но если кратко, то важно не только количество инструкций, но и зависимости между ними, и это то, что компилятор умеет выстраивать достаточно не плохо, если ему не мешать. Например на Cortex A7 пара ldr/str для одного и того же регистра выполняется столько же, сколько простой ldr.

Также

addhi      r0, r0, #0x1
subs       r1, r1, #0x1

выполнятся за 1 такт потому что поддерживается dual issue для инструкций читающих по одному регистру.

Вот так, примерно, будет выглядеть выполнение кода по тактам:

1 ldrb r2, [r3]!, #0x1

2 strb r2, [ip, r0]

3 cmp r2, #0x20

4 addhi r0, r0, #0x1

4 subs r1, r1, #0x1

5 bne loc_10554



1 ldrb r1, [r3]!, #0x1

3 cmp r1, #0x21

4 strbhs r1, [ip]!, #0x1

5 cmp r3, r2

6 blo loc_10584

Дизассемблер

Выводы.

Оригинальная функция из статьи написана оптимальным образом
Не надо мешать компилятору оптимизировать код
Оптимизация с использованием NEON имела смысл

Look

Быстрое удаление пробелов из строк на процессорах ARM

notorca Jul 13 2017 at 13:11

Мне кажется что на Cortex A15 не будет разницы по скорости выполнения межу strhib r2, [ip], #1 и strhib r2, [ip]; addhi ip, ip, #1. А на Cortex A7 скорее всего будет, это я чуть позже проверю.

В ARM64 больше нету условного выполнения каждой инструкции, есть b, и csel.

Look

Быстрое удаление пробелов из строк на процессорах ARM

notorca Jul 11 2017 at 13:37

Вот для arm с gcc. 9я строчка, strb ip, [r0, r3], одна команда адресации со смещением.

Вот arm64, 11я строчка csinc для примера из статьи и 49я csel и 45я mov для if.

Look

Быстрое удаление пробелов из строк на процессорах ARM

notorca Jul 10 2017 at 20:36

Вышло продолжение статьи

Look

Быстрое удаление пробелов из строк на процессорах ARM

notorca Jul 10 2017 at 19:28

Вариант из статьи на x86_64 тоже будет оптимальнее на многих компиляторах. Только для варианта из статьи clang 4.0 дополнительно развернул цикл

Look

Быстрое удаление пробелов из строк на процессорах ARM

notorca Jul 10 2017 at 19:09

На обычном ARM индексирование тоже не стоит времени. LDR (register offset). Последний вариант чуть быстрее, но все еще хуже способа из статьи.
despace(buffer, N): 0.79 ns per operation
despace3(buffer, N): 1.19 ns per operation

if вместо тернарного оператора генерирует код через csel + move вместо csinc, что делает цикл на одну инструкцию больше (7 vs 6). Вообще заменять работу с массивами и индексами на указатели — только мешать компилятору оптимизировать.

Look

Быстрое удаление пробелов из строк на процессорах ARM

notorca Jul 10 2017 at 13:51

Поскольку в статье речь идет об arm64 то и скорость я сравнивал на arm64.
Вот результаты:
despace(buffer, N): 0.79 ns per operation
despace2(buffer, N): 1.40 ns per operation
1) Превращение индекса в указатель занимает 0 инструкции (ldrsb w10, [x9], #0x1)
2) Безусловная запись быстрее чем условная, т.к. нет лишнего условного перехода.
3) Проверка генерирует дополнительный условный переход. в то время как тернарный оператор дает одну безусловную инструкцию cinc x0, x0, gt.
В итоге во втором варианте больше ветвлений, которые портят конвейер.

Вот картинки из дизассемблера