Мелкие вопросы по теории

просто КОТ

Друзья, а вот маленький теоретический вопрос от простого Кота... Предположим лежит у нас препарированный микроконтроллер, с прошивкой внутри. В ней, разумеется, циклы задействованы, ветвления. так вот вопрос, сколько тактов тратится на принятия решения по операторам If, For, While?

Правильным ли будет полагать, что IF съедает 1 такт, WHILE 2 такта, а FOR три? Т.е. рассмотреть while как <If + goto>. А FOR как <i++ + if + goto> ?

Или же на практике эти инструкции исполняются рациональнее? Или это очень зависит от архитектуры процессора, и будет в корне различным для мелких RISK аврок, пиков и, скажем, более массивнго Cortex-M3, из STM-32. А как обстоит дело в процессорах полноразмерных? Типа х86

Реклама

Андрей Бедов

Или это очень зависит от архитектуры процессора

Да.

как обстоит дело в процессорах полноразмерных? Типа х86

Несколько десятков инструкций за такт.

Реклама

Slabovik

Андрей Бедов писал(а):Несколько десятков инструкций за такт.

просто КОТ, у процессоров нет инструкций типа IF, FOR и т.п. Потому что это инструкции языка программирования, по иерархии стоящего гораздо выше процессорных команд. Но у процессоров есть команды перехода по условиям. Условиями при этом служат биты из регистра состояния процессора, которые называют флагами. Флаги устанавливаются (1) или сбрасываются (0) автоматически в процессе обработки команд АЛУ. При исполнении команды перехода по условию анализируется конкретный флаг и производится (или не производится) переход. Естественно, заботу о флагах выполняет программист, задавая такую последовательность команд, чтобы состояние нужного флага было адекватным непосредственно перед исполнением команды перехода.

Например, команда перехода в процессорах на ядре i8080 занимает либо 7 либо 10 тактов. 7 - если переход не производится. 10 - если производится.
Вообще, у всего семейства i80xx эта система похожа. Правда, у современных процессоров очень развита конвейерность, поэтому что-то конкретное сказать по занимаемому времени невозможно однозначно - всё зависит от контекста.

У микроконтроллеров типа PIC, AVR картина тоже похожа. Конвейер там простенький. Команды также исполняются за 4 такта, однако их выполнение хитро распараллелено - с каждым тактом в конвейер поступает новая команда, а уже поступившая "переходит" на следующий такт исполнения. Поэтому заявляется, что скорость исполнения 1 команда за 1 такт. И это верно для пользователя, но неверно с точки зрения АЛУ. При исполнении команды перехода АЛУ может сбрасывать такую очередь "почти исполненных команд" (ну, это потому что чтобы не сбрасывать, АЛУ должно предугадывать состояние флагов, что реально сложно), поэтому следующая команда за командой перехода (если переход был выполнен) исполняется также 4 такта, а не 1, как было бы, если бы она была в ряду простых команд.

p.s. Я описал чрезмерно упрощённо, чтобы не залезать в дебри конкретных архитектур, где у каждой много своих тонкостей. Поведение каждой лучше всего узнавать в тех. документации на неё.

просто КОТ

Неверно выразился... Разумеется, процессор не исполняет команд в том виде напрямую. Упрощу вопрос до того, в каком виде он появился:

Можно ли полагать, что переход с конца в начало цикла WHILE выполнится быстрее чем у цикла FOR, т.к. нет необходимости обрабатывать пресловутое I++. Или это всё выполняется одинаково?

Вот этот вопрос для восьмибитных RISC интересует. И для X86.

Есть ли разница в том, какими инструкциями описываются процессору два этих разных цикла?

Реклама

Slabovik

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

Вот, например, фрагмент кода для PIC

Код: Выделить всё

Str2M_L4:

        ; далее выводим буфер строки с подготовленными в нём битами
        movlw   str_data_buf        ; указатель на буфер
        movwf   FSR
        movlw   MATRIX_LENGTH
        movwf   str_byte_cnt

        bcf     PIX_STRDY           ; опустим защелку строки
Str2M_L5:   ; большой круг - считаем байты буфера
        movlw   8                   ; количество бит в байте
        movwf   str_bit_cnt
Str2M_L6:   ; малый круг - вывод битов из байта буфера
        bcf     PIX_SYNC            ; опустим защелку пиксела
        rrf     INDF,F              ; вращаем буфер вправо через флаг переноса
        btfsc   STATUS,C
        goto    Str2M_L7            ; если флаг не 1, идём поставим 0
        bsf     PIX_DATA            ; а если 1 - то ставим 1
        goto    Str2M_L8
Str2M_L7:
        bcf     PIX_DATA
        nop
