rstrategies

RPython 툴체인을 기반으로 한 가상 머신(VM)에서 저장 전략(storage strategies)을 구현하기 위한 라이브러리입니다. rstrategies는 언어나 언어 계열에 관계없이 모든 가상 머신에서 사용할 수 있습니다.

이 라이브러리는 Anton Gulenko의 석사 학위 논문의 일환으로 개발되었습니다.

“동적 타입 언어에서의 컬렉션을 위한 저장 전략(Storage Strategies for collections in dynamically typed languages)”이라는 최적화를 설명하는 원본 논문은 C.F. Bolz, L. Diekmann, L. Tratt가 작성했으며, 여기에서 확인할 수 있습니다.

지금까지 이 라이브러리는 3개의 VM에서 채택되었습니다: RSqueak, Topaz (Forked here), Pycket (Forked here).

개념

컬렉션은 흔히 동질적으로 사용됩니다. 즉, 동일한 타입의 객체만 담습니다. int나 float 같은 원시 숫자 타입은 최적화 측면에서 특히 흥미롭습니다. 이러한 경우는 이 객체들의 언박싱된 데이터를 연속된 메모리에 저장함으로써 최적화할 수 있습니다. 이는 특수한 “전략(strategy)” 객체가 컬렉션의 전체 저장소를 다루게 함으로써 이루어집니다. 컬렉션 객체는 두 개의 별도 참조, 즉 전략에 대한 참조 하나와 저장소에 대한 참조 하나를 가집니다. 컬렉션에 대한 모든 연산은 전략에 위임되며, 전략은 필요할 때 저장소에 접근합니다. 전략은 더 적합한 것으로 전환될 수 있으며, 이 경우 저장소 배열을 변환해야 할 수도 있습니다.

사용법

다음은 RPython VM에 rstrategies를 통합하는 데 필요한 단계입니다. 이 라이브러리는 특수한 성격을 지니고 있기 때문에 단순히 몇 가지 API 메서드를 호출하는 것만으로는 충분하지 않으며, 메타클래스, 믹스인 및 기타 메타프로그래밍 기법을 사용하여 기존 VM 클래스 내에 통합되어야 합니다.

여기서 설명한 단계들의 순서는 일종의 “설정 안내”와 같으며, 다소 추상적일 수 있습니다. 구체적인 예시를 보려면 RSqueak VM의 SingletonStorageStrategy, StrategyFactory, W_PointersObject를 보십시오. 코드에도 주석이 잘 달려 있습니다.

기초

현재 rstrategies 라이브러리는 고정 크기 컬렉션과 가변 크기 컬렉션을 지원합니다. 이는 배열, 리스트, 일반 객체와 같은 다양한 기본 데이터 구조를 최적화하는 데 사용할 수 있습니다. 이 문맥에서는 이들을 모두 ‘컬렉션(collections)’이라고 부릅니다. VM은 컬렉션을 위한 중앙 클래스 또는 클래스 계층 구조를 가지고 있어야 합니다. 이러한 클래스를 확장하고 전략(strategies)을 사용하려면, 라이브러리는 컬렉션 객체의 두 속성인 strategy와 storage에 대한 접근자 메서드가 필요합니다. 가장 쉬운 방법은 루트 컬렉션 클래스의 본문에 다음 줄을 추가하는 것입니다:

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에서 찾을 수 있습니다. VM의 다른 곳에서 인덱스 검사가 안전하게 수행된다면, 대신 rstrategies.UnsafeIndexingMixin을 사용할 수 있습니다. 자신만의 메타클래스가 필요하다면, 다중 상속을 사용하여 여기처럼 rstrategies의 메타클래스와 결합할 수 있습니다. 또한 아래에서 설명하는 rstrategies.StorageFactory의 인스턴스를 반환하는 storage_factory() 메서드도 구현하십시오.

추가로 space 매개변수를 저장하는 예시 AbstractStrategy 클래스는 다음과 같이 생길 수 있습니다:

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

전략 클래스

이제 단일 루트 클래스로부터 서브클래싱하여 실제 전략(strategy) 클래스를 만들 수 있습니다. 다음 목록은 사용 가능한 기본 전략들을 요약한 것입니다.

• EmptyStrategy는 빈 컬렉션을 위한 전략으로, 매우 효율적이지만 제한적입니다. 아무것도 할당하지 않습니다.
• SingleValueStrategy는 동일한 객체를 n번 포함하는 컬렉션을 위한 전략입니다. 컬렉션의 크기를 저장할 메모리만 할당합니다.
• GenericStrategy는 일반적인 파이썬 리스트를 기반으로 하는 최적화되지 않은 전략입니다. 이는 모든 것을 저장할 수 있지만 최적화되지 않았기 때문에 대체(fallback) 전략입니다.
• WeakGenericStrategy는 GenericStrategy와 유사하지만, weakref를 사용하여 요소를 약하게 참조합니다.
• SingleTypeStrategy는 int나 float와 같은 언박싱된(unboxed) 단일 타입을 저장할 수 있습니다. 이것이 주요 최적화 전략입니다.
• TaggingStrategy는 SingleTypeStrategy의 확장입니다. 언박싱된 타입의 값 범위에서 특정 값을 사용하여 추가적인 임의의 객체 하나를 표현합니다. 예를 들어, float의 NaN 표현 중 하나를 nil과 같은 특수한 값을 표현하는 데 사용할 수 있습니다.

새롭고 더 커스터마이즈된 전략을 만들 수 있게 해주는 중간 클래스들도 있습니다. 이를 위해서는 코드에 익숙해져야 합니다.

import_from_mixin을 사용하여 이 믹스인 클래스 중 하나를 포함시키십시오. 믹스인 클래스에는 이를 사용하기 위해 전략 클래스에도 필요한 메서드나 필드를 설명하는 주석이 포함되어 있습니다. 또한, 모든 전략 클래스에 @rstrategies.strategy(generalize=alist) 데코레이터를 추가하십시오. alist 매개변수는 데코레이션된 전략이 더 이상 새로운 요소를 표현할 수 없을 때 전환할 수 있는 모든 전략을 포함해야 합니다. 구현된 전략에 대한 예시입니다. 더 많은 예시는 이 링크 뒤에 있는 다른 전략 클래스들을 참고하십시오.

최적화된 int 저장을 위한 전략(strategy) 클래스의 예는 다음과 같이 생길 수 있습니다:

@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

전략 팩토리(Strategy Factory)

마지막 부분은 rstrategies.StrategyFactory를 서브클래싱하고, 필요한 경우 instantiate_strategy 메서드를 오버라이드하며, 생성자에 전략의 루트 클래스를 전달하는 것입니다. 이 팩토리는 VM 코드가 전략(strategies) 뒤의 메커니즘을 사용할 수 있도록 switch_strategy, set_initial_strategy, strategy_type_for 메서드를 제공합니다. 소스 코드의 주석을 참고하십시오.

전략(strategy) 믹스인은 컬렉션의 내용물을 조작하기 위해 다음과 같은 메서드를 제공합니다:

• 기본 API
  • size
• 고정 크기 API
  • store, fetch, slice, store_all, fetch_all
• 가변 크기 API
  • insert, delete, append, pop

컬렉션이 고정된 크기를 가지고 있다면, VM 코드에서 가변 크기 메서드를 전혀 사용하지 않으면 됩니다. 전략들이 싱글턴이기 때문에, 이 메서드들은 첫 번째 매개변수로 컬렉션 객체가 필요합니다. 편의를 위해 더 적합한 접근자 메서드를 컬렉션 클래스 자체에 구현해야 합니다.

위 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)