Быстрый поиск атрибутов в динамически типизированном языке?

Question

В настоящее время я разрабатываю динамически типизированный язык.

Одной из основных проблем, с которыми я столкнулся во время разработки, является выполнение быстрых поисков символов времени выполнения.

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

Однако для атрибутов в объектах проблема намного сложнее. Я не могу использовать для них одну и ту же схему индексирования, потому что я понятия не имею, к какому объекту я обращаюсь сейчас, поэтому я не знаю, какой индекс использовать!

Вот пример в питоне, который отражает то, что я хочу работать на моем языке:

class A: 
    def __init__(self): 
     self.a = 10 
     self.c = 30 

class B: 
    def __init__(self): 
     self.c = 20 

def test(): 
    if random(): 
     foo = A() 
    else: 
     foo = B() 
    # There could even be an eval here that sets foo 
    # to something different or removes attribute c from foo. 
    print foo.c 

Кто-нибудь знает какие-то трюки, чтобы сделать взгляд вверх быстро? Я знаю о хэш-картах и ​​деревьях, поэтому мне интересно, есть ли способы сделать это так же эффективно, как и мой другой поиск.

Answer 1

Как только вы достигли точки, где поиск свойств в хеш-таблице не достаточно быстрый, следующий следующий шаг: inline caching. Вы можете сделать это на языках JIT или даже компиляторах или интерпретаторах байт-кода, хотя, похоже, это встречается там редко.

Если форма ваших объектов может меняться со временем (то есть вы можете добавлять новые свойства во время выполнения), вы, вероятно, в конечном итоге сделаете что-то похожее на hidden classes V8.

Answer 2

Техника, известная как maps, может хранить значения для каждого атрибута в компактном массиве. Знание, имя атрибута которого соответствует тому, какой индекс поддерживается во вспомогательной структуре данных (одноименная карта), поэтому вы не сразу получаете преимущество в производительности (хотя он использует память более эффективно, если многие объекты используют набор атрибутов). С JIT-компилятором вы можете сделать постоянный и постоянный поиск карты, поэтому конечный машинный код может использовать постоянные смещения в массиве атрибутов (для постоянных имен атрибутов).

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

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