Elixir Comprehension Filter Optimize

Elixir에서는 enumerable이나 bitstring 자료형을 쉽게 만들 수 있게 해주는 Comprehension이라는 매크로가 있다. 조금 더 쉽게 설명하자면 반환값이 있는 for문이다. 이 Comprehension을 사용할 때, 필터(Filter)를 사용하여 몸체 실행 여부를 제어할 수 있다. 그런데 이 필터가 적용되는 위치에 따라 성능에 큰 차이를 주기도 하는데, 이에 대해 작성해보고자 한다.

Filter 위치에 따른 시간 차이를 측정해보자

defmodule MyModule do
  def func1(n, m) do
    for i <- 1..n, j <- 1..m, i <= 100 do
      # ...
    end
  end
  
  def func2(n, m) do
    for i <- 1..n, i <= 100, j <- 1..m do
      # ...
    end
  end
end

위 두 함수의 차이는 Filter의 위치이다. func1은 필터가 마지막에 위치하지만, func2는 첫번째 Generator와 두번째 Generator 사이에 위치한다.

{time1, _} = :timer.tc(func1, [10_000, 10_000])
{time2, _} = :timer.tc(func2, [10_000, 10_000])

IO.puts("func1 수행 시간 : #{time1 / 1_000_000}초")
IO.puts("func2 수행 시간 : #{time2 / 1_000_000}초")

# func1 수행 시간 : 1.116457초
# func2 수행 시간 : 0.017684초

위 두 함수의 수행 시간을 측정해보면, 시간 차이가 꽤 큰 것을 알 수 있다. 이 차이는 인자 값의 크기가 커질수록 더욱 커지게 된다.

차이가 왜 날까?

for i <- 1..n, j <- 1..m, i <= 100 do
for i <- 1..n, i <= 100, j <- 1..m do

엘릭서에서 Comprehension은 순서대로 실행된다. 즉, 첫번째 Comprehension은 i가 할당이 되고 j가 할당이 된 뒤, 필터를 통해 이후의 실행 여부를 결정한다. 이와 달리 두번째 Comprehension에서는 i가 할당이 된 뒤, 바로 필터를 통해 이후의 실행 여부를 결정한다.

그렇기 때문에, 첫번째 Comprehension은 i가 100이 넘어가더라도 j는 1부터 m까지 반복하게 된다. 이와 달리 두번째 Comprehension은 i가 100이 넘어갈 경우 j <- 1..m 구문이 전혀 실행되지 않는다. 그러한 이유로 두 함수간의 시간 차이가 나는 것이다.

위에서 예시로 보여준 함수 호출을 생각해보자. 첫번째 함수의 경우 i <- 1..n와 j <- 1..m이 모두 수행된다. 그렇기에 총 10000 * 10000 = 10^8 번의 반복이 일어나게 된다.
두번째 함수의 경우, i의 값이 100이 넘어가면 j <- 1..m 구문을 수행하지 않는다. 그렇기에 총 100 * 10000 + 9900 ≒ 10^6 번의 반복이 일어난다. 이러한 차이로 인해 두 함수의 수행시간이 차이가 나는 것이다.

결론

여러개의 Generator와 필터를 같이 사용하는 경우, 필터의 위치에 따라 수행 시간에 차이가 날 수 있다. 만약 위의 경우처럼 조건에 따라 특정 Generator를 사용하지 않아도 된다면, 필터의 위치를 앞당겨 Generator가 수행되지 않도록 구현하자.