[Kotlin] Sequence와 Lazy evaluation

어쩌다보니 내 첫 코틀린 게시물이 되는 것 같다. 파이썬, c++등의 언어를 접해본 적은 있지만 스스로의 의지로 메인스택(Javascript, Typescript)이 아닌 "언어"에 대해 학습해보는 시간은 생각보다 흥미로웠다. 

첫 포스팅은 어떤 내용을 다루면 좋을까 생각해보았다. 사실 첫 글은 코틀린 언어 자체에 대해 느껴보는 글을 적고자 하였지만 이를 느끼는 시간이 생각보다 조금 걸릴지 모르겠단 생각을 하였다. (추후 해당 경험및 생각을 포스팅 해보도록 하겠습니다)

그렇게 고민끝에 선택한 첫 글은 지루한 언어의 개념적 내용이 되었지만 생각보다 흥미있게 공부한 부분인 만큼 포스팅 해 볼 가치가 있다 생각하였다.

바로 코틀린의 "Sequence"이다.

마치 자바의 Stream이 연상되는 코틀린의 Sequence는 단순히 인지만 하고 넘어갈 수도 있었지만, 조금 더 파헤쳐보면 매우 흥미로운 키워드였다.  (이 글에 나온 예제 일부는 "Kotlin In Action" 을 참고하였습니다)

 

✔ 간단한 예시로 알아보는 Collection vs Sequence

아래는 간단하게 map()과 filter()를 활용하여 거듭제곱된 수의 값중 짝수인 것만 필터링해 값을 반환하는 로직이다.

그냥 눈으로만 보아도 collectionList의 결과는 [4, 16]이 될 것으로 예상된다. 그렇다면 해당 컬렉션이 순회하는 과정은 어떻게 될까?

fun main(args: Array) {
    // sequence evaluation  
    val collectionList = listOf<Int>(1, 2, 3, 4)  
        .map { println("map($it) "); it \* it }   
        .filter { println("filter($it) "); it % 2 == 0 }  
        .toList()   

    println(collectionList)
}

결과

map(1)
map(2)
map(3)
map(4)
filter(1)
filter(4)
filter(9)
filter(16)
[4, 16]

 

list의 각 원소마다 map()과 filter()를 수행하는 것이 아닌 전체 원소에 대해 모든 각 연산을 거친 뒤 최종 값을 리턴하는 것을 확인할 수 있다.

그렇다면, Sequence를 사용하였을 경우는 어떨까? (with asSequence())

fun main(args: Array) {
    // sequence evaluation
    val sequenceList = listOf(1, 2, 3, 4).asSequence() 
    .map { println("map($it) "); it * it } 
    .filter { println("filter($it) "); it % 2 == 0 }
    .toList() 
    println(sequenceList)    
}

결과

map(1)
filter(1)
map(2)
filter(4)
map(3)
filter(9)
map(4)
filter(16)
[4, 16]

리스트의 최종 결과는 동일하지만 원소를 계산하는데 있어, 순회하는 과정이 달라진 것을 확인할 수 있다.

전체 원소를 전부 첫 번째 연산 후(map) 다음 연산(filter)으로 넘어가는 것이 아닌, 각 원소에 대해 바로바로 다음 컬렉션을 수행한다는 것이다.

위의 예시가 가시적 차이를 느끼기엔 부족하지만 만약 연산을 수행해야할 원소의 양이 매우 클 경우, 특정 조건에 만족하면 바로 값을 리턴 해야한다면 어떨까?

예를 들면 아래와 같이 말이다.

val ca1 = (100 .. 200_000_000).asSequence()
    .map { println("doubling $it"); it * 2 }
    .filter { println("filtering $it"); it % 3 == 0 }
    .first() // sequence가 비었다면 NoSuchElementException 이 발생한다. (.fistOrNull() 를 사용할 수도 있다.)
println("cal: $ca1")

만약, Sequence가 아닌 일반 Collection을 사용했다면 위의 연산에서 `100`부터 `200_000_000` 까지의 모든 원소에 대한 연산을 수행해야 했을 것이다.

결과

doubling 100
filtering 200
doubling 101
filtering 202
doubling 102
filtering 204
cal: 204

 

