1

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

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

对于一般的、自由的全局和局部符号，我只需对它们进行索引，并让每个范围（全局或局部）保留一个符号数组并使用索引快速查找它们。我对这种方法非常满意。

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

这是 python 中的一个示例，它反映了我希望用我的语言工作的内容：

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

有谁知道快速查找的任何巧妙技巧？我知道哈希图和展开树，所以如果有任何方法可以像我的其他查找一样高效，我会很有趣。

4

2 回答 2

3

一旦达到在哈希表中查找属性不够快的程度，标准的下一步就是内联缓存。您可以使用 JIT 语言，甚至字节码编译器或解释器来执行此操作，尽管在那里似乎不太常见。

如果您的对象的形状可以随时间改变（即您可以在运行时添加新属性），您最终可能会做一些类似于 V8 的隐藏类的事情。

于 2013-06-01T00:08:33.993 回答
1

一种称为映射的技术可以将每个属性的值存储在一个紧凑的数组中。属性名称对应于哪个索引的知识保存在辅助数据结构（同名映射）中，因此您不会立即获得性能优势（尽管如果许多对象共享一组属性，它确实会更有效地使用内存）。使用 JIT 编译器，您可以使映射持久化和常量折叠查找，因此最终的机器代码可以在属性数组中使用常量偏移量（用于常量属性名称）。

在解释器中（我将假设字节码），事情要困难得多，因为您没有太多机会专门针对特定对象进行代码。但是，我自己有一个想法，将属性名称转换为完整的键。维护一个全局映射，将完整的 ID 分配给属性名称。在向 VM 添加新的字节码（从磁盘加载或在内存中编译）时，扫描用作属性的字符串，并将它们替换为关联的 ID，如果以前没有看到过该字符串，则创建一个新的 ID。您现在可以使用稀疏数组，而不是在每个对象上存储哈希表或类似映射 - 或者在地图中，如果您使用地图 - 您现在可以使用稀疏数组，希望它们更紧凑，操作更快。

我没有改变来实现和测试这个，你仍然需要一个稀疏数组。除非您想让所有对象（或映射）占用与整个程序中不同属性名称一样多的内存字，否则就是这样。至少您可以用整数哈希表替换字符串哈希表。只需将 ID 的哈希表调整为键，您就可以进行一些优化：不要调用哈希函数（使用 ID 作为哈希），删除一些间接性并因此缓存未命中，节省处理病态错误哈希的复杂性功能等

于 2013-05-31T16:23:40.300 回答