Functional Programming - Memoization (메모이제이션)

함수형 프로그래밍 패러다임으로 바꾸는 이유 중 하나는 지루한 일은 런타임이 하도록 떠맡겨서 개발자로 하여금 더 중요한 문제에 집중할 수 있게 한다는 것이다.

이번 글에서는 개발자가 기능을 구현할 때 실수를 많이 저지를 수 있는 부분인 ‘캐시’ 에 대하여, 함수형 언어가 어떤 식으로 쉽게 해결할 수 있도록 도와주는지 알아보려고 한다.

시간이 많이 걸리는 연산을 반복적으로 사용해야 한다고 가정해보자. 굳이 연산이 아니더라도 좋다, 안드로이드에서 사용자 지정 글꼴을 불러올 때 사용해야 하는 Typeface Cache 등을 생각해보자.

보편적인 해결 방법은 내장 캐시를 설정하는 것이다. 주어진 파라미터를 사용하여 행동을 수행할 때 마다 맵에 저장해놓고, 차후 같은 파라미터로 요청이 들어왔을 경우에는 맵에 있는 데이터를 가져온다.

물론, 이 캐시는 메모리를 차지하게 되므로 기본 전제 조건은 ‘메모리가 충분한 경우’ 이다.

단 이 캐싱 방법이 제대로 작동하려면 함수가 순수해야 하는데, 간단히 설명하자면 같은 파라미터로 넣으면 항상 똑같은 값이 나와야 한다는 것이다. 처음에 12를 넣었는데 값이 14가 나오고, 다음에 12를 넣었을 때 16이 나오는 등 그때그때마다 변하면 안된다.

캐시를 구현하는 방법은 두 가지가 있는데, 원시적으로 개발자가 맵을 구현하는 외부 캐싱 방법과 반복되는 함수의 리턴 값을 자동으로 캐시해주는 메모이제이션 방법이 있다.

예제 코드

본 글에서는 어떤 한 자연수를 넣었을 때 그 자연수의 모든 약수의 값을 더해주는 코드로 예시를 들 것이다.

기본적으로 어떤 자연수(B)가 어떤 자연수(A)에 대하여 약수이려면, A / B 했을 때 나머지가 0이면 된다. 여기서 B는 A보다 같거나 작아야 한다.

코드로 표현하자면 아래와 같을 것이다. 리턴 타입은 Boolean 이나 여기서는 생략했다.

fun isFactor(number: Int, potential: Int) = number % potential == 0

그리고 모든 약수를 구해야 하니, 1 부터 A 까지 isFactor 작업을 반복해서 true 인 것만 걸러내자.

역시 마찬가지로 리턴 타입은 List 이나 여기서는 생략했다.

fun factorsOf(number: Int) = (1..number).filter { isFactor(number, it) }.toList()

마지막으로 모든 약수의 합을 구하자.

말 안해도 알겠지만, 리턴 타입은 Int이다.

fun sumFactors(number: Int) = factorsOf(number).sum()

합산 결과를 캐시하기 (외부 캐싱)

val sumMap = mutableMapOf<Int, Int>()

private fun cachedSumFactors(number: Int): Int {
    val value = sumMap[number]
    return if (value == null) {
        val answer = sumFactors(number)
        sumMap.put(number, answer)
        answer
    } else {
        value
    }
}

먼저 클래스 초기화 당시 sumMap 라는 해시를 만든다. cahceSumFactors 메서드 내부에선 해당 sumMap 에 파라미터로 온 자연수의 약수의 합이 들어있으면 바로 그 값을 반환, 없으면 계산 후 맵에 넣고서 반환한다.

어디서나 흔히 볼 수 있는 캐시 방법이니 더 설명할 부분이 없다고 생각된다.

벤치마크 결과는 아래와 같다.

• 첫 시행: 15.09254ms
• 두번째 시행: 0.45838ms
• 10회 평균: 0.2975ms
• 캐시 첫 시행: 14.41842ms
• 캐시 두번째 시행: 0.0116ms
• 10회 평균: 0.0029ms

첫 시행 때에는 10번 반복과 캐시의 결과가 그렇게 차이나지는 않는다. 오히려 캐시 첫 시행의 시간이 더 적게 걸렸는데 이는 환경적 요인에 의한 것으로 보통이라면 맵에 넣는 과정이 있어서 캐시 첫 시행이 시간이 더 걸린다.

