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

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

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

    Indy_ Well-Known Member

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

    Цикл может существовать в виде замкнутости графа, но это статик подход и при этом нет понятия потока исполнения. В графе будет описано условие и все его ветви, но при исполнении будет выбран один путь в графе(если он есть). Вот пример: cmp R,N/jcc back. В графе будут описаны два блока - следующий за ветвлением и ветвь(и все дальнейшие блоки). При исполнении же поток инструкций образует петлю: cmp -> jcc -> cmp.. и при выделении кода в буфер ветвление пропускается, код за ним не трогается, это не нужно. Если условие не совпадёт, поток инструкций станет другим и ветвление пойдёт на стаб, который запустит снова визор.
     
  2. UbIvItS

    UbIvItS Well-Known Member

    Публикаций:
    0
    Регистрация:
    5 янв 2007
    Сообщения:
    6.067
    Вот и спрашивается ==>> нафига этот граф вообще нужоОнЪ, если никакой новой инфы об исследуемом коде он не даёт и дать не может.
     
    Indy_ нравится это.
  3. Indy_

    Indy_ Well-Known Member

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

    Ну вот поэтому я и сказал что гадят графом во все вопросы на всех ресурсах ;)
     
  4. DelAlt

    DelAlt Member

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

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

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

    Вы раздражаетесь лишь на собственное непонимание вопроса, ко мне и к матчасти это не имеет отношения. Особенно с учетом, что весь топ -- попытка переизобрести эту самую "матчасть" :)

    UbIvItS
    > ... щимить цикл в общем виде -- слишком напряжно для любой машины.

    Очевидно, вы этого не делали. Разложите для нас "слишком напряжно" во что-то более конкретное с оценкой временной сложности? Думаю, это внесет определенную ясность и даст почву для конструктивного обсуждения ;)
     
  5. Indy_

    Indy_ Well-Known Member

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

    > Описывать весь код не нужно, строится только то, что приходит с потока.
    А что собственно вы собрались строить, если это поток исполнения :preved:?

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

    > Проблема в том, что если мы сейчас возьмем любое ваше утверждение и попросим вас аргументировать

    Я уже всё аргументировал по теме. Выше задал вопрос - конкретный пример реализации, что там у вас llvm etc.. где решение ?

    Раз адекватно обьяснить не способны, зачем какие то графы нужны, то давайте пример, прогоним профайлером.
     
  6. DelAlt

    DelAlt Member

    Публикаций:
    0
    Регистрация:
    31 янв 2017
    Сообщения:
    62
    Indy_
    > Может наконец конкретно алгос приведёте, надоел ваш спам уже.

    Какой именно? Вы не умеете добавить вершин/ребер в список смежности? Я похож на учителя дискретки? У вас странные запросы.

    > Я уже всё аргументировал по теме.

    Можно пруфлинк на аргументацию по "... в графе найти замыкания ветвей, но мы его построить не можем - это слишком долго ..."? Я привел оценку по временной сложности построения и поиска циклов. Что у вас?
     
  7. Indy_

    Indy_ Well-Known Member

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

    > Какой именно?

    ВАШ алгоритм, который позволяет эффективно решить данную задачу. Если вы не знаете как я это решил, то опишу:

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

    > Вы не умеете добавить вершин/ребер в список смежности? Я похож на учителя дискретки?

    Да, похож. Вот зачем мне ваши рёбра графа, если графа нет. Зачем его строить, как и чем не понятно.

    Оценка может быть дана в общем виде на основе алгоритма, либо прямым снятием тайминга. Вы ничего этого не привели, кроме как какого то мусора из матчасти школьной по графам, когда математик какие то абстракции в уме крутит. Которые к реалу отношения не имеют.
     
Статус темы:
Закрыта.