Форум программистов, компьютерный форум CyberForum.ru

Что делает данный код и зачем такое кому-нибудь может понадобиться? - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 47, средняя оценка - 4.74
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
08.06.2009, 23:57     Что делает данный код и зачем такое кому-нибудь может понадобиться? #1
Я ответил на вопрос,но точной формулировки не нашёл,хотел бы свериться(приложения с ответами нет).Задание:
Чёрный ящик.Что делается в данном примере?Зачем кому нибудь может понадобиться подобный код?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void send (int* to,int* from,int count)
{
    int n = (count+7)/8;
    swith(count%8)
    {
           case 0: do { *to++=*from++;
           case 7:        *to++=*from++;
           case 6:        *to++=*from++;
           case 5:        *to++=*from++;
           case 4:        *to++=*from++;
           case 3:        *to++=*from++;
           case 2:        *to++=*from++;
           case 1:        *to++=*from++;
                            }  while(--n>0);
     }
}
Я так думаю,параметр count содержит количество незаполненных байт(или не байт,но кратно 8-ми) "чего-то",и копируется информация(из массива в массив),пока нужное количество элементов не скопируется.Только меня смущает одна штука:если count%8==7,то не рухнет ли вся программа из-за разорванного цикла?Может это ловушка,чтобы программа вылетела?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.06.2009, 23:57     Что делает данный код и зачем такое кому-нибудь может понадобиться?
Посмотрите здесь:

C++ Обьясните пожайлуста как и что делает данный оператор в этом выражении fState [x][y] ^= 1;. Неполный код привожу ниже.
Может кому понадобиться Выключение/перезагрузки компа и завершение сеанса C++
Что делает функция compare в коде и зачем она нужна в qsort C++
C++ Что делает данный цикл ?
зачем может понадобиться делать операторы виртуальными? C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
XuTPbIu_MuHTAu
Эксперт C++
 Аватар для XuTPbIu_MuHTAu
2219 / 734 / 10
Регистрация: 27.05.2008
Сообщений: 1,507
09.06.2009, 01:33     Что делает данный код и зачем такое кому-нибудь может понадобиться? #2
Единственное,что я пока смог придумать - уменьшить количество сравнений при копировании. Деление на восемь выполняется быстро,деление на восемь с остатком тоже шустро,а потом имеем то же копирование,но счетчик уменьшается в 8 раз реже.

#pragma,а что значит "разорванный цикл"?) Си - это низкоуровневый ассемблер. Свич тут просто определяет, с какой точки цикл начнется ( причем компилятор тут сделает таблицу джампов,а не кучу сравнений).

Добавлено через 29 минут 46 секунд
Интересно.Буду говорить не называя цифр.
Я взял функцию
Код
void cpy (int * to,int * from,int count) {
    for(int i =0;i<count;i++)
        *to++=*from++;
};
При малых count разницу не замерять особо.Начиная с некоторых cpy ощутимо отстает от send. При средних - отстает неощутимо. При больших cpy работает быстрее.
Не думаю, что у всех результат будет такой.Вообще-то,все должно зависить от механизма предсказания переходов,конвеера и проч. Интересно посмотреть,как выйдет на интеле,у меня атлончик.)

Добавлено через 18 секунд
Интересная темка,спасибо автору ^^
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16833 / 5254 / 323
Регистрация: 30.03.2009
Сообщений: 14,145
Записей в блоге: 26
09.06.2009, 08:43     Что делает данный код и зачем такое кому-нибудь может понадобиться? #3
pragma, почитай тут, там я уже описывал семантику switch'а Проверьте себя. А хорошо ли вы знакомы со switch'ом?
А задачка и вправду прикольная. Где такое достаёшь? Если в институте, то хороший у вас преподаватель

Добавлено через 1 минуту 0 секунд
Цитата Сообщение от XuTPbIu_MuHTAu Посмотреть сообщение
Единственное,что я пока смог придумать...
Не та том посте на "Спасибо" нажал
EnzoMatrix
 Аватар для EnzoMatrix
