Здравствуйте, tarkil, Вы писали:


Орлы из МС которе писали Шарп тоже думали над этим воросом. По началу тоже хотели отказаться от брэйка. Даже сделали альфу в которой он был не обязателньным. Но быстро поняли, что это дико мозолит глаза тем кто привык к классическому С-шному синтаксису и остановились на том, что брэйк должен быть обязательным (контролируется компилятором), том что пустые идущие друг за другом кейсы могут автоматически конкатенироваться и том, что ввели оператор goto case позволяющий перейти из конца одного кейса в начало другого.

Здравствуйте, FDSC, Вы писали:

FDS>Здравствуйте, MShura, Вы писали:

MS>>Между прочим есть еще более быстрые алгоритмы memcpy и memset, но они уже зависят от процессора, поскольку используют знания размеров кэша разных уровней.

FDS>Не буду спорить, точнее, соглашусь. Кстати, можно и через assembler написать с использованием строковых команд, тогда размер кэша знать не надо

Речь как раз не об этом.
Комманды типа rep stos(b)(d)(q) работают с памятью напрямую.
Чтобы ускорить процесс достаточно периодически обращаться к памяти чуть дальше, а затем продолжать процесс.
Крис Касперский писал, что он получал (разные) выигрыши на Intel и AMD, но это всегда были именно выигрыши по сравнению с тривиальным rep stos...

Здравствуйте, MShura, Вы писали:

MS>Речь как раз не об этом.
MS>Комманды типа rep stos(b)(d)(q) работают с памятью напрямую.
MS>Чтобы ускорить процесс достаточно периодически обращаться к памяти чуть дальше, а затем продолжать процесс.
MS>Крис Касперский писал, что он получал (разные) выигрыши на Intel и AMD, но это всегда были именно выигрыши по сравнению с тривиальным rep stos...


Крис Касперски ничего не понимает в компьтерах.

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, MShura, Вы писали:

MS>>В коде, который привел я, в среднем количество jump в 8 (!) раз меньше.
MS>>Цена jump в большинстве процессоров большая (даже на x86), а на некоторых ОЧЕНЬ большая, поэтому первый код работает существенно быстрее.

VD>Если только компилятор не умеет делать раскрутку цикла или использовать спец. инструкции процессора.

Кстати, компилятор не всегда делает раскрутку цикла, даже если умеет.

Количество операций перехода, насколько я понял, не в 8 раз меньше, а в 4 (если в среднем).

Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, MShura, Вы писали:

MS>>В коде, который привел я, в среднем количество jump в 8 (!) раз меньше.
MS>>Цена jump в большинстве процессоров большая (даже на x86), а на некоторых ОЧЕНЬ большая, поэтому первый код работает существенно быстрее.

VD>Если только компилятор не умеет делать раскрутку цикла или использовать спец. инструкции процессора.

Согласен.

На ранних процессорах TMS после комманды BD (branch delayed) до реального перехода можно было вставить три инструкции. На современных TMS эта задержка еще увеличилась.
И если в в основном цикле вся операция занимает одну инструкцию, то без специальных подсказок компилятору (что цикл выполняется всегда более 4 раз, что число повторений делится на 4 нацело и т.д.) получится нехилый overhead в 3-5 раз. Правда на сигнальных процессорах работа с циклами (особенно внутренними) обычно делается не через jump.

Здравствуйте, FDSC, Вы писали:

FDS>Здравствуйте, VladD2, Вы писали:

VD>>Здравствуйте, MShura, Вы писали:

MS>>>В коде, который привел я, в среднем количество jump в 8 (!) раз меньше.
MS>>>Цена jump в большинстве процессоров большая (даже на x86), а на некоторых ОЧЕНЬ большая, поэтому первый код работает существенно быстрее.

VD>>Если только компилятор не умеет делать раскрутку цикла или использовать спец. инструкции процессора.