하지만 두번째 시행 부터는 차이가 많이 나는데, 캐시를 했을 경우 두번째 부터는 해시를 얼마나 빠르게 읽을 수 있는지를 측정하는 셈이 되는 것이다.

합을 캐시하게 되면 성능은 좋아지지만 단점 역시 존재하는데 내부 캐시가 상태를 표시하기 때문에 이 캐시를 사용하는 모든 메서드를 인스턴스 메서드로 만들어야 한다. Singleton 을 만들 수도 있으나 이럴 경우에는 코드가 더 복잡해지고 테스트 할 때 문제를 일으킬 수 있다. 개발자가 캐시 변수를 제어하기 때문에 이 역시 직접 정확성을 테스트나 다른 방법으로 사용하여 확인해야 한다. 이 방법은 성능을 향상시키는 대신 코드의 복잡성 증가 및 유지보수 난이도 상승이란 결과를 가지고 온다.

또한 캐시의 범위가 커지면 그만큼 적은 값을 캐시하기 때문에 정확함과 함께 실행 조건도 신경써야 한다. 이 것이 지난 글에서 페더스가 말한 ‘움직이는 부분’에 해당하게 된다.

메모이제이션

메모이제이션 이란 단어는 Donald Michie 라는 인공지능 연구학자가 ‘연속해서 사용되는 연산 값을 함수 레벨에서 캐시하는 것’을 지칭하기 위해 사용한 단어이다.

흔히 메모이제이션을 설명하기 위해 사용되는 예제는 피보나치 수열인데, f(1)는 f(1) + f(0), f(2)는 f(2) + f(1) + f(0) 이런 식이다. 만일 f(4) 를 구한다고 해보면 f(3) + f(2) + f(1) + f(0) 인데 각각의 f(n) 조차 하위 계산을 요구하니 그 시간복잡성은 매우 커지게 된다. 이 때 메모이제이션 방법을 사용해 함수 레벨 자체를 캐시하게 되면 하위 계산을 하지 않게 되어 시간복잡성이 O(n) 수준으로 줄어든다.

전에도 말했지만 함수형 프로그래밍은 재사용 가능한 메서드를 만들어서 ‘움직이는 부분’을 최소화하는 데에 주력한다. 이는 캐시도 제외되지 않는데, 많은 언어들이 메모이제이션을 언어 단에서 제공하기도 한다.

메모이제이션과 외부 캐싱은 서로 다른데, 외부 캐싱은 합산한 결과, 즉 연산 결과를 저장하지만 메모이제이션은 코드 블럭, 즉 연산하는 부분 자체에서 캐시를 한다는 점이다. 어떻게 보면 메타함수를 적용하는 것이라고도 볼 수 있다.

Groovy 등에서는 코드 블럭(클로져) 에 .memoize() 라는 메소드를 사용함으로서 메모이제이션 기능을 활성화할 수 있는데, 안타깝게도 Kotlin 은 내장하고 있지 않다.

하지만 우리가 누군가, 개발자다. 없으면 만들면 되는 것이다.

class MemoizeHelper<in T, out R>(private val function: (T) -> R) : (T) -> R {
    private val valuesMap = mutableMapOf<T, R>()
    override fun invoke(key: T): R = valuesMap.getOrPut(key, { function(key) })
}

fun <T, R> ((T) -> R).memoize(): (T) -> R = MemoizeHelper(this)

기본적으로 외부 캐시와 비슷한 구조인데, 클래스 초기화시 valuesMap 라는 맵을 초기화하고 memoize() 메서드가 실행되면 MemoizeHelper 의 invoke 메서드를 통하여 valuesMap 에 값이 있으면 바로 반환, 없으면 연산하고 맵에 넣고 반환하는 기능을 수행한다. (getOrPut 라는 메서드가 이 기능을 다 해준다.)

그리고 주어진 자연수의 약수의 합을 구하는 코드 자체를 블럭으로 감싸서 이를 메모아이즈 해보자.

val memoizeSumFactors = { number: Int -> sumFactors(number) }.memoize()

시행 결과는 아래와 같다.