119 / 119 / 4
Регистрация: 14.03.2009
Сообщений: 462
09.06.2009, 10:41     Что делает данный код и зачем такое кому-нибудь может понадобиться? #4
решил прогнать прогу под досбоксом, результаты поражают для 32000 прогонов при count=20, send работает в 2,5 раза быстрее, тока я так и не понял за счет чего такой прирост в скорости
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16833 / 5254 / 323
Регистрация: 30.03.2009
Сообщений: 14,145
Записей в блоге: 26
09.06.2009, 10:49     Что делает данный код и зачем такое кому-нибудь может понадобиться? #5
В 2.5 раза быстрее чем что?
EnzoMatrix
 Аватар для EnzoMatrix
119 / 119 / 4
Регистрация: 14.03.2009
Сообщений: 462
09.06.2009, 10:53     Что делает данный код и зачем такое кому-нибудь может понадобиться? #6
чем по индексам приравнивать, но если брать эту функцию,
Цитата Сообщение от XuTPbIu_MuHTAu Посмотреть сообщение
Код:
void cpy (int * to,int * from,int count) {
for(int i =0;i<count;i++)
*to++=*from++;
};
то cpy пашет на 25% быстрее чем send
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
09.06.2009, 11:46     Что делает данный код и зачем такое кому-нибудь может понадобиться? #7
еще бы.
switch - это цепочка if(a == b) goto xx.
в исходном коде таких ветвлений 7.
а ветвление(оно-же - условный переход)... если почитать документацию по процессорам...
при неверном предсказании обрывает суперконвейер, и требует заново загрузить данные из кэша.
что требует очень много времени.
а вот на старых процессорах тот код со switch делался быстрее, чем версия от XuTPbIu_MuHTAu
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16833 / 5254 / 323
Регистрация: 30.03.2009
Сообщений: 14,145
Записей в блоге: 26
09.06.2009, 12:10     Что делает данный код и зачем такое кому-нибудь может понадобиться? #8
Цитата Сообщение от CartmanRules Посмотреть сообщение
чем по индексам приравнивать, но если брать эту функцию
Всё равно я так и не понял, что сравнивалось с чем и кто круче

