Оптимизация циклов.

Тема в разделе "WASM.A&O", создана пользователем Indy_, 20 май 2017.

Статус темы:
Закрыта.
  1. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    UbIvItS,

    Размер цикла определяется размером кольцевого буфера, в который накапливается трасса. Для примера выше такой буфер будет содержать 4 указателя. Никакие тяжёлые операции по времени не используются.
     
  2. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    Indy_, а что если твой код маленько поменять
    Код (ASM):
    1. L2:
    2.     push @L1
    3.     ret
    4. L1:
    5.    func()
    6.     dec eax
    7.     jnz L2
    8.     jmp ebx
    тело функции не нарушает цикл, но весьма меняет картину с регистрами/флагами/стеком.
     
  3. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    UbIvItS,

    Сохранится трасса для функи, затем если она совпадёт на следующей итерации цикл обнаружен. Если же внутри функи сработает какое то условие, трасса изменится и цикл обнаружен не будет. Если цикл обнаружен, то в буфер выделится и код функи.
     
  4. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    Indy_, и какой размер буфера?
     
  5. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    UbIvItS,

    Зависит от размера цикла. Если например 64 указателя помещается, то цикл может состоять макс из 64 инструкций. А почему вам именно память интересует ?
     
  6. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    полиморфизм может делаться без доп. записи/перезаписи, а засчёт сдвигов. jmp label -одно тело вызывается, а jmp [label+n] - другое
     
  7. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    то бишь опкоды меняются.
     
  8. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
  9. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    UbIvItS,

    Регистровые ветвления: [R + n], косвенные [M] etc так не могут быть обработаны, только релатив, иначе после выделения цикла управление может быть передано вникуда.
     
  10. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    отправка в хзк тожь вполне приемлема, ежель речь идёт о дидосах.
     
  11. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    UbIvItS,
    cy4.png
    Вот семпл для примера. Детектор ровный, но выделение цикла в буфер нужно есчо допилить. Там буфер в 64 поинтера.
    На кряклабе было вчера обсуждение, но я там тему закрыл что бы не гадили jit etc.
     

    Вложения:

    • Cycle3.zip
      Размер файла:
      43,4 КБ
      Просмотров:
      380
  12. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    Indy_, Молодец:good2:правда, мне сейчас не до тестов с вынью.
     
  13. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    Допилил немного.
     

    Вложения:

    • Cycle.zip
      Размер файла:
      184,5 КБ
      Просмотров:
      380
    UbIvItS и rococo795 нравится это.
  14. DelAlt

    DelAlt Member

    Публикаций:
    0
    Регистрация:
    31 янв 2017
    Сообщения:
    62
    Indy_
    Оперировать здесь надо не инструкциями, а базовыми блоками. Как только доходите до ветвления -- финализируете блок, добавляете в качестве вершины CFG и сбрасываете очередь инструкций.

    > Вначале нужно дать какое то чёткое определение - что такое цикл.

    Весна 2017-го. Пора бы дать определение циклу. Полностью поддерживаю! :)
    Например, в вашем случае -- это компонента сильной связности на графе потока управления.

    > Можно в графе найти замыкания ветвей, но мы его построить
    > не можем - это слишком долго, нужно всё сделать в динамике.

    Список смежности с добавлением за O(1) и Тарьян для компонентов за O(V+E) -- это долго?
    Если проапгрейдитесь до Intel 80286 -- будет с запасом, еще и хватит на замутить падающий снег по INT 8.
     
    TermoSINteZ нравится это.
  15. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    DelAlt,

    Как вы себе это представляете ?

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

    > финализируете блок, добавляете в качестве вершины CFG и сбрасываете очередь инструкций.

    Вы уже все форумы загадили этим мат. дерьмом, не нужно тут.
     
  16. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    DelAlt, Можешь накатать код и показать изложенное в действие, но у меня имеются подозрения, что Инди тута чертовски прав: щимить цикл в общем виде -- слишком напряжно для любой машины.
     
  17. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    UbIvItS,

    Могу запилить взятие всей процедуры конструктором, десяток строк занимает. Вот только смысл совсем не в этом.
     
  18. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    а ежель цикл спрятан в условных ветвлениях и надо выщимить параметры, при коих он активируется?
     
  19. Indy_

    Indy_ Well-Known Member

    Публикаций:
    4
    Регистрация:
    29 апр 2011
    Сообщения:
    4.775
    UbIvItS,

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

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

    Из всех существующих моторов только мой самый быстрый(kite). Но там тоже затыки по профайлу:
    1. Дизасм длин. Была моя тема на клабе, тестились все существующие моторы на профайл. Лучшим оказался dizahex. Xed на порядок тормознее, хотя заявляется как табличный. Жаль что все быстрые моторы не поддерживают NPX инструкции(fpu etc).
    2. Поиск описателей в графе. Используется обычный проход по связанным спискам. Можно использовать авл деревья.
    3. Аллокатор. Добавление элемента в граф приводит к выделению памяти, реконструкции графа - оптимизации и связыванию структур. Глобальный аллокатор нэйтив, нельзя использовать стек. Но можно заранее выделить буфер достаточного размера, но всё равно это затыка по скорости.

    Да и вообще я поднял тему для оптимизации визора, а он выполняется в реалтайме. Невозможен никакой анализ, иначе приложение повиснет.
     
  20. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    int x=100, y=123, P=93;

    while (x**y mod P > x){
    -------
    }
    ========================
    цикл какбе есть, но может не срабатывать.
    я про них даже не упоминал. :)
     
Статус темы:
Закрыта.