lookup table

Есть такой рабочий код:

Код (Text):

1. // af.h
2. typedef struct _AF_DATA
3. {
4.  unsigned long int h;
5.  double * x;
6.  double * y;
7.  //double * w;
8. } AF_DATA, * PAF_DATA;
9.  
10. extern AF_DATA af_data;
11.  
12. typedef double _fastcall (* fptr)(void);
13.  
14. extern const fptr ptr_af;
15. double _fastcall _af(void);
16. #define af_g(x) (__emit__(0xDD, 0x05, &x), _af())         // только для глобальных x и static x
17. #define af_l(x) (__emit__(0xDD, 0x85, &x), _af())          // только для локальных x
18.  
19. // af.cpp
20. #include "af.h"
21.  
22. AF_DATA af_data;
23.  
24. #pragma warning (disable : 4035)
25. __declspec(naked) double _fastcall _af(void)                // Аппаратная функция
26. {
27.  asm
28.  {
29.           push EDX
30.           mov EDX, dword ptr [af_data].(_AF_DATA)x       // EDX = &x
31.  
32.           FLD qword ptr [EDX]                                      // FLD x[0]
33.           FCOMIP ST, ST(1)                                         // xmin > x
34.           jae @zero1
35.  
36.           push EAX
37.           mov EAX, dword ptr [af_data].(_AF_DATA)h       // high = af_data.h
38.           FLD qword ptr [EDX + 8*EAX]                          // FLD x[high]
39.           FCOMIP ST, ST(1)                                         // xmax < x
40.           jbe @zero2
41.  
42.           push EAX                                                     // h = high
43.           push 0                                                         // l = 0
44.  
45.   @bisec: dec EAX                                                   // *h -> h - 1
46.           cmp EAX, dword ptr [ESP]                               // h - l == 1
47.           je @laprx                                                      // if true then EAX == l == *h
48.           inc EAX                                                        // h -> *h + 1
49.           add EAX, dword ptr [ESP]                               // EAX = h + l
50.           shr EAX, 1                                                    // EAX = (h + l)/2
51.           FLD qword ptr [EDX + 8*EAX]                          // FLD x[(h + l)/2]
52.           FCOMIP ST, ST(1)                                         // x[(h + l)/2] < x
53.           ja @h
54.           mov dword ptr [ESP], EAX                               // lower // l = (h + l)/2
55.           mov EAX, dword ptr [ESP + 0x04]                     // EAX = h
56.           jmp @bisec
57.   @h:     mov dword ptr [ESP + 0x04], EAX                  // higher // h = (h + l)/2
58.           jmp @bisec
59.  
60.   @laprx: FLD qword ptr [EDX + 8*EAX]                       // xl, x
61.           FSUB ST(1), ST                                             // xl, x - xl
62.           FLD qword ptr [EDX + 8*EAX + 0x08]                // xh, xl, x - xl
63.           FSUBRP ST(1), ST                                         // xh - xl, x - xl
64.           mov EDX, dword ptr [af_data].(_AF_DATA)y      // EDX = &y
65.           FDIVP ST(1), ST                                           // (x - xl)/(xh - xl)
66.  
67.           FLD qword ptr [EDX + 8*EAX]                         // yl, (x - xl)/(xh - xl)
68.           FLD qword ptr [EDX + 8*EAX + 0x08]               // yh, yl, (x - xl)/(xh - xl)
69.  
70.           pop EAX
71.           pop EAX
72.           pop EAX
73.           pop EDX
74.  
75.           FSUB ST, ST(1)                                          // yh - yl, yl, (x - xl)/(xh - xl)
76.           FMULP ST(2), ST                                        // yl, (yh - yl)*(x - xl)/(xh - xl)
77.           FADDP ST(1), ST                                        // yl + (yh - yl)*(x - xl)/(xh - xl)
78.           RET
79.  
80.   @zero2: pop EAX
81.   @zero1: pop EDX
82.  
83.           FSTP ST
84.           FLDZ                                                       // out of table => 0.0
85.           RET
86.  }
87. }
88. #pragma warning (default : 4035)

На C++Builder 6.
Делает следующее: линейно интерполирует в таблице, вне - функция возвращает нуль. Таблица находится в af_data.x af_data.y. Поиск в таблице - бинарный (или как его там... bisection из Numerical Recipes in C). Параметр уже лежит в ST(0).
Единственное, что здесь относится к оптимизации - это воткнуты инструкции матсопроцессора перед RET/после pop в соответствие с выводами, сделанными из http://www.wasm.ru/forum/viewtopic.php?pid=327834#p327834. Какие есть недочёты явные и как это всё оптимизировать? Функция вызывается Очень много раз за время решения задачи оптимизации - является частью целевой функции.

 

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

 

