[Utils] CompactList

 나무위키 문서들을 노드삼아 공통되는 기여자가 있다면 엣지를 추가하는 식으로 데이터를 정재해나가다 메모리 문제를 겪었다.

 나무위키 문서의 수는 대략 87만개(2021년 3월 기준)로 이 중 redirect 문서를 제외하더라도 57만개의 문서가 존재하며,

기여자의 숫자는 2백만이 넘는다. 이들 중 극히 일부로 문서와 기여자를 줄이고 그래프를 제작하더라도 1억이 넘는 엣지가 생겨나고 이를 저장할 List는 매우 큰 메모리를 갖게된다.

Python의 List 메모리 할당

단순하게 백만개의 int List가 있다고 생각해보자, int가 64bit 기준 8byte라 생각한다면 사용되는 메모리는 8 * 1,000,000 = 대략 8 mb 일 것이다.

python의 sys.getsizeof() 함수를 이용하여 원소가 백만개인 리스트의 크기를 측정해보면 다음과 같은 결과를 얻을 수 있다.

import sys

a = []

for i in range(1000000):
	a.append(i)

print(sys.getsizeof(a))

8697464

 

결과는 약 8.6 mb 로 8mb와 큰 차이는 없어보인다. 하지만 공식문서에서 getsizeof() 함수의 정의를 보면

sys — System-specific parameters and functions — Python 3.9.7 documentation

Only the memory consumption directly attributed to the object is accounted for, not the memory consumption of objects it refers to

즉, 해당 크기는 list 자체가 가지는 값으로 내부 원소들의 메모리는 포함되어 있지않다. 문서에 나와있는대로 recursive한 함수를 작성하여 제대로 된 크기를 구할 순 있지만 편하게 pympler 라이브러리를 사용하여 값을 구하면,

from pympler import asizeof

a = []

for i in range(1000000):
	a.append(i)

print(asizeof.asizeof(a))

40697456

무려 40.6mb로 처음 예측하였던 8mb에서 5배나 큰 값을 가지는 것을 알 수 있다. 이렇게 큰 차이가 나타나는 것은 크게 두 가지 이유가 있는데 우선 다음 코드를 확인하여보자

from pympler import asizeof

print(asizeof.asizeof(1))

32

처음가정으로 int 자료형의 기본 크기를 8byte로 가정하였는데, 64bit python 3.7 환경에서 int는 32 byte의 크기를 갖는다. 그렇기 때문에 이를 고려하여 계산한다면 32mb 의 메모리를 소모하는데 여전히 8mb의 오차가 발생한다.

How is Python's List Implemented?

Python list structure

이는 python의 리스트가 구현된 방식을 보면 알 수 있다. List object가 pointer들로 이루어져있기때문이다. 따라서 포인터들의 총 크기를 합친다면, 백만개의 원소를 갖는 python list의 크기를 구할 수 있고 우리는 이것이 40mb라는 것을 확인하였다. 따라서 단순한 리스트와 달리 python의 리스트는 매우 큰 메모리를 소비한다는 것을 알 수 있는데 이는 numpy의 array를 사용한다면 가볍게 해결할 수 있다.

import numpy as np
from pympler import asizeof

a = []

for i in range(1000000):
	a.append(i)

print(asizeof.asizeof(np.array(a)))

4000112

백만개의 원소를 갖는 array의 메모리는 무려 4mb로 python의 리스트에 비하면 10배나 차이가 난다. 이는 array가 데이터를 저장하는 방식이 다름은 물론 numpy에서 취급하는 자료형의 크기또한 다르기 때문에 나타난다. 따라서 크기가 고정된경우 numpy의 array를 이용한다면 매우 효과적으로 메모리를 사용할 수 있지만, 크기가 고정되지 않은 데이터의 경우는 이야기가 달라진다. 위의 예제에서 a 라는 리스트를 만들지 않고 array만 사용한다면 어떨까? 다음 두 코드를 비교하여보자

st = time.time()

a = []

for i in range(1000000):
	a.append(i)

