Следующий лист дерева на ассемблере в девяти инструкциях и единственном регистре +15




Люди часто думают, что код на ассемблере читается не просто плохо, а очень плохо. Но я думаю, что это совершенно не так.


Я всегда считал, что читаемость кода на совести программистов и язык здесь совершенно не причём.


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


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


Но возможно я ошибаюсь. Увидим далее в статье.


Дерево для которого писался код, является упорядоченным, двусвязным и с произвольным количеством дочерних узлов. Каждый узел, описывается следующей структурой:


struct Node
  .parent      dd ?   ; к родительскому узлу
  .f_child     dd ?   ; к первому дочернему узлу
  .l_child     dd ?   ; к последнему дочернему узлу
  .next        dd ?   ; к следующему узлу в списке дочерних узлов
  .prev        dd ?   ; к предыдущему узлу в списке дочерних узлов
ends

Все дочерние узлы родительского узла образуют двусвязный список (поля .next, .prev). Родительский узел указывает только на начало и конец этого списка, соответственно через указатели .f_child и .l_child.


Задача: По заданному листу дерева, надо найти следующий лист. Если лист последний, найти первый лист дерева.


Это показано на Фиг.1; Синим пунктиром изображены связи через .prev и .next, черными линиями связи через .parent, .f_child и .l_child, а красными линиями, изображена последовательность переходов по алгоритму.


Если кому интересно зачем это мне понадобилось?
Я работаю над ОС-независимой GUI библиотекой на ассемблере. В этой библиотеке, каждое окно, представляет узел дерева с такой структурой.

Обсуждаемый поиск по листьям нужен, для передачи фокуса вперёд или назад при нажатии на клавиши Tab или Shift+Tab.

Конечно, в библиотеке это сложнее – нужно проверять хочет ли данное окно фокус и может ли его принять (например окно невидимое, или неактивное) в данный момент. Но это детали, которые никак не влияют на обсуждаемой теме.

Короткий ликбез для совсем уж начинающих. Чтобы им тоже было интересно.
В обсуждаемом коде используются только 3 инструкции:

CMP – сравнивает два операнда и устанавливает флаги состояния.

CMOVcc – условная пересылка данных – если условие cc выполнено, данные пересылаются из второго операнда в первый. Если условие не выполнено, то ничего не делается. Условия могут быть разными, но здесь используется только NEне равно, то есть, инструкция CMOVNE.

Jcc – условный переход. Условия те же самые как в CMOVcc. Если условие выполнено, переход делается. Если нет, исполнение продолжается вниз.

Квадратные скобки в выражениях на ассемблере означают содержание памяти на данном адресе. А значение в скобках, это адрес. То есть, примерно [eax+Node.f_child] означает, что вычисляется адрес как сумма содержания регистра eax и константы Node.f_child (Node.f_child == 4 в этом случае), читается содержимое так полученного адреса и с ним что-то делается – пересылается куда-то (mov, cmov) или сравнивается с чем-то (cmp) и т.д.

А вот и сам код в девяти инструкциях:


; Поиск следующего листа
; EAX == указатель к исходному листу дерева.

.next:
        cmp    [eax + Node.next], 0
        cmovne eax, [eax + Node.next]
        jne    .to_leaf

        cmp    [eax + Node.parent], 0
        cmovne eax, [eax+Node.parent]
        jne    .next

.to_leaf:
        cmp    [eax + Node.f_child], 0
        cmovne eax, [eax + Node.f_child]
        jne    .to_leaf

; Здесь EAX содержит указатель к следующему листу дерева.

Тот же код, но с комментариями. Сразу не смотрите. Проверим гипотезу о читаемости.
; Поиск следующего листа
; EAX == указатель к исходному листу дерева.

.next:                                   ; Ищем следующий узел:
        cmp    [eax + Node.next], 0      ; Это последний узел?
        cmovne eax, [eax + Node.next]    ; если нет, берём следующий...
        jne    .to_leaf                  ; ...и идём к выходу.

        cmp    [eax + Node.parent], 0    ; это корневой узел?
        cmovne eax, [eax+Node.parent]    ; если нет, берём родительский узел...
        jne    .next                     ; ...и ищем следующий узел.

.to_leaf:                                ; Идём вниз к листьям:
        cmp    [eax + Node.f_child], 0   ; это лист?
        cmovne eax, [eax + Node.f_child] ; если нет, идём вниз...
        jne    .to_leaf                  ; ...и повторяем

