rstrategies¶

一个用于在基于 RPython 工具链的虚拟机中实现存储策略的库。rstrategies 可用于任何语言或语言族的虚拟机。

该库是 Anton Gulenko 的硕士论文的一部分开发的。Anton Gulenko.

描述优化“动态类型语言中集合的存储策略”的原始论文由 C.F. Bolz、L. Diekmann 和 L. Tratt 撰写，可以在这里找到这里.

到目前为止，该库已被 3 个虚拟机采用：RSqueak、Topaz (在此处分叉) 和 Pycket (在此处分叉).

概念¶

集合通常被同构地使用，即它们只包含相同类型的对象。像整数或浮点数这样的原始数值类型对于优化尤其有趣。这些情况可以通过将这些对象的未装箱数据存储在连续的内存中来优化。这是通过让一个特殊的“策略”对象处理集合的整个存储来实现的。集合对象持有两个独立的引用：一个指向其策略，另一个指向其存储。对集合的每个操作都委托给策略，策略在需要时访问存储。策略可以切换到更合适的策略，这可能需要转换存储数组。

用法¶

以下是将 rstrategies 集成到 RPython 虚拟机中所需的步骤。由于该库的特殊性质，仅仅调用一些 API 方法是不够的；该库必须使用元类、mixin 和其他元编程技术集成到现有的虚拟机类中。

此处描述的步骤序列类似于“设置演练”，可能有点抽象。要查看一个具体的示例，请查看 SingletonStorageStrategy、StrategyFactory 和 W_PointersObject 来自 RSqueak 虚拟机。代码也写有很好的注释。

基础¶

目前，rstrategies 库支持固定大小和可变大小的集合。这可用于优化各种原始数据结构，如数组、列表或常规对象。在本文档中，任何这些都称为“集合”。虚拟机应该有一个用于集合的中心类或类层次结构。为了扩展这些类并使用策略，库需要访问集合对象两个属性的访问器方法：策略和存储。最简单的方法是在根集合类的主体中添加以下行

rstrategies.make_accessors(strategy='strategy', storage='storage')

这将为相应的属性生成 4 个访问器方法 _[get/set]_[storage/strategy]()。或者，手动实现这些方法或覆盖 StrategyFactory 中的 getter/setter。

接下来，必须定义策略类。这需要一个具有专用根类的小类层次结构。在此根类的定义中，包含以下行

__metaclass__ = rstrategies.StrategyMetaclass
import_from_mixin(rstrategies.AbstractStrategy)
import_from_mixin(rstrategies.SafeIndexingMixin)

import_from_mixin 可在 rpython.rlib.objectmodel 中找到。如果在虚拟机的其他地方安全地执行索引检查，则可以使用 rstrategies.UnsafeIndexingMixin。如果需要自己的元类，则可以使用多重继承将自己的元类与 rstrategies 元类结合起来如这里所示。还要实现一个 storage_factory() 方法，该方法返回 rstrategies.StorageFactory 的实例，如下所述。

一个示例 AbstractStrategy 类，它还存储一个额外的 space 参数，可能如下所示

class AbstractStrategy(AbstractStrategy):
    _attrs_ = ['space']
    _immutable_fields_ = ['space']
    __metaclass__ = rstrat.StrategyMetaclass
    import_from_mixin(rstrat.AbstractStrategy)
    import_from_mixin(rstrategies.SafeIndexingMixin)

    def __init__(self, space):
        self.space = space

    def strategy_factory(self):
        return self.space.strategy_factory

策略类¶

现在可以创建实际的策略类，从单个根类继承它们。以下列表总结了可用的基本策略。

EmptyStrategy 用于空集合的策略；非常高效，但功能有限。不分配任何内容。
SingleValueStrategy 用于包含相同对象 n 次的集合的策略。仅分配内存以存储集合的大小。
GenericStrategy 一个由通用 Python 列表支持的非优化策略。这是后备策略，因为它可以存储任何内容，但未进行优化。
WeakGenericStrategy 与 GenericStrategy 类似，但使用 weakref 来弱引用其元素。
SingleTypeStrategy 可以存储单个未装箱类型，如整数或浮点数。这是主要的优化策略
TaggingStrategy SingleTypeStrategy 的扩展。在未装箱类型的取值范围内使用特定值来表示一个额外的任意对象。例如，float 的 NaN 表示之一可用于表示特殊值，如 nil。

还有一些中间类，允许创建新的、更自定义的策略。为此，应该熟悉代码。

使用 import_from_mixin 包含其中一个 mixin 类。mixin 类包含描述方法或字段的注释，这些方法或字段在策略类中也需要才能使用它们。此外，将 @rstrategies.strategy(generalize=alist) 装饰器添加到所有策略类。 alist 参数必须包含所有策略，如果装饰的策略无法再表示新元素，则可以切换到这些策略。示例用于已实现的策略。有关更多示例，请参阅此链接后面的其他策略类。

一个用于优化 int 存储的示例策略类可能如下所示

@rstrat.strategy(generalize=[GenericStrategy])
class IntegerOrNilStrategy(AbstractStrategy):
    import_from_mixin(rstrat.TaggingStrategy)
    contained_type = model.W_Integer
    def wrap(self, val): return self.space.wrap_int(val)
    def unwrap(self, w_val): return self.space.unwrap_int(w_val)
    def wrapped_tagged_value(self): return self.space.w_nil
    def unwrapped_tagged_value(self): return constants.MAXINT

策略工厂¶

最后一部分是继承 rstrategies.StrategyFactory，必要时覆盖方法 instantiate_strategy 并将策略根类传递给构造函数。该工厂提供方法 switch_strategy、set_initial_strategy、strategy_type_for，虚拟机代码可以使用这些方法来使用策略背后的机制。请参阅源代码中的注释。

策略 mixin 提供以下方法来操作集合的内容

基本 API
- 大小
固定大小 API
- store、fetch、slice、store_all、fetch_all
可变大小 API
- insert、delete、append、pop

如果集合具有固定大小，只需在虚拟机代码中从不使用任何可变大小方法。由于策略是单例，因此这些方法需要集合对象作为第一个参数。为方便起见，应该在集合类本身上实现更合适的访问器方法。

上面 AbstractStrategy 类的示例策略工厂可能如下所示

class StrategyFactory(rstrategies.StrategyFactory):
    _attrs_ = ['space']
    _immutable_fields_ = ['space']

    def __init__(self, space):
        self.space = space
        rstrat.StrategyFactory.__init__(self, AbstractStrategy)

    def instantiate_strategy(self, strategy_type):
        return strategy_type(self.space)

    def strategy_type_for(self, list_w, weak=False):
        """
        Helper method for handling weak objects specially
        """
        if weak:
            return WeakListStrategy
    return rstrategies.StrategyFactory.strategy_type_for(self, list_w)