‮Сдвиг по фазе (kincajou) wrote,
‮Сдвиг по фазе
kincajou

uncommon lisp: нет, SICP я ещё не прочитал :)

Подумал-подумал... и понял, что идея с тэгированными указателями хороша, но не совсем.
И код надо переписать опять.
Потому что вместо экономии памяти получается чуть ли не наоборот! Казалось бы, если мы используем "ненужные" биты для хранения какой-то нужной информации, мы поступаем экономно, а по взвешенному рассуждению выходит совсем иначе.
То есть, если бы тип атомарных данных у меня был бы всего один (например, только INTEGER и всё), тогда да, без особых вопросов (разве что всё равно пришлось бы хранить сами "атомы" где-то в куче). Но я хочу встроить чуть побольше типов, поэтому любой "атом" сейчас выглядит так:
typedef struct {
  void *type;
  void *data;
} atom_t;


т.е. при создании ЛЮБОГО атома неизбежно выделяется память под ДВА указателя, даже если это какой-нибудь boolean. Мне это всё время царапало череп изнутри, ведь получается так, что я сначала создаю cons (это же лисп всё-таки):
[ ATOM . nil ]
потом сам ATOM:
[ TYPE . DATA ]
и под хранение вышеупомянутого boolean отжирается... отжирается под хранение... ЧЕТЫРЕ указателя. На 64-битной машине это 4*8 = 32 байта! И 16 байт на машине 32-битной.
Непозволительная роскошь.
Поэтому тэги и идентификатор типа я включу в структуру cons. По-прежнему, будут присутствовать два "классических" поля (CAR и CDR), а тэг будет там, например, в виде компактного битфилда:
typedef struct {
  void *car;
  void *cdr;
  struct {
    uint8_t car:4;
    uint8_t cdr:4;
  } tags;
} cons_t;

С помощью костылей от компилятора (#pragma pack) эту структуру можно ужать очень сильно, наплевав на производительность - и вместо четырёх указателей на одно значение будет, в минимальном случае, два указателя (один из которых вообще не указатель, а само значение - целые числа так хранить вполне ok) и ещё один байт. С другой стороны, в реальных условиях под хранение нечётного количества байт будет выделяться объём, принудительно подогнанный под alignment, поэтому код можно слегка распустить:
typedef struct {
  void *car;
  void *cdr;
  struct {
    uintptr_t car:HALFPTR;
    uintptr_t cdr:HALFPTR;
  } tags;
} cons_t;

где HALFPTR - "пол-указателя" (для 32-битной машины это 16 бит, для 64-битной, очевидно, 32 бита). Решается макросами.

В любом случае, 65535 встроенных типов, думаю, мне хватит на первое время.

Такая реализация будет и достаточно экономной (хотя тоже не очень), и достаточно быстрой (конечно, это уже как остальное код написать).
Subscribe

  • Толерантность и равноправие

    Подразделение компании Disney, студия Lucas Film больше не будет сотрудничать с актрисой Джиной Карано, которая снималась в сериале "Мандалорец",…

  • Конечно, они ведь не могут

    "Я все еще не могу поверить, что Дж. К. Роулинг написала роман, который подразумевает, что транслюди могут быть злодеями" Это только белый…

  • Принуждение к равноправию

    С 2025 года фильмы, в которых хотя бы один из исполнителей главных ролей не принадлежит к "недопредставленным расовым и этническим группам", не…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 0 comments