Наиболее подходящая структура данных для доступа к полям динамических языков

Question

Я реализую динамический язык, который будет компилироваться в C #, и он реализует собственный API отражения (.NET слишком медленный, а DLR ограничен только более свежими и находчивыми реализациями).

Для этого я реализовал простой интерфейс .GetField (строка f) и .SetField (строка f, object val).До недавнего времени реализация просто переключала все возможные значения строки поля и выполняла соответствующее действие.Кроме того, этот динамический язык имеет возможность определять анонимные объекты.Для этих анонимных объектов сначала я реализовал простой алгоритм хеширования.

К настоящему времени я ищу способы оптимизации динамических частей языка, и я столкнулся с тем фактом, что алгоритм хэшированиядля анонимных объектов было бы излишним.Это потому, что объекты обычно маленькие.Я бы сказал, что объекты содержат 2 или 3 поля, как правило.Очень редко они будут содержать более 15 полей.На самом деле потребуется больше времени для хеширования строки и выполнения поиска, чем если бы я проверял равенство между ними всеми.(Это не проверено, только теоретически).

Первое, что я сделал, - во время компиляции - создал красно-черное дерево для каждого объявления анонимного объекта и поместил его в массив так,что объект может искать его очень оптимизированным способом.

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

Эти два длинных будут закодированы для поддержки 10 символов (A-za-z0-9_) каждый, что в основном является хорошим прогнозом размера полей.Для полей больше этого значения также будет предусмотрена специальная функция (более медленная), получающая строку.

В результате строки будут встроены (не ссылки), и их сравнения будут такими же дешевыми, как и длинные.сравнение.

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

Есть ли у кого-нибудь мысли или советы по поводу лучшей структуры данных для обработки динамических вызовов?

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

Answer 1

Я не знаю, полезно ли это, но я выкину это на всякий случай;

Если это компилируется в C #, знаете ли вы полный список полей во время компиляции? Так что в качестве идеи, если ваш код читает

// dynamic
myObject.foo = "some value";
myObject.bar = 32;

тогда во время разбора ваша таблица символов может построить int для каждого имени поля;

// parsing code
symbols[0] == "foo"
symbols[1] == "bar"

затем сгенерируйте код, используя массивы или списки;

// generated c#
runtimeObject[0] = "some value"; // assign myobject.foo
runtimeObject[1] = 32; // assign myobject.bar

и создать отражение в виде отдельного массива;

runtimeObject.FieldNames[0] == "foo"; // Dictionary<int, string>
runtimeObject.FieldIds["foo"] === 0;  // Dictionary<string, int>

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

Answer 2

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

Answer 3

Для такого небольшого набора данных (ожидаемые верхние границы 15) я думаю, что почти любое хеширование будет дороже, чем просмотр дерева или даже списка, но это действительно зависит от вашего алгоритма хеширования.

Если вы хотите использовать словарь / хеш, то вам нужно убедиться, что объекты, которые вы используете для ключа, быстро возвращают хеш-код (возможно, один хэш-код с одной константой, который создается один раз).Если вы сможете предотвратить столкновения внутри объекта (звучит довольно выполнимо), то вы получите скорость и масштабируемость (хорошо для любого реалистичного размера объекта / класса) хеш-таблицы.

Что-то, что приходит на ум, этоРуби символы и передача сообщений.Я полагаю, что символы Руби действуют как константа только для ссылки на память.Таким образом, сравнение является постоянным, они очень легкие, и вы можете использовать символы, такие как переменные (я немного запутался в этом и у меня нет интерпретатора Ruby на этой машине).Метод "вызова" Руби действительно превращается в передачу сообщений.Что-то вроде: obj.func(arg) превращается в obj.send(:func, arg) (символ "func").Я полагаю, этот символ делает поиск обработчика сообщений (как я его назову) внутри объекта довольно эффективным, поскольку его хеш-код, скорее всего, не нужно вычислять, как большинство объектов.

Возможно, что-то похожееможно сделать в .NET.