루아 퍼포먼스 팁(Lua Performance Tip) : 2. 테이블을 초기화하자.

어도비 포토샵 개발자 Mark Hamburg는 새로운 제품 개발에 루아를 활용하여 쉽고, 강력하며, 높은 성능을 제공할 수 있었다고 전했다. 이 제품이 바로 Photoshop Lightroom이다. 뛰어난 스크립트 언어인 루아의 장점도 어떻게 활용하느냐에 따라, 득 또는 실이 될 수도 있다는 점을 반드시 명심해야 한다.

지난번 루아 퍼포먼스 팁(Lua Performance Tip) : 1. 지역변수를 사용하자. 에서는 루아의 지역변수를 사용을 통한 최적화 방법에  대해 알아봤는데, 이번 포스트는 테이블의 초기화와 관련된 최적화를 설명한다. 루아에서 테이블은 일반 변수(문자열, 숫자 등) 못지않게 많이 쓰이며 중요한 역할을 한다. 테이블의 성능과 메모리 관리에 대해서 이해를 하면 퍼포먼스에 좋은 영향을 줄 것이다.


# 내용 요약
테이블은 키와 값을 가지게 되는데, 특정 테이블에 키와 값을 추가하면 테이블의 크기를 계산하여 공간을 할당한다. 흔히 STL 자료형에서 Capacity이 있듯 루아에서도 테이블의 알맞은 크기로 초기 할당을 함으로써, 반복문에서 값을 설정하며 발생하는 오버헤드를 사전에 방지할 수 있다.




Lua Performance Tip - 테이블

일반적으로 루아에서 테이블을 사용할 때, 루아 내부에서 테이블을 어떻게 정의하고 있는지 알 필요는 없다. 실제로 루아는 사용자에게 겉으로 드러내놓지 않고 내부에서 테이블을 상세히 정의하고 있다. 그러나 이러한 세부적인 정의를 루아가 처리함으로써, 테이블 연산의 퍼포먼스는 루아 스스로에 의해 좌우하게 된다. 따라서 테이블을 사용하는 프로그램의 최적화(사실상 어떠한 루아 프로그램이라도)를 위해, 루아에서 어떻게 테이블을 정의하고 있는지 조금은 알고 있는 게 나을 것이다.

루아에서 테이블의 정의는 다소 영리한 알고리즘을 포함하고 있다. 루아에서의 모든 테이블은 배열(Array) 파트와 해시(Hash) 파트, 이 2가지로 구성된다. 배열 파트는 1부터 n(특정한 값의 n) 범위의 정수 키를 갖는 모든 값을 저장한다.(앞으로 어떻게 n이 빠르게 계산되는지를 논할 것이다.) 그밖에 모든 값(정수 키 이외의 범위)은 해시 파트에서 처리한다.

이름에서 알 수 있듯이 해시 파트는 키를 저장하거나 찾기 위해 해시 알고리즘을 사용한다. 해시 알고리즘은 공개된 주소 테이블을 호출하여 사용된다. 이것은 모든 값이 스스로 해시 배열에 저장되는걸 의미한다. 해시 함수는 하나의 키를 기본 인덱스로 제공한다. 만약 저장된 키가 서로 충돌(두 개의 키가 같은 주소 값에 뒤엉켜 있을 때) 한다면, 각각의 값이 하나의 배열 공간을 점유하는 방식으로 연결 리스트화 된다.

테이블에 새로운 키를 삽입하려는데 해시 배열이 가득 차게 되면 루아는 리해시(rehash)를 수행한다. 해시 재수행의 첫 번째로 새로운 배열 파트와 해시 파트의 크기를 결정한다. 그럼으로써 루아는 모든 값을 순회하며 카운팅하고 분류하게 된다. 그리고 나서 배열 파트의 값들을 절반 이상 채우며 두 배의 능력으로 배열 파트의 크기를 정한다. 해시 테이블의 크기는 두 배의 가장 작은 능력으로 남은 모든 값을 처리할 수 있게 된다. So, Lua traverses all entries, counting and classifying them, and then chooses as the size of the array part the largest power of 2 such that more than half the elements of the array part are filled. The hash size is then the smallest power of 2 that can accommodate all the remaining entries (배열 파트안에서 실제 크기가 완벽하게 일치하지 않다.)