; Здесь EAX содержит указатель к следующему листу дерева.

У этого кода есть только один изъян. Если у дерева есть несколько корневых узлов, то алгоритм не будет переходить правильно от последнего к первому листу.


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


Этого можно достичь, добавив еще три инструкции. А точнее, те же три инструкции еще раз:


.next:
        cmp     [eax + Node.next], 0
        cmovne  eax, [eax + Node.next]
        jne     .to_leaf

        cmp     [eax + Node.parent], 0
        cmovne  eax, [eax+Node.parent]
        jne     .next

.to_first:                             ; Вот здесь.
        cmp    [eax + Node.prev], 0
        cmovne eax, [eax + Node.prev]
        jne    .to_first

.to_leaf:
        cmp    [eax+Node.f_child], 0
        cmovne eax, [eax+Node.f_child]
        jne    .to_leaf

А если нужен не следующий, а предыдущий лист?

Тот же самый код можно использовать и для поиска предыдущего листа, поменяв prev на next и f_child на l_child:


.prev:
        cmp    [eax + Node.prev], 0
        cmovne eax, [eax + Node.prev]
        jne    .to_leaf

        cmp    [eax + Node.parent], 0
        cmovne eax, [eax+Node.parent]
        jne    .prev

.to_last:
        cmp    [eax + Node.next], 0
        cmovne eax, [eax + Node.next]
        jne    .to_last

.to_leaf:
        cmp    [eax + Node.l_child], 0
        cmovne eax, [eax + Node.l_child]
        jne    .to_leaf

Вы наверное заметили, что весь код состоит из одинаковых триплетов:


        cmp    [variable], 0
        cmovne REG, [variable]
        jne    somewhere

Это дополнительно увеличивает удобочитаемость кода. Достаточно однажды понять, как эти три инструкции работают в связке, чтобы понять весь код.


А теперь давайте сравним этот код с эквивалентным кодом на C++.


У меня, с трудом (я не силён в C++), но получилось как-то так:


Структура:


struct Node {
  Node *parent;
  Node *f_child;
  Node *l_child;
  Node *prev;
  Node *next;
};

И сам код:


// Поиск следующего листа
// leaf == указатель к исходному листу дерева.

while (1) {
  if (leaf->next) {
    leaf = leaf->next;
    break;
  };
  if (leaf->parent)
    leaf = leaf->parent;
  else {
    while (leaf->prev) leaf = leaf->prev;
    break;
  };
};

while (leaf->f_child) leaf = leaf->f_child;

// Здесь, leaf указывает на следующий лист.

Я оставил только код, который непосредственно делает работу. Постарался оформить его, так, чтобы был более читабельным. Но все равно, ассемблерный код читается легче.


В коде на C++ нет никакого общего шаблона. Чтобы понять, как он работает, надо рассматривать каждую линию в отдельности и в связке с остальными.


А может это мне только кажется и зависит от знания языка? Или этот код можно написать лучше?


Конечно, я скомпилировал этот C++ код.

Компилировал так:


g++ -m32 -Os ./test.cpp -o ./test

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


.next:
        mov   edx, [eax + Node.next]
        test  edx, edx
        jnz   .to_leaf

        mov   edx, [eax + Node.parent]
        test  edx, edx
        jz    .to_first

        mov   eax, edx
        jmp   .next

.to_first:
        mov   edx, eax
        mov   eax, [eax + Node.prev]
        test  eax, eax
        jnz   .to_first

.to_leaf:
        mov   eax, edx
        mov   edx, [edx + Node.f_child]
        test  edx, edx
        jnz   .to_leaf

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


Но даже этот неидеальный код, мне кажется, читается лучше, чем оригинальный код на C++.


Напишите в комментариях, считаете ли вы ассемблерный код сложным для чтения? А что вам мешает – незнание языка, программисты, которые пишут плохо читаемый код, или вы думаете, что это свойство ассемблера и ничего нельзя сделать в принципе?




