algorithm - 动态类型语言中的快速属性查找？

Question

我目前正在开发一种动态类型语言。

我在开发过程中面临的主要问题之一是如何进行快速运行时符号查找。

对于一般的、免费的全局和局部符号，我只是简单地将它们编入索引，让每个作用域(全局或局部)保存一个符号数组，并使用索引快速查找它们。我对这种方法非常满意。

但是，对于对象中的属性，问题要困难得多。我不能对它们使用相同的索引方案，因为我不知道我当前正在访问哪个对象，因此我不知道要使用哪个索引!

这是一个 python 示例，它反射(reflect)了我想用我的语言工作的内容:

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

有谁知道快速查找的巧妙技巧？我知道 HashMap 和伸展树(Splay Tree)，所以我很感兴趣是否有任何方法可以像我的其他查找一样高效。

Answer 1

一旦您发现在哈希表中查找属性的速度不够快，下一步的标准步骤是 inline caching .您可以在 JIT 语言甚至字节码编译器或解释器中执行此操作，尽管它似乎不太常见。

如果您的对象的形状可以随时间改变(即您可以在运行时添加新属性)，您可能最终会做类似于 V8 的 hidden classes 的事情。 .