루아에서 빈 테이블을 생성할 때 배열 파트와 해시 파트는 0의 크기를 가지며, 딱히 할당된 배열 값은 없다. 아래의 코드를 수행했을 때 발생하는 내용을 확인해 보자.

local a = {}

for i = 1, 3 do
    a[i] = true

end

위의 코드는 a라는 빈 테이블을 한 개 생성하면서 시작한다. 첫 번째 반복문에서 a[1]=true 로 할당은 리해시를 요청하게 된다. 루아에서는 1부터 테이블의 배열 파트 크기를 설정하며 해시 파트는 비어 있는 상태로 유지하게 시킨다. 두 번째 루프를 돌았을 때 a[2]=true로 할당은 또 다시 리해시를 요청하게 된다. 그래서 테이블의 배열파트는 2의 크기를 가지게 된다. 마지막으로 세 번째 루프를 돌았을 때 또 다시 리해시를 요청하며 배열파트의 크기는 4로 증가한다.

위의 코드와 약간은 유사하지만, 아래의 코드는 테이블의 해시 파트 크기 증가가 제외되었다.

a = {}

a.x = 1; a.y = 2; a.z = 3

큰 테이블을 예로 들자면 이런 초기화에 대한 오버헤드는 전체 생성에 대한 부하를 증가시킨다. 3개의 값이 필요한 테이블에 3번의 리해시를 요구하는 동안에, 100만 개의 값을 가지는 테이블은 단지 20번을 필요로 한다. 그러나 작은 테이블을 수천 개 생성한다면 오버헤드의 조합은 중요해질 수 있다.

이전 버전의 루아는 작은 테이블에 대한 초기화의 오버헤드에서 벗어나려고 슬롯을 약간 초기 할당(내가 정확하게 기억한다면 4번)하여 빈 테이블을 생성하였다. 그러나 이러한 접근방식은 메모리를 낭비하게 된다. 예를 들어 테이블(단지 2개의 값을 가지는 테이블처럼)을 100만 개를 생성하였다고 가정했을 때, 각각의 테이블은 이것이 실제로 필요한 메모리의 두 배를 사용하게 된다. 높은 비용을 지불해야 할 것이다. 이런 까닭에 현재의 루아는 초기 할당된 슬롯 없이 빈 테이블을 생성하도록 만들어진 것이다.

만약 당신이 C로 프로그래밍한다면, 루아 API 함수인 lua_createtable를 사용하여 리해시에서 벗어날 수 있다. lua_State 생성 후에 새로운 테이블의 배열파트 초기 크기와 해시 파트 초기 크기 2개의 인자 값을 받는다.¹ 새로운 테이블의 적절한 크기를 제공하여, 초기 리해시에서 손쉽게 벗어날 수 있다. 그러나 주의해야 한다. 이것은 루아의 테이블을 리해시 할 때에만 줄일 수 있다. 그래서 만약 당신의 초기화 크기가 요구하는 크기보다 클 때에는 루아가 낭비된 공간을 절대로 올바르게 처리할 수 없을 것이다.

루아로 프로그래밍할 때에는 이러한 초기화에 대한 리해시에서 벗어나 생성을 해야 한다. {true, true, true} 를 작성하였을 때, 루아는 그 테이블이 배열파트로 3개의 슬롯이 필요하다는 것을 미리 알아챈다. 그래서 루아는 해당 크기로 테이블을 생성한다. 유사한 방식으로 {x = 1, y = 2, z = 3} 를 작성하였을 경우, 루아는 해시 파트로 4개의 슬롯을 갖는 테이블을 생성한다. 아래의 예제에 나온 루프문은 2.0초 안에 처리가 된다.

for i = 1, 1000000 do
    local a = {}
    a[1] = 1; a[2] = 2; a[3] = 3

end

만약 올바른 크기로 테이블을 생성한다면 0.7초로 감소한다.