FDS>Кстати, компилятор не всегда делает раскрутку цикла, даже если умеет.

FDS>Количество операций перехода, насколько я понял, не в 8 раз меньше, а в 4 (если в среднем).

Грубо количество переходов есть 1 + count/8

Здравствуйте, MShura, Вы писали:

FDS>>Количество операций перехода, насколько я понял, не в 8 раз меньше, а в 4 (если в среднем).

MS>Грубо количество переходов есть 1 + count/8

MS>>void* memset( void *dst,  int val,  size_t count )
MS>>{
MS>>  char* beg = (char*)dst;
MS>>  char* end = beg + count;
MS>>  switch (count & 7)
MS>>  {
MS>>  case 0: 
MS>>    while (beg != end)
MS>>    {
MS>>      *beg++ = (char)val;
MS>>  case 7: *beg++ = (char)val;
MS>>  case 6: *beg++ = (char)val;
MS>>  case 5: *beg++ = (char)val;
MS>>  case 4: *beg++ = (char)val;
MS>>  case 3: *beg++ = (char)val;
MS>>  case 2: *beg++ = (char)val;
MS>>  case 1: *beg++ = (char)val;
MS>>    }
MS>>  }
MS>>}

T>> void* memset( void *dst,  int val,  size_t count )
T>> {
T>>  char* end = dst + count;
T>>  for( char* curr = (char*)dst; curr != end; ++curr )
T>>    *curr = (char)val;
T>> }

1. Переходы по switch: 3 перехода при выборке (switch осуществляется бинарным поиском, иначе ещё дольше). Допустим, среднее значение 1,5 (так как не всегда у нас самый плохой случай) и точно больше 1.
2. Далее, цикл повторяется count/8 раз вместо count раз.

Ваша оценка правильна, я ошибся.

ВОПРОС!!! Почему в развёрнутом цикле всего 7 операторов? Я тупой???!!!

Здравствуйте, FDSC, Вы писали:

FDS>Здравствуйте, MShura, Вы писали:

FDS>>>Количество операций перехода, насколько я понял, не в 8 раз меньше, а в 4 (если в среднем).

MS>>Грубо количество переходов есть 1 + count/8

FDS>

MS>>>void* memset( void *dst,  int val,  size_t count )
MS>>>{
MS>>>  char* beg = (char*)dst;
MS>>>  char* end = beg + count;
MS>>>  switch (count & 7)
MS>>>  {
MS>>>  case 0: 
MS>>>    while (beg != end)
MS>>>    {
MS>>>      *beg++ = (char)val;
MS>>>  case 7: *beg++ = (char)val;
MS>>>  case 6: *beg++ = (char)val;
MS>>>  case 5: *beg++ = (char)val;
MS>>>  case 4: *beg++ = (char)val;
MS>>>  case 3: *beg++ = (char)val;
MS>>>  case 2: *beg++ = (char)val;
MS>>>  case 1: *beg++ = (char)val;
MS>>>    }
MS>>>  }
MS>>>}

T>>> void* memset( void *dst,  int val,  size_t count )
T>>> {
T>>>  char* end = dst + count;
T>>>  for( char* curr = (char*)dst; curr != end; ++curr )
T>>>    *curr = (char)val;
T>>> }


FDS>

FDS>1. Переходы по switch: 3 перехода при выборке (switch осуществляется бинарным поиском, иначе ещё дольше). Допустим, среднее значение 1,5 (так как не всегда у нас самый плохой случай) и точно больше 1.
FDS>2. Далее, цикл повторяется count/8 раз вместо count раз.

FDS>Ваша оценка правильна, я ошибся.

FDS>ВОПРОС!!! Почему в развёрнутом цикле всего 7 операторов? Я тупой???!!!

Если множество значений case для switch непрерывно, то обычно компиляторы составляют таблицу jump
В итоге весь switch() в нашем случае это goto Table[count&7]. Т.е. один jump.