а где редактирование? хм... строчку не дописал

Код (Text):

1. const fptr ptr_af = _af;

 

Аргумент не попадает в таблицу предположительно в 0.3 случаях

 

таблица длиной 100-200

 

По общепринятому соглашению о вызовах функции могут свободно использовать\изменять регистры EAX,EDX и ECX, поэтому пушить\попить EAX и EDX да еще по нескольку раз - незачем, и уж тем более юзать локальную переменную [ESP], когда есть свободный регистр ECX

 

Функция вызывается из динамически скомпилированной функции типа _fastcall Borland. Та в свою очередь имеет два параметра - EAX и EDX. Один из которых указывает на массив с константами, другой - на массив с переменными. Функция использует только (исключительно) комманды работы с матсопроцессором, записывая в ESP - 8, ESP - 16, ESP - 24... параметры, переполняющие стек ST. Потом забирает. При компиляции функция _af может быть в любом месте выражения, то есть если будет так "a + @(x) + b", (@() - так она обозначается у меня в компиляторе), то при разборе строки справа налево регистры EAX и EDX будут испорчены к моменту вызова переменной a (для того чтобы не затёрлись запушеные параметры делается sub ESP, n*8 перед и add ESP, n*8 после). Вывод: пушить - надо.
В методе оптимизации (Хука-Дживса) используются ВСЕ регистры (EAX, EDX, EBX, ECX). Трогать их в вызываемых процедурах нельзя. Ну или тоже пушить. Думаю стек кэшируется, так что можно и поиспользовать локальные переменные, так? Ну исправить на ECX и EBX например тоже не долго. Может есть какие-то существенные фишки с порядком инструкций?

 

Код (Text):

1.           pop EAX
2.           pop EAX
3.           pop EAX
4.           pop EDX

? =)
это)?
Вообще-то первые два раза попаются совсем не для надёжности))), а для того чтобы ESP восстановить. Они вроде две в сумме короче и быстрее, чем add ESP, 8?

 

Если хочешь юзать свои нестандартные конвенции вызова, то пушь себе наздоровье А при стандартном соглашении вызывющий код сам должен знать, что EAX и EDX могут затереться и в случае необходимости запушить их до вызова функции и воостановить после - "от перестановки мест слагаемых сумма не меняется", т.е. что внутри ф-и сохранять\восстанавливать, что снаружи - без особой разницы, но так уж принято, что заботиться о сохранении EAX,EDX и ECX должен сам вызывающий код

 

Да, всё так. Вызывающий код, повторяю, генерируется динамически. Так что мне проще не в компиляторе вписывать, чтобы он в массив байтов добавлял 0x50, а в этой процедуре написать push EAX. Если конечно отсутствие работы со стеком между call и ret увеличит скорость ret'а, то не поленюсь перенести это.
Кроме того дериктива _fastcall в определение функции
__declspec(naked) double _fastcall _af(void)
роли не играет. Играла бы, если бы было
__declspec(naked) double _fastcall _af(a, b)
, тогда бы не смотря на naked в точке входа был бы код
mov [EBP - 08h], EDX
mov [EBP - 04h], EAX
, несмотря на то, что под них в фрейме не выделялось место (таков уже Borland C++ 6).
Просто рудимент.

Эти мои

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

Код (Text):

1.           pop EAX
2.           pop EAX

: Borland C++ 6 поднимает стек таким же образом для 1 дворда, только ECX использует.

 

так получается оптимальнее?

Код (Text):

