Построение правильного многоугольника

[Aether]

Добрый день.

Приведу для информации, заодно и для критики:

Код: (ASM)

use32
global calc

    ; void __cdecl calc(point* psPoint, int iCurrentVertex, int iTotalVertexes, float fRadius);

    ; typedef struct {
    ; float fX;
    ; float fY;
    ; } point;

calc:

    push ebp

    ; [esp + 20]   - параметр fRadius
    ; [esp + 16]   - параметр iTotalVertexes
    ; [esp + 12]   - параметр iCurrentVertex
    ; [esp + 8]    - адрес psPoint
    ; [esp + 4]    - адрес возврата для ret
    ; [esp + 0]    - значение ebp при входе в функцию

    mov       ebp, dword [esp + 8]     ; Теперь ebp указывает на структуру psPoint

    fld       dword [esp + 20]         ; st0 = fRadius

    fld1                               ; st0 = 1.
                                       ; st1 = fRadius

    fld1                               ; st0 = 1.
                                       ; st1 = 1.
                                       ; st2 = fRadius

    faddp                              ; st0 = 2.
                                       ; st1 = fRadius

    fldpi                              ; st0 = pi
                                       ; st1 = 2.
                                       ; st2 = fRadius

    fmulp                              ; st0 = 2pi
                                       ; st1 = fRadius

    fild      dword [esp + 12]         ; st0 = (float)iCurrentVertex
                                       ; st1 = 2pi
                                       ; st2 = fRadius

    fmulp                              ; st0 = 2pi * iCurrentVertex
                                       ; st1 = fRadius

    fild      dword [esp + 16]         ; st0 = (float)iTotalVertexes
                                       ; st1 = 2pi * iCurrentVertex
                                       ; st2 = fRadius

    fdivp                              ; st0 = 2pi * iCurrentVertex / iTotalVertexes = a
                                       ; st1 = fRadius

    fsincos                            ; st0 = cos(a)
                                       ; st1 = sin(a)
                                       ; st2 = fRadius

    fmul      st2                      ; st0 = fRadius * cos(a)
                                       ; st1 = sin(a)
                                       ; st2 = fRadius

    fstp dword [ebp]                   ; st0 -> psPoint.fX
                                       ; st0 = sin(a)
                                       ; st1 = fRadius

    fmulp                              ; st0 = fRadius * sin(a)

    fstp dword [ebp + 4]               ; st0 -> psPoint.fY

    pop ebp
    ret

Код: (C)

#include <stdio.h>

#define VERTEX_START 4
#define VERTEX_END 10

typedef struct {
    float fX;
    float fY;
} point;

void __cdecl calc(point* psPoint, int iCurrentVertex, int iTotalVertexes, float fRadius);

int main(int argc, char* argv[]) {

    for(int j = VERTEX_START; j < VERTEX_END + 1; j++) {
        printf("\nVertex num = %i\n", j);

        for(int i = 0; i < j; i++) {
        static point Temp;
        calc(&Temp, i, j, 100.);
        printf("Point [%2i] X = %10.4f Y = %10.4f\n", i, Temp.fX, Temp.fY);
        }
    }
    return 0;
}

Vertex num = 4
Point [ 0] X =   100.0000 Y =     0.0000
Point [ 1] X =     0.0000 Y =   100.0000
Point [ 2] X =  -100.0000 Y =     0.0000
Point [ 3] X =    -0.0000 Y =  -100.0000

Vertex num = 5
Point [ 0] X =   100.0000 Y =     0.0000
Point [ 1] X =    30.9017 Y =    95.1057
Point [ 2] X =   -80.9017 Y =    58.7785
Point [ 3] X =   -80.9017 Y =   -58.7785
Point [ 4] X =    30.9017 Y =   -95.1057

Vertex num = 6
Point [ 0] X =   100.0000 Y =     0.0000
Point [ 1] X =    50.0000 Y =    86.6025
Point [ 2] X =   -50.0000 Y =    86.6025
Point [ 3] X =  -100.0000 Y =     0.0000
Point [ 4] X =   -50.0000 Y =   -86.6025
Point [ 5] X =    50.0000 Y =   -86.6025

Vertex num = 7
Point [ 0] X =   100.0000 Y =     0.0000
Point [ 1] X =    62.3490 Y =    78.1832
Point [ 2] X =   -22.2521 Y =    97.4928
Point [ 3] X =   -90.0969 Y =    43.3884
Point [ 4] X =   -90.0969 Y =   -43.3884
Point [ 5] X =   -22.2521 Y =   -97.4928
Point [ 6] X =    62.3490 Y =   -78.1832

