PyPyのListStrategyまとめ

はじめに

Pythonの処理系の一つである 「PyPy」では、条件を満たす配列に対して内部の構造を変えることで最適化が行われています。

下記のコードは

import __pypy__

を前提とします。また、64bit環境下のpypy3 ( 確認したバージョンはPyPy 7.3.12 )での動作を前提としています。

ObjectListStrategy

print(__pypy__.strategy([[],"hello",42])) # -> ObjectListStrategy

汎用的なものです。これ以降のStrategyに対して当てはまらない配列はこれになります。
各オブジェクトへの参照を持っています。

要素を代入・削除して専用のStrategyの条件を再び満たしても、通常元のStrategyには戻りません。
ただし、sort() や clear() などStrategyが変わるケースも存在します。

import __pypy__
x = [2, 1, None]
x.pop()
print(__pypy__.strategy(x))  # ObjectListStrategy
x.sort()
print(__pypy__.strategy(x))  # IntegerListStrategy
x.clear()
print(__pypy__.strategy(x))  # EmptyListStrategy

IntegerListStrategy

print(__pypy__.strategy([3,2,1,0]))       # -> IntegerListStrategy
print(__pypy__.strategy([1,2,3,2**63-1])) # -> IntegerListStrategy
print(__pypy__.strategy([1,2,3,2**63]))   # -> ObjectListStrategy
print(__pypy__.strategy([3,2,1,0,None]))  # -> ObjectListStrategy
print(__pypy__.strategy([3,2,1,0,True]))  # -> ObjectListStrategy

整数の配列用です。内部でRPythonの list[int] を持ちます。64bit環境下では、64-bit符号付き整数列になります。
64-bitの符号付き整数に収まらない数や整数でないものを入れようとすると ObjectListStrategy になります。bool値もダメです。(後述しますが、float だけはちょっと特殊です。)
Strategyの変更処理は基本的に $\mathrm{O}(N)$ かかるので気を付けましょう。例えば、下記のようなことが起こります。

import time,__pypy__
x = list(range(10**8))

start = time.time()
x[0] = 1
print(time.time()-start)    # -> 4.5299530029296875e-06
print(__pypy__.strategy(x)) # -> IntegerListStrategy

start = time.time()
x[0] = 2**63
print(time.time()-start)    # -> 2.469036817550659
print(__pypy__.strategy(x)) # -> ObjectListStrategy

start = time.time()
x[0] = 1
print(time.time()-start)    # -> 3.814697265625e-06
print(__pypy__.strategy(x)) # -> ObjectListStrategy

FloatListStrategy

print(__pypy__.strategy([2.718,3.14,float("inf"),float("NaN")])) # -> FloatListStrategy
print(__pypy__.strategy([2.718,3.14,0])) # -> IntOrFloatListStrategy
print(__pypy__.strategy([2.718,3.14,None])) # -> ObjectListStrategy

float 型の配列用です。内部ではRPython list[float] を持っています。ここで言う float はC/C++の double 相当 (64bit) です。

float 型以外を入れると他のStrategyになります。特に、32bit符号付き整数に収まる整数を追加した場合は下記の IntOrFloatListStrategy に変化します。(変換処理が挟まります。)

IntOrFloatListStrategy

print(__pypy__.strategy([2.718,3.14,0,2**31-1])) # -> IntOrFloatListStrategy
print(__pypy__.strategy([2.718,3.14,0,2**31]))   # -> ObjectListStrategy
print(__pypy__.strategy([2.718,3.14,0,False]))   # -> ObjectListStrategy

float 型と32bit符号付き整数に収まる整数が混じった配列用です。内部ではRPythonの list[r_int64] を持っています(つまり、64bit整数列です)。
float 値はビット列をそのまま入れて、整数については上位32bitに 0xfffffffe をつけて持ちます。

0xfffffffeが上位32bitについている float の値と混じってしまうのを避けるため、そのような値が存在する場合は ObjectListStrategy が利用されます。例えば、下記の通りです。(起こそうと思わなければ起きませんが...)

import struct

bits = 0xfffffffe12345678
value = struct.unpack(">d", struct.pack(">Q", bits))[0]
print(value) # -> nan
print(__pypy__.strategy([2.718,3.14,value]))   # -> FloatListStrategy
print(__pypy__.strategy([2.718,3.14,value,0])) # -> ObjectListStrategy

AsciiListStrategy

print(__pypy__.strategy(["hello","world"])) # -> AsciiListStrategy
print(__pypy__.strategy(["こんにちは","世界"])) # -> ObjectListStrategy

Ascii文字だけで表すことができる文字列からなる配列の際だけ利用されます。

PyPy のstr 型は型内部に文字列の長さの情報やインデックスの場所の情報などを持っています。(インデックスの方については、Ascii に収まる場合は作成されません。)
これはUnicode文字について一点取得や len が正常に動作するためのものですが、Ascii 文字だけで構成されるような文字列の場合については必要ありません。このような情報を持たずに、直接内部のRPython文字列への参照を持ちます。

BytesListStrategy

print(__pypy__.strategy([b"hello",b"world"])) # -> BytesListStrategy

bytesからなる配列の時に利用されます。

bytesは内部でRPython の str へのポインタを持っていますが、これをポインタの配列として直接持つようにします。

EmptyListStrategy

print(__pypy__.strategy([])) # -> EmptyListStrategy

新しく作成した空の配列の時に利用されます。その後追加した要素によってStrategyが変化します。

要素用のストレージは持ちません。

下のような場合、 EmptyListStrategy は適用されません。

import __pypy__
x = [1]
x.pop()

print(x)                    # []
print(__pypy__.strategy(x)) # IntegerListStrategy

SizeListStrategy

print(__pypy__.strategy(__pypy__.newlist_hint(100))) # -> SizeListStrategy

空の配列だが、サイズヒントがついている配列に利用されます。
最初の要素を入れたときにStrategyが変化します。

内部的には生成された時点では配列の確保を行っておらず、初めの要素が追加されたタイミングで領域を確保します。

既存の配列に対して、あとからサイズのヒントを指定することもできます。

X = []
print(__pypy__.strategy(X)) # -> EmptyListStrategy
__pypy__.resizelist_hint(X, 1000)
print(__pypy__.strategy(X)) # -> SizeListStrategy