• 첫 시행: 15.09254ms
• 두번째 시행: 0.45838ms
• 10회 평균: 0.2975ms
• 캐시 첫 시행: 14.41842ms
• 캐시 두번째 시행: 0.0116ms
• 10회 평균: 0.0029ms
• 메모이제이션 첫 시행: 17.60542ms
• 메모이제이션 두번째 시행: 0.00778ms
• 10회 평균: 0.0026ms

두번째 실행부터 외부 캐싱 결과보다 속도가 빨라졌는데, sumFactors 자체를 코드 블록을 만들고, memoizeSumFactors 는 그 코드 블럭의 메모아이즈된 인스턴스를 가리키게 한 것이다.

결론

명령형 버전(외부 캐싱)에서는 개발자가 코드를 소유하고 책임을 진다. 함수형 언어는 가끔 특별한 상황을 제외하고는 주로 표준에 맞는 구조에 적합한 일반적인 도구를 만든다. 함수가 언어의 기초적인 요소이기 때문에, 그 레벨에서 최적화가 된 고급 기능을 공짜로 얻는 셈이다. 언어 설계자들은 자기 자신이 정한 규칙도 어길 수 있다. 다시 말하자면 일반 개발자들이 접근할 수 없는 부분까지 접근할 수 있기 때문에 최적화를 진행할 수 있어 이미 만들어진 것 보다 더 효율적인 캐시를 만드는 것은 거의 불가능하다고 볼 수 있다.

또, 언어가 캐싱을 더 효율적으로 지원하기도 하지만 개발자는 그런 지루한 일을 런타임에게 떠맡기고, 더 높은 수준에서 추상화된 문제들에 고민해야 한다.

외부 캐싱 같은 수작업으로 캐시를 만드는 것은 간단하다. 하지만 코드에 내부 상태를 더하고 복잡하게 만들어 ‘움직이는 부분’을 증가시키는데 비해 함수형 언어의 메모이제이션 기능을 사용하면 함수 레벨에서 캐시를 더할 수 있어서, 코드를 거의 바꾸지 않고도 더 좋은 성능과 간결한 코드를 얻을 수 있다.

단 외부 캐싱이든 메모이제이션이든 중요한 전제조건이 있는데, 함수가 순수해야 한다. 외부 캐싱된 결과나 메모아이즈된 함수의 결과가 주어진 파라미터 이외의 어떤 것에라도 의존하면 기대하는 결과는 항상 얻을 수 없다.

부록

전체 테스트 코드는 아래와 같다.

import kotlin.system.measureNanoTime

// region Factors
fun isFactor(number: Int, potential: Int) = number % potential == 0

fun factorsOf(number: Int) = (1..number).filter { isFactor(number, it) }.toList()
fun sumFactors(number: Int) = factorsOf(number).sum()

/**
 * formatting methods for showing measureNanoTimes effectively
 */
fun Long.format() = String.format("%.5f", (this.toDouble() / 1000000.toDouble()))
// endregion

// region Memoize implement part
class MemoizeHelper<in T, out R>(private val function: (T) -> R) : (T) -> R {
    private val valuesMap = mutableMapOf<T, R>()

    override fun invoke(key: T): R = valuesMap.getOrPut(key, { function(key) })

}

fun <T, R> ((T) -> R).memoize(): (T) -> R = MemoizeHelper(this)
val memoizeSumFactors = { number: Int -> sumFactors(number) }.memoize()
// endregion

// region Cache implement part
val sumMap = mutableMapOf<Int, Int>()

private fun cachedSumFactors(number: Int): Int {
    val value = sumMap[number]
    return if (value == null) {
        val answer = sumFactors(number)
        sumMap.put(number, answer)
        answer
    } else {
        value
    }
}

// endregion
fun Boolean.toInt() = if (this) 1 else 0

val isMemoize = true
val isApply = true
val examplenumber = 2016
val loopCount = 10

fun main(args: Array<String>) {
    val value = isApply.toInt() + isMemoize.toInt()
    println("Measuring start, methods is $value")

    val applyMethod = {
        when (value) {
            2 -> {
                memoizeSumFactors(examplenumber)
            }
            1 -> {
                cachedSumFactors(examplenumber)
            }
            else -> {
                sumFactors(examplenumber)
            }
        }
    }

    for (i in 1..loopCount) {
        println("Step $i, Measured Time is ${(measureNanoTime { applyMethod.invoke() }).format()}ms")
    }
}