Комментарии (45):

  1. Kotofay
    /#23939855 / +2

    Компилятор делает более оптимально, минимизируя циклы обращения к RAM.

    • johnfound
      /#23939967 / +1

      Статья о удобочитаемости, а не о эффективности кода.


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


      Но опять – статья о читаемости и понятности, а не о производительности.

      • Kotofay
        /#23941645

        Кэш не регистр, быстрее быть не может априори.

        А мне всегда казалось, что чистый ассемблер это не про удобочитаемость.

        Тут, думаю, будут удобнее макрокоманды ассемблерные а не чистый код.

  2. forthuser
    /#23939859

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

    Си же код записи алгоритма более подходит для «обобщённого» понимания записи алгоритма вне прямого акцентирования на потоке команд управления данными.

    Как то так. ????

  3. lorc
    /#23939947 / +2

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

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

  4. picul
    /#23940075 / +6

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

    while ( !p->next && p->parent ) p = p->parent;
    p = p->next ? p->next : p;
    while ( p->f_child ) p = p->f_child;

    • johnfound
      /#23940339 / +1

      Ваш код не работает корректно если коренных узлов больше одного. То есть не эквивалентен C++ коду в статье.

      • picul
        /#23941651 / +4

        Даже если не вариант сделать список корней кольцевым, то можно так:

        while ( !p->next && p->parent ) p = p->parent;
        if ( p->next ) p = p->next;
        else
        {
            while ( p->prev ) p = p->prev;
        }
        while ( p->f_child ) p = p->f_child;

        • johnfound
          /#23941881

          Да, теперь все в порядке.


          Но самое интересное, что теперь ваш код компилируется до абсолютно тех же самых инструкции как и мой C++ код.


          Теперь надо только разобраться кто из них более удобочитаемый. :)

          • picul
            /#23942091 / +1

            Этого не может быть. Нормальный компилятор как минимум заиспользует инструкцию test вместо cmp.

            Удобочитаемый - тот, где путь выполнения выражен простыми для понимания конструкциями вроде цикла while. А не jmp и иди разбирайся куда оно там прыгает.

            • johnfound
              /#23942127 / +1

              Нет, вы не поняли. Я имел ввиду что ваш C++ код и мой C++ код, компилируются одинаково. Хотя и отличаются в исходниках. И они компилируются до варианта в статье – с test и использованием второго регистра (код спрятан в спойлере «Конечно, я скомпилировал этот C++ код».

  5. lgorSL
    /#23941525 / +1

    Я попробовал написать аналогичный код на kotlin (работоспособность не проверял, он больше для иллюстрации). Благодаря elvis оператору, nullable типам и хвостовой рекурсии выглядит сильно иначе. На мой взгляд, в таком декларативном стиле получается понятнее.

    tailrec fun lastFChild(n: Node): Node =
    n.fChild?.let{ lastFChild(it) } ?: n

    fun Node.first(): Node =
    prev?.first() ?: this

    fun cycle(n: Node): Node =
    n.next ?: n.parent?.let{ cycle(it) } ?: n.first()

    fun Node.findNext(): Node =
    lastFChild(cycle())

  6. auddu_k
    /#23941813

    Кажется, если написать на С с использованием goto получится тоже самое, что на Асм?

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

    В общем любопытно, лайкнул бы, да грехи карма не позволяет )

    • johnfound
      /#23941829

      На ассемблер можно и нужно писать сообразно идеи структурного программирования. Структурное программирование далеко не заключается в неиспользованием goto/jmp.

      • forthuser
        /#23942187

        Да, но при этом использование команды перехода не помогает эту структуру легко выявлять. И даже c использованием каких то отступов.

        Для примера в Форт при близкой семантике представления кода в сравнении с ассемблером всё же есть:

        и IF… ELSE… THEN
        и BEGIN… WHILE… REPEAT
        и BEGIN… UNTIL
        и DO… LOOP
        и CASE… OF… ENDOF… ENDCASE

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

        FOR… NEXT SWITCH BREAK CONTINUE…

        P.S. Даже на стандартном ассемблере для AVR примерно такое тоже возможно Конструкции структурного программирования для AT90s8515

        • johnfound
          /#23942305

          Вы просто путаете форму с содержанием. Все эти if-else-while, суть высокоуровневые конструкции, которым не место в ассемблере.


          Но суть структурного программирования совсем в другом. Можно программировать структурно и на ассемблере. А можно писать неструктурированный код и на C++.

          • forthuser
            /#23942385

            А, такой вариант облегчающий ассемблерное программирование? Дополнительные команды ассемблера2

            Из этого проекта для AVR

            И статья Машина времени для крошек.

            P.S. В любом случае при использовании в большой программе ассемблера программист старается формализовать в какой то степени и возможности по его эффективному использованию с точки зрения своих трудозатрат на написание кода на нём и дальнейшего его понимания.

            У меня достаточно личного опыта использования ассемблера в программировании на них, чтобы сформировался определённый взгляд на его счёт. ????

            Даже когда делал эмулятор PDP-11 процессора на x86 ассемблере и то от связки его с Форт не отказался.

          • forthuser
            /#23942429

            Вы просто путаете форму с содержанием.

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

          • forthuser
            /#23943349

            Можно программировать структурно и на ассемблере.

            Сложно, не используя комманды структурного перехода, а GOTO остаться в рамках «ограничений» структурного программирования.
            В этом аспекте рассмотрения можно сказать, что и Дракон язык схем сделан «структурным» при ограничениях его применения.

            P.S. Кстати, по возможностям изменения эргономики мнемоник ассемблерных команд показателен случай из программы AB (Algorithm Builder 5.44) для AVR Описание ассемблер мнемомик AB программы
            Учебник по работе с АВ

            Топик на форуме vrtp.ru пользователей данной программы:
            Algorithm Builder for AVR, Начинаем

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

          • qw1
            /#23943499

            Но суть структурного программирования совсем в другом. Можно программировать структурно и на ассемблере
            Из текста программы будет сложно извлечь структуру. Ведь структурное программирование — это использование вложенных друг в друга блоков типа «последовательность», «ветвление», «итерация». Языки высокого уровня эти блоки естественно отображают отступами, а на ассемблере границы и вложенность блоков никак нельзя понять, не читая весь код от начала до конца.

            • johnfound
              /#23943905

              Ассемблер читается очень и очень не так как ЯВУ. Отступы конечно можно использовать, некоторые так и делают. Но лучше всё-таки читать по ассемблерному – по вертикали и аккордами, а не отдельными инструкциями. Тогда и вложенность отличается прекрасно.

              • qw1
                /#23944225

                Например, по условному переходу не видно даже, вверх он идёт или вниз.
                А если вниз, что это за структура — ветвление (переход на else) или итерация (переход на конец цикла как часть условия while).

                • johnfound
                  /#23944253 / -1

                  Очень даже хорошо видно, если ограничить переходы в пределах страницы текста. А это кстати одна из хороших практик в ассемблере. Если надо прыгать дальше, значит нужно написать по другому.


                  Правильные имена меток тоже помогают лучше проследить структуру.

      • auddu_k
        /#23942795

        Тогда предложенный код можно на С написать так же как на АСМ и не факт, что будет менее понятно.

        Короче для меня пока тезис не доказан :-)

  7. Sayonji
    /#23942383 / +2

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

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

    • Refridgerator
      /#23942797

      названия переменных фиксированы (эах, оух, ...)
      Это скорее издержки IDE, которые для ассемблера от примитивного текстового редактора ничем не отличаются. В Visual Studio для MASM даже подсветки синтаксиса нет! Не говоря уже о сворачивании частей кода (аналог #region в шарпе). Я писал для этого расширение, которое в том числе позволяло привязывать к регистрам вменяемые имена (в виде всплывающих подсказок), и в идеале их вполне возможно отображать непосредственно в листинге.

    • johnfound
      /#23943025 / +6

      Тот факт, что у вас названия переменных фиксированы

      Не надо рассуждать о регистрах как о переменных. Они такими не являются. Переменные в ассемблере, находятся в памятью и имеют нормальные имена. А регистры, это регистры – ресурс которого просто нет в высокоуровневых языков.

      • forthuser
        /#23943391 / +1

        А регистры, это регистры – ресурс которого просто нет в высокоуровневых языков.

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

        P.S. И непосредственного доступа к стеку процессора нет в высокоуровневом языке, если не ввести, как в Форт, непосредственно доступ к управлению им и дополнительного стека оперирования данными вместо необходимости использования непосредственных регистров процессора в явной форме.

        • Kotofay
          /#23947647

          В Turbo C register вполне размещал переменную в регистр.

          Но если переменная использовалась не как регистровая, например брался её адрес, то она размещалась в памяти.

          • qw1
            /#23950809

            Тут речь о том, что ключевое слово register игнорируется компиляторами. Вы не проверяли, какой код сгенерирует Turbo C без слова register? Все обычные компиляторы так же по возможности поместят переменную в регистр. То есть, что есть это слово, что нет его, на кодогенерацию никак не влияет.

      • qw1
        /#23943481

        То есть, для повышения читаемости вы предлагаете писать код в стиле gcc -O0, если надо изменить переменную, надо её прочитать из памяти (используя символьную метку, чтобы видеть название переменной), модифицировать, записать в память. А больше чем на 1 операцию держать в регистрах не рекомендуется, чтобы человек, читающий код, не напрягал себя запоминанием соответствий регистров и переменных.

        • johnfound
          /#23943879

          Конечно нет. Я такое не писал. Опять повторяю, регистры (да и стек тоже) это ресурс, которого нет в языках высокого уровня. И поэтому нельзя рассматривать их с высокоуровневой точки зрения. Ничего не получится.


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

          • qw1
            /#23944233

            Тогда вернёмся на сообщение выше. В computer science, в алгоритмах, есть такая абстракция, как переменная. Она соответствует регистру, или нет? Если да, как узнать, какому регистру соответствует какая переменная в некотором участке кода?

            • johnfound
              /#23944255

              Она соответствует регистру, или нет?

              Нет.

              • qw1
                /#23944367

                Вы же писали

                Переменные в ассемблере, находятся в памятью и имеют нормальные имена
                Как в соответствии с этим реализовать, например, алгоритм Евклида с переменными a и b
                while (a != b)
                {
                    if (a > b)
                        a = a - b
                    else
                        b = b - a;
                }
                Чему в ассемблере соответствует переменная a? Регистру, адресу в памяти?

                • johnfound
                  /#23946575

                  Как в соответствии с этим реализовать, например, алгоритм Евклида с переменными a и b

                  А зачем нужно это ограничение «с переменными a и b»? Правильный вопрос будет «Как реализовать алгоритм Евклида?»

                  • qw1
                    /#23950827

                    Когда вы будете обдумывать реализацию алгоритма, или объяснять его кому-то, вы как будете называть объекты «a» и «b»?

                • go-prolog
                  /#23947425 / +1

                  Любопытно, а как Эвклид представлял переменные и поток команд в своем алгоритме.

                  Может не переменные, а парметры/неизвестные:

                  gcd(A,A)->A;
                  gcd(A,B)when A>B ->gcd(A-B,B);
                  gcd(A,B)->gcd(B,A).

  8. vasyakolobok77
    /#23943757

    Не холивара ради, но вот такой вопрос: а для arm-процессоров будете повторно такой код писать? Поскольку набор команд и подходы написания кода для arm совсем другие. Или же ОС-независимый GUI не включает ОС под arm?

    К чему это я – если вам нравится хардкор и оттачивание до мелочей, не эффективней ли писать на C (т.е. даже не плюсах)?

    • johnfound
      /#23943857

      Не холивара ради, но вот такой вопрос: а для arm-процессоров будете повторно такой код писать?

      Да, я считаю, что для разных процессоров код надо писать отдельно. Да, «по мотивам», но отдельно.

      • Kotofay
        /#23947663

        Вот сейчас создателям UNIX было обидно.

  9. 0x4eadac43
    /#23947689

    Можно и на плюсах написать такой же рекурсивный читабельный алгоритм, повторяющий указанный в статье один к одному: https://godbolt.org/z/nEcWE73Eo. (Рассматривается лишь случай с одним корнем. Функция find_leaf была заинлайнена.) Естественно, компилятор не заставишь использовать единственный регистр (но зачем?).

    Node * find_next(Node * node)
    {
        assert(node);
        if (node->next)
            return find_leaf(node->next);
        if (node->parent)
            return find_next(node->parent);
        return find_leaf(node);
    }
    
    Node * find_leaf(Node * node)
    {
        if (node->first)
            return find_leaf(node->first);
        return node;
    }

    • johnfound
      /#23947719

      Ну-у-у, а зачем вообще рекурсивно??? Нерекурсивный алгоритм в случае намного и читабельнее и компактнее.

      • 0x4eadac43
        /#23948675

        Читабельность - субъективная штука. Мне вот проще рекурсивный вариант воспринимать.

        Реализовал для интереса компактный вариант с циклом: https://godbolt.org/z/4fPhnThMG. С точки зрения компилятора не изменилось ничего (тот же самый скомпилированный код). Забавно

        • qw1
          /#23950855

          Это удивительно. Две рекурсивные функции компилятор сложил в одну большую нерекурсивную.