for i = 1, 1000000 do
    local a = {true, true, true}
    a[1] = 1; a[2] = 2; a[3] = 3

end

또한, {[1] = true, [2] = true, [3] = true} 처럼 작성한다면 루아는 배열 인덱스를 서술하기에는 주어진 표현(이 경우에는 정수 값)에 대한 판단이 아주 훌륭하지 않다. 그래서 이것은 메모리와 CPU 시간을 낭비하면서 해시 파트로 테이블을 4개의 슬롯으로 생성한다.

테이블의 배열과 해시 파트의 크기는 단순히 테이블이 리해시될때에만 재계산된다. 그래서 테이블이 완전히 가득 차 새로운 값을 추가할 필요가 있을 때에만 발생하게 된다. 결과적으로 만약 테이블의 모든 필드(모든 값을 nil로 설정)를 순회하여 지웠을 때는 이 테이블의 크기가 줄어들지 않는다. 그러나 몇 개의 새로운 값을 추가할 때에는 결국 테이블의 크기를 재설정하게 된다. 대개 이것은 문제가 되지 않는다. 만약 값들을 지우거나 새로 추가할 때, 이 테이블의 크기는 완전하게 남아 있다. 그러나 큰 테이블에서는 값을 지움으로써 당신이 메모리 되찾기를 예측할 수 없다. 테이블 스스로 해제되는 게 낫다.

리해시의 능력에서 다소 훌륭하지 못한 편법으로는 충분한 nil 값을 테이블 안에 넣는 것이다.
아래의 예문을 보자.

a = {}

lim = 10000000

for i = 1, lim do a[i] = i end -- 거대한 테이블을 생성한다.

print(collectgarbage("count")) --> 196626

for i = 1, lim do a[i] = nil end -- 모든 값을 지운다.

print(collectgarbage("count")) --> 196626

for i = lim + 1, 2*lim do a[i] = nil end -- 많은 수의 nil 값을 생성한다.

print(collectgarbage("count")) --> 17

특별한 상황을 제외하곤 이 트릭을 추천하지 않는다. 이 트릭은 속도가 느릴뿐더러 현재 테이블의 크기가 얼마나 많이 필요한지 알기도 어렵다.

아마도 루아가 왜 nil 값을 넣어도 테이블을 줄이지 않는지를 궁금해할 것이다. 첫 번째로 테이블에 값을 추가하는 테스트를 제외한 nil 할당은 모든 할당을 느려지게 만드는 걸 확인하자. 두 번째로 더 중요한 점은 테이블을 순회하는 동안 nil 값을 할당할 수 있다. 다음의 루프를 고려해보자.

for k, v in pairs(t) do
    if some_property(v) then
        t[k] = nil -- 값을 지운다.
    end

end

만약 루아에서 값을 nil로 할당하고서 테이블을 리해시 하면 반복문은 참혹하게 순회할 것이다. 단순히 테이블의 모든 값을 지우길 원한다면 아래처럼 테이블을 순회하는 것이 옳을 것이다.

for k in pairs(t) do
    t[k] = nil

end

한 가지 더, 아래와 같은 스마트(smart)한 반복문이 있다.

while true do
    local k = next(t)
    if not k then break end
    t[k] = nil

end

그러나 이와 같은 반복문을 큰 테이블에서 사용할 때 속도가 매우 느리다. 이전 키가 없을 때 next 함수에서는 테이블(랜덤한 순서로)의 첫 번째 값을 반환된다. next 함수는 처음부터 테이블의 배열을 순회하면서 nil이 아닌 값을 찾는다. 반복문에서 테이블의 첫 번째 값을 nil로 설정하는 것처럼, next 함수는 오랜 시간에 걸쳐 첫 번째로 nil이 아닌 값을 찾는다. 결론적으로 pairs를 사용한 루프의 순회는 0.04초가 걸리는 반면, 이 스마트한 루프는 100,000개의 값을 테이블에서 지우는 데 20초가 걸린다.


관련 사이트


루아를 활용한 플러그인 개발이 가능한 Lightroom 2 SDK
Lightroom 에서 사용된 루아 예제 보기

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-동일조건변경허락 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.