Структуры, в принципе, не обязаны быть сплошными. Компилятор мог бы, в принципе, хранить часть данных отдельно, оптимизируя патерны доступа и locality, но в современных языках до этого обычно не доходит. Как редко доходит и до несплошного стека, впрочем, я сегодня не об этом. В предыдушие выходные я выкинул из своего домашнего проекта иерархию классов, заменив классы несплошными структурами, до сих пор не могу нарадоваться, насколько все стало проще и понятнее.
Итак было синтаксическое двоичное древо. С узлами и листьями, которые все наследовались от базового класса, содержащего пару указателей, и нескольких обязательных полей. Наследуемые классы имели несколько виртуальных методов и некоторые контекстно-зависимые данные. Классов в синтаксическом дереве было, как операций в языке, несколько десятков. Был такой огромный файл с их определениями.
class Node {
Node *left, *right;
Lexem lexem;
OpCode code;
Type type;
public:
Node();
virtual ~Node();
...
};
class ConstantNode : public Node { ... };
class IntNode : public ConstantNode { ... int value; ... };
class StringNode : public ConstantNode { ... double value; ... };
...
class Op1Node : public Node { ... };
class MinusOpNode : public Op1Node { ... };
...
class Op2Node : public Node { ... };
class AddNode : public Op2Node { ... };
...
В результате я выкинул все эти классы. Оставил структуру, почти без внутренних методов:
struct Node {
Node *left, *right;
Lexem lexem;
OpCode code;
Type type;
void *ext;
Node() : ext(0){ ... }
~Node(){ delete ext; }
};
Важное отличие здесь - поле ext. Оно указывает на контекстно-зависимые данные для данной node. Фактически это продолжение структуры. То, что было непрерывно в классе теперь разорвано, и содержит дополнительный уровень indirection. Однако это дает и преимущества.
Во многих случаях никакого продолжения вообще нет, указатель просто нулевой.
Появляется возможность менять тип узла на месте. Так у меня работает компилятор, меняя тип по мере того, как удается что-то вычислить новое про данный узел. Сначала, после первого прохода компилятора, строится синтаксическое дерево, но никакой информации оно не содержит, кроме кодов операций. По мере вычислений типов заполняется поле type и иногда создаются вспомогательные структурки с дополнительными деталями и присваиваются полю ext. Дальше происходят некоторые другие вычисления и поле ext получает новое значение.
На самом деле все несколько сложнее, но идея та же. Как ни странно, оказалось, что почти никаких виртуальных методов мне не надо, таблица функций, индексируемая полем code делает все то же самое.
Какова же мораль? Мораль такова, что не все есть объект. Объект - это черный ящик. А иногда черный ящик не удобен, иногда нужна прозрачность, индексируемость. Синтаксическое дерево - вполне себе хороший объект. А узел дерева - вовсе не обязательно. База данных может быть объектом, но записям в базе данных лучше не быть объектами, а быть записями - структурами, состоящими из полей. Объект - там, где надо скрыть внутреннюю структуру, непосредственные данные - там где внутренняя структура должна быть легко доступна.
![[info]](http://l-stat.livejournal.com/img/userinfo.gif?v=92.1)
vtolkov
Заметки копируются сюда с задержкой примерно на сутки.
Я читаю комментарии в обоих журналах.