Re: Фантазии на тему switch
От: BlackBox Россия ---
Дата: 09.06.05 11:22
Оценка: -2 :)
Здравствуйте, tarkil, Вы писали:

T>Но, с другой стороны, необязательность break даёт две фишки:

T>- использовать один case, как фрагмент другого

За это убивать сразу
Re: Фантазии на тему switch
От: MShura  
Дата: 09.06.05 11:44
Оценка: 2 (1) -1
А как будет выглядеть с таким синтаксисом классическая memset?

void* memset( void *dst,  int val,  size_t count )
{
  char* beg = (char*)dst;
  char* end = beg + count;
  switch (count & 7)
  {
  case 0: 
    while (beg != end)
    {
      *beg++ = (char)val;
  case 7: *beg++ = (char)val;
  case 6: *beg++ = (char)val;
  case 5: *beg++ = (char)val;
  case 4: *beg++ = (char)val;
  case 3: *beg++ = (char)val;
  case 2: *beg++ = (char)val;
  case 1: *beg++ = (char)val;
    }
  }
}
Re[3]: Фантазии на тему switch
От: GlebZ Россия  
Дата: 09.06.05 11:34
Оценка: -1 :)
Здравствуйте, FDSC, Вы писали:

FDS>Между прочим такие вещи и в MFC можно встретить. УБИТЬ Microsoft и программистов, писавших компиляторы Си.

Хорошее предложение. Я в доле.

С уважением, Gleb.
... << RSDN@Home 1.1.4 beta 4 rev. 358>>
Фантазии на тему switch
От: tarkil Россия http://5209.copi.ru/
Дата: 09.06.05 11:13
Оценка: 1 (1)
Коль уж пошла такая синтаксическая пьянка, то хочу (просто в порядке фантазии) обсудить конструкцию switch в C++. Главная, как мне кажется, неприятность этой конструкции в том, что нужно после каждого case писать по break. Это и забывают нередко, к тому же.

Но, с другой стороны, необязательность break даёт две фишки:
— использовать один case, как фрагмент другого
— ставить несколько меток одному и тому же коду

Чтоб не быть голословным, придумаю пример — по коду причины отказа нужно вычислить текст отказа и некоторый условный "вес", тяжесть этой причины. Код несколько надуманный, но уж что пришло в голову под конец рабочего дня

string text; // текст причины
unsigned reasonWeight = 0; // "тяжесть" причины

switch( reasonCode )
{
    case REASON_1:
    case REASON_2:
        text = "Текст главной причины отказа";
        reasonWeight = 1000;
        break;
    case REASON_3:
        text = " (но с дополнением)";
        reasonWeight = 500;
    case REASON_4:
        text = "Текст второстепенной причины" + text;
        reasonWeight += 1000;
        break;
    case REASON_5:
        text = "А, считай и не причина"; // вес остался нулевым по умолчанию
        break;
    default:
        text = "(встречен отказ с неизвестным кодом)";
        reasonWeight = REASON_WEIGHT_MAX;
}

Фактически, мы тут имеем goto на метку. Не знаю, как вам, но мне поведение case REASON_3, case REASON_4 кажется несколько ненаглядным, что ли...

Предлагаю вариант улучшения номер раз.

string text; // текст причины
unsigned reasonWeight = 0; // "тяжесть" причины

switch( reasonCode )
{
    mixin addAppendix
    {
        reasonWeight += 500;
        text += " (но с дополнением)";
    }
    case REASON_1, REASON_2:
        text = "Текст главной причины отказа";
        reasonWeight = 1000;
    case REASON_3: addAppendix();
    case REASON_4:
        text = "Текст второстепенной причины"
        reasonWeight = 1000;
        addAppendix();
    case REASON_5: text = "А, считай и не причина";
    default:
        text = "(встречен отказ с неизвестным кодом)";
        reasonWeight = REASON_WEIGHT_MAX;
};

Мало того, что код стал компактней, так за счёт миксина (видимого только внутри данного switch) он ещё и приобрёл привычный процедурный стиль, addAppendix теперь выделен в особую сущность с чётко определёнными функциями. Не нравятся миксины? Ну, никто не отменял макросы

Однако, мне тут продолжает не нравится нагромождение ключевых слов case... тут бы по пустой строке между ними вставить, но это почти убивает пользу от исключения break...

Поэтому, смотрите вариант номер два.

string text; // текст причины
unsigned reasonWeight = 0; // "тяжесть" причины

mixin addAppendix
{
    reasonWeight += 500;
    text += " (но с дополнением)";
}

