PyPy의 리스트 전략이 동질적인 원시 타입 리스트에서 메모리를 절약하고 일부 연산을 더 빠르게 만드는 방법을 설명합니다.
리스트 전략 브랜치를 머지하는 시점이 가까워지고 있어서, 오늘은 이 메모리 최적화에 대해 설명해 보려고 합니다.
PyPy의 데이터 타입은 W_<type>Object들로 저장됩니다(예: 문자열을 나타내는 W_StringObject, 정수를 나타내는 W_IntObject). 이것은 Python의 동적인 특성 때문에 필요합니다. 따라서 실제 값(예: 문자열, 정수)은 그 박스 내부에 저장되며, 그 결과 한 번의 간접 참조가 생깁니다. 이런 박싱된 객체가 대량으로 존재할 때, 예를 들어 리스트 안에 많이 들어 있을 경우 낭비되는 메모리는 꽤 커질 수 있습니다.
이런 리스트들을 자세히 보면, 그중 많은 리스트에는 한 가지 타입의 데이터만 저장되어 있고, 섞인 타입을 저장하는 리스트는 소수이며 대체로 더 작습니다. 또 하나 관찰할 수 있는 점은, 이런 리스트들이 실행 중에 포함한 객체들의 타입을 자주 바꾸지 않는다는 것입니다. 예를 들어 정수 백만 개가 들어 있는 리스트에 갑자기 문자열 하나가 추가될 가능성은 매우 낮습니다.
이 작업의 목표는 이런 동작을 활용하는 최적화를 작성하는 것입니다. 리스트 안의 모든 항목을 래핑하는 대신, 특정한 원시 데이터 타입을 저장하는 데 최적화된 방식으로 리스트를 구현합니다. 이런 구현은 리스트의 내용을 언래핑된 형태로 저장하여 추가적인 간접 참조와 래퍼 객체를 없앱니다.
한 가지 접근법은 간접 참조를 한 단계 더 추가해서, 각 W_ListObject 인스턴스가 실제 내용을 저장하는 다른 객체를 가리키게 만드는 것입니다. 이 다른 객체에는 래핑 없이 저장하려는 각 데이터 타입마다 여러 구현이 존재하고, 임의의 내용을 다루는 일반 구현도 존재하게 됩니다. 데이터 배치는 대략 다음과 같을 것입니다.
이 접근법의 문제는 데이터에 도달하기 위해 두 번의 간접 참조가 필요하고, 구현 인스턴스들 자체도 메모리를 필요로 한다는 점입니다.
우리가 하고 싶은 것은 W_ListObject가 래핑된 데이터나 언래핑된 데이터를 담고 있는 RPython 리스트를 직접 가리키게 만드는 것입니다. 이 계획의 문제는 서로 다른 언래핑된 데이터를 RPython에서 직접 저장하는 것이 가능하지 않다는 점입니다.
이 문제를 해결하기 위해 우리는 rerased RPython 라이브러리 모듈을 사용합니다. 이것은 객체의 타입을 지울 수 있게 해 주는데, 여기서는 리스트의 타입을 지우며, C의 void-star나 Java의 Object와 비슷한 무언가를 반환합니다. 그런 다음 이 객체를 W_ListObject의 storage 필드에 저장합니다. 리스트에 대해 작업하려면, 예를 들어 항목을 추가하거나 삭제하려면, storage를 다시 unerase해야 합니다.
rerase의 예:
storage = erase([1 ,2 ,3 ,4])
# storage는 아무것도 할 수 없는 불투명한 객체이다
....
l = unerase(storage)
l.clear()이제 W_ListObject가 래핑된 데이터나 언래핑된 데이터를 직접 가리키게 만드는 방법을 알았으니, 실제로 이 데이터에 대해 연산을 수행하는 방법을 찾아야 합니다. 이것은 W_ListObject에 필드를 하나 더 추가함으로써 이룰 수 있습니다. 이 필드는 ListStrategy 객체를 가리킵니다. 이제 W_ListObject의 실제 구현은 이 ListStrategy 클래스들에 위임됩니다. 예를 들어 정수만 담고 있는 W_ListObject는 IntegerListStrategy를 사용하게 됩니다.
내용물의 타입이 바뀌면, 사용 중인 전략과 storage도 서로 호환되는 방식으로 바뀌어야 합니다. 예를 들어 정수 리스트에 문자열을 추가하면 ObjectListStrategy로 전환하고 storage를 래핑된 객체들의 리스트로 바꿔야 합니다. 따라서 현재 사용 중인 전략은 storage에 현재 들어 있는 것에 대해 무엇을 해야 하는지 항상 알고 있습니다.
보시다시피, 이제 일부 데이터를 언래핑된 상태로 저장함으로써 간접 참조 한 단계를 절약할 수 있습니다. 물론 리스트에서의 각 연산은 전략을 거쳐야 하지만, 그 리스트에 저장된 각 원소마다 한 번의 간접 참조를 절약하고 Strategy 클래스들이 싱글턴이기 때문에, 이점이 비용보다 큽니다.
현재는 많은 리스트가 이런 데이터 타입을 갖는 것으로 보이기 때문에 정수와 문자열에 대한 전략만 있습니다. 즉, float와 유니코드 문자열을 위한 다른 전략도 계획되어 있습니다. 또한 빈 리스트와 range-list를 위한 두 가지 특별한 전략도 구현했습니다. EmptyListStrategy의 storage는 None입니다. 리스트에 객체가 추가되면 적절한 전략으로 전환하기만 하면 됩니다(항목의 타입으로 결정됨). RangeListsStrategies는 어떤 항목도 전혀 저장하지 않습니다. 대신 리스트의 범위를 설명하는 값들, 즉 start, step, length만 저장합니다. 리스트의 데이터를 바꾸는 어떤 연산이든 수행되면 IntegerStrategy로 전환합니다.
언래핑된 데이터 타입을 저장하는 것의 좋은 부수 효과는 특정한 경우에 최적화된 메서드를 구현할 수 있다는 점입니다. 예를 들어 언래핑된 정수의 비교는 이제 임의 객체 간 비교보다 훨씬 빠르므로, 정수를 담고 있는 리스트의 정렬 메서드를 다시 작성할 수 있습니다.
마지막으로, 서로 다른 Python 구현들의 메모리 소비에 대한 초기 개요를 소개합니다. CPython, PyPy, 그리고 리스트 전략을 사용하는 PyPy-list입니다. 최상의 경우에 리스트 전략이 얼마나 강력할 수 있는지 보여 주기 위해, 우리는 각각 백만 개의 원소를 가진 정수 리스트, 문자열 리스트, range-list를 생성하고, 그다음 OS가 보고한 프로세스의 힙 크기를 읽는 벤치마크를 작성했습니다.
결과는 다음과 같습니다.
이 이상적인 경우에 정수와 문자열에서의 절감은 꽤 큽니다.
range-list에 대한 벤치마크는 조금 불공정한데, CPython에서는 xrange를 사용해 같은 메모리 동작을 얻을 수 있기 때문입니다. 하지만 PyPy에서는 내부적으로 리스트가 모든 항목을 저장하지 않는다는 사실을 사용자가 알아차리지 못하므로, append나 delete 같은 모든 리스트 메서드를 여전히 사용할 수 있습니다.
우리는 리스트 전략이 원시 타입의 동질적인 리스트를 사용하는 애플리케이션에 메모리 절감을 가져다주기를 바랍니다. 더 나아가, 그런 리스트에 대한 연산은 다소 더 빨라지는 경향도 있습니다. 이것은 JIT와도 잘 통합됩니다. 리스트 전략 최적화는 앞으로 몇 달 안에 어느 시점에서 PyPy의 기본 브랜치에 머지될 것입니다. 딕셔너리에 대한 동등한 최적화는 이미 머지되었고(PyPy 1.6의 일부입니다), 셋에 대한 것은 앞으로 나올 예정입니다.
Lukas Diekmann and Carl Friedrich Bolz
리스트 전략 브랜치를 머지하는 시점이 가까워지고 있어서, 오늘은 이 메모리 최적화에 대해 설명해 보려고 합니다.
PyPy의 데이터 타입은 W_<type>Object들로 저장됩니다(예: 문자열을 나타내는 W_StringObject, 정수를 나타내는 W_IntObject). 이것은 Python의 동적인 특성 때문에 필요합니다. 따라서 실제 값(예: 문자열, 정수)은 그 박스 내부에 저장되며, 그 결과 한 번의 간접 참조가 생깁니다. 이런 박싱된 객체가 대량으로 존재할 때, 예를 들어 리스트 안에 많이 들어 있을 경우 낭비되는 메모리는 꽤 커질 수 있습니다.
이런 리스트들을 자세히 보면, 그중 많은 리스트에는 한 가지 타입의 데이터만 저장되어 있고, 섞인 타입을 저장하는 리스트는 소수이며 대체로 더 작습니다. 또 하나 관찰할 수 있는 점은, 이런 리스트들이 실행 중에 포함한 객체들의 타입을 자주 바꾸지 않는다는 것입니다. 예를 들어 정수 백만 개가 들어 있는 리스트에 갑자기 문자열 하나가 추가될 가능성은 매우 낮습니다.
이 작업의 목표는 이런 동작을 활용하는 최적화를 작성하는 것입니다. 리스트 안의 모든 항목을 래핑하는 대신, 특정한 원시 데이터 타입을 저장하는 데 최적화된 방식으로 리스트를 구현합니다. 이런 구현은 리스트의 내용을 언래핑된 형태로 저장하여 추가적인 간접 참조와 래퍼 객체를 없앱니다.
한 가지 접근법은 간접 참조를 한 단계 더 추가해서, 각 W_ListObject 인스턴스가 실제 내용을 저장하는 다른 객체를 가리키게 만드는 것입니다. 이 다른 객체에는 래핑 없이 저장하려는 각 데이터 타입마다 여러 구현이 존재하고, 임의의 내용을 다루는 일반 구현도 존재하게 됩니다. 데이터 배치는 대략 다음과 같을 것입니다.
이 접근법의 문제는 데이터에 도달하기 위해 두 번의 간접 참조가 필요하고, 구현 인스턴스들 자체도 메모리를 필요로 한다는 점입니다.
우리가 하고 싶은 것은 W_ListObject가 래핑된 데이터나 언래핑된 데이터를 담고 있는 RPython 리스트를 직접 가리키게 만드는 것입니다. 이 계획의 문제는 서로 다른 언래핑된 데이터를 RPython에서 직접 저장하는 것이 가능하지 않다는 점입니다.
이 문제를 해결하기 위해 우리는 rerased RPython 라이브러리 모듈을 사용합니다. 이것은 객체의 타입을 지울 수 있게 해 주는데, 여기서는 리스트의 타입을 지우며, C의 void-star나 Java의 Object와 비슷한 무언가를 반환합니다. 그런 다음 이 객체를 W_ListObject의 storage 필드에 저장합니다. 리스트에 대해 작업하려면, 예를 들어 항목을 추가하거나 삭제하려면, storage를 다시 unerase해야 합니다.
rerase의 예:
storage = erase([1 ,2 ,3 ,4])
# storage는 아무것도 할 수 없는 불투명한 객체이다
....
l = unerase(storage)
l.clear()이제 W_ListObject가 래핑된 데이터나 언래핑된 데이터를 직접 가리키게 만드는 방법을 알았으니, 실제로 이 데이터에 대해 연산을 수행하는 방법을 찾아야 합니다. 이것은 W_ListObject에 필드를 하나 더 추가함으로써 이룰 수 있습니다. 이 필드는 ListStrategy 객체를 가리킵니다. 이제 W_ListObject의 실제 구현은 이 ListStrategy 클래스들에 위임됩니다. 예를 들어 정수만 담고 있는 W_ListObject는 IntegerListStrategy를 사용하게 됩니다.
내용물의 타입이 바뀌면, 사용 중인 전략과 storage도 서로 호환되는 방식으로 바뀌어야 합니다. 예를 들어 정수 리스트에 문자열을 추가하면 ObjectListStrategy로 전환하고 storage를 래핑된 객체들의 리스트로 바꿔야 합니다. 따라서 현재 사용 중인 전략은 storage에 현재 들어 있는 것에 대해 무엇을 해야 하는지 항상 알고 있습니다.
보시다시피, 이제 일부 데이터를 언래핑된 상태로 저장함으로써 간접 참조 한 단계를 절약할 수 있습니다. 물론 리스트에서의 각 연산은 전략을 거쳐야 하지만, 그 리스트에 저장된 각 원소마다 한 번의 간접 참조를 절약하고 Strategy 클래스들이 싱글턴이기 때문에, 이점이 비용보다 큽니다.
현재는 많은 리스트가 이런 데이터 타입을 갖는 것으로 보이기 때문에 정수와 문자열에 대한 전략만 있습니다. 즉, float와 유니코드 문자열을 위한 다른 전략도 계획되어 있습니다. 또한 빈 리스트와 range-list를 위한 두 가지 특별한 전략도 구현했습니다. EmptyListStrategy의 storage는 None입니다. 리스트에 객체가 추가되면 적절한 전략으로 전환하기만 하면 됩니다(항목의 타입으로 결정됨). RangeListsStrategies는 어떤 항목도 전혀 저장하지 않습니다. 대신 리스트의 범위를 설명하는 값들, 즉 start, step, length만 저장합니다. 리스트의 데이터를 바꾸는 어떤 연산이든 수행되면 IntegerStrategy로 전환합니다.
언래핑된 데이터 타입을 저장하는 것의 좋은 부수 효과는 특정한 경우에 최적화된 메서드를 구현할 수 있다는 점입니다. 예를 들어 언래핑된 정수의 비교는 이제 임의 객체 간 비교보다 훨씬 빠르므로, 정수를 담고 있는 리스트의 정렬 메서드를 다시 작성할 수 있습니다.
마지막으로, 서로 다른 Python 구현들의 메모리 소비에 대한 초기 개요를 소개합니다. CPython, PyPy, 그리고 리스트 전략을 사용하는 PyPy-list입니다. 최상의 경우에 리스트 전략이 얼마나 강력할 수 있는지 보여 주기 위해, 우리는 각각 백만 개의 원소를 가진 정수 리스트, 문자열 리스트, range-list를 생성하고, 그다음 OS가 보고한 프로세스의 힙 크기를 읽는 벤치마크를 작성했습니다.
결과는 다음과 같습니다.
이 이상적인 경우에 정수와 문자열에서의 절감은 꽤 큽니다.
range-list에 대한 벤치마크는 조금 불공정한데, CPython에서는 xrange를 사용해 같은 메모리 동작을 얻을 수 있기 때문입니다. 하지만 PyPy에서는 내부적으로 리스트가 모든 항목을 저장하지 않는다는 사실을 사용자가 알아차리지 못하므로, append나 delete 같은 모든 리스트 메서드를 여전히 사용할 수 있습니다.
우리는 리스트 전략이 원시 타입의 동질적인 리스트를 사용하는 애플리케이션에 메모리 절감을 가져다주기를 바랍니다. 더 나아가, 그런 리스트에 대한 연산은 다소 더 빨라지는 경향도 있습니다. 이것은 JIT와도 잘 통합됩니다. 리스트 전략 최적화는 앞으로 몇 달 안에 어느 시점에서 PyPy의 기본 브랜치에 머지될 것입니다. 딕셔너리에 대한 동등한 최적화는 이미 머지되었고(PyPy 1.6의 일부입니다), 셋에 대한 것은 앞으로 나올 예정입니다.
Lukas Diekmann and Carl Friedrich Bolz
리스트 전략으로 더 압축적인 리스트
Carl Friedrich Bolz-Tereick 작성, 시간 13:25
이메일로 보내기BlogThis!X에 공유Facebook에 공유Pinterest에 공유
Winston Ewert 님이 말했습니다... 좋네요.
그런데 이렇게 하려면 의미론에 작은 변화가 생기지 않나요? 제가 Python int 객체를 리스트에 push했다가 다시 pop하면 정확히 같은 객체를 얻게 됩니다. 하지만 객체를 언래핑해서 그냥 int로 저장한 다음 다시 꺼내면 정확히 같은 객체가 아니게 됩니다. 새 객체를 얻게 되니까요.
Anonymous 님이 말했습니다... 아주 좋아 보입니다.
그런데 객체 속성도 같은 방식으로 최적화되나요? 같은 클래스의 객체들은 같은 속성에 같은 타입의 데이터를 자주 저장할 것으로 예상할 수 있습니다.
맵에 관한 거의 1년 전 글( http://morepypy.blogspot.com/2010/11/efficiently-implementing-python-objects.html )을 찾았는데, 속성 값 타입에 대해서는 언급하지 않더군요... 이 아이디어도 고려된 적이 있나요?
Unknown 님이 말했습니다... float 지원은 더 넓은 문제를 상징하는 흥미로운 도전 과제를 제시할 것 같습니다. 누군가가 "float" 리스트를 갖는 것은 매우 쉬운 일이지만, 그 리스트를 리터럴로 채운다면 대부분 정수 리터럴일 가능성이 높아서 float 최적화를 놓치게 됩니다.
대부분의 앱에서는 문제가 아니겠지만, 누군가가 애플리케이션을 최적화하려 한다면 이를 성능 하이젠버그처럼 볼 수도 있습니다. 예를 들어 하드코딩된 리스트를 작성하면 느리고, 파일에서 읽으면 빠를 수 있습니다.
한 가지 접근법은 어떤 웹사이트에 PyPy 마이크로 최적화 목록을 문서로 두는 것입니다(그리고 그 문서는 곧 낡게 되겠지요). 그러면 누군가는 자신의 코드를 그 목록과 계속 대조해 감사해야 할 것입니다. 이건 현실적이지 않아 보입니다.
저수준 시각화 도구가 게시된 것을 본 적이 있습니다. 리스트의 혼합 float/int 상황 같은 패턴을 감지해서 이런 마이크로 최적화를 더 자동화된 방식으로 표시하도록, 더 높은 수준의 프로파일러 도구가 JIT와 통합될 수 있을지 궁금합니다.
Alex 님이 말했습니다...
Winston: 맞습니다, 그 점을 알아차리시다니 아주 날카로우시네요 :) 하지만 저희도 그 점을 알고 있습니다. 앞으로 정수(그리고 다른 원시 타입)의 동일성은 박스의 동일성이 아니라 값의 함수가 될 것입니다. 이는 모든 int에 대해 i is x 가 오직 i == x 일 때만 참이라는 뜻입니다. 또한 원시 타입의 id() 역시 이제 값의 함수가 된다는 뜻입니다. 그렇다고 거기에 의존하지는 마세요! 지금도 사람들이 i == x and -100 < i < 200 이면 i is x 라고 기대하는 데 의존하지 않기를 바라는 것처럼, 이것에도 의존하지 않기를 바랍니다.
Anonymous:
네, 그 점은 분명히 고려 대상입니다. 시간을 내서 작업해야겠다고 계속 생각하고 있습니다.
evilpies 님이 말했습니다... 흥미롭네요. SpiderMonkey도 NaN-boxing이 보통 많은 메모리를 낭비하기 때문에 이런 것의 구현을 고려하고 있습니다.
Maciej Fijalkowski 님이 말했습니다... @Ed 제 생각에는 float 리스트가 제한된 범위의 정수 값들(float로 해석했을 때 정확히 표현될 수 있는 값들)을 문제 없이 수용할 수 있을 것 같습니다. 다만 그러면 어느 것이 정수이고 어느 것이 float인지 태그를 달아야 해서 비트맵을 유지해야 할 것입니다. 물론 가능은 하지만, 좀 지저분하겠지요.
Alex 님이 말했습니다... fijal: float를 정수처럼 허용하는 비트맵 같은 난해한 꼼수보다는, 그런 폴백이 일어날 때 로깅하는 기능을 결국 갖는 편이 더 나을 것 같습니다. 물론 언젠가 jitviewer와의 통합도 가능하겠지요 :)
Winston Ewert 님이 말했습니다... 다음과 같은 말을 해 줄 수 있는 일반적인 런타임 경고 시스템이 있으면 유용할지도 모르겠습니다. 예를 들어 "int를 추가해서 float 리스트가 객체 리스트로 퇴화함", "두 int가 is로 비교되고 있음" 같은 것들 말이지요. 놀라운 의미론이나 성능을 가진 수많은 상황을 다룰 수 있을 것 같습니다.
Anonymous 님이 말했습니다... 이건 매우 흥미롭습니다. 저는 한동안 다소 비슷한 방향으로 생각해 왔습니다(메모리 크기보다는 성능상의 이유로요). 그래서 이미 제 코드에서 리스트를 사용하는 방식을 검토해 보았습니다. 제 프로그램에서는 리스트 안에 비균일한 데이터 타입이 들어가는 경우가 극히 드뭅니다. 하지만 일부 리스트는 리스트의 리스트(또는 튜플이나 딕셔너리)입니다. 그러나 가장 흔한 큰 리스트는 대체로 문자열 리스트입니다.
제가 여러분이 하는 일을 제대로 이해했다면, 여러분의 "리스트 전략"은 균일한 리스트를 몇 가지 알려진 기본 타입 중 하나(예: IntegerListStrategy) 또는 그냥 전통적인 객체 리스트로 표시하는 셈인가요? 맞습니까?
리스트 타입을 미리 알 때 얻을 수 있는 의미 있는 성능 최적화가 있을까요?
all(), any(), len(), min(), max() 같은 내장 함수는 어떻습니까? 이것들도 이를 활용해서 성능을 높일 수 있을까요?
기반 배열 데이터 형식이 직접 사용하려는 사람들에게 노출될까요(예: SIMD 라이브러리 같은 것용 확장을 작성하려는 경우)?
이것이 리스트를 공유 메모리에 두고 다른 프로그램이 직접 접근하게 만드는 것을 가능하게 할까요?
새로운 리스트 형식이 "memoryview"와 호환될 수 있을까요(str와 bytearray처럼)?
예전에 제가 생각한 방식은 리스트가 생성되거나 변경될 때 균일 데이터인지 비균일 데이터인지 표시하고, 균일 리스트에 대해서는 예상 타입용 최적화 코드를 사용하는 것이었습니다. 그런데 한 가지 까다로운 점은 스레딩이었습니다. 다른 스레드에서 다른 타입이 append될 수 있기 때문에, 소비하는 함수가 somehow 이를 알아야 하기 때문입니다. 여러분의 개념에서는, 다른 스레드가 같은 리스트에 접근하는 동안 정수 리스트에 문자열을 append하면 내부 리스트 전략을 갑자기 바꿔야 하는 상황이 스레딩 문제를 일으키지 않을까요?
Python 3.x는 리스트를 생성하는 대신 이터레이터를 선호하는 것처럼 보입니다(예: map, filter, range가 예전의 imap, ifilter, xrange에 해당하는 것으로 바뀜). 그리고 메모리를 절약하기 위해 제너레이터가 리스트 내포를 보완하도록 도입되었습니다. 이것이 여러분이 하는 일에 어떤 함의를 가질까요?
여러분의 리스트 개념을 CPython 개발자들이 CPython에 적용할 수 있을까요? 그렇게 하면 결과적으로 생길 수 있는 미묘한 의미론 문제들이 CPython에도 똑같이 적용되어, 사람들이 그것을 "Pypy 버그"라고 부르지 않게 하는 데 도움이 될 수도 있겠습니다.
Python 언어 의미론을 바꿔서 사용자가 리스트가 특정한 균일 타입이어야 한다고 지정하고, 예상치 못한 타입의 원소가 추가되면 타입 오류를 발생시키도록 하는 것은 어떨까요? 사실 이것은 제가 갖고 싶은 언어 기능입니다. 각 개별 데이터 원소를 검사하는 코드를 직접 쓰지 않고도 오류를 잡을 수 있기 때문입니다(그 작업 자체도 느리고 오류가 나기 쉽습니다).
마지막으로, 여러분의 마이크로벤치마크에서 Pypy-list를 CPython과 비교할 때 시작 메모리 사용량이 왜 그렇게 큰가요? 이것은 그냥 PyPy 자체의 일반적인 오버헤드인가요, 아니면 리스트 형식을 특정 "리스트 전략"으로 바꾸는 것과 관련된 것인가요?
Alex 님이 말했습니다... Anonymous: 와 질문이 많네요, 답해 보겠습니다 :)
네.
아마 아닐 겁니다. 가장 큰 성능 이득은 큰 리스트에서 나오는데, 리스트가 크다면 아주아주아주 작은 초기 전환 비용은 많은 원소에 걸쳐 상쇄됩니다.
그중 상당수는 순수 Python으로 되어 있어서 자동으로 이런 이점을 얻을 것입니다. 불행히도 max()와 min()은 그렇지 않습니다.
아마 아닐 겁니다. 저희는 다른 어느 곳에서도 이 데이터를 노출하지 않고, 그것을 위한 API도 없습니다.
이론상으로는 그럴 수도 있겠지만, 역시 그것을 위한 API는 없습니다.
아니요, 그렇지 않을 것입니다. 그건 리스트 API의 일부가 아니기 때문입니다. 언어를 정의하는 것은 저희가 아니라, 저희는 그저 그것을 더 빠르게 구현할 뿐입니다.
아니요, 문제 없습니다. 그냥 리스트를 잠그고(또는 STM에서 이에 해당하는 무언가를 하고) 수정을 수행하면 됩니다.
아니요, 그럴 것 같지는 않습니다.
네, CPython에도 약간 더 어렵게 적용할 수는 있고 메모리 이득도 볼 수 있을 것입니다. 하지만 성능 손실도 보게 될 텐데(CPython의 array 모듈에서 그렇듯이), 각 반복마다 box/unbox를 해야 하기 때문입니다. 반면 JIT는 그 비용을 제거할 수 있습니다.
python-ideas에 제안해 보세요. 언어를 정의하는 것은 저희가 아닙니다.
저는 차트를 이해할 수가 없어서, 이 질문에는 답할 수 없습니다.
Anonymous 님이 말했습니다... Alex: 질문이 많았던 그 Anonymous입니다. 자세한 답변 감사합니다. 지금 시점에서 다루고 싶지 않은 주변 이슈들이 있다는 점은 충분히 이해합니다.
제안된 새 리스트 데이터 형식을 CPython에 적용했을 때의 잠재적 성능 효과에 관해서는, x가 1,000,000개의 정수로 이루어진 리스트 또는 배열일 때 y = reduce(operator.add, x, 0) 연산을 수행해도 제 환경에서는 속도 차이가 측정되지 않는 것 같습니다(64비트 Ubuntu의 Python 2.6). 테스트를 반복하면 차이는 어느 쪽으로든 오가므로, 오차 범위 내에서 동등해 보입니다. 동등한 for 루프도 같은 결과를 냅니다(물론 더 느리다는 점만 제외하면요).
for 루프 안에서 리스트와 배열의 슬라이스를 추출하거나 교체할 때(예: y = x[i:i + 50] 와 x[i:i + 50] = y), 배열 버전은 큰 슬라이스(예: 50)에서는 리스트 버전보다 상당히 더 빠른 것 같고, 작은 슬라이스(예: 5)에서는 거의 비슷합니다.
이론적으로는 그렇습니다. 배열을 사용한 구현이 항상 더 느려야 합니다. 하지만 제가 측정해 보려 하면 그런 결과를 얻을 수가 없습니다. 제가 뭔가 잘못하고 있는 것일 수도 있겠지만, 제가 해 본 테스트는 많지 않더라도, CPython에서 상당한 속도 페널티가 있다고 그냥 가정할 수는 없어 보입니다.
궁극적으로는 이것이 Pypy 개발자들이 신경 쓸 문제는 아니라는 점은 알고 있지만, 이 질문이 언젠가 제기된다면 그렇게 쉽게 일축할 수는 없다고 생각합니다.
Carl Friedrich Bolz-Tereick 님이 말했습니다... @Anonymous 질문들에 대해 몇 가지 추가 생각을 덧붙이면:
3) all(), any(), len(), min(), max() 같은 내장 함수는 어떻습니까? 이것들도 이를 활용해서 성능을 높일 수 있을까요?
len은 리스트의 내용에 의존하지 않으므로 이득이 없습니다. all, any, min, max는 개선될 수 있습니다.
7) 예전에 제가 생각한 방식은 리스트가 생성되거나 변경될 때 균일 데이터인지 비균일 데이터인지 표시하고, 균일 리스트에 대해서는 예상 타입용 최적화 코드를 사용하는 것이었습니다. 그런데 한 가지 까다로운 점은 스레딩이었습니다. 다른 스레드에서 다른 타입이 append될 수 있기 때문에, 소비하는 함수가 somehow 이를 알아야 하기 때문입니다. 여러분의 개념에서는, 다른 스레드가 같은 리스트에 접근하는 동안 정수 리스트에 문자열을 append하면 내부 리스트 전략을 갑자기 바꿔야 하는 상황이 스레딩 문제를 일으키지 않을까요?
JIT는 실제로 현재 관찰하고 있는 리스트 타입에 대해 특수화된 최적화 코드를 생성하여 연산을 더 빠르게 만듭니다. 다른 스레드가 리스트의 타입을 바꿀 수 있다는 사실은 문제가 되지 않습니다. 왜냐하면 우리에게는 GIL이 있고, 따라서 JIT는 다른 스레드가 어느 지점에서 실행될 수 있는지를 알고 있기 때문입니다.
10) Python 언어 의미론을 바꿔서 사용자가 리스트가 특정한 균일 타입이어야 한다고 지정하고, 예상치 못한 타입의 원소가 추가되면 타입 오류를 발생시키도록 하는 것은 어떨까요? 사실 이것은 제가 갖고 싶은 언어 기능입니다. 각 개별 데이터 원소를 검사하는 코드를 직접 쓰지 않고도 오류를 잡을 수 있기 때문입니다(그 작업 자체도 느리고 오류가 나기 쉽습니다).
그건 이미 존재합니다. array 모듈이라고 부릅니다.
11) 마지막으로, 여러분의 마이크로벤치마크에서 Pypy-list를 CPython과 비교할 때 시작 메모리 사용량이 왜 그렇게 큰가요? 이것은 그냥 PyPy 자체의 일반적인 오버헤드인가요, 아니면 리스트 형식을 특정 "리스트 전략"으로 바꾸는 것과 관련된 것인가요?
더 높은 시작 메모리는 리스트 전략이 없는 PyPy에도 존재하므로, 그것들과는 아무 관련이 없습니다.
Anonymous 님이 말했습니다... 저도 그 차트를 이해하기 어려웠습니다. 세로축에는 델타를 나타내는 음수가 없으니, 부호는 그냥 무시하세요.
파란 영역은 대수적으로 양수인 영역으로, 시작 메모리 사용량을 나타냅니다. 노란 영역은 1e6 항목 리스트 연산을 수행한 뒤의 메모리 사용량 델타를 나타냅니다.
Armin Rigo 님이 말했습니다... float와 int가 섞인 리스트에 관해: 완전히 호환되는 방법은 SpiderMonkey의 NaN-tagging 아이디어를 사용하는 것입니다. 즉, 일반적으로는 사용되지 않는 특별한 NaN 인코딩을 두고, 여전히 32비트의 추가 정보를 남겨 두는 방식입니다. 그러면 리스트 안의 int를 그런 NaN 인코딩된 float로 표현하게 됩니다. (적어도 정수가 너무 크지 않고 64비트 플랫폼인 한에서는 동작합니다.)
Ole Laursen 님이 말했습니다... 깔끔하네요!
좋은 작업입니다. 결국 첫 번째 원소가 무엇인지에 따라 타입을 바꾸기만 하면 되다니, 이렇게 단순하다는 점이 놀랍습니다. 가비지 컬렉션에도 큰 도움이 되겠지요?
Anonymous 님이 말했습니다... 이 벤치마크는 가상 메모리를 측정합니다(어떤 아키텍처인지는 모르겠습니다). RSS를 측정하는 편이 데이터를 저장하는 데 실제로 사용된 RAM 양을 더 잘 대표할 것입니다. 아마 PyPy에도 더 유리할 텐데, 이동하는 가비지 컬렉션은 가상 메모리 양을 두 배로 만들기 때문입니다.
구독: 댓글 (Atom)
Blogger 제공.
