`Text` with locale

문자열을 좀 더 효율적으로 다루기 위해서는, String뿐만 아니라 Text나 ByteString도 다루어야 한다.
특히 기존의 library들도 Text나 ByteString을 적극적으로 사용하고 있기 때문에,
그 library들을 제대로 활용하기 위해서도 String만 다룰수는 없다.

그런데, 이 Text나 ByteString은 String과는 달리1 문자열을 꼭 UTF8로 다루지 않는다.
ByteString은 문자열을 UTF8로 다루기 위해서는 utf8-string이라는 library를 사용해야 한다.
그리고, Text의 경우에는 내부적으로 UTF8나 UTF16으로 다룰 수는 있는데, 이건 그 program이 작동하는 system의 locale 설정에 따른다.

더 보기 “`Text` with locale”

Compare `sandi` and `byte64-bytestring`

Background

오랜만에 darcs를 사용하려다가 update되었는지 확인해보려고, cabal install darcs --dry-run을 해 보았다.
darcs의 버전은 올라가지 않았지만, 의존성 충돌 문제가 발생했다.
뭐, 해결할 필요성은 느끼지 않았지만, darcs는 어떤 library를 사용하는지 흥미가 생겨서 조금 살펴보았다.
그 중 흥미를 끄는 이름을 가진 library가 sandi였다.

sandi?

기본적으로 sandi는 binary-to-text를 위한 encoding/decoding library다.
그 중에서 바로 눈에 들어온 것이 Codec.Binary.Base64Url이었다.
이전에 AuthHash를 개발하면서 base64-bytestring을 사용해봤기 때문이다.

더 보기 “Compare `sandi` and `byte64-bytestring`”

Unpacking에 관한 추측(Draft)

Unpacking에 관한 추측(Draft)

기본적으로 unpacking은 고려해야 할 방법이다.

이번 simulation에서 만들고 있는 커다란 자료 구조는 크게 두 개로 분리하고 있다.

자주 갱신하는 parameter value와 전혀, 혹은 거의 갱신하지 않는 config value이다.
이 두 가지 value를, 하나의 data 안에 기술하고 있다.

data Something = S
  { config :: SConfig
  , parameterA :: PA
  , ...
  }

data SConfig = SC
  { configA :: CA
  , ...
  }

이 두 가지를 어떻게 다루는가에 따라서 memory 사용 효율과 처리 속도가 바뀔 것이다.

그럼 다시 Boxed와 Unboxed가 무엇인가를 살펴보자.

Boxed data

Boxed data는 기본적으로, 그 data의 상태를 기술하는 word와 그 data의 value를 기술하는 word들로 구성된다.
data의 상태를 기술하는 부분은 word 하나로 구성되어있다고 배웠지만, 진짜로 그런지는 잘 모르겠다.
어쨌거나, 최소한 word 하나는 사용한다고 생각하자.

value를 기술하는 부분은 당연히 그 value의 크기에 따른다.
Int를 정의할 때는 word 하나를 사용한다. 문자열이라면 상당한 크기일 것이고, ByteString이라면, 두세 개의 offset 정보와 payload의 배열만큼을 필요로 한다.

더 보기 “Unpacking에 관한 추측(Draft)”

Haskell 공부 노트의 공개가 이렇게 늦어진 이유

프로그래밍을 하면서 깨달은 점들을 남겨왔지만, 그걸 공개하기까지 오랜 시간이 걸렸다.
그 이유 중 하나가, 남겨놓은 메모들이 거의 다 일본어, 나머지는 영어로 쓰여있기 때문이다.

연구실에서 공유하려고 했다면 모를까, 내가 개인적으로 남긴 메모들을 일본어로 쓴 이유는 몇 가지가 있다.

더 보기 “Haskell 공부 노트의 공개가 이렇게 늦어진 이유”

함수 `length`를 사용할 때 주의할 점

Haskell을 사용하면서 리스트를 사용하지 않는 경우는 거의 없다고 볼 수 있다.
리스트는 다루기 쉽고 강력한 자료 구조이지만, 만능은 아니다.
특히나 함수형 언어는 성능이 떨어진다고 비판을 받고는 하는데, 리스트는 그 구조 때문에 함수형 언어와 관계없이 느리다.
그러므로 성능이 신경 쓰인다면 리스트의 특성을 잘 이해하고서 사용해야 한다.

그 한 가지 예로서, 리스트를 다룰 때 자주 사용하는 함수 중 하나인 length를 살펴보자.

Definition of length

함수 length는 주어진 리스트의 길이를 재는 함수이다.