switch( reasonCode )
REASON_1, REASON_2 {
    text = "Текст главной причины отказа";
    reasonWeight = 1000;
}
REASON_3 { addAppendix(); }
REASON_4 {
    text = "Текст второстепенной причины"
    reasonWeight = 1000;
    addAppendix();
}
REASON_5 { text = "А, считай и не причина"; }
default {
    text = "(встречен отказ с неизвестным кодом)";
    reasonWeight = REASON_WEIGHT_MAX;
};

Обращаю внимание на ";" в конце — это признак конца оператора.

Что лучше не стало? Жаль. У кого какие ещё будут фантазии на тему?
--
wbr, Peter Taran
Re[3]: Фантазии на тему switch
От: FDSC Россия consp11.github.io блог
Дата: 09.06.05 11:35
Оценка: 1 (1)
Здравствуйте, tarkil, Вы писали:

T>В этом тоже есть сермяга. Но писать несколько функций, с кучей (двумя в нашем случае ) параметров, вызываемых только один раз... Не знаю, что-то тут не то — писать четыре доп. функции, каждая из двух строк, вызываемые из единственного места...


Мысль правильная, но по моему опыту, если количество операторов больше 1, то появятся ещё. Потом всё равно функции создавать придётся.
Re: Фантазии на тему switch
От: VladD2 Российская Империя www.nemerle.org
Дата: 09.06.05 14:54
Оценка: 1 (1)
Здравствуйте, tarkil, Вы писали:


Орлы из МС которе писали Шарп тоже думали над этим воросом. По началу тоже хотели отказаться от брэйка. Даже сделали альфу в которой он был не обязателньным. Но быстро поняли, что это дико мозолит глаза тем кто привык к классическому С-шному синтаксису и остановились на том, что брэйк должен быть обязательным (контролируется компилятором), том что пустые идущие друг за другом кейсы могут автоматически конкатенироваться и том, что ввели оператор goto case позволяющий перейти из конца одного кейса в начало другого.
... << RSDN@Home 1.1.4 beta 7 rev. 466>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[7]: Фантазии на тему switch
От: MShura  
Дата: 09.06.05 14:54
Оценка: 1 (1)
Здравствуйте, FDSC, Вы писали:

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


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


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


Речь как раз не об этом.
Комманды типа rep stos(b)(d)(q) работают с памятью напрямую.
Чтобы ускорить процесс достаточно периодически обращаться к памяти чуть дальше, а затем продолжать процесс.
Крис Касперский писал, что он получал (разные) выигрыши на Intel и AMD, но это всегда были именно выигрыши по сравнению с тривиальным rep stos...
Re[4]: Фантазии на тему switch
От: Павел Кузнецов  
Дата: 15.06.05 20:23
Оценка: 1 (1)
0xDEADBEEF,

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


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


Device.

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


От автора: http://www.lysator.liu.se/c/duffs-device.html
Posted via RSDN NNTP Server 2.0 beta
Легче одурачить людей, чем убедить их в том, что они одурачены. — Марк Твен
Re[2]: Фантазии на тему switch
От: FDSC Россия consp11.github.io блог
Дата: 09.06.05 11:24
Оценка: -1
Здравствуйте, BlackBox, Вы писали:

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


T>>Но, с другой стороны, необязательность break даёт две фишки:

T>>- использовать один case, как фрагмент другого

BB>За это убивать сразу



Между прочим такие вещи и в MFC можно встретить. УБИТЬ Microsoft и программистов, писавших компиляторы Си.
Re[4]: Фантазии на тему switch
От: tarkil Россия http://5209.copi.ru/
Дата: 09.06.05 11:34
Оценка: :)
Здравствуйте, FDSC, Вы писали:

FDS>В том, чтоб убивать или в том, чтоб писать?


Ну чур меня, в натуре! Чтоб убивать, конечно
--
wbr, Peter Taran
Re[2]: Фантазии на тему switch
От: tarkil Россия http://5209.copi.ru/
Дата: 09.06.05 11:59
Оценка: +1
Здравствуйте, MShura, Вы писали:

MS>А как будет выглядеть с таким синтаксисом классическая memset?


MS>
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>}
MS>


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

А подобной классики есть какие-то преимущества перед новаторскими технологиями:

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


Что, на самом деле восемь присваиваний подряд эффективнее их же, но в цикле?
--
wbr, Peter Taran
Re[3]: Фантазии на тему switch
От: MShura  
Дата: 09.06.05 12:09
Оценка: +1
Здравствуйте, tarkil, Вы писали:

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