간단히 컬렉션과 시퀀스의 예시 코드를 통해 둘을 비교해 보았고 어떠한 차이점이 있는지 확인해볼 수 있었다. 

아래에선 조금은 더 심화적인 개념에 접근해보도록 하자.

 

✔ Sequence 심층 분석 (part_1)


예시로 알아보았던 Collection과 Sequence를 한 번 해석해보자.

map()이나 filter() 같은 몇 가지 컬렉션 함수를 살펴보았다. 그런 함수는 결과 컬렉션을 즉시 생성한다. 이는 컬렉션 함수를 연쇄하면 매 단계마다 계산 중간 결과를 새로운 컬렉션에 임시로 담는다는 뜻이다. 시퀀스(sequence)를 사용하면 중간 임시 컬렉션을 사용하지 않고도 컬렉션 연산을 연쇄할 수 있다.

코틀린 지연 연산(lazy evaluation)은 Sequence 인터페이스에서 시작한다. Sequence 안에는 `iterator`라는 단 하나의 메서드가 존재한다. 그 메서드를 통해 시퀀스로부터 원소 값을 얻을 수 있다.

public interface Sequence<out T> {
    public operator fun iterator(): Iterator<T>
}

또한, iterator 메서드를 이루는 Iterator 인터페이스는 아래와 같다.

public interface Iterator<out T> {
    /**
     * Returns the next element in the iteration.
     *
     * @throws NoSuchElementException if the iteration has no next element.
     */
    public operator fun next(): T

    /**
     * Returns `true` if the iteration has more elements.
     */
    public operator fun hasNext(): Boolean
}

 

Iterator에 대해 알아보자. 

Iterator의 가장 큰 특징은 현재 Position을 기억한다. next()를 호출하면 현재 Position이 가리키는 요소를 return 하고, Position 값을 한 칸 이동한다. Position을 이전 위치로 이동시킬 순 없다. 아래 코드를 살펴보자.

val iterator = listOf(1,2,3).iterator()
println(iterator.next()) // 1
println(iterator.next()) // 2
println(iterator.next()) // 3
println(iterator.next()) // Exception

결과

1
2
3
Exception in thread "main" java.util.NoSuchElementException
    at java.base/java.util.Arrays$ArrayItr.next(Arrays.java:4245)

Iterator 인터페이스 description에서 볼 수 있듯이 Position이 끝에 도달하였을 경우, `NoSuchElementException`을 발생시키기 때문에 `next()` 메서드 호출 시엔 `hasNext()`의 선 작업을 통하여 안전성을 체킹하는 것이 보통의 케이스다.

 

✔ Sequence 심층 분석 (part_2)

Sequence vs Iteratable(일반 컬렉션) 측정 시간 분석

