@node Дешёвые пары
@subsection Дешёвые пары
Однако существует ещё одна проблема с которой придётся столкнуться.
Большинство куч в Скимах содержат пар больше чем других типов объектов.
Джонатан Рис однажды сказал, что куча состоит из пар на 45% в его реализации
Скимы, Scheme 48.Однако наше представление требует три @code{SCM} слова на одну пару ---
одно под слово, и ещё два под @sc{car} и @sc{cdr}. А есть ли какой нибудь способ представить
пару используя только два слова?
Давайте точнее определим чего мы хотим. Допустим, мы утверждаем следущее:
@itemize @bullet
@item
Если последние три бита значения @code{SCM} представляют собой нули -- @code{#b000}, тогда
это указатель, как всё и было ранее.
@item
Если последние три бита таковы: @code{#b001}, то верхние биты представляют целое число.
Это немного более строго чем раньше.
@item
Если последние три бита это @code{#b010}, то его значение, за
исключением трёх последних битов, содержит адрес пары.
@end itemize
Посмотрим на новый С код:
@example
enum type @{ string, vector, ... @};
typedef struct value *SCM;
struct value @{
enum type type;
union @{
struct @{ int length; char *elts; @} string;
struct @{ int length; SCM *elts; @} vector;
...
@} value;
@};
struct pair @{
SCM car, cdr;
@};
#define POINTER_P(x) (((int) (x) & 7) == 0)
#define INTEGER_P(x) (((int) (x) & 7) == 1)
#define GET_INTEGER(x) ((int) (x) >> 3)
#define MAKE_INTEGER(x) ((SCM) (((x) << 3) | 1))
#define PAIR_P(x) (((int) (x) & 7) == 2)
#define GET_PAIR(x) ((struct pair *) ((int) (x) & ~7))
@end example
Заметьте, что @code{enum type} и @code{struct value} теперь содержат
только описания?? для вектора и строки; и целые числа и пары теперь
стали специальными случаями. Код выше так же подразумаевает, что
@code{int} достаточно большой что бы хранить указатель, что в общем
случае не так.
Наш список примеров теперь таков:
@itemize @bullet
@item
Что бы проверить, что @var{x} это целое число, мы, как и ранее, можем написать @code{INTEGER_P
(@var{x})}.
@item
Что бы получить его значение, нам, как и ранее, нужно выполнить @code{GET_INTEGER (@var{x})}.
@item
Что бы проверить, что @var{x} это вектор, мы пишем:
@example
@code{POINTER_P (@var{x}) && @var{x}->type == vector}
@end example
Нам до сих пор нужно убеждаться, что @var{x} это указатель на @code{struct
value} что бы получить значение по ссылке и проверить его тип.
@item
Если мы знаем, что @var{x} это вектор, мы можем написать
@code{@var{x}->value.vector.elts[0]} что бы обратиться к его
первому элементу, как и ранее.
@item
Мы можем написать @code{PAIR_P (@var{x})}, что бы определить, является ли @var{x} парой,
а затем написать @code{GET_PAIR (@var{x})->car} что бы обратиться к его первому значению.
@end itemize
Это изменение в представлении данных сокращает ипользование кучи на 15%.
Это так же делает проверку на пару дешевле, так как не надо ссылаться на
память; необходимо всего лишь проверить последние два бита у значения @code{SCM}.
Это может быть значительным при проходе по списку, что является
обычной опрецией в Ским системах.
Опять таки, большинство реально существующих Ским систем используют слегка
изменённые реализации; например, если GET_PAIR удаляет последние три бита из
@code{x}, а не маскирует их, оптимайзер часто может связать удаление
со смещением элемента структуры, чьё значение мы хотим получить, так что
изменённый указатель такой же быстрый, как немодифицированный.