MS>>А как будет выглядеть с таким синтаксисом классическая memset?


MS>>
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>>}
MS>>


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


T>А подобной классики есть какие-то преимущества перед новаторскими технологиями:


T>
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>}
T>


T>Что, на самом деле восемь присваиваний подряд эффективнее их же, но в цикле?


В коде, который привел я, в среднем количество jump в 8 (!) раз меньше.
Цена jump в большинстве процессоров большая (даже на x86), а на некоторых ОЧЕНЬ большая, поэтому первый код работает существенно быстрее.
Re[8]: Фантазии на тему switch
От: Dusty Россия  
Дата: 10.06.05 06:27
Оценка: +1
Здравствуйте, 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...
Re: Фантазии на тему switch
От: tarkil Россия http://5209.copi.ru/
Дата: 09.06.05 11:16
Оценка:
Да, я там чуток напутал с вызовом mixin, но не суть важно, идея, думаю понятна
--
wbr, Peter Taran
Re: Фантазии на тему switch
От: FDSC Россия consp11.github.io блог
Дата: 09.06.05 11:22
Оценка:
Здравствуйте, tarkil, Вы писали:

T>Коль уж пошла такая синтаксическая пьянка, то хочу (просто в порядке фантазии) обсудить конструкцию switch в C++. Главная, как мне кажется, неприятность этой конструкции в том, что нужно после каждого case писать по break. Это и забывают нередко, к тому же.


Это точно.


Теперь чуть-чуть фантазии.

НИКОГДА не пишите после метки оператора выбора несколько операторов. Тогда всегда будет процедурный стиль (извините, что не даю ваших фраз).

Получим тогда ()
switch( reasonCode )
{
case R1: func1(); break;
case R2: func1(); break;
case REASON_3: func2(); break;
default: ...
}

Между прочим в Delphi не нужно писать break, но там приходится ставить begin и end, если хочешь написать более одного оператора — то же не очень.
Re[2]: Фантазии на тему switch
От: tarkil Россия http://5209.copi.ru/
Дата: 09.06.05 11:27
Оценка:
Здравствуйте, BlackBox, Вы писали:

T>>- использовать один case, как фрагмент другого

BB>За это убивать сразу

В этом есть здравое зерно
--
wbr, Peter Taran
Re[3]: Фантазии на тему switch
От: FDSC Россия consp11.github.io блог
Дата: 09.06.05 11:27
Оценка:
Здравствуйте, tarkil, Вы писали:

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


T>>>- использовать один case, как фрагмент другого

BB>>За это убивать сразу

T>В этом есть здравое зерно


В том, чтоб убивать или в том, чтоб писать?
Re[2]: Фантазии на тему switch
От: tarkil Россия http://5209.copi.ru/
Дата: 09.06.05 11:31
Оценка:
Здравствуйте, FDSC, Вы писали:

FDS>НИКОГДА не пишите после метки оператора выбора несколько операторов. Тогда всегда будет процедурный стиль (извините, что не даю ваших фраз).


FDS>Получим тогда ()

FDS>switch( reasonCode )
FDS>{
FDS> case R1: func1(); break;
FDS> case R2: func1(); break;
FDS> case REASON_3: func2(); break;
FDS> default: ...
FDS>}

В этом тоже есть сермяга. Но писать несколько функций, с кучей (двумя в нашем случае ) параметров, вызываемых только один раз... Не знаю, что-то тут не то — писать четыре доп. функции, каждая из двух строк, вызываемые из единственного места...
--
wbr, Peter Taran
Re: Фантазии на тему switch
От: Sergey Россия  
Дата: 09.06.05 11:44
Оценка:
Hello, tarkil!
You wrote on Thu, 09 Jun 2005 11:13:45 GMT:

t> Коль уж пошла такая синтаксическая пьянка, то хочу (просто в порядке

t> фантазии) обсудить конструкцию switch в C++. Главная, как мне кажется,
t> неприятность этой конструкции в том, что нужно после каждого case писать
t> по break. Это и забывают нередко, к тому же.

t> Но, с другой стороны, необязательность break даёт две фишки:

t> — использовать один case, как фрагмент другого
t> — ставить несколько меток одному и тому же коду

Заменить break на какой-нибудь fall_through — всего-то и делов. И так, если
бряк нарочно опускаешь, коммент такой писать приходится, иначе на ошибку
сильно смахивает. Правда, легаси код при этом пойдет лесом, а потому такого
изменения в языке не будет никогда.

With best regards, Sergey.
Posted via RSDN NNTP Server 1.9
Одним из 33 полных кавалеров ордена "За заслуги перед Отечеством" является Геннадий Хазанов.
Re[4]: Фантазии на тему switch
От: FDSC Россия consp11.github.io блог
Дата: 09.06.05 12:40
Оценка:
Здравствуйте, MShura, Вы писали:

MS>В коде, который привел я, в среднем количество jump в 8 (!) раз меньше.

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

Разворачивать циклы при программировании не принято. Хотя это и стандартная операция оптимизации, всё-таки код становится полностью не читаемым.

Ни один компилятор не додумается как скомпилировать приведённую Вами кострукцию (хотя, почему бы и нет?). По крайней мере это путь многократного умножения ошибок.
Re[5]: Фантазии на тему switch
От: MShura  
Дата: 09.06.05 13:52
Оценка:
Здравствуйте, FDSC, Вы писали:

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


MS>>В коде, который привел я, в среднем количество jump в 8 (!) раз меньше.

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

FDS>Разворачивать циклы при программировании не принято. Хотя это и стандартная операция оптимизации, всё-таки код становится полностью не читаемым.


FDS>Ни один компилятор не додумается как скомпилировать приведённую Вами кострукцию (хотя, почему бы и нет?). По крайней мере это путь многократного умножения ошибок.


Зачем строить догадки, когда можно скопилить и посмотреть на результат.

Сравнение такого алгоритма (правда memcpy) можно найти здесь

http://www.cuj.com/documents/s=7990/cujcexp1910alexandr/

Между прочим есть еще более быстрые алгоритмы memcpy и memset, но они уже зависят от процессора, поскольку используют знания размеров кэша разных уровней.
Re[2]: Фантазии на тему switch
От: Tuo_Bellas Россия  
Дата: 09.06.05 14:16
Оценка:
Здравствуйте, MShura, Вы писали:

MS>А как будет выглядеть с таким синтаксисом классическая memset?


MS>
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>}
MS>


Кстати, называется Duff's device. http://gzip.rsdn.ru/Forum/Message.aspx?mid=581909&amp;all=1
Автор: Tuo_Bellas
Дата: 25.03.04


Tuo_Bellas.
Re[6]: Фантазии на тему switch
От: FDSC Россия consp11.github.io блог
Дата: 09.06.05 14:35
Оценка:
Здравствуйте, MShura, Вы писали:

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


Не буду спорить, точнее, соглашусь. Кстати, можно и через assembler написать с использованием строковых команд, тогда размер кэша знать не надо
Re[4]: Фантазии на тему switch
От: VladD2 Российская Империя www.nemerle.org
Дата: 09.06.05 14:54
Оценка:
Здравствуйте, MShura, Вы писали:

MS>В коде, который привел я, в среднем количество jump в 8 (!) раз меньше.

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

Если только компилятор не умеет делать раскрутку цикла или использовать спец. инструкции процессора.
... << RSDN@Home 1.1.4 beta 7 rev. 466>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[8]: Фантазии на тему switch
От: FDSC Россия consp11.github.io блог
Дата: 09.06.05 15:00
Оценка:
Здравствуйте, MShura, Вы писали:

MS>Речь как раз не об этом.

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


Крис Касперски ничего не понимает в компьтерах.
Re[5]: Фантазии на тему switch
От: FDSC Россия consp11.github.io блог
Дата: 09.06.05 15:07
Оценка:
Здравствуйте, VladD2, Вы писали:

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


MS>>В коде, который привел я, в среднем количество jump в 8 (!) раз меньше.

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

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


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

Количество операций перехода, насколько я понял, не в 8 раз меньше, а в 4 (если в среднем).
Re[5]: Фантазии на тему switch
От: MShura  
Дата: 09.06.05 15:25
Оценка:
Здравствуйте, VladD2, Вы писали:

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


MS>>В коде, который привел я, в среднем количество jump в 8 (!) раз меньше.

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

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


Согласен.

На ранних процессорах TMS после комманды BD (branch delayed) до реального перехода можно было вставить три инструкции. На современных TMS эта задержка еще увеличилась.
И если в в основном цикле вся операция занимает одну инструкцию, то без специальных подсказок компилятору (что цикл выполняется всегда более 4 раз, что число повторений делится на 4 нацело и т.д.) получится нехилый overhead в 3-5 раз. Правда на сигнальных процессорах работа с циклами (особенно внутренними) обычно делается не через jump.
Re[6]: Фантазии на тему switch
От: MShura  
Дата: 09.06.05 15:28
Оценка:
Здравствуйте, FDSC, Вы писали:

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


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