Str2M_L8:
        bsf     PIX_SYNC            ; защёлкиваем пиксель
        decfsz  str_bit_cnt,F       ; все биты выдвинули?
        goto    Str2M_L6            ; нет - возвращается за следующим
        incf    FSR,F
        decfsz  str_byte_cnt,F      ; весь буфер выдвинули?
        goto    Str2M_L5            ; нет - возвращаемся
        bsf     PIX_STRDY           ; защелкиваем строку на отображение
        return

Как видим, здесь два вложенных цикла. Но где же тут FOR или While? Их нет. А команды перехода выглядят как
cccfsflag
goto xxx
; где ccc - команда, flag - конкретный флаг, проверяемый на условие по выполнению этой команды ; при этом по соответствию флага процессор исполняет одну следующую за этой инструкцией команду, по несоответствии - скипает.

Реклама

Gisteresis

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

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

ПС: прочитал ваши сообщения выше, вижу вы и так это знаете

Реклама

Андрей Бедов

в современных процессорах код выполняется в так называемых конвеерах (их может быть несколько, а в видеокартах их сотни), они могут выполняться параллельно.

Об этом я пытался сказать выше. Просто выразился коряво.

Slabovik

Архитектура железа - это тоже отдельный вопрос и к конструкции While To отношения совершенно не имеющий. Перпендикулярное такое пространство. Поэтому при сравнениях принято, что при сравнении трансляций их исполнение производится на идентичной архитектуре. В противном случае эксперимент и вовсе некорректен. Потому что, к примеру, тот же I8086 не имеет возможности скорректировать код, который ещё формально не исполнен, но уже находится в конвейере, а 80286 такую коррекцию допускает, но ценой перезагрузки конвейера. Кстати, тот же микрокод, о котором вы говорите, как раз у 286-х и появился, и по факту он представляет собой нечто подобное коду для программируемой логической матрицы (предположение, причём не моё, т.к. людей, реально знающих, как оно работает, кроме "а вот в третьем пне", я не встречал)

А простейший конвейер - это вот как раз глядите те же PIC, как оно там.

p.s. Кстати, есть процессоры, исполняющие код Z80 за один такт. Секрет прост - такая же конвейеризация. Сами команды при этом как исполнялись 4 такта, так и исполняются.

Gisteresis

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

Архитектура железа - это тоже отдельный вопрос и к конструкции While To отношения совершенно не имеющий.

Отношение не имеющий к конструкции но имеющий ко времени выполнения.

просто КОТ на эту тему есть статьи в которых рассматриваются разные компиляторы и во что они транслируют те или иные операторы.
Вот например. Конечно это не для AVR но суть таже.
http://www.cyberguru.ru/programming/cpp ... page5.html

5 лет занимался геймдевом в качестве хобби. Заморочка с оптимизацией дает 10..30% прироста производительности и несравненно больше головняков и увеличение времени разработки программы. А при современных мощностях кристаллов выигрыш часто не оправдывает затраченных сил.

ypppu

По-моему, что WHILE, что FOR - это разновидности IF внутри цикла. Каждую итерацию производится проверка условия. При прочих равных принципиальной разницы нет.

Кстати в одной программке проверил ради интереса. Цикл WHILE выполняется за то же время, что и IF внутри LOOP. Однако, если внутри LOOP дать сравниение If x > 1000000, работает быстрее, чем If x < 1000000.

Вывод такой, что все факторы учесть трудно, нужно пробовать.

Slabovik

Я боюсь, что в утверждении

Gisteresis писал(а):в современных процессорах код выполняется в так называемых конвеерах (их может быть несколько, а в видеокартах их сотни)

заключено заблуждение. Точнее, некоторая путаница понятий о том, что такое конвейер, поток, вычислительное ядро (АЛУ) и чем они всё-таки отличаются, чтобы не лепить их в одну кучу.

Процедура распараллеливания простая на словах, однако на деле я настоятельно рекомендую зарыться в даташиты Microchip или AVR и посмотреть на простейших реализациях, как именно работает конвейер, и какие ограничения при этом существуют. Да, конвейер современного ядра Core2 весьма сложен, однако и у него куча ограничений, и вот "просто так" он не в состоянии исполнять две ветви кода сразу, а только по соблюдении условий. Но. НО! Вы понимаете, что при этом ускорения исполнения кода нет? О, отличный вопрос: а что же тогда? А отвечу. Предсказание переходов позволяет делать одну простую штуку (а на деле очень затратную штуку) - оно позволяет не сбрасывать конвейер при исполнении перехода по условию. А это экономит сотни тактов, необходимых для наполнения этого весьма длинного конвейера. Просто то время, пока конвейер наполняется, команды не исполняются - ядро просто стоит и ждёт...

Gisteresis