Haskell의 리스트는 길이 정보를 별도로 저장하지 않는 단순한 구현이다.
그도 그럴 것이 지연 계산법의 특성상, 리스트의 길이가 얼마나 될지는 그 리스트가 주어진 시점에서는 알 수 없기 때문이다.
거기에 무한 리스트도 당연하다시피 다루고 있는데, 리스트의 길이를 미리 파악할 수 없는 이상, 길이 정보가 리스트에 포함되지 않는 것은 당연하다고 볼 수 있다.

하지만 리스트의 길이는 자주 사용할 일이 있으니까 재어 볼 필요는 있고, 그를 위해서 length함수가 존재한다.

그런데 이 length 함수로 길이를 재는 것이 비효율적이거나, 불가능한 경우가 있다.
length 함수의 구현은 매우 단순해서, 앞에서부터 하나하나 세어가는 재귀함수이다.

최신 버전의 length는 다음과 같이 구현되어 있다.

length :: t a -> Int
length = foldl' (\c _ -> c+1) 0

이 구현은 옛 버전에 비해서 일반화되었다1.
초심자가 읽고서 이해하기 힘든 괴기 무쌍한 정의인지라, 좀 더 옛날의 정의를 살펴보자.

length                  :: [a] -> Int
length l                =  len l 0#
  where
    len :: [a] -> Int# -> Int
    len []     a# = I# a#
    len (_:xs) a# = len xs (a# +# 1#)

이건 최적화를 위해 몇 가지 손을 본 구현인데, 이건 copy & paste 해도 동작하지 않는다.2
최적화된 부분을 복원(…)하면 다음과 같다.

length :: [a] -> Int
length l = len l 0
  where
    len []     a = a
    len (_:xs) a = len xs (a + 1)

즉, 리스트의 요소를 하나하나 세어가면서 길이를 재는 것이다.
이것만 보면 당연하고 의심할 바 없는 정의이지만, 이게 문제가 되는 경우가 많다는 것이다.

언제 문제가 될까?

이 length 함수를 손쉽게 사용할 때 일어날 수 있는 잠재적인 문제점들은 매우 많다.
이 글에서는 지연 계산법에 관한 부분은 간단히 언급만 하고, 연산량에 관련된 부분만을 살펴보기로 하자.

Case 1: 지연 계산법 (lazy evaluation)

먼저, 지연 계산법에 관련된 부분이다.

다음과 같은 조건을 살펴보자.

if length [1..] == 1
  then ...
  else ...

이건 당연히 False이지만, 리스트의 길이가 무한하고, length 함수는 그 리스트를 무한히 따라가기 때문에 정지하지 않는다.

이 외에도 계산할 필요가 없어서 error를 발생시킬 필요가 없는데, length 함수를 사용해서 error를 발생시키는 경우가 있다.

사실 이 지연 계산법에 관한 부분을 더 깊게 다루어야 하지만, 상당히 길어지고 length함수만이 관련된 것도 아니기에 다른 글에서 다루도록 하겠다.

Case 2: 연산량 문제 – 길이가 1인지 아닌지만 확인하고 싶은데

length 함수는 if의 조건문 안에서 자주 사용하게 된다.

이를테면 일직선 상에 있는 바위의 위치가 들어있는 리스트를 받으면 그 바위 간의 거리를 돌려주는 함수를 생각해보자.
머리를 잘 쓰면 다음과 같은 구현을 작성하지 않고 훨씬 더 보기 좋게 만들 수 있지만, 초심자가 쓸 것 같이 써봤다.

getDistances list
  | null list = []                                          -- (1)
  | length list == 1 = []                                   -- (2)
  | otherwise = (second - first) : getDistances (tail list) -- (3)
  where
    first = head list
    second = head (tail list)

이 함수의 구현 자체에는 아무런 문제도 없다.
하지만 조건문을 하나하나 자세히 살펴보면 문제가 있다는 것을 알 수 있다.

먼저, (1)은 아무런 문제가 없다.
null 함수는 빈 리스트인지 아닌지를 확인하는 함수로, O(1)의 엄청나게 싼 연산이다.
(2)는 잠시 내버려두고 (3)을 살펴보자.
where 안에서 정의한 것을 몇 개 사용하고 있지만, (3)도 전부 O(1)의 엄청나게 싼 연산이다.

문제는, (2)의 조건문 length list == 1이다.
length 함수는 그 구현을 보면 알겠지만, O(n)이다. (n은 리스트의 길이)
getDistances 함수는 (2)번 조건문에서 length 함수를 n번 불러내기 때문에, 결과적으로 getDistances의 연산량은 O(n^2)가 된다.
간단한 함수가 말도 안 되는 연산량을 가지게 된 것이다.
물론 getDistances의 구현 자체를 바꾸어버리면 되지만, 이번에는 length의 문제를 살펴보는 게 목적이니까 내버려두자.