MS>>>В коде, который привел я, в среднем количество jump в 8 (!) раз меньше.

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

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


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


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


Грубо количество переходов есть 1 + count/8
Re[7]: Фантазии на тему switch
От: FDSC Россия consp11.github.io блог
Дата: 09.06.05 15:58
Оценка:
Здравствуйте, 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 операторов? Я тупой???!!!
Re[8]: Фантазии на тему switch
От: MShura  
Дата: 09.06.05 16:33
Оценка:
Здравствуйте, 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.
Re[4]: Фантазии на тему switch
От: _vovin http://www.pragmatic-architect.com
Дата: 09.06.05 16:40
Оценка:
> T>Что, на самом деле восемь присваиваний подряд эффективнее их же, но в цикле?
>
> В коде, который привел я, в среднем количество jump в 8 (!) раз меньше.
> Цена jump в большинстве процессоров большая (даже на x86), а на некоторых ОЧЕНЬ большая, поэтому первый код работает существенно быстрее.

Предсказанные ветвления отнимают один такт. А такими являются все
итерации цикла, кроме первой и последней.
Posted via RSDN NNTP Server 1.9
Re[5]: Фантазии на тему switch
От: MShura  
Дата: 09.06.05 17:07
Оценка:
Здравствуйте, _vovin, Вы писали:

>> T>Что, на самом деле восемь присваиваний подряд эффективнее их же, но в цикле?

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

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

_>итерации цикла, кроме первой и последней.

Тем не менее обычный цикл всегда проигрывает Duff's Device (на примере реализации memcpy).
Re[9]: Фантазии на тему switch
От: FDSC Россия consp11.github.io блог
Дата: 10.06.05 06:59
Оценка:
Здравствуйте, Dusty, Вы писали:

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

D>Нет, просто считать не умеешь 7 операторов помечено метками, и один непомеченный — итого 8...

Говорил я: код нечитаемый. Чёрт... я действительно тупой!
Re[6]: Фантазии на тему switch
От: _vovin http://www.pragmatic-architect.com
Дата: 10.06.05 07:34
Оценка:
MShura wrote:

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

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

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

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

Posted via RSDN NNTP Server 1.9
Re[2]: Фантазии на тему switch
От: tarkil Россия http://5209.copi.ru/
Дата: 10.06.05 09:05
Оценка:
Здравствуйте, VladD2, Вы писали:

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


Ну что ж, если стояло требование синтаксической совместимости с C++, это было оптимальное, наверное, решение.
--
wbr, Peter Taran
Re[4]: Фантазии на тему switch
От: tarkil Россия http://5209.copi.ru/
Дата: 10.06.05 09:26
Оценка:
Здравствуйте, 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-битные процессоры (да, да, не надо так громко ругаться, я знаю, что тут надо бы ещё выравнивание учитывать, лениво мне это делать флейма ради ...)
--
wbr, Peter Taran
Re[3]: Фантазии на тему switch
От: VladD2 Российская Империя www.nemerle.org
Дата: 10.06.05 10:27
Оценка:
Здравствуйте, tarkil, Вы писали:

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


Похоже на то. По крайней мере не напрягает, а ломка привычек процесс очень неприятный. Хотя я лично бы не отказался от возможности перечислять константы в одном case-е.
... << RSDN@Home 1.1.4 beta 7 rev. 466>>
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Re[3]: Фантазии на тему switch
От: 0xDEADBEEF Ниоткуда  
Дата: 15.06.05 09:32
Оценка:
Hello, tarkil!
You wrote on Thu, 09 Jun 2005 11:59:44 GMT:

t> Три минуты пытался понять, что эта хрень делает. Десять лет на C++ пишу,

t> а такого ещё не видел. Неисчерпаемый язык
Сер, эта штука называется "Duffs engine". И ей значительно больше чем 10 лет...
Кажется 20 или 25, но я могу ошибаться...
Posted via RSDN NNTP Server 1.9
__________
16.There is no cause so right that one cannot find a fool following it.
Re[4]: Фантазии на тему switch
От: tarkil Россия http://5209.copi.ru/
Дата: 16.06.05 08:36
Оценка:
Здравствуйте, 0xDEADBEEF, Вы писали:

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

DEA>Кажется 20 или 25, но я могу ошибаться...

Why бы и not? Я низкоуровневой оптимизацией на высокоуровневых языках мало интересовался...
--
wbr, Peter Taran
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.