Vertex num = 8
Point [ 0] X =   100.0000 Y =     0.0000
Point [ 1] X =    70.7107 Y =    70.7107
Point [ 2] X =     0.0000 Y =   100.0000
Point [ 3] X =   -70.7107 Y =    70.7107
Point [ 4] X =  -100.0000 Y =     0.0000
Point [ 5] X =   -70.7107 Y =   -70.7107
Point [ 6] X =    -0.0000 Y =  -100.0000
Point [ 7] X =    70.7107 Y =   -70.7107

Vertex num = 9
Point [ 0] X =   100.0000 Y =     0.0000
Point [ 1] X =    76.6044 Y =    64.2788
Point [ 2] X =    17.3648 Y =    98.4808
Point [ 3] X =   -50.0000 Y =    86.6025
Point [ 4] X =   -93.9693 Y =    34.2020
Point [ 5] X =   -93.9693 Y =   -34.2020
Point [ 6] X =   -50.0000 Y =   -86.6025
Point [ 7] X =    17.3648 Y =   -98.4808
Point [ 8] X =    76.6044 Y =   -64.2788

Vertex num = 10
Point [ 0] X =   100.0000 Y =     0.0000
Point [ 1] X =    80.9017 Y =    58.7785
Point [ 2] X =    30.9017 Y =    95.1057
Point [ 3] X =   -30.9017 Y =    95.1057
Point [ 4] X =   -80.9017 Y =    58.7785
Point [ 5] X =  -100.0000 Y =     0.0000
Point [ 6] X =   -80.9017 Y =   -58.7785
Point [ 7] X =   -30.9017 Y =   -95.1057
Point [ 8] X =    30.9017 Y =   -95.1057
Point [ 9] X =    80.9017 Y =   -58.7785

[Dale]

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

Во-первых, совершенно непонятно, зачем каждый раз заново вычислять произведение 2*pi? Со времени предыдущего вызова это значение вряд ли изменится. Поэтому эту константу можно вычислить единственный раз, лучше всего - на этапе компиляции. Компилятор на фазе оптимизации именно так бы и сделал, если бы ему предоставили такой шанс; более того, по возможности еще и закэшировал бы на свободных регистрах. Это одна из причин, по которой гуру крайне не рекомендуют отбивать хлеб у компилятора и выполнять за него "оптимизацию", кодируя вручную. Практика показывает, что крайне редко кому удается действительно превзойти компилятор по части эффективности кода. Я уже не говорю о том, что этот трюк сразу отметает возможность выполнить программу на платформе, отличной от x86.

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

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

В-третьих, я бы еще попробовал такой, более общий алгоритм.
1. Получаем угол между соседними вершинами как fi = 2*pi/N.
2. Вычисляем синус/косинус этого угла (один раз!!!).
3. Располагаем первую точку, скажем, в (1, 0).
4. N-1 раз крутим эту точку вокруг начала координат на угол fi.
5. ...
6. Profit!!!

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

Ну и в качестве бонуса - замечательная статья на злобу дня "Оптимизация: ваш злейший враг", которую я перевел 6 лет назад, но актуальность она вряд ли когда-нибудь утратит.

[Aether]

(иначе зачем это баловство?)

Господин ..::SCRIBE::.. жаловался на неправильное приведение Extended к Real средствами Delphi. Я предположил, что вставка может помочь ему преодолеть ошибки, если они связаны с несовершенством библиотеки. Естественно, в Паскале соглашение о вызове другое, и подключать модуль на ассемблере в Delphi тоже нужно как-то иначе.

Во-первых, совершенно непонятно, зачем каждый раз заново вычислять произведение 2*pi?

Строго говоря, если бы я считал группу точек, то поступил бы иначе:

Код: (C)

typedef struct {
    float fX;
    float fY;
} dot;

typedef struct {
    unsigned int uiTotal;
    float fRadius;
    dot sCenter;
    dot[] psArray;
} dot_array_radial;

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

Ну и так далее по степеням двойки

В целом задача выглядит так: насколько симметрична функция sin(x)? Я знаю, что можно перейти от прямого вычисления к сумме, используя математические преобразования, но, если без компромисса в точности, то анализ должен быть на то, кратны ли вершины двум. Если кратны, то копируем четыре раза, если нет - два раза. Любой правильный многоугольник уже симметричен хотя бы для одной оси.

4. N-1 раз крутим эту точку вокруг начала координат на угол fi.

Как её повернуть без тригонометрии?

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

[Dale]

насколько симметрична функция sin(x)?

Обычная нечетная функция.

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

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

4. N-1 раз крутим эту точку вокруг начала координат на угол fi.

Как её повернуть без тригонометрии?

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

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