ypppu, видимо вы не смотрели во что транслируются эти операторы разными компиляторами. Есть компиляторы у которых текст оператора в 2..3 раза больше чем у оптимизированного.

Кроме того сильно сомневаюсь, что замер времени произведен верно. Разрядность таймера винды слишком низка для этого. Если мои предположения конечно верны.

Если вы пишите под ПК, советую использовать процессорный счетчик тактов. Причем алгоритм такой.
10 раз запускаем один и тот же тест и если время выполнения одинаково, считаем его верным. Или смотрим время за которое выполнилось большинство запусков, оно будет верным. Потому, что может произойти например прерывание и мы получим неверное время. Если хотите дам свой класс бенчмарка, хотя он не мной изобретен, он типовой.

Slabovik писал(а):Точнее, некоторая путаница понятий о том, что такое конвейер, поток, вычислительное ядро (АЛУ) и чем они всё-таки отличаются, чтобы не лепить их в одну кучу.

Конечно, но зачем сейчас вдаваться в эти подробности.

Поэтому и нужно задаться вопросом а нужно ли оптимизировать и если да тогда что.
Значительный прирос дает отыскание критически важного места и оптимизация только его.

ypppu

Я предполагаю, что для WHILE, FOR и IF конечный машинный код после компиляции может оказаться одинаковым. Вроде об этом изначально спрашивал просто КОТ.

Slabovik

С равной уверенностью можно предполагать, что он будет отличаться.
Реально же необходим разбор конкретного кода конкретного компилятора при абсолютно одинаковых условиях. В противном случае любое утверждение будет лишь предположением.

p.s. Я уже говорил, что нет никакого смысла притягивать язык высокого уровня к машинным командам? Почему? А потому что результат неоднозначен, и даже если вы сделаете работу и разберёте один компилятор, это отнюдь не будет означать, что другой компилятор будет вести себя так же

Gisteresis

просто КОТ писал(а): так вот вопрос, сколько тактов тратится на принятия решения по операторам If, For, While?
Правильным ли будет полагать, что IF съедает 1 такт, WHILE 2 такта, а FOR три? Т.е. рассмотреть while как <If + goto>. А FOR как <i++ + if + goto> ?
Или же на практике эти инструкции исполняются рациональнее?

1 зависит от компилятора и архитектуры.
2 нет, смотри ответ 1.
3 да.

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

Вот Slabovik выражает здравую мысль, имеет смысл сравнивать куски ассемблера.

А еще лучше просто бенчмарк написать и им сравнивать.

просто КОТ

Огромнейшее спасибо, други! Как я и подозревал, после компилятора всё не так и однозначно. Мой маленький вопрос решён, и я пошёл взвешивать результат. Задачи как таковой я не имел, если честно. Это небольшая лабораторная работа по алгоритмам сортировки. Просто мы считаем "шагами" по коду, а я задумался и решил привязать это к тактам процессора. Вот так...

Gisteresis

Бенчмарк решает задачу измерения затратности кода на конкретном оборудовании.

Еще аналитический метод есть оценки алгоритмов. Представляется формулой.
Например
https://ru.wikipedia.org/wiki/%D0%A1%D0 ... 0%BC%D0%B8
Вычислительная сложность - O(n^2).
https://ru.wikipedia.org/wiki/%D0%A1%D0 ... 0%B5%D0%BC
O(n log n) обычно, O(n) на упорядоченном массиве
И т.д.

Часто алгоритм можно построить таким образом, чтобы он выполнялся эффективнее. Например, чтобы избежать сортировки в массиве, можно при вставке элементов в него сразу выбирать необходимое место, чтобы он сразу был отсортирован.

ypppu

Вопрос по симистору.
IGT в документации - это максимальный длительный ток, который разрешено пропускать через управляющий электрод? Или же это минимальный ток, при котором симистор гарантированно откроется?

Просто смотрел документацию к Z01xxN и увидел сноску:
Note 1: minimum IGT is guaranted at 5% of IGTmax.

А по ГОСТ 20332-84 IGT - это наименьший постоянный ток управления тиристора, необходимый для включения тиристора.

Slabovik

Надо верить ГОСТу. Пороговый ток - это ток, необходимый для включения.
Ну а то, что

ypppu писал(а):minimum IGT is guaranted at 5% of IGTmax.

означает всего лишь, что минимальный пороговый ток составляет 5% максимального порогового тока. Это разброс, нижняя граница возможного порогового тока для всех приборов. В таблице же указан только максимальный.

А максимальный ток УЭ (гейта) к пороговому отношение имеет лишь то, что текут они в один электрод.

ypppu

Правильно я понял, что

IGTmax - это ток, в пределах которого я точно не спалю УЭ;
minimum IGT = IGTmax *5% - это ток, при котором симистор гарантированно включится?