print(time.time() - st)

0.13212037086486816

st = time.time()

a = np.array([])

for i in range(100000):
	a = np.append(a, [i], axis=0)

print(a.shape) #값이 제대로 append 되었는지 확인
print(time.time() - st)

(100000,)
1.5994656085968018

np append 를 이용하여 dynamic 한 np array를 구성하였을 때 원소의 크기를 1/10하였음에도 불구하고 10배가 넘는 시간차이가 발생하였고, 백만개의 원소는 더욱 오래걸려 측정이 힘들었다. 따라서 데이터의 크기를 정확히 모르는 경우 그냥 append를 사용하는 것은 좋은 생각이 아닌 것으로 보인다. 여기서 한 가지 트릭을 생각할 수 있는데

import numpy as np
import time

st = time.time()

a = np.array([])

for i in range(100000):
	a = np.append(a, [j + (10 * i) for j in range(10)], axis=0)

print(a.shape)
print(time.time() - st)

(1000000,)
94.81219935417175

백만개의 원소를 갖는 array를 dynamic하게 만들었으며 원소를 하나씩 집어넣을 때보다 훨씬 빠른 것을 알 수 있다. 예시에서는 십만개로 줄여서 확인을 했었으니 다시 십만개로 비교를 해보자면,

st = time.time()

a = np.array([])

for i in range(10000):
	a = np.append(a, [j + (10 * i) for j in range(10)], axis=0)

print(a.shape)
print(time.time() - st)

(100000,)
0.19117355346679688

한 개씩 추가하는 것보다 훨씬 빠르다는 것을 알 수 있다. 지금까지 내용을 정리하면 다음과 같다.

정리

1. Python의 List는 numpy 의 array에 비해 메모리를 많이 차지한다.

2. 고정된 사이즈의 데이터가 있다면 array를 사용하는 것이 효과적이다.

3. 하지만 고정되지 않고 dynamic한 구조의 array가 필요하다면 numpy append를 사용하는 것이 매우 느리다.

4. 원소를 하나씩 append 하지않고 여러개를 한번에 append 한다면 더욱 빠르게 dynamic array를 구성할 수 있다.

 

이 4가지 사실을 조합하여 CompactList를 구성하였다.

 

class CompactList:
    def __init__(self, blocksize, dtype=np.int32):
        """
        Using list allocate memory much more than numpy array.
        But numpy array is not dynamic and use it with append is slow.
        So make list block and if elements exceed block size, append it to np array
        :param blocksize: Size of list block
        """
        self.blocksize = blocksize
        self.list = []
        self.array = None
        self.dtype= dtype
        self.block_idx = 0

    def __len__(self):
        return len(self.list) + len(self.array)

    def __getitem__(self, idx):
        if idx >= self.block_idx * self.blocksize:
            idx -= self.block_idx * self.blocksize

            return self.list[idx]

        return self.array[idx]

    def append(self, data):
        self.list.append(data)

        if len(self.list) >= self.blocksize:
            self.block_idx += 1

            if self.array is not None:
                self.array = np.append(self.array, self.list, axis=0)
            else:
                self.array = np.array(self.list, dtype=self.dtype)
            self.list = []

간단하게 해설을 하자면, CompactList는 내부적으로 기본 리스트와 numpy array 두 가지를 갖는다. 기본 리스트를 block 이라고 이야기하자. CompactList에 원소를 append 하게되면 처음엔 block속에 값을 넣는다. 그러다가 block이 blocksize를 초과하게되면 array에 값을 append 하는 형식이다.

import time
import numpy as np
from pympler import asizeof

st = time.time()

compact = CompactList(blocksize=4096)

for i in range(1000000):
	compact.append(i)

print(asizeof.asizeof(compact))
print(time.time() - st)

4021616
0.6275708675384521

이를 이용하여 백만개의 원소를 갖는 CompactList를 살펴보면 List보다는 메모리를 적게먹고 Numpy array 보다 빠르게 append가 가능한 리스트를 만들 수 있다.