Это скорее "оружие последнего шанса", как пистолет Derringer для диверсанта или ядерная кнопка для президента, когда влип уже по самые уши, но хватаешься за последнюю возможность.

У меня есть товарищ, который очень любит делать ассемблерные вставки в код для микроконтроллеров Atmel AVR. Я ему много раз показывал, что при правильной оптимизации код на C ничем не уступает его творениям, но без толку - "у меня все под контролем". В итоге на рынке появились замечательные 32-разрядные ARM Cortex-M по бросовым ценам, и огромная масса накопленного за годы работы хорошо отлаженного кода превратилась в тыкву. А как показал рассмотренный пример, выбор правильного алгоритма дает неизмеримо больше, чем микрооптимизация на уровне машинного кода.

[Aether]

У меня есть товарищ, который очень любит делать ассемблерные вставки в код для микроконтроллеров Atmel AVR. Я ему много раз показывал, что при правильной оптимизации код на C ничем не уступает его творениям, но без толку - "у меня все под контролем". В итоге на рынке появились замечательные 32-разрядные ARM Cortex-M по бросовым ценам, и огромная масса накопленного за годы работы хорошо отлаженного кода превратилась в тыкву.

ARM я не отношу к микроконтроллерам - это уже полноценный МП, который может быть использован как МК. Я пробовал применить "С" в программировании 8 бит PIC, однако, не могу сказать, что это переносимо и эффективно. Слишком много деталей: у одного МК есть предделитель частоты, у другого пред- и постделитель, завязанный ещё с чем-то, у третьего нет ни того, ни другого, и нужен программный подход. В общем, МК - это отдельная тема, просто взять код, перекомпилировать его и решить так задачу не выйдет. Чтение документации, проработка деталей - от этого не уйти.
С другой стороны, весьма хитрая адресация в 8 бит PIC способна сделать код на ассемблере трудно воспринимаемым, возможно, мне просто не доводилось делать что-то тяжёлое.

[Dale]

Я пробовал применить "С" в программировании 8 бит PIC, однако, не могу сказать, что это переносимо и эффективно.

За младшие PIC ничего не скажу, я даже ни разу их в руках не держал. Как-то сразу не понравилась архитектура. А вот насчет 8-разрядных Atmel AVR мне неоднократно в литературе попадались упоминания, что их архитектура изначально проектировались с возможностью эффективной компиляции кода на C. Существует вполне пригодный клон GCC для AVR, хоть и не рекордсмен по компактности и скорости кода, но обладающий другими достоинствами (открытость, стандартность диалекта C). Так что далеко не все 8-разрядники одинаково непригодны для C.

Слишком много деталей: у одного МК есть предделитель частоты, у другого пред- и постделитель, завязанный ещё с чем-то, у третьего нет ни того, ни другого, и нужен программный подход. В общем, МК - это отдельная тема, просто взять код, перекомпилировать его и решить так задачу не выйдет. Чтение документации, проработка деталей - от этого не уйти.

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

Эта болезнь свойственна не только МК, и лечится она совсем другим лекарством - разделением кода приложения на слои абстракции. Выделяется аппаратно-зависимый Hardware Abstraction Level (HAL), содержащий необходимые низкоуровневые драйверы, и вся работа с оборудованием ведется через него. Объем HAL редко превышает 5% от общего объема кода, а остальные ~95% оказываются полностью переносимыми. Если эти 95% к тому же написаны на C, они легко портируются не только среди процессоров одного производителя, но и на любые другие, для которых существует компилятор. В случае ассемблера такой перенос, естественно, невозможен.

Ну и напоследок убийственный аргумент: какие инструменты для автоматизированного тестирования ассемблерного кода Вам известны? Я знаю людей, которые сейчас над ними работают, но большого прогресса пока не вижу. Язык C в этом плане гораздо благополучнее. А код, не покрытый тестами, я давно привык не принимать всерьез, неважно, написан ли он для монструозного сервера или крошечного микроконтроллера. Тестировать его вручную слишком дорого, а не тестировать - непрофессиональный подход.

[RXL]

PIC имеет в комплекте компилятор Си, но убогость архитектуры и скудость ресурсов ясно не в пользу Си. Пришлось лет 18 назад работать с 16F84 и еще лет 5 назад на 10F20x на асме. Цена/качество не в пользу PIC. Годится как заменитель небольшого набора низкоскоростной дискретной логики. Если скорость побоку, можно рискнуть писать на Си. Мои задачи были риалтаймовые.
А при чем тут тригонометрия и PIC?  

В случае ассемблера такой перенос, естественно, невозможен

Исключение: LLVM.