아래는 주어진 문장의 공백을 통해 구분 된 단어를 컬렉션 연산자(혹은 시퀀스 연산자)를 통해 조건(단어의 길이가 3이상인 단어들을 추출하고 그 단어의 길이를 통해 새로운 배열을 생성한다. 이때 단 4개의 원소만을  배열 생성에 쓰이게끔 한다.

fun main() {
  val time1 = measureTimeMillis {
        val words = "The quick brown fox jumps over the lazy dog".split(" ")
        val wordsIterator = words.toList()
        wordsIterator.filter { println("filter: $it"); it.length > 3  }
            .map { println("length: ${it.length}"); it.length }
            .take(4)
    }
    println("Iterable : $time1 mills")

    println("---------------------------------------------")

    val time2 = measureTimeMillis {
        val words = "The quick brown fox jumps over the lazy dog".split(" ")
        val wordsSequence = words.asSequence()
        wordsSequence.filter { println("filter: $it"); it.length > 3 }
            .map { println("length: ${it.length}"); it.length }
            .take(4)
            .toList()  // sequence의 경우 toList()가 있어야 리스트가 생성 가능하다.
    }
    println("Sequence : $time2 mills")
}

동작 진행 및 측정 시간은 어떻게 될까?

결과

filter: The
filter: quick
filter: brown
filter: fox
filter: jumps
filter: over
filter: the
filter: lazy
filter: dog
length: 5
length: 5
length: 5
length: 4
length: 4
Iterable : 18 mills
---------------------------------------------
filter: The
filter: quick
length: 5
filter: brown
length: 5
filter: fox
filter: jumps
length: 5
filter: over
length: 4
Sequence : 20 mills

보다시피 오히려 Iterator보다 Sequence에서 연산 시간이 더 많이 측정된 것을 확인할 수 있다.

이는 왜 그런 것일까? 물론, `measureTimeMillis()`의 불정확성도 존재하겠지만 비교한 데이터 셋의 크기가 "작기" 때문이 아닐까 싶다.

그렇다면 데이터 셋의 크기를 확실히 키워보자.

fun main() {
  val largeWordsList = generateLargeWordsList()

    // Sequence 사용
    val timeSequence = measureTimeMillis {
        val wordsSequence = largeWordsList.asSequence()
        val result = wordsSequence
            .filter { it.length > 3 }
            .map { it.length }
            .take(4)
            .toList()
        println("Sequence result: $result")
    }
    println("Sequence time: $timeSequence ms")

    println("---------------------------------------------")

    // Iterator 사용
    val timeIterator = measureTimeMillis {
        val wordsIterator = largeWordsList.toList()
        val result = wordsIterator
            .filter { it.length > 3 }
            .map { it.length }
            .take(4)
            .toList()
        println("Iterator result: $result")
    }
    println("Iterator time: $timeIterator ms")
}

fun generateLargeWordsList(): List<String> {
    val words = "The quick brown fox jumps over the lazy dog".split(" ")
    val repeatedWords = List(1000000) { words }.flatten()
    return repeatedWords.shuffled()
}

첫 번째 예시와 동일한 문장을 `1,000,000`번 반복해 합친 뒤, `shuffled()`를 통해 무작위로 배열시킨다. 이 정도면 일반 Iterator와 Sequence의 차이를 비교하기 충분하다.

결과

(실제로는 각각 따로 계산해야 정확한 결과를 얻을 수 있다)

Sequence result: [4, 5, 5, 4]
Sequence time: 2 ms
----------------------------------------------
Iterator result: [4, 5, 5, 5]
Iterator time: 230 ms

 

✔ Sequence 심층 분석 (part_3)

Sequence가 무조건 옳을까? (feat _inline)

앞서 심층 분석 part_2에서도 알아보았지만 Sequence를 사용하는 것이 Collection을 사용하는 것 보다 무조건적으로 성능상 우위를 점하는 것은 아니다. 보았다시피, 데이터 셋의 크기가 작은 경우, 오히려 컬렉션을 사용할 경우 실행 시간이 더 빠른 것을 확인할 수 있었다.

그 이유는 무엇일까? 왜 특정 임계치 이하 크기의 데이터 셋에선 오히려 컬렉션의 성능이 더 좋은 것일까? (사실, 그렇다고 해서 엄청 크리티컬한 성능 우위를 점하진 않다고 본다...)

이유는 바로 "람다의 부가 비용"에 있다. 
조금 더 자세히 말하면 "외부 변수 캡쳐"에 의한 람다의 부가 비용이다.

코틀린에 대해 어느정도 학습이 되었다면 코틀린은 람다 내부에서 외부 변수 캡쳐를 통한 접근을 허용한다는 점을 인지할 것이다.

여태껏 위에서 봐온 예시들에서 filter,  map 등의 컬렉션 함수의 람다식 내부에서 it을 통해 접근한 외부 변수 또한 변수 Capture를 통해 가능케 된 것이다. 

자, 일단 위의 내용을 Keep해 두고, 
코틀린에서 ***람다를 인자로 둔 함수를 호출할 때*** 어떤 일이 일어나는지 먼저 알아볼 필요가 있다.

ex1) 일반적 케이스

val runnable = Runnable { println(42) }
fun handleComputation() {
    postponeComputation(1000, runnable)
}

매번 postponeComputation()을 호출할 새로운 `object`를 생성하지 않는다. 위와 같이 매번 이미 생성된 runnable 객체를 사용하는 것이다.(Singleton)

ex2) 외부 변수 캡쳐

fun handleComputation(id: String) { // 람다 안에서 id 변수 사용
    postponeComputation(1000) { println(id) } // 람다 호출 시 마다 매번 새로운 Runnable 인스턴스 생성 
}