1. __declspec(naked) double _fastcall _af(void) // Àïïàðàòíàÿ ôóíêöèÿ // @
2. {
3.  asm
4.  {
5.           push EDX
6.           mov EDX, dword ptr [af_data].(_AF_DATA)x      // EDX = &x
7.  
8.           FLD qword ptr [EDX]                           // FLD x[0]
9.           FCOMIP ST, ST(1)                              // xmin > x
10.           jae @zero1
11.  
12.           push EAX
13.           mov EAX, dword ptr [af_data].(_AF_DATA)h      // high = af_data.h
14.           FLD qword ptr [EDX + 8*EAX]                   // FLD x[high]
15.           FCOMIP ST, ST(1)                              // xmax < x
16.           jbe @zero2
17.  
18.           push ECX
19.           mov ECX, EAX                                  // h = high
20.           push EBX
21.           xor EBX, EBX                                  // l = 0
22.  
23.   @bisec: dec EAX                                       // *h -> h - 1
24.           cmp EAX, EBX                                  // h - l == 1
25.           je @laprx                                     // if true then EAX == l == *h
26.           inc EAX                                       // h -> *h + 1
27.           add EAX, EBX                                  // EAX = h + l
28.           shr EAX, 1                                    // EAX = (h + l)/2
29.           FLD qword ptr [EDX + 8*EAX]                   // FLD x[(h + l)/2]
30.           FCOMIP ST, ST(1)                              // x[(h + l)/2] < x
31.           ja @h
32.           mov EBX, EAX                                  // lower // l = (h + l)/2
33.           mov EAX, ECX                                  // EAX = h
34.           jmp @bisec
35.   @h:     mov ECX, EAX                                  // higher // h = (h + l)/2
36.           jmp @bisec
37.  
38.   @laprx: FLD qword ptr [EDX + 8*EAX]                   // xl, x
39.           FSUB ST(1), ST                                // xl, x - xl
40.           FLD qword ptr [EDX + 8*EAX + 08h]             // xh, xl, x - xl
41.           FSUBRP ST(1), ST                              // xh - xl, x - xl
42.           mov EDX, dword ptr [af_data].(_AF_DATA)y      // EDX = &y
43.           FDIVP ST(1), ST                               // (x - xl)/(xh - xl)
44.  
45.           FLD qword ptr [EDX + 8*EAX]                   // yl, (x - xl)/(xh - xl)
46.           FLD qword ptr [EDX + 8*EAX + 08h]             // yh, yl, (x - xl)/(xh - xl)
47.  
48.           pop EBX
49.           pop ECX
50.           pop EAX
51.           pop EDX
52.  
53.           FSUB ST, ST(1)                                // yh - yl, yl, (x - xl)/(xh - xl)
54.           FMULP ST(2), ST                               // yl, (yh - yl)*(x - xl)/(xh - xl)
55.           FADDP ST(1), ST                               // yl + (yh - yl)*(x - xl)/(xh - xl)
56.           RET
57.  
58.   @zero2: pop EAX
59.   @zero1: pop EDX
60.  
61.           FSTP ST
62.           FLDZ                                          // out of table => 0.0
63.           RET
64.  }
65. }

 

Может так сделать?

Код (Text):

1. @@:mov    eax,ecx          repeat
2.    add    eax,ebx          ;i=(max+min)/2
3.    shr    eax,1
4.    fld    qword[edx+eax*8] ;if X[i]>x then
5.    fcomip st,st(1)         ;max=i
6.    cmova  ecx,eax          ;else
7.    cmovna ebx,eax          ;min=i
8.    lea    eax,[ecx-1]
9.    cmp    eax,ebx          ;until max-1=min
10. jne @b

 

Вместо

Код (Text):

1. FSTP ST
2. FLDZ

можно

Код (Text):

1. fsub st,st

 

while надо - таблица может сразу состоять из 2 точек (ну в общем случае). Спасибо. Переделаю

 

Меня по скорости оптимизация интересует
FSUB [reg,reg] | 486 8-20
а
FSTP reg | 486 3
FLDZ | 486 4
так что оставлю.

 

Чтобы превратить repeat в while просто добавь jmp на lea перед циклом.

 

спасибо

 

Dukales

Ты надеешься еще где-то 486 найти ?!
На современных компах парочка FSTP + FLDZ действительно чуть быстрее FSUB, но от силы на 1-2 такта, которые на фоне call+ret и пары непредсказанных переходов - вообще никакой роли не играют

 

А это

Код (Text):

1. mov    eax,ecx
2. add    eax,ebx

всё же лучше записать так

Код (Text):

1. lea eax,[ecx+ebx]

 

Dukales
Раз тебя "по скорости оптимизация интересует", то прежде чем заниматься мелочной экономией тактов не мешало бы на сам алгоритм взглянуть и попытаться основные тормоза убрать. Например, почему бы в таблице _AF_DATA не задать еще один массив double *dx предвычесленных значений 1/(x[i+1]-x) и соотв-но вместо тормозного деления использовать умножение на dx ? Или почему бы не использовать таблицу с равномерным шагом, если функция достаточно гладкая ?