rstrategies

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

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

이 최적화를 설명하는 원 논문 “Storage Strategies for collections in dynamically typed languages”의 저자는 C.F. Bolz, L. Diekmann, L. Tratt이며, 이 논문은 여기에서 찾을 수 있습니다.

지금까지 이 라이브러리를 채택한 VM은 RSqueak, Topaz (포크 저장소), Pycket (포크 저장소)의 3개입니다.

개념

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

사용법

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

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

기본 사항

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

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

이렇게 하면 각 속성에 대한 접근자 메서드 _[get/set]_[storage/strategy]() 4개가 생성됩니다. 또는 이 메서드들을 직접 구현하거나 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() 메서드도 구현하십시오. rstrategies.StorageFactory는 아래에서 설명합니다.

추가로 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 일반 Python 리스트를 기반으로 하는, 최적화되지 않은 전략입니다. 모든 것을 저장할 수 있으므로 대체(fallback) 전략으로 쓰이지만, 최적화되어 있지는 않습니다.
• WeakGenericStrategy GenericStrategy와 같지만, weakref를 사용하여 요소를 약한 참조로 유지합니다.
• SingleTypeStrategy는 int나 float 같은 언박싱된(unboxed) 단일 타입을 저장할 수 있습니다. 이것이 주된 최적화 전략입니다
• TaggingStrategy SingleTypeStrategy의 확장입니다. 언박싱된 타입의 값 범위 안에 있는 특정 값을 사용하여 임의의 객체 하나를 추가로 표현합니다. 예를 들어, float의 NaN 표현 중 하나를 사용하여 nil과 같은 특수한 값을 표현할 수 있습니다.

새롭고 더 세밀하게 맞춤화한 전략을 만들 수 있게 해 주는 중간 클래스도 있습니다. 이를 위해서는 코드에 익숙해져야 합니다.

import_from_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 메서드를 제공하며, VM 코드는 이 메서드들을 사용해 전략의 기반이 되는 메커니즘을 활용할 수 있습니다. 소스 코드의 주석을 참고하십시오.

전략 믹스인은 컬렉션의 내용을 조작할 수 있는 다음 메서드들을 제공합니다:

• 기본 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)