암보스 (ambos)

두 여자가 서로 다른 방향을 보고 있지만, 그 얼굴 안에서는 마주보기도 하는 듯, 흑심을 품고 있는 듯한 이미지가 프랙탈처럼 나타나 있는 기괴한 표지에 담긴 내용은 대체 어떤 사연일까?

출판사 ‘황금가지’에서 만든 새로운 라인업 ‘수상한 서재’ 시리즈의 첫 작품인 김수안 작가의 암보스를 읽어봤다. 시간이 없어 서울-대구를 오가는 KTX 안에서 읽었는데, 다소 두꺼운 외형과는 달리 꽤나 빨리 따라갈 수 있었다.

암보스 (ambos) 는 스페인어로 ‘양쪽, 두 사람’ 이란 뜻이다. 두 여자가 주인공인 것을 표현하고자 했겠으나, 실제로 스페인어는 남성형/여성형 명사가 따로 존재한다. 그래서 표지만 보고는 왜 암바스 (ambas) 라는 여성형 명사를 채택하지 않았을까 자뭇 궁금해졌다. arm boss 같은 느낌도 있어서

줄거리

이하는 최대한 스포일러를 피해서 나온 (그래서 책 소개내용과 거의 흡사한) 초반 상황 요약이다.

신문 기자 이한나 는 어느 날 방화사건 현장에 있었고, 목격한 모든 정보를 회사에 전달한 뒤 의식을 잃었다. 이대로 죽는건가… 아니, 죽는 것도 나쁘지 않겠지. 무능하고 철면피인 아버지가 진 빚이며, 헤어진 남자친구며, 내가 잘못 굴린 펜으로 사람이 곤란에 겪었으니까.

깨어나보니, 이한나는 다른 사람이 되어 있었다. 같은 날 옥상에서 뛰어내렸지만 가까스로 목숨을 건졌던 강유진이란 사람으로. 이한나는 퇴원하자 마자 강유진의 집을 찾아갔는데, 별안간 이한나의 모습을 한 누군가가 뒤따라 찾아왔다. 그는 강유진 이었다.

몸이 뒤바뀐 것이다. 어떻게 된 일일까.

초자연은 중요한 게 아니다

하지만 책은 왜 이들의 몸이 바뀌었는지는 독자들에게 이야기해주지 않는다. 누군가가 상대방의 몸을 원했다면, 영화 ‘더 게임’ 의 강회장 (변희봉 扮) 같은 캐릭터가 나와야 하겠지만, 여기선 어느 누구도 그런 역을 자처하지 않는다. 그보다는, 서로의 삶에서 느끼는 ‘잃은 것과 얻은 것의 의미’를 알아가고 행동하는 데에 많은 부분을 할애한다. 강유진은 비만에 집에 틀어박혀 지내기 일쑤지만 돈이 많았고, 이한나는 예쁜데다 활기차고 자기주관이 강했지만 안하무인 아버지로 인해 많은 빚을 졌다.

설마 강유진의 모습을 한 이한나가 ‘나는 열심히 운동해서 살을 빼야지’ 라거나 ‘이제부터 사람들과 잘 어울려야지’ 같은 뭐 이런 희망적인 스토리를 기대하지는 말자. 그들은 언젠가 다시 본래의 상태로 돌아갈 것이라고 확신하고 있었다. 정확히 말하자면 강유진이 그렇게 될 것이라고 이야기했지만. 아무튼 그렇게 돌아가버린다고 가정했을 때 이들은 어떤 행동을 취할까. 상대방의 미스터리한 행적이 서로의 시선을 통해 서술되는 그 순간.

갑자기 교차하는 사건

연쇄살인사건, 그리고 그 범인을 찾는 형사가 교차되어 나타난다. 일면 관련없어 보이는 사건 이야기가 갑자기 주인공 일행과 교차점을 지나면서 충돌하기 시작한다. 그것도 아주 빠르게. 파열음은 의외로 강하고, 당사자들의 추리 게임은 꼬리에 꼬리를 문다.

형사 측 인물에서 가장 눈에 띄는 것은 단연 박선호 형사일 것이다. 우락부락한 체격과 어울리지 않게 집요하리만치 파고드는 집중력이 소설 내내 돋보인다. 그 옆의 부사수 칠범 역시 파트너로서의 역할에 충실한다. 이한나의 가족과 주변인, 강유진의 증언 등으로 그 사건 이후 사람이 달라졌다는 부분을 끝까지 물고 늘어지는데, 이 부분에서 주인공 일행과의 긴박한 밀당이 계속 이뤄진다. 결국 살인사건은 실마리를 찾고 해결되지만… 이게 정말 끝일까?

이야기 하는 방식

