@#pragma

Я ответил на вопрос,но точной формулировки не нашёл,хотел бы свериться(приложения с ответами нет).Задание:
Чёрный ящик.Что делается в данном примере?Зачем кому нибудь может понадобиться подобный код?Я так думаю,параметр count содержит количество незаполненных байт(или не байт,но кратно 8-ми) "чего-то",и копируется информация(из массива в массив),пока нужное количество элементов не скопируется.Только меня смущает одна штука:если count%8==7,то не рухнет ли вся программа из-за разорванного цикла?Может это ловушка,чтобы программа вылетела?

8

@XuTPbIu_MuHTAu

Единственное,что я пока смог придумать - уменьшить количество сравнений при копировании. Деление на восемь выполняется быстро,деление на восемь с остатком тоже шустро,а потом имеем то же копирование,но счетчик уменьшается в 8 раз реже.

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

Добавлено через 29 минут 46 секунд
Интересно.Буду говорить не называя цифр.
Я взял функцию
При малых count разницу не замерять особо.Начиная с некоторых cpy ощутимо отстает от send. При средних - отстает неощутимо. При больших cpy работает быстрее.
Не думаю, что у всех результат будет такой.Вообще-то,все должно зависить от механизма предсказания переходов,конвеера и проч. Интересно посмотреть,как выйдет на интеле,у меня атлончик.)

Добавлено через 18 секунд
Интересная темка,спасибо автору ^^

2

Evg

pragma, почитай тут, там я уже описывал семантику switch'а Проверьте себя. А хорошо ли вы знакомы со switch'ом?
А задачка и вправду прикольная. Где такое достаёшь? Если в институте, то хороший у вас преподаватель

Добавлено через 1 минуту 0 секунд
Не та том посте на "Спасибо" нажал

1

@EnzoMatrix

решил прогнать прогу под досбоксом, результаты поражают для 32000 прогонов при count=20, send работает в 2,5 раза быстрее, тока я так и не понял за счет чего такой прирост в скорости

0

Evg

В 2.5 раза быстрее чем что?

0

@EnzoMatrix

чем по индексам приравнивать, но если брать эту функцию,
то cpy пашет на 25% быстрее чем send

1

@Patch

еще бы.
switch - это цепочка if(a == b) goto xx.
в исходном коде таких ветвлений 7.
а ветвление(оно-же - условный переход)... если почитать документацию по процессорам...
при неверном предсказании обрывает суперконвейер, и требует заново загрузить данные из кэша.
что требует очень много времени.
а вот на старых процессорах тот код со switch делался быстрее, чем версия от XuTPbIu_MuHTAu

1

Evg

Всё равно я так и не понял, что сравнивалось с чем и кто круче

Добавлено через 1 минуту 48 секунд
По замыслу switch был коммутируемым переходом, а потому любой более-менее приличный компилятор в культурном случае построит switch на ОДНОМ динамическом переходе (правда при этом будет как минимум один статический переход, чтобы проверить, что значение ключа попадает в диапазон case'ов). В итоге код с 1000 алтернативами будет работать так же быстро, как код с 2000 альтернатив

1

@EnzoMatrix

извиняюсь за тупость высказывания*sorry*
сравнивалась send и
send работал в два с половиной раза шустрей это конструкции

0

Evg

Принципиальная разница между send'ом и этим кодом в том, что в твоём коде получается на одну итерацию цикла идёт одна пересылка. Т.е. количество операций передачи упарвления (который в данном случае НЕ являются полезными) равно количеству пересылок и, будем условно считать, что занимают 50% времени.

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

(to pragma)
Выше и написано, в чём заключается действие этого "чёрного ящика". Т.е. мы делаем некий аналог широкого копирования (которое ты видел в навороченной реализации strcpy), только широта тут заключается в том, что уменьшается доля бесполезных операций перехода. А switch нужен для того, чтобы правильно отпилить начало (т.е. чтобы при копировании 13 байт сначала скопировалось 5, а затем уже шло пачками по 8)

6

@EnzoMatrix

т.е. данный код (который с функцией send) можно назвать по стуи развернуутым циклом, если я правильно понял
и еще вопрос в чем такое принципиальное отличие между
и кодом, который привел хитрый_минай?

0

Evg

Я не знаю, как правильно по-русски, по-английски называется unrolled loop. По сути да, это раскрученный цикл с хорошим preloop'ом

Щас положу два кода, чтобы перед глазами было

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

Приличный оптимизирующий компилятор скорее всего сведёт второй код к первому (случай у нас простой), но вот в более сложном случае не факт, что это получится сделать

4

@Patch

для сравнений переменной с последовательными значениями - пожалуй.
и даже при этом код примерно вдвое диннее.
для непоследовательных значений - switch строится только на проверках каждого значения.
лучший код такого рода, который я видел делал что-то вроде бинарного дерева...
получалось на 20 значений - 6 условных переходов.

0

Evg

Ничего подобного. Либо у тебя в руках был плохой компилятор. В случае непоследовательных значений в таблице переходов на месте "дырок" долен стоять адрес default'а

Всё-таки какой компилятор и включены ли опции оптимизации (и какие опции)?

1

@Patch

вот не помню. вскрывал что-то для личных нужд...
а вкрывал я немало. любопытный очень.

0

Evg

Просто 6 услоных переходов - это слишком много. Для intel'а с его длинным конвейером это смерти подобно. Т.е. такой код либо строился в режиме без оптимизаций, либо case'ы были уж очень разреженные

1

@Patch

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

Добавлено через 3 минуты 59 секунд
кстати, только что сделал в VC++ код. с оптимизацией на скорость.
.
в ассемблере это выгляди так:
пожалуста вам: 4 последовательных сравнения.

0

Evg

Боюсь ошибиться, но branch prediction вроде бы не на интеле начали развивать.

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

Если switch нормально пакуется в таблицу - это не нормально. Для компилятора.

В данном случае мы имеем разреженный switch. т.е. в таблице, которая захватывала бы весь диапазон, было бы более 99% дырок. Если отбросить альтернативу в 50000, то остаётся 3 альтернативы, которые незачем лепить в таблицу. Короткие и разреженные switch'и через таблицу не делают, ибо выходит дороже

1

@#pragma

Я просто немного недопонимаю пока,как компилируется код,тонкости процесса,поэтому думал,что чтобы цикл вообще начал выполняться,при выполнении программы должна быть "прочитана" первая строка цикла ,а со свитчами как-будто попадаем в разорванный цикл(как-то так).Наивное представление.Но ваши ответы помогли понять,что инструкция цикла сначала компилируется в некий код,и,независимо от switch,цикл будет работать.

Не,я книжки сам читаю,это Страуструп,например.Кстати,был бы рад,если бы кто-нибудь навел меня на ответы к задачам,а то сверяться надо как-то,вас не мучать)

0

Evg

Кстати, в той теме я так и не раскрыл принцип работы switch'а. Напишу тогда сейчас

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

эквивалентен коду

На самом деле это не так. Правильный эквивалент будет

Исходя из этого дальше сам соображай, как этот цикл работает

3