> T>Что, на самом деле восемь присваиваний подряд эффективнее их же, но в цикле?
>
> В коде, который привел я, в среднем количество jump в 8 (!) раз меньше.
> Цена jump в большинстве процессоров большая (даже на x86), а на некоторых ОЧЕНЬ большая, поэтому первый код работает существенно быстрее.

Предсказанные ветвления отнимают один такт. А такими являются все
итерации цикла, кроме первой и последней.

Здравствуйте, _vovin, Вы писали:

>> T>Что, на самом деле восемь присваиваний подряд эффективнее их же, но в цикле?
>>
>> В коде, который привел я, в среднем количество jump в 8 (!) раз меньше.
>> Цена jump в большинстве процессоров большая (даже на x86), а на некоторых ОЧЕНЬ большая, поэтому первый код работает существенно быстрее.

_>Предсказанные ветвления отнимают один такт. А такими являются все
_>итерации цикла, кроме первой и последней.

Тем не менее обычный цикл всегда проигрывает Duff's Device (на примере реализации memcpy).

Здравствуйте, FDSC, Вы писали:

FDS>Здравствуйте, MShura, Вы писали:

FDS>>>Количество операций перехода, насколько я понял, не в 8 раз меньше, а в 4 (если в среднем).

MS>>Грубо количество переходов есть 1 + count/8

FDS>

MS>>>void* memset( void *dst,  int val,  size_t count )
MS>>>{
MS>>>  char* beg = (char*)dst;
MS>>>  char* end = beg + count;
MS>>>  switch (count & 7)
MS>>>  {
MS>>>  case 0: 
MS>>>    while (beg != end)
MS>>>    {
MS>>>      *beg++ = (char)val;
MS>>>  case 7: *beg++ = (char)val;
MS>>>  case 6: *beg++ = (char)val;
MS>>>  case 5: *beg++ = (char)val;
MS>>>  case 4: *beg++ = (char)val;
MS>>>  case 3: *beg++ = (char)val;
MS>>>  case 2: *beg++ = (char)val;
MS>>>  case 1: *beg++ = (char)val;
MS>>>    }
MS>>>  }
MS>>>}

T>>> void* memset( void *dst,  int val,  size_t count )
T>>> {
T>>>  char* end = dst + count;
T>>>  for( char* curr = (char*)dst; curr != end; ++curr )
T>>>    *curr = (char)val;
T>>> }


FDS>

FDS>1. Переходы по switch: 3 перехода при выборке (switch осуществляется бинарным поиском, иначе ещё дольше). Допустим, среднее значение 1,5 (так как не всегда у нас самый плохой случай) и точно больше 1.
FDS>2. Далее, цикл повторяется count/8 раз вместо count раз.

FDS>Ваша оценка правильна, я ошибся.

FDS>ВОПРОС!!! Почему в развёрнутом цикле всего 7 операторов? Я тупой???!!!
Нет, просто считать не умеешь 7 операторов помечено метками, и один непомеченный — итого 8...

Здравствуйте, Dusty, Вы писали:

FDS>>ВОПРОС!!! Почему в развёрнутом цикле всего 7 операторов? Я тупой???!!!
D>Нет, просто считать не умеешь 7 операторов помечено метками, и один непомеченный — итого 8...

Говорил я: код нечитаемый. Чёрт... я действительно тупой!

MShura wrote:

> Здравствуйте, _vovin, Вы писали:
>
>
>>>T>Что, на самом деле восемь присваиваний подряд эффективнее их же, но в цикле?
>>>
>>>В коде, который привел я, в среднем количество jump в 8 (!) раз меньше.
>>>Цена jump в большинстве процессоров большая (даже на x86), а на некоторых ОЧЕНЬ большая, поэтому первый код работает существенно быстрее.
>
>
> _>Предсказанные ветвления отнимают один такт. А такими являются все
> _>итерации цикла, кроме первой и последней.
>
> Тем не менее обычный цикл всегда проигрывает Duff's Device (на примере реализации memcpy).

Никто и не сомневался, с итерации по такту — циклу скорость.
Но это не тот случай, когда

Цена jump в большинстве процессоров большая (даже на x86), а на
некоторых ОЧЕНЬ большая

Здравствуйте, VladD2, Вы писали:

VD>Орлы из МС которе писали Шарп тоже думали над этим воросом.

Ну что ж, если стояло требование синтаксической совместимости с C++, это было оптимальное, наверное, решение.

Здравствуйте, MShura, Вы писали:

MS>В коде, который привел я, в среднем количество jump в 8 (!) раз меньше.
MS>Цена jump в большинстве процессоров большая (даже на x86), а на некоторых ОЧЕНЬ большая, поэтому первый код работает существенно быстрее.

Ну, если использовать C++ как "высокоуровневый ассемблер", решая на нём задачи оптимизации кода, то это, действительно, очень красивый код. Вполне возможно, что удачным вариантом специально для целей низкоуровневой оптимизации было бы выделение метки в особый тип и чтоб аргументом goto могло быть некоторое выражение, этот тип возвращающее.

void* memset( void *dst, int val, size_t count )
{
  val = val & 0xFF;

  char* curr = (char*)dst;
  char* end = (char*)dst + count;

  const static label labs[8] = { l0, l1, l2, l3, l4, l5, l6, l7 };
  goto labs[ count & 7 ];

  l7: *curr++ = (char)val;
  l6: *curr++ = (char)val;
  l5: *curr++ = (char)val;
  l4: *curr++ = (char)val;
  l3: *curr++ = (char)val;
  l2: *curr++ = (char)val;
  l1: *curr++ = (char)val;
  l0:

  if( count >= 8 )
  {
    BOOST_STATIC_ASSERT( sizeof long == 4 );
    long int* curr32 = (long int)curr;
    long int value32 = (val << 24) | (val << 16) | (val << 8) | val;
    while( curr32 < end )
    {
      *curr32++ = value32;
      *curr32++ = value32;
    }
  }
}

Более громоздко, но куда лучше читается. Жертва вполне допустимая, учитывая, что такого кода аномально мало. Заодно и присвоение оптимизируем под 32-битные процессоры (да, да, не надо так громко ругаться, я знаю, что тут надо бы ещё выравнивание учитывать, лениво мне это делать флейма ради ...)

Здравствуйте, tarkil, Вы писали:

T>Ну что ж, если стояло требование синтаксической совместимости с C++, это было оптимальное, наверное, решение.

Похоже на то. По крайней мере не напрягает, а ломка привычек процесс очень неприятный. Хотя я лично бы не отказался от возможности перечислять константы в одном case-е.

Hello, tarkil!
You wrote on Thu, 09 Jun 2005 11:59:44 GMT:

t> Три минуты пытался понять, что эта хрень делает. Десять лет на C++ пишу,
t> а такого ещё не видел. Неисчерпаемый язык
Сер, эта штука называется "Duffs engine". И ей значительно больше чем 10 лет...
Кажется 20 или 25, но я могу ошибаться...

0xDEADBEEF,

> t> Три минуты пытался понять, что эта хрень делает. Десять лет на C++ пишу, а такого ещё не видел. Неисчерпаемый язык

> Сер, эта штука называется "Duffs engine".

Device.

> И ей значительно больше чем 10 лет... Кажется 20 или 25, но я могу ошибаться...

От автора: http://www.lysator.liu.se/c/duffs-device.html

Здравствуйте, 0xDEADBEEF, Вы писали:

DEA>Сер, эта штука называется "Duffs engine". И ей значительно больше чем 10 лет...
DEA>Кажется 20 или 25, но я могу ошибаться...

Why бы и not? Я низкоуровневой оптимизацией на высокоуровневых языках мало интересовался...