하지만 위의 경우 (람다 내부에서 외부 변수에 접근하는 경우)는 다르다. 마치 람다를 object로 구현한 것처럼 람다를 호출할 때마다 새로운 객체(인스턴스)가 생성된다.

"ex1"을 일반적 케이스라 두었지만 사실 더 많이 쓰이는 경우는 후자가 아닐까 싶다. 그렇다면 이렇게 람다에서 외부 변수에 접근하는 경우 항상 새로운 객체를 생성하게 되는데... 이러한 성능 이슈는 어떻게 해결할 수 있는 걸까? 어떻게 하면 효율적으로  람다를 사용할 수 있는 걸까?

그것이 바로 이번 내용의 키 포인트인  "inline" 키워드이다.

inline 변경자를 함수 앞에 붙이면, 컴파일러는 그 함수를 호출하는 모든 문장을 함수 본문에 해당하는 바이트코드로 바꿔치기 해 준다.

직접 Decompiling 하는 시간을 가져보면 좋을거 같다.  인자에 람다 식을 담은 간단한 고차 함수(High-order Function)가 좋은 예시일 듯 하다. 

Kotlin

fun main(args: Array<String>) {
    // 람다 식을 전달하는 예제
    val resultInline = operateInline { a, b -> a * b }
    val resultNonInline = operateNonInline { a, b -> a * b }

    println("Result with inline function: $resultInline")
    println("Result with non-inline function: $resultNonInline")
}

// inline 키워드 사용
inline fun operateInline(operation: (Int, Int) -> Int): Int {
    return operation(5, 10)
}

// inline 키워드 사용하지 않음
fun operateNonInline(operation: (Int, Int) -> Int): Int {
    return operation(5, 10)
}

Decompiling with JAVA (`main`함수만)

public static final void main(@NotNull String[] args) {
    Intrinsics.checkNotNullParameter(args, "args");
    int $i$f$operateInline = false;
    int b = 10;
    int a = 5;
    int var5 = false;
    int resultInline = a * b;
    int resultNonInline = operateNonInline((Function2)null.INSTANCE);
    String var7 = "Result with inline function: " + resultInline;
    System.out.println(var7);
    var7 = "Result with non-inline function: " + resultNonInline;
    System.out.println(var7);
 }

 

✔ Byte코드 확인하는 법: Android Studio -> Tools -> Kotlin -> Show Kotlin Byte Code

 

위에서 볼 수 있듯이 자바로 변환 시 inline 함수의 결과와 inline이 아닌 함수의 결과 데이터의 차이가 존재한다.

int resultInline = a * b;   --> 람다 식 본문을 그대로 전달
int resultNonInline = operateNonInline((Function2)null.INSTANCE);  --> 새로운 인스턴스 생성

 

이것이 의미하는 바가 무엇일까?
 
아래는 코틀린의 컬렉션 함수인 filter의 구현코드이다.

public inline fun <T> Iterable<T>.filter(predicate: (T) -> Boolean): List<T> {
    return filterTo(ArrayList<T>(), predicate)
}

이처럼 코틀린에서 람다를 인자로 받는 유용한 메서드는 inline 키워드를 자체 제공한다. 그만큼 코틀린도 해당 이익을 볼 것이다는 메시지를 주는 것이 아닐까 싶다.

하지만, 아래의 경우는 얘기가 달라진다.

아래는 동일한 filter가 컬렉션이 아닌 Sequence일 경우이다.

public fun <T> Sequence<T>.filter(predicate: (T) -> Boolean): Sequence<T> {
    return FilteringSequence(this, true, predicate)
}

Sequence에서 filter 함수엔 inline 변경자가 제공되지 않는다.  즉, 시퀀스를 사용할 경우 "람다가 인라이닝 되지 않고", "호출 시 별도의 객체를 생성" 하게 된다. 

글이 장황해 졌지만, 아무튼 위와 같은 이유로 성능을 향상시킨다는 명목하에 모든 컬렉션 연산에 시퀀스를 사용하면 안된다는 것이다. 데이터 셋이 작은 컬렉션은 오히려 일반 컬렉션일 경우 성능이 더 좋다는 것이 이러한 이유로 설명된다.