자, 생각해보면 어떤 리스트의 길이가 1인지 아닌지를 살펴보는 것은 역시 상당히 싼 연산일 것이 분명하다.
그렇다면, 어떤 리스트의 길이가 주어진 길이인지 아닌지만 살펴보는 함수를 만들면 될 것 갈다.

길이를 측정하는 함수 isLength

isLength 함수를 다음과 같이 구현해보았다.

isLength [] 0   = True                       -- (1)
isLength [] _   = False                      -- (2)
isLength _ 0    = False                      -- (3)
isLength list len = isLength (tail list) (len-1) -- (4)

이 함수의 연산량은 O(min(n,len))이다. 위의 getDistances에서 사용하는 경우에는 당연히 O(1)이다.
(3)은 없어도 동작하지만, 매우 긴 리스트가 올 경우를 생각하면 O(n)이 되기 때문에 있어야 한다.

isLength를 사용한 getDistances

getDistances list
  | null list = []                                     -- (1)
  | isLength list 1 = []                               -- (2)
  | otherwise = (second - first) : getDistances (tail list)   -- (3)
  where
    first = head list
    second = head (tail list)

당연하지만, 거의 바뀐 점이 없다.
하지만 length 대신에 isLength를 사용한 것 때문에 연산량은 O(n^2)에서 O(n)으로 획기적으로 줄어들었다.

Conclusion 1

기본적으로 제공되는 함수라고 하더라도 꼭 그 함수가 어떻게 구현되었는지 살펴보자.
Hackage에서 받은 라이브러리라면, 그 구현을 쉽게 찾아볼 수 있다. 하나하나 책갈피도 잘 달려있으니까 소스 코드를 검색할 필요도 없다.

Appendix 1: getDistances의 다른 구현을 생각해보자.

더 나은 구현이 있다고 주장했으니까, 예를 하나 정도 들어야 할 것 같다.
일단 간략한 구현의 예를 들어보자.

Trial 1: use pattern matching

Pattern matching을 사용하면 길이를 잴 필요가 없다.

다음은, getDistances를 pattern matching을 사용해서 그대로 옮겨놓은 구현이다.

getDistances' [] = []
getDistances' (_:[]) = []
getDistances' (x:y:zs) = (y - x) : getDistances' (y:zs)

Trial 2: one more step

getDistances'를 살펴보면 알겠지만, 위에서부터 두 개의 조건은 한 개로 합칠 수 있다.
고쳐 써보면 다음과 같다.

getDistances'' (x:y:zs) = (y - x) : getDistances'' (y:zs)
getDistances'' _ = []

확인해보면 잘 동작한다.

Question 1: 새로운 구현 getDistances''와 length를 개선한 본래의 getDistances, 어느 쪽이 더 성능이 좋을까?

getDistances''의 구현은 간단하고 보기 좋지만(?), 하나 걱정되는 부분이 있다.
문제는 patttern matching의 비용이 얼마나 되는지 잘 모르겠다는 것이다.
특히나 이건 컴파일러와 그 최적화 방법에 따라서 바뀔 수 있는 부분이기에 항상 맞아들어가지는 않는다.

criterion으로 측정해보면, 그렇게 큰 차이는 없지만, pattern matching을 사용하는 getDistances''가 getDistances보다 조금 더 빠르다. 측정 오차 수준은 아니지만, 유의미한 수준이기는 하다. 다만 아주 조금 빠르다.

Appendix 2: 비교 함수를 만들어보자.

isLength는 길이가 딱 얼만큼인가만 확인할 수 있다.
하지만 당연하게도 길이가 더 긴지 짧은지를 확인하고 싶은 경우도 있다.

더 긴지 확인하는 경우와 짧은지를 확인하는 경우의 경계 조건이 미묘하게 다르지만, 그 정도는 모두 알고 있을 테니까 isShorter의 경우만 소개한다.

isShorter _ 0 = False
isShorter [] _ = True
isShorter list n = isShorter (tail list) (n-1)

실제로 사용할때는 주어진 길이가 음수인지를 확인한다든지, 인수를 정격(strict)화 한다든지 몇 가지 간단한 최적화를 할 필요가 있다.

  1. 리스트를 Traversal class의 한가지 data type으로 다루면서 일반화되었다. ↩
  2. 최적화를 위해 MagicHash라는 GHC 확장이 적용되어있다. ↩