소설이 가지는 강점은 심리 묘사와 비유에 많은 에너지를 쏟았고 그걸 고스란히 전달하려고 노력했단 점이다. 사건의 진위가 아니라, 사건에 휘말린 인물의 세세한 면면을 나타내려고 애를 썼다. 그래서 스토리 자체에 태클을 걸면서 본다면 자칫 넘어지기 쉬울 것 같아 보이긴 하지만, 그런 세세한 부분을 너그러이 이해해준다면 재밌게 읽힐 소설이지 않을까.

작중 이한나의 시점, 박선호 (를 포함한 외부)의 시점에서는 이한나와 강유진을 지칭하는 자아가 서로 다른 것이 신선했다. 이한나의 시점에서 서술될 때는 ‘나’ 와 ‘(내 모습을 한) 강유진’ 이지만, 그 외에는 외모대로 ‘강유진’ 과 ‘이한나’ 로 서술된다. 박선호가 이를 눈치챈 종반부에서는 서술이 다시 뒤바뀌긴 하지만. 그래서 이 부분을 따라가기가 조금 피곤해 질 수는 있겠다.

마치며

독자에게 추리할 여지를 많이 주는 것 같지만, 사실 복선은 야속하게 정류장을 지나치는 시내버스 같이 지나간다. 어느샌가 소설 속 인물들의 추리보다 한발 앞서 나간게 아닐까, 그랬던 거였어! 라고 생각하고 있다면, 조심해야 한다. 끈적한 손으로 뒤통수를 후려갈겨서 뒷맛이 찜찜하다. 이게 뭐야, 꼭 그렇게 했어야만 했냐! 같은 느낌. 하지만, 역으로 생각해보면 책을 한번 더 돌려보게 만드는 매력을 지니고는 있다고 볼 수 있다.

소설 중에 이런 내용이 있다. 강유진의 모습을 한 이한나가 창문을 바라본다. 창문에는 강유진이 보인다. 내가 정말 나인지, 상대방이 내 모습을 하고 유리창에 나타난건지, 정말로 상대방이 내가 된건지. 나는 누구일까. 사람의 몸이 뒤바뀐다는 초자연적인 전개에만 관심을 가지지 말고, 상대방의 거죽을 쓰고 자신도 몰랐던 민낯을 드러내는 속물같은 추악함도 기대해 보자.

Atomic Operation 으로 하는 동시성 제어

Test-And-Set (TAS)

TAS 를 이용해서 간단한 동시성 제어를 할 수 있다. testAndSet 이라는 function 을 가지고 아래의 do...while 문을 쓰레드 A, B 에서 동시에 호출한다고 해 보자. 이 때 lock 은 같은 변수이다.

function TestAndSet(boolean_ref lock) {
    boolean initial = lock
    lock = true
    return initial
}

do {
    while(TestAndSet(&lock))
        ; // do nothing
    // critical section
    lock = false;
    // remainder section
} while(true);

우선 TestAndSet() 은 다음과 같은 일을 한다. 말 그대로 ‘지금 값이 무엇인지 검사하고, 값을 바꾼다’ 는 것이다.

  1. lock의 현재 값을 저장해 둔다.
  2. lock의 값을 true 로 설정한다.
  3. 저장한 lock 의 값을 반환한다.

그럼 이걸로 어떻게 아래 block 의 critical section 에 대한 동시성 제어를 할 수 있을까? Thread A 가 먼저 실행했다고 가정하면, 이런 시나리오가 된다.

  1. A : TestAndSet() 의 반환값이 false 이다. while 문을 빠져나온다.
  2. B : TestAndSet() 의 반환값이 true 이다. (A가 true로 두고 나왔기 때문에) while 문에서 계속 돈다.
  3. A : Critical Section 수행 후, lock 을 false 로 바꾼다.
  4. B : 여러 번의 TestAndSet() 호출 후에, 드디어 반환값이 false 가 되었다
    (A가 false 로 두고 나왔기 때문에) while 문을 빠져나온다.

자, 그런데 뭔가 이상하다. 이렇게 이상적으로 동작하지 않을 것 같다. TestAndSet() 함수를 라인별로 동시에 실행한다고 하면 이런 사단이 날 수 있다.

  1. A : TestAndSet() 에 진입해 lock 값을 저장한다. 이 값은 false 이다.
  2. B : TestAndSet() 에 진입해 lock 값을 저장한다. 이 값은 false 이다.
  3. A : TestAndSet() 에서 lock 값을 true 로 바꾼다.
  4. B : TestAndSet() 에서 lock 값을 true 로 바꾼다.
  5. A : TestAndSet() 에서 저장한 값을 반환한다. 이 값은 false 이다.
  6. B : TestAndSet() 에서 저장한 값을 반환한다. 이 값은 false 이다.
  7. A & B : 모두 동시에 critical section 을 수행한다.

그럼 어떡하나? TestAndSet() 은 그래서 저런 함수만으로는 안 되고 Test-And-Set 의 연산이 일관되도록 조정해야 한다. 함수 안에 spinlock 을 쓰면 되겠네요? 싶겠지만 lock 구현하자고 lock 을 또 만드는 건 아닌 것 같다. 그래서 Test-And-Set 은 CPU에서 지원하는 Atomic Instruction 을 사용한다.

Fetch-And-Add : Ticket Lock

Atomic Operation 으로 구현할 수 있는 Lock 중에 Ticket Lock 이 있는데, Fetch-And-Add 로 구현할 수 있는 방법을 알아보자.

ticketLock_init(int *next_ticket, int *now_serving)
{
    *now_serving = *next_ticket = 0;
}

ticketLock_acquire(int *next_ticket, int *now_serving)
{
    my_ticket = fetch_and_inc(next_ticket);
    while(*now_serving != my_ticket) {}
}

ticketLock_release(int *now_serving)
{
    now_serving++;
}

TAS 의 케이스를 이해하고 본다면 별 다른 설명이 필요 없을 것 같다.

  1. Table Lock 초기화를 한다.
  2. A : Table Lock 을 얻으려 한다. 이미 얻었던 my_ticket (0) 과 now_serving (0) 이 같은 값이므로 곧바로 빠져나온다.
  3. B : Table Lock 을 얻으려 한다. 이미 얻었던 my_ticket (1) 과 now_serving (0) 이 다른 값이므로 while 문에서 대기한다.
  4. C : Table Lock 을 얻으려 한다. 이미 얻었던 my_ticket (2) 과 now_serving (0) 이 다른 값이므로 while 문에서 대기한다.
  5. A : Table Lock 을 해제한다. now_serving (0) 을 증가시켜 now_serving (1) 을 만든다.
  6. B : 비로소 Table Lock 을 얻었다. (C는 여전히 대기 중이다.)

여기서 핵심은 fetch_and_inc 인데, 마찬가지로 얻어오는 루틴과 값을 증가시키는 루틴이 따로 떨어져 있으면 중복된 티켓을 들고 기다리는 쓰레드들이 발생할 수 있다. 따라서 이것도 atomic operation 이 되어야 한다.

Timsort

학부에서 알고리즘 수업을 들으면, 가장 빠른 정렬 알고리즘이 뭐냐는 질문에 쉽게 Quicksort 라고 답할 수 있겠다. 실제로 현업에서도 적용하기 가장 편하기 때문에 많이 차용되는 편이다. 그런데 모든 문제를 쉽게 풀 수 있는 은탄은 세상에 존재하지 않듯, Quicksort 역시 특정 케이스에서는 성능이 낮게 나오는 경우가 있다. 더 심각한(?) 것은, 이 특정 케이스가 현실에서는 꽤나 자주 발생한다는 것이다.

그 케이스란 바로 ‘거의 정렬된 데이터’ 이다. 거의 정렬된 데이터라면 pivoting – partitioning 을 반복할 필요도 없이 Bubble Sort 나, 심지어는 Insertion Sort 를 해도 된다. Bubble Sort 의 경우엔 알고리즘 복잡도가 n이지만 compare 과정에서 조기에 끝날 가능성이 매우 높아 비용이 거의 발생하지 않을 것이고, Insertion Sort 도 비슷한 이유로 빠르게 끝날 것이다. 하지만 모든 정렬 케이스가 거의 정렬된 데이터만 있지 않기 때문에 쓰지 않는 것일 뿐이다.

만약에 데이터 순열이 ‘거의 정렬된 데이터의 N 벌’이라고 하자. 1, 2, 3, …, 10, 2, 3, 4, …, 20 이런 식으로 말이다. (여기서는 2벌) 그림을 그리자면 산이 N 개 생긴 것 처럼 보일 것이다. 이런 경우에는 Bubble Sort 가 큰 힘을 쓰지 못한다. 특정 원소가 산의 제 위치에 찾아가야 하는데, 조기에 끝났던 아까의 경우와는 달리 재수가 없다면 거의 모든 원소 개수와 비교해 봐야 하기 때문이다. 이럴 경우 역시 특효약이 있는데, 산마다 Mergesort 를 하면 쉽다.

오늘 이야기할 Timsort 는 Mergesort 의 변형이라고 보면 된다. 아까 ‘산마다 Mergesort’ 를 한다고 했는데, 어느 지점부터 산으로 봐야할지를 판단하는 알고리즘이 선행된다. 그리고 Mergesort 도 단순히 1개씩 건너뛰는 방법에서 좀 더 나은 방법을 제시한다.

결론부터 말하자면 Timsort 는 무작위 데이터에서 Quicksort 보다 뒤쳐진다. 프로젝트할 때 적용해 본 결과로는 30~50% 정도 느렸다. 하지만 말했다시피, 현실 데이터는 어느 정도 정렬된 데이터의 덩어리를 가지고 있는 경우가 매우 많기 때문에, 그 부분에서는 확실한 성능 차이를 보였다.

자, 이제 한 번 알아보자.

1단계 : Run

데이터 순열에서 이미 정렬이 끝난 부분 데이터들을 Run 이라고 한다. 1, 2, 1, 2, 3, 1, … 같이 주어졌을 때, 1, 2 와 1, 2, 3 을 Run 으로 인식하는 것이다. Timsort 에서는, 데이터 순열을 이런 Run 들로 찾거나 만들어서 확보하는 과정을 거친다. 이게 1단계이다.

Timsort 는 Run 이 너무 짧으면 나중에 의미가 없으므로, 최소 길이를 정해서 Run 을 만들도록 한다. 보통은 길이가 16인 Run 부터 의미있게 쓰길래, 나도 똑같이 16으로 조건을 설정했다.

Run 은 데이터 처음부터 정렬되어 있는 위치까지를 찾는다. 이 길이가 16 미만이라면, 해당 범위는 기억해 두고 다음 Run 을 찾는다. 이렇게 길이가 16 이상의 Run 을 만들 수 있는데, 이 때 쓰는 알고리즘은 사실 아무거나 가져다 써도 된다. 길이가 짧을 때의 정렬 알고리즘은 어느 것을 쓰나 대동소이하기 때문에, 나는 Insertion Sort를 썼다.

2단계 : Merge

1단계 이후로는, 이제 데이터 순열에 Run 여러개가 연속되어 있다. 만약 Run 이 1개뿐이라면? 축하한다. 아주 작은 원소 개수를 정렬하려 했거나, 이미 정렬된 데이터를 넣었단 것이니 이번 단계를 하지 않아도 된다.

앞의 두 Run 을 불러서 Mergesort 하면 되는데, 여기서 Timsort 만의 트릭이 두 개 존재한다.

하나는, Merge 에 참여할 두 Run 의 최소값/최대값을 서로 비교해서, 아예 이긴 구간이나 아예 진 구간을 미리 산정해 두는 것이다. 이 부분은 사실상 Mergesort 과정에서 비교 대상이 될 필요가 없다. 괜한 compare 연산만 낭비하지 말고 처음에 (혹은 나중에) 순순히 들어와주기만 하면 된다. 이 전처리 과정이 끝나면, 남아있는 Run 끼리 Merge 과정을 거친다.

두 번째는, Merge 과정에서 만약 한 쪽이 계속 이기는 상황 (오름차순 정렬이라고 가정했을 때, 한 쪽의 Run 이 계속 작은 원소를 가지고 있을 때) 라면 더 이상의 비교는 무의미하다. 이런 연속 위닝 회수를 정해서, 이후에는 ‘어디까지 이기는지 binary search 로 찾아서 한 번에 그냥 옮기자’ 라는 건너뛰기 모드 (galloping mode) 로 전환된다. 코드를 참조했을 땐, 이 위닝 회수는 3이었다. 스윕승?

건너뛰기 모드 (galloping mode) 에서는, 지고 있던 Run 의 첫 번째 원소가 이기고 있던 Run 의 어느 원소에서 비로소 이기는지를 찾는 것이다. 처음엔 한 칸, 다음엔 두 칸, 그 다음엔 네 칸씩 뛰며 이길 때 까지 찾는다. 그러다가 찾았다면, 직전 구간 사이를 Binary Search 를 통해 최초로 이긴 위치를 찾아내면 된다.

그 다음은? 이기고 있던 Run 의 처음부터 발견된 위치 직전까지를 통째로 memcpy 하면 된다.

마치며

이걸 구현할 때는 급한 나머지 그냥 구현했었는데, (물론 어딘가에선 하고 있겠지만) Mergesort 자체가 병렬 구현이 가능하므로 Timsort 역시 병렬 구현이 가능하리라 본다. Run 을 만드는 작업은 병렬로 할 수 있을까 고민이 되지만, Merge 과정은 작업 큐만으로도 쉽게 그려낼 수 있다.

역시 이것도 만병통치약이 될 수 없다. 상황에 맞춰 적절히 섞어써야 한다. 이런 정렬 알고리즘도 있구나 하며 배웠던 소중한 기회로 여기고 있다.