Добавлено через 1 минуту 48 секунд
Цитата Сообщение от Patch Посмотреть сообщение
switch - это цепочка if(a == b) goto xx.
По замыслу switch был коммутируемым переходом, а потому любой более-менее приличный компилятор в культурном случае построит switch на ОДНОМ динамическом переходе (правда при этом будет как минимум один статический переход, чтобы проверить, что значение ключа попадает в диапазон case'ов). В итоге код с 1000 алтернативами будет работать так же быстро, как код с 2000 альтернатив
EnzoMatrix
 Аватар для EnzoMatrix
119 / 119 / 4
Регистрация: 14.03.2009
Сообщений: 462
09.06.2009, 12:11     Что делает данный код и зачем такое кому-нибудь может понадобиться? #9
Цитата Сообщение от Evg Посмотреть сообщение
Всё равно я так и не понял, что сравнивалось с чем и кто круче
извиняюсь за тупость высказывания*sorry*
сравнивалась send и
C++
1
2
for(i;i<count;i++)
  to[i]=from[i];
send работал в два с половиной раза шустрей это конструкции
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16833 / 5254 / 323
Регистрация: 30.03.2009
Сообщений: 14,145
Записей в блоге: 26
09.06.2009, 12:13     Что делает данный код и зачем такое кому-нибудь может понадобиться? #10
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от CartmanRules Посмотреть сообщение
извиняюсь за тупость высказывания*sorry*
сравнивалась send и
C++
1
2
for(i;i<count;i++)
  to[i]=from[i];
Принципиальная разница между send'ом и этим кодом в том, что в твоём коде получается на одну итерацию цикла идёт одна пересылка. Т.е. количество операций передачи упарвления (который в данном случае НЕ являются полезными) равно количеству пересылок и, будем условно считать, что занимают 50% времени.

В варианте с send'ом получается, что на 8 пересылок у тебяодин переход и таким образом на НЕполезные операции уходит (опять-таки условно) порядка 10% времени

(to pragma)
Выше и написано, в чём заключается действие этого "чёрного ящика". Т.е. мы делаем некий аналог широкого копирования (которое ты видел в навороченной реализации strcpy), только широта тут заключается в том, что уменьшается доля бесполезных операций перехода. А switch нужен для того, чтобы правильно отпилить начало (т.е. чтобы при копировании 13 байт сначала скопировалось 5, а затем уже шло пачками по 8)
EnzoMatrix
 Аватар для EnzoMatrix
119 / 119 / 4
Регистрация: 14.03.2009
Сообщений: 462
09.06.2009, 12:18     Что делает данный код и зачем такое кому-нибудь может понадобиться? #11
т.е. данный код (который с функцией send) можно назвать по стуи развернуутым циклом, если я правильно понял
и еще вопрос в чем такое принципиальное отличие между
C++
1
2
for(i;i<count;i++)
  to[i]=from[i];
и кодом, который привел хитрый_минай?
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16833 / 5254 / 323
Регистрация: 30.03.2009
Сообщений: 14,145
Записей в блоге: 26
09.06.2009, 12:29     Что делает данный код и зачем такое кому-нибудь может понадобиться? #12
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от CartmanRules Посмотреть сообщение
т.е. данный код (который с функцией send) можно назвать по стуи развернуутым циклом, если я правильно понял
Я не знаю, как правильно по-русски, по-английски называется unrolled loop. По сути да, это раскрученный цикл с хорошим preloop'ом

Цитата Сообщение от CartmanRules Посмотреть сообщение
и еще вопрос в чем такое принципиальное отличие между
Щас положу два кода, чтобы перед глазами было

C
1
2
for(int i =0;i<count;i++)
  *to++=*from++;
C
1
2
for(i;i<count;i++)
  to[i]=from[i];
По принципу работы разницы нет. Но здесь есть разница по скорости работы. Т.е. для первого кода на каждой итерации цикла помимо пересылки, инкрементации i и перехода делается две операции сложения (to++, from++, i++). Во втором случае дооплнительных операций больше: т.е. нужно вычислять адрес to[i], который равен (to + i *sizeof(char)). Т.е. к двум операциям сложения у тебя добавились две операции умножения. В случае с char'ом его размер равен единице, а потому операцию умножения компилятор выкинет. Но вот если копирование будет проходить int'ами, то от умножения уже никуда не деться (хотьи реализовано оно удет через сдвиг, но тем не менее две лишние операции в цикле появятся).

Приличный оптимизирующий компилятор скорее всего сведёт второй код к первому (случай у нас простой), но вот в более сложном случае не факт, что это получится сделать
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
09.06.2009, 15:13     Что делает данный код и зачем такое кому-нибудь может понадобиться? #13
Цитата Сообщение от Evg Посмотреть сообщение
любой более-менее приличный компилятор в культурном случае построит switch на ОДНОМ динамическом переходе
для сравнений переменной с последовательными значениями - пожалуй.
и даже при этом код примерно вдвое диннее.
для непоследовательных значений - switch строится только на проверках каждого значения.
лучший код такого рода, который я видел делал что-то вроде бинарного дерева...
получалось на 20 значений - 6 условных переходов.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16833 / 5254 / 323
Регистрация: 30.03.2009
Сообщений: 14,145
Записей в блоге: 26
09.06.2009, 15:16     Что делает данный код и зачем такое кому-нибудь может понадобиться? #14
Цитата Сообщение от Patch Посмотреть сообщение
для непоследовательных значений - switch строится только на проверках каждого значения.
Ничего подобного. Либо у тебя в руках был плохой компилятор. В случае непоследовательных значений в таблице переходов на месте "дырок" долен стоять адрес default'а

Цитата Сообщение от Patch Посмотреть сообщение
лучший код такого рода, который я видел делал что-то вроде бинарного дерева...
получалось на 20 значений - 6 условных переходов.
Всё-таки какой компилятор и включены ли опции оптимизации (и какие опции)?
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
09.06.2009, 15:23     Что делает данный код и зачем такое кому-нибудь может понадобиться? #15
Цитата Сообщение от Evg Посмотреть сообщение
Всё-таки какой компилятор
вот не помню. вскрывал что-то для личных нужд...
а вкрывал я немало. любопытный очень.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16833 / 5254 / 323
Регистрация: 30.03.2009
Сообщений: 14,145
Записей в блоге: 26
09.06.2009, 15:27     Что делает данный код и зачем такое кому-нибудь может понадобиться? #16
Просто 6 услоных переходов - это слишком много. Для intel'а с его длинным конвейером это смерти подобно. Т.е. такой код либо строился в режиме без оптимизаций, либо case'ы были уж очень разреженные
Patch
2276 / 491 / 11
Регистрация: 01.04.2009
Сообщений: 2,178
09.06.2009, 16:02     Что делает данный код и зачем такое кому-нибудь может понадобиться? #17
с оптимизацей.
но не суть важно.
код все равно получается не очень быстрым. по моим понятиям.
а помнится, исследователи еще писали, что в средней программе на каждые 8 команд приходится по одному условному переходу.
из-за чего интел и стал развивать технологию предсказания ветвлений.
так что описанная мной ситуация - это нормально.

Добавлено через 3 минуты 59 секунд
кстати, только что сделал в VC++ код. с оптимизацией на скорость.
C++
1
2
3
4
5
6
7
switch(i)
{
case 1: i = 500;
case 2: i =500000;
case 3: i = 0;
case 8: i = 15;
}
.
в ассемблере это выгляди так:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
text:00412D22                 jnz     short loc_412D5C
.text:00412D24                 mov     eax, ds:40003Ch
.text:00412D29                 cmp     dword ptr [eax+400000h], 4550h
.text:00412D33                 jnz     short loc_412D5C
.text:00412D35                 mov     ecx, 10Bh
.text:00412D3A                 cmp     [eax+400018h], cx
.text:00412D41                 jnz     short loc_412D5C
.text:00412D43                 cmp     dword ptr [eax+400074h], 0Eh
.text:00412D4A                 jbe     short loc_412D5C
.text:00412D4C                 xor     ecx, ecx
.text:00412D4E                 cmp     [eax+4000E8h], esi
.text:00412D54                 setnz   cl
.text:00412D57                 mov     [ebp-1Ch], ecx
.text:00412D5A                 jmp     short loc_412D5F
пожалуста вам: 4 последовательных сравнения.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16833 / 5254 / 323
Регистрация: 30.03.2009
Сообщений: 14,145
Записей в блоге: 26
09.06.2009, 16:10     Что делает данный код и зачем такое кому-нибудь может понадобиться? #18
Цитата Сообщение от Patch Посмотреть сообщение
из-за чего интел и стал развивать технологию предсказания ветвлений.
Боюсь ошибиться, но branch prediction вроде бы не на интеле начали развивать.

К тому же статистика про переход на 8 операций - сама по себе ничего не говорит. Важно не сколько переходов, а насколько точно они предсказываются. На целочисленных задах как правило идёт куча ветвлений (if'ов) и предсказываемость здесь хуже. Плавающие задачи в основном состоят из циклов, где предсказатели как правило работаю хорошо. Ну это так, лирика

Цитата Сообщение от Patch Посмотреть сообщение
так что описанная мной ситуация - это нормально.
Если switch нормально пакуется в таблицу - это не нормально. Для компилятора.

Цитата Сообщение от Patch Посмотреть сообщение
C++
1
2
3
4
5
6
7
switch(i)
{
case 1: i = 500;
case 2: i =500000;
case 3: i = 0;
case 8: i = 15;
}
.
в ассемблере это выгляди так:
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
text:00412D22                 jnz     short loc_412D5C
.text:00412D24                 mov     eax, ds:40003Ch
.text:00412D29                 cmp     dword ptr [eax+400000h], 4550h
.text:00412D33                 jnz     short loc_412D5C
.text:00412D35                 mov     ecx, 10Bh
.text:00412D3A                 cmp     [eax+400018h], cx
.text:00412D41                 jnz     short loc_412D5C
.text:00412D43                 cmp     dword ptr [eax+400074h], 0Eh
.text:00412D4A                 jbe     short loc_412D5C
.text:00412D4C                 xor     ecx, ecx
.text:00412D4E                 cmp     [eax+4000E8h], esi
.text:00412D54                 setnz   cl
.text:00412D57                 mov     [ebp-1Ch], ecx
.text:00412D5A                 jmp     short loc_412D5F
пожалуста вам: 4 последовательных сравнения.
В данном случае мы имеем разреженный switch. т.е. в таблице, которая захватывала бы весь диапазон, было бы более 99% дырок. Если отбросить альтернативу в 50000, то остаётся 3 альтернативы, которые незачем лепить в таблицу. Короткие и разреженные switch'и через таблицу не делают, ибо выходит дороже
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
09.06.2009, 21:44  [ТС]     Что делает данный код и зачем такое кому-нибудь может понадобиться? #19
Цитата Сообщение от XuTPbIu_MuHTAu Посмотреть сообщение
#pragma,а что значит "разорванный цикл"?) Си - это низкоуровневый ассемблер. Свич тут просто определяет, с какой точки цикл начнется ( причем компилятор тут сделает таблицу джампов,а не кучу сравнений).
Я просто немного недопонимаю пока,как компилируется код,тонкости процесса,поэтому думал,что чтобы цикл вообще начал выполняться,при выполнении программы должна быть "прочитана" первая строка цикла ,а со свитчами как-будто попадаем в разорванный цикл(как-то так).Наивное представление.Но ваши ответы помогли понять,что инструкция цикла сначала компилируется в некий код,и,независимо от switch,цикл будет работать.

Цитата Сообщение от Evg Посмотреть сообщение
А задачка и вправду прикольная. Где такое достаёшь? Если в институте, то хороший у вас преподаватель
Не,я книжки сам читаю,это Страуструп,например.Кстати,был бы рад,если бы кто-нибудь навел меня на ответы к задачам,а то сверяться надо как-то,вас не мучать)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.06.2009, 21:56     Что делает данный код и зачем такое кому-нибудь может понадобиться?
Еще ссылки по теме:

C++ Скажите, что делает данный код?
Что делает данный цикл? C++
Что делает данный код? C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16833 / 5254 / 323
Регистрация: 30.03.2009
Сообщений: 14,145
Записей в блоге: 26
09.06.2009, 21:56     Что делает данный код и зачем такое кому-нибудь может понадобиться? #20
Кстати, в той теме я так и не раскрыл принцип работы switch'а. Напишу тогда сейчас

Грубо говоря, во многих учебниках объясняется так, что код:

C
1
2
3
4
5
6
7
8
9
switch (x) 
{ 
  case 1: 
   statement1 
   break 
  case 2: 
   statement2 
   break 
}
эквивалентен коду

C
1
2
3
4
5
6
7
(if x == 1) 
{ 
  statement1 
} else if (x == 2) 
{ 
  statement2 
}
На самом деле это не так. Правильный эквивалент будет

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
(if x == 1) 
  goto L1; 
else if (x == 2) 
  goto L2; 
else 
  goto Finish; 
 
L1: 
  statement1 
  goto Finish; // инструкция break 
L2: 
  statement2 
  goto Finish; // инструкция break 
Finish:
Исходя из этого дальше сам соображай, как этот цикл работает
Yandex
Объявления
09.06.2009, 21:56     Что делает данный код и зачем такое кому-нибудь может понадобиться?
Ответ Создать тему
Опции темы

Текущее время: 07:04. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru