Главная » Игры, Теория » Замечания по технике программирования

0

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

Стековые переменные

Переменные могут быть стековыми или глобальными. Когда начинается выполнение функции, в стек программы заносится адрес возврата, происхо­дит переход на начало машинных инструкций данной функции. Вот типич­ная сигнатура функции:

function Foo(argl,arg2:integer):integer; var

tmpl,tmp2:integer;

begin

{ . . . }

end;

Стек программы начинается в верхних адресах, и при каждом занесении туда нового значения (равного размерности регистра, аккумулятора АХ или ЕАХ) указатель вершины стека (регистр SP или ESP) уменьшается, и стек смещается вниз. Когда значение извлекается из стека, указатель стека, на­оборот, увеличивается. Занесение в стек — ассемблерная инструкция push, извлечение — pop. Переход на начало машинных инструкций функции вы­полняется командой call (имя метки).

Команда call автоматически заносит в стек адрес возврата из функции, и когда тело функции завершилось, выполняется инструкция ret, которая из­влекает из стека адрес возврата.

В теле функции могут быть объявлены переменные и могут быть аргументы функции. В приведенном примере argl, arg2 — аргументы функции, tmpl, tmp2 — переменные внутри функции. Мы должны понимать, что и аргумен­ты, и переменные располагаются в стеке. Это — стековые переменные. Ар­гументы функции являются такими же стековыми переменными, что и пе­ременные, объявленные внутри функции. Аргументы функции — такие же переменные, просто инициализированные при вызове функции. В приве­денном примере можно также присвоить значение аргументам argi, arg2, как и переменным tmpi, tmp2.

function Foo(argl,arg2:integer):integer; var

tmpi,tmp2:integer; begin

argl := 0;

tmpi := 0; {…}

end;

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

type Pint = Лinteger; function Foo:Pint; var

tmp:integer; begin

tmp := 0; Foo := @tmp; end;

Это ошибка. Если мы хотим вернуть из функции адрес переменной, такая переменная должна быть статической и существовать вне стека. На языке С это спецификатор static, на Паскале — const.

function Foo:Pint; const tmp:integer = 0; begin

Foo := @tmp;

end;

int *Foo(void) {

static int tmp = 0; return Stmp;

Инициализация статических переменных выполняется один раз при запуске программы. Когда функция foo начинает выполняться, значение tmp уже 0. Если мы присвоим tmp при выполнении функции некоторое значение, то при следующем вызове функции tmp будет уже с новым значением. Это эк­вивалентно объявлению tmp вне функции обычной глобальной переменной, только ее область видимости ограничена данной функцией.

static int tmp = 0;

int *Foo(void) {

return &tmp;

}

Если мы в функции присвоили tmp некоторое значение, оно сохранится при завершении функции.

int *Foo(void) {

static int tmp = 0; tmp = tmp + 1; return Stmp;

}

Память под стековые переменные выделяется мгновенно. Не так обстоит с их инициализацией. При каждом вызове функции инициализация стеко­вых переменных происходит заново.

void Foo(void) {

int array[] = {0,1,2,3,4,5,6}; II…

}

При каждом вызове функции массив array будет инициализироваться зано­во. Если он не изменяется, лучше написать:

void Foo(void) {

static int array[] = {0,1,2,3,4,5,6}; //. . .

}

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

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

Операции умножения

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

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

Вот типичный пример. Можно объявить массив как одномерный, а можно как двумерный:

data:array[0..7][0..7] of byte; data:array[0..63] of byte ;

Когда компилятор обрабатывает двумерный массив, то реальный адрес вы­числяется по формуле:

N = Y*8 + X;

Старый компилятор бы изобразил это по-другому:

N = (N « 3) + X;

Небольшие операции умножения только разгоняют процессор, и если мы не пишем системного кода, можно руководствоваться только соображения­ми удобства.

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

type TRec = record {…}

end;

var data:array[0..2000] of TRec;

При доступе к каждому элементу такого массива в критичной по скорости программе лучше придумать что-нибудь другое, чем

data[N]

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

Есть и анекдотичные примеры. Например, у нас в программе используется 64-битовый хеш-индекс. Чтобы получить номер хеш-ячейки, нужно иметь остаток от деления этого неправдоподобно огромного числа на конечный размер хеш-таблицы:

type

THItem = record (…)

end;

PHItem = "THItem; const MAX_ITEM = 100000;

var hashTable:array[0..MAX_ITEM-1] of THItem;

function Look(index:U64):PHItem; begin

Look := @hashTable[ index mod MAX_ITEM ]; end;

Гораздо эффективнее делать размер хеш-таблицы таким, чтобы в двоичном представлении это было что-то вроде

10000000

Тогда, чтобы получить остаток от деления любого сколь угодно огромного числа на размер хеш-таблицы, мы должны просто провести поразрядную операцию AND с размером таблицы на единицу меньше:

10000000 1

=01111111

Приведенный пример в следующем листинге:

type

THItem = record (…)

end;

PHItem = "THItem;

const MAX_ITEM = (1 shl 18);

var hashTable:array[0.,MAX_ITEM-1] of THItem;

function Look(index:U64):PHItem;

begin

Look := ShashTable[ index and (MAX_ITEM-1) ];

end;

 

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии