Ускорить функцию

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

хотябы квадраты вычислить один раз...

он их там модифицирует

Второе — это посчитать общие члены выражений один раз и записать в константную переменную. SML_SQR(line.p2.x), SML_SQR(line.p2.y), line.p2.y * target.y встречаются по тексту по несколько раз, а вычисляются каждый раз заново.

Про аргументы сказали. Вопрос (к сабжу значения не имеет): такой вид комментирования присутствует во всем проекте?

такой вид комментирования присутствует во всем проекте?

Такой ответ устроит?

Как минимум не передавать аргументы функции по значению.

Я для ускорения вычислений модифицирую p2 и target. Поэтому придется снимать копию. Что приводит к тому же, откуда пришли.

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

Ну или так.

думаю уже на 2м уровне вложенности там будет труба с читаемостью. Но зато алгоритм понятен, да.

У меня такое ощущение, что, посчитав одинаковые части выражений, ты сможешь безболезненно заменить свои модифицированные переменные на разности, и передача по значению станет не нужна.

это чем так нарисовано?

Как ты выделяешь память под структуры? Проверь локальность данных.

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

100% не будет.

Руками и ASCII символами.

Руками и ASCII символами.

Если б код так же хорошо писали, как схемы чертите...

За меня это делает компилятор:

void test()
{
    SmlLine line =
            (SmlLine){(SmlPoint){rand(), rand()},
                      (SmlPoint){rand(), rand()}};
    SmlPoint point = (SmlPoint){rand(), rand()};

    SmlGradientValue(line, point);
}

Покажи, где плохо. Обосрать каждый может.

100% не будет.

Да ладно, cache miss мимо обоих аргументов вполне может выйти в лишние пару-тройку сотен циклов.

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

А поскольку проект проприетарный, как я понял, — коммерческие проекты бесплатно я не консультирую.

void test()
{
    SmlLine line =
            (SmlLine){(SmlPoint){rand(), rand()},
                      (SmlPoint){rand(), rand()}};
    SmlPoint point = (SmlPoint){rand(), rand()};

    SmlGradientValue(line, point);
}

И сколько в этой тестовой функции реально занимает вычисление SmlGradientValue(), а сколько — вызов 6-ти randr()?

Прям интересно стало. К чему такая информированность каждой строки кода? Учебный проект? Преподаете какие нибудь алгоритмы компьютерной графики?

А поскольку проект проприетарный, как я понял,

А на это вас натолкнул файл LGPL на скриншоте. Ну ок, чо.

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

А на это вас натолкнул файл LGPL на скриншоте.

А, ну слепой, значит, не видел. Натолкнуло отсутствие релевантных ссылок в гугле.

Как объявлены структуры?

И сколько в этой тестовой функции реально занимает вычисление SmlGradientValue(), а сколько — вызов 6-ти randr()?

 Nul function: 100 000 000 cycle took 30.270328 s
Full function: 100 000 000 cycle took 32.362579 s

Натолкнуло отсутствие релевантных ссылок в гугле.

А я должен о нем кричать во все стороны?

Как объявлены структуры?

/* E */ typedef struct
{
    int32_t x;
    int32_t y;
} SmlPoint;

/* E */ typedef struct
{
    SmlPoint p1;
    SmlPoint p2;
} SmlRect;

/* E */ typedef SmlRect SmlLine;

Алгоритм по ссылке какой-то очень сложный.
Я бы развернул систему координат так, чтобы отрезок AB лёг строго на ось OX.
При этом проекция D точки T будет получаться просто отбрасыванием координаты y.

Поворот на угол L выполняется по формулам

x_new = x_old * cos(L) - y_old * sin(L)
y_new = x_old * sin(L) + y_old * cos(L)

x_new = x_old * AB.x + y_old * AB.y

short Grad(const Point &a, const Point &b, const Point &t)
{
    int64 ab_x = b.x - a.x;
    int64 ab_y = b.y - a.y;
    int64 new_ab_x = ab_x * ab_x + ab_y * ab_y;
    int64 new_at_x = (t.x - a.x) * ab_x + (t.y - a.y) * ab_y;
    if(new_at_x <= 0) return 0;
    if(new_at_x >= new_ab_x) return 255;
    return 255 * new_at_x / new_ab_x;
}

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

Идея хорошая, но ускорения не получилось:

Manhunt's function: 100 000 000 cycle took 34.813816 s
Full function: 100 000 000 cycle took 32.362579 s

ыыы! В общем int64 там не нужен. 1) Он жрет время, 2) Чтобы добиться переполнения нужны текстуры настолько больших размеров, что они не влезают в память.

Поменял на int32. В общем вы волшебник.

int32 function: 100 000 000 cycle took 31.315514 s

Спасибо вам большое.

Manhunt интересный способ предложил. Но я на другое хотел обратить внимание, пригодится на будущее. Вот ты пишешь:

    if ((line.p1.x == line.p2.x) &&
        (line.p1.y == line.p2.y))
        return 0;

    line.p2.x -= line.p1.x; line.p2.y -= line.p1.y;

Здесь у тебя дважды вычисляется разность line.p2.x - line.p1.x (один раз при сравнении, второй раз при выполнении -= ), дважды вычисляется разность line.p2.y - line.p1.y и выполняется до двух условных переходов.

Компилятор не такой умный, чтобы это оптимизировать. Вот что получается:

        cmpl    %eax, %ebx
        jne     .L2
        cmpl    %edx, %esi
        je      .L8
.L2:
        subl    %eax, %ebx
        subl    %edx, %esi

Как это переписать короче и читабельнее? Примерно так:

    int32_t dx = line.p2.x - line.p1.x;
    int32_t dy = line.p2.y - line.p1.y;
    if (dx | dy == 0)
        return 0;

Результат:

        subl    %edx, %ebx
        sete    %cl
        subl    48(%esp), %eax
        orl     %eax, %ecx
        je      .L2

Что касается переменных, у компилятора нет «стоимости создания переменных». Всё вычисляется в регистрах. При недостатке регистров — сохраняется/загружается из стэкового фрейма. Цена создания фрейма стека константная: одно вычитание при входе в функцию и одно сложение при выходе.

Кстати, насколько велика разница, если считать на флотатах?

Вопрос такой, что за SML_SQR?

Лень читать тред, мб уже сказали, так что не бейте за повторение:

if (((int64_t)-SML_SQR(line.p2.x)   - SML_SQR(line.p2.y)) *
                 (-line.p2.x * target.x - line.p2.y * target.y) <= 0)
        return 0;

/* comments stripped */

if (((int64_t)-line.p2.x * target.x - line.p2.y * target.y +
                SML_SQR(line.p2.x)    + SML_SQR(line.p2.y)) <= 0)
        return 255;

Тут все по 2 раза вычисляется, хотя между условиями ничего не меняется. Можно один раз же посчитать квадраты, произведения ну и т.д. не?

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

Raw function: 100 000 000 cycle took 58.118729 s
Int function: 100 000 000 cycle took 41.755593 s

Спасибо, буду знать.

И более того, далее в части

/* II & III */

использовать уже посчитаные значения.

К моему вопросу.

Если SML_SQR( a ) = a * a, то

Dx = ((SML_SQR(line.p2.x) * target.x + line.p2.y  * line.p2.x * target.y)) /
                (SML_SQR(line.p2.y) + SML_SQR(line.p2.x));
return (unsigned char)(Dx * 255 / line.p2.x);

можно записать как

Dx = (unsigned char)(255 * (line.p2.x * target.x + line.p2.y * target.y)) /
                (SML_SQR(line.p2.y) + SML_SQR(line.p2.x)) );

И аналогично в другом условии. Избавляемся от пары умножений и деления.

int32_t dx = line.p2.x - line.p1.x;
int32_t dy = line.p2.y - line.p1.y;
if (dx | dy == 0)
    return 0;

Битовые операции с signed int? Хм, знатное извращение.

Битовые операции с signed int? Хм, знатное извращение.

А шо, инты уже имеют минус ноль, отличный от плюс ноля?

А шо, инты уже имеют минус ноль, отличный от плюс ноля?

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

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

Здрасти, приехали.

Constraints

Each of the operands shall have integer type.

Semantics

The usual arithmetic conversions are performed on the operands.

The result of the | operator is the bitwise inclusive OR of the operands (that is, each bit in the result is set if and only if at least one of the corresponding bits in the converted operands is set).

http://asciiflow.com/, например.

какая(времени)цель?

Здрасти, приехали.

Похоже я в очередной раз попутал с операциями сдвига signed.

Перепиши на ASMе же!

Простите, а вы не могли бы подробнее рассказать, почему мы принимаем cos\sin равными таким значениям? Очень интересно.

Пфф. Только «анскильные лалки» (с) пишут на асме. Настоящие братюни сразу в машинных кодах.