34 그릇과 정렬 — sortlib·sortgen·hashmap·vecgen·spsc

34 그릇과 정렬 — `sortlib`·`sortgen`·`hashmap`·`vecgen`·`spsc`

먼저 알아야 할 것

22장 제네릭 · 비교는 값이 아니라 타입이 들고 온다

20장 할당기와 고정 메모리 · 할당기를 using 으로 건넨다

32장 표준 라이브러리의 지도 · 버퍼는 호출자의 것

돌아보기

22장에서 C 의 qsort 는 비교 함수를 값으로 받는데 Lowent 의 sortgen 은 무엇으로 받는다고 했는가?

답. 비교를 타입이 들고 온다. 정렬할 타입이 ordered 트레이트를 갖추고 less 를 붙이면, sort_by 는 그 타입 전용으로 단형화되어 비교가 직접 호출로 박힌다. 이 장은 그 정렬과 함께 표준 라이브러리의 그릇들을 둘러본다.

이 장의 필요성과 맥락

정렬·탐색·해시맵·자라는 배열은 거의 모든 프로그램에 들어간다. 다른 언어에서 이런 그릇은 대개 몰래 힙에서 할당하고, 가득 차면 조용히 자란다. Lowent 의 그릇은 두 갈래다. 호출자가 뒷받침 슬라이스를 건네는 고정 그릇(hashmap·sortlib)과, 할당기를 using 으로 받아 스스로 자라는 제네릭 그릇(vecgen·mapgen)이다. 어느 쪽이든 메모리가 어디서 오는지가 머리에 보인다.

이 장이 끝나면

sortlib.sort 와 searchlib.bsearch 로 u64 슬라이스를 정렬·탐색하고, sortgen.sort_by 로 구조체를 타입이 정한 기준으로 정렬하는 법을 익힌다. hashmap 이 호출자의 슬라이스 위에서 동작하는 방식(빈칸·묘비)을 알게 된다. vecgen 이 할당기를 받아 자라는 모습과 그 효과가 할당기 타입에 따라 달라지는 것을 확인한다. 락 없이 흐름 사이로 값을 넘기는 spsc 와 그 밖의 그릇의 자리도 보게 된다.

이 장에서 답할 질문

less a a 가 참이면 어떻게 되는가?

34.1 `u64` 를 정렬하고 찾는다#

examples/ch34/sorted.low

module sorted .
rem run: main

use sortlib .
use searchlib .

proc main input al cap allocator . output u8 . effects alloc .
do
  let g option mut slice u8 be alloc_bytes al capacity 40 .
  guard is_some g . else return 255 .
  var xs mut slice u64 be view_array u64 (some_value g) .
  set (index xs 0) 42 .
  set (index xs 1) 7 .
  set (index xs 2) 19 .
  set (index xs 3) 3 .
  set (index xs 4) 25 .
  sortlib.sort xs .
  let at option u64 be searchlib.bsearch xs 19 .
  guard is_some at . else return 254 .
  let missing option u64 be searchlib.bsearch xs 20 .
  guard not (is_some missing) . else return 253 .
  return narrow u8 (add (mul (index xs 0) 10) (some_value at)) .
end

실행 결과

$ lowentc --run main sorted.low
main() = 32

alloc_bytes al capacity 40 으로 40 바이트를 받고 view_array u64 로 u64 다섯 칸의 슬라이스로 본다. 할당은 여기서만 일어난다.
sortlib.sort xs 는 제자리에서 오름차순으로 정렬한다. effects none 이다.
searchlib.bsearch xs 19 는 정렬된 슬라이스에서 19 의 자리를 option 으로 준다. 없으면 none 이다. lower_bound 는 넣을 자리를 준다.

가장 작은 값 3 과 19 의 자리 2 로 32 가 나온다. bsearch 는 입력이 정렬되어 있다고 믿는다. 정렬되지 않은 슬라이스를 주면 틀린 답을 낸다. 그 믿음은 모듈 문서에 적힌 전제다.

34.2 타입이 기준을 들고 온다#

examples/ch34/rows.low

module rows .
rem run: main

use sortgen .

struct score do
  satisfies sortgen.ordered .
  points u64 .
  id u64 .
end

fn score.less input a score . input b score . output bool .
do
  return gt (field a points) (field b points) .
end

proc main input al cap allocator . output u8 . effects alloc .
do
  let g option mut slice u8 be alloc_bytes al capacity 48 .
  guard is_some g . else return 255 .
  var rs mut slice score be view_array score (some_value g) .
  set (index rs 0) (make score do points 70 . id 1 . end) .
  set (index rs 1) (make score do points 95 . id 2 . end) .
  set (index rs 2) (make score do points 80 . id 3 . end) .
  sortgen.sort_by score rs .
  return narrow u8 (add (mul (field (index rs 0) id) 100) (add (mul (field (index rs 1) id) 10) (field (index rs 2) id))) .
end

실행 결과

$ lowentc --run main rows.low
main() = 231

score 는 satisfies sortgen.ordered . 로 순서를 안다고 선언하고, score.less 가 “점수가 높은 것이 앞” 이라는 기준을 준다. sortgen.sort_by score rs 는 그 기준으로 정렬한다. 점수 95·80·70 의 번호가 차례로 2·3·1 이다.

내림차순이나 여러 키로 정렬하고 싶으면 less 를 그렇게 쓰면 된다. 모드 인자를 다는 대신 타입이 뜻을 들고 온다. sort_by 는 삽입정렬이라 안정하고(같은 점수의 차례가 바뀌지 않는다) 거의 정렬된 입력에 빠르다. 큰 배열에는 sort_fast(제네릭 quicksort) 가 있다. u64 같은 스칼라는 트레이트를 갖출 수 없으므로 칸 하나짜리 구조체로 감싼다. 배치는 그대로 8 바이트다.

문. less a a 가 참이면 어떻게 되는가?

답. 정렬이 멈추지 않거나 틀린 차례를 낼 수 있다. less 는 엄격한 약한 순서여야 한다 — 특히 자기 자신보다 앞일 수 없다. le 로 적어야 할 자리를 lt 로, 또는 그 반대로 적는 실수가 여기서 난다. 트레이트는 op 이 있다는 것을 검사하지 그 op 이 수학적 성질을 지키는지까지 검사하지는 않는다. 그 성질은 모듈 문서에 적힌 계약이다.

34.3 호출자의 슬라이스 위의 해시맵#

examples/ch34/table.low

module table .
rem run: main

use hashmap .

proc main input al cap allocator . output u8 . effects alloc .
do
  let g option mut slice u8 be alloc_bytes al capacity 128 .
  guard is_some g . else return 255 .
  var slots mut slice u64 be view_array u64 (some_value g) .
  let a bool be hashmap.put slots 7 700 .
  let b bool be hashmap.put slots 9 900 .
  let c bool be hashmap.put slots 7 777 .
  let v option u64 be hashmap.lookup slots 7 .
  guard is_some v . else return 254 .
  let gone bool be hashmap.del slots 9 .
  let w option u64 be hashmap.lookup slots 9 .
  guard not (is_some w) . else return 253 .
  return narrow u8 (add (mul (div (some_value v) 100) 10) (hashmap.size slots)) .
end

실행 결과

$ lowentc --run main table.low
main() = 78

hashmap 은 u64 → u64 오픈 어드레싱 해시맵이다. 뒷받침은 호출자가 드는 mut slice u64 이고, [키0+1, 값0, 키1+1, 값1, …] 으로 배치된다. size 는 칸 수(len / 2)다. 처음에는 전부 0(빈칸)이어야 하는데, alloc_bytes 가 0 으로 채운 바이트를 주므로 그대로 쓴다.

put slots 7 700 은 넣고, 같은 키로 다시 put 하면 값을 바꾼다. 가득 차면 false 다.
lookup 은 option 을 준다.
del 은 칸을 빈칸으로 되돌리지 않고 묘비로 덮는다. 빈칸으로 되돌리면 그 뒤에 이어진 탐색 사슬이 끊겨 뒤의 키를 못 찾기 때문이다.

이 설계의 대가도 문서에 적혀 있다. 빈칸(0)과 묘비를 표시하려고 가장 큰 키 둘을 쓸 수 없고, 자동으로 자라지 않는다. 바이트열 키는 strmap 이, 자라는 제네릭 해시맵은 mapgen 이 맡는다.

34.4 자라는 제네릭 벡터#

examples/ch34/growing.low

module growing .
rem run: main

use allocs .
use vecgen .

proc main input h cap heap . output u8 . effects heap state .
do
  var hb allocs.heap_bytes be spawn actor allocs.heap_bytes .
  let vo option (vecgen.vec u32 allocs.heap_bytes) using hb be vecgen.open u32 4 .
  guard is_some vo . else return 255 .
  var v vecgen.vec u32 allocs.heap_bytes be some_value vo .
  var i u32 be 0 .
  while lt i 100 . do
    let pushed bool be vecgen.append u32 allocs.heap_bytes v (mul i 2) .
    guard pushed . else return 254 .
    set i (add i 1) .
  end
  let x option u32 be vecgen.at u32 allocs.heap_bytes v 50 .
  guard is_some x . else return 253 .
  return narrow u8 (some_value x) .
end

실행 결과

$ lowentc --run main growing.low
main() = 100

allocs.heap_bytes 를 띄워 할당기로 쓴다. cap heap 을 쥔 main 만 띄울 수 있다(20장).
vecgen.open u32 4 는 원소 타입 u32, 처음 용량 4 인 벡터를 연다. 할당기는 바인딩의 using hb 로 건넨다.
vecgen.append … v x 는 자리가 모자라면 할당기에게 더 청해 자란다. 실패하면 false 다. 벡터는 자기 할당기를 이미 들고 있으므로 append 에는 using 을 적지 않는다. 적으면 E-ALLOC-USING-UNUSED 로 거절된다.
vecgen.at … v 50 은 50 번 원소를 option 으로 준다. 50 × 2 = 100 이다.

vecgen.append 의 효과는 state via a 다. 여기서 a 가 heap_bytes 이므로 이 인스턴스의 효과는 heap state 이고, main 의 머리에도 heap 이 선다. 같은 코드를 빌린 바이트 위의 범프로 열면 state 만 선다. 그릇이 운영체제 없는 기계에서 도는지를 할당기 타입이 정한다.

흔한 오해. 자라는 벡터는 결국 숨은 할당이다

할당은 일어나지만 숨지 않는다. append 의 효과 줄이 할당기의 효과를 그대로 싣고, 부르는 op 의 머리에 heap 이나 alloc 이 선다. 할당기가 모자라면 append 가 false 를 준다 — 메모리 부족이 값이다. 숨은 할당은 머리에 보이지 않고 실패하면 프로그램을 멈추는 할당이다.

34.5 흐름 사이로 값을 넘기는 링 버퍼#

spsc 는 락 없는 단일 생산자·단일 소비자 링 버퍼다. 한 흐름이 넣고 다른 한 흐름이 뺀다. 제어 칸과 뒷받침 칸을 호출자가 건네고, 넣고 빼는 op 은 cap atomic 을 받아 원자 연산으로 커서를 옮긴다(27장). 인터럽트 처리기와 보통 코드가 값을 주고받는 자리(30장)에 쓰인다.

락 없는 자료구조는 드문 차례에서만 틀리기로 악명이 높다. spsc 의 정확성은 약한 메모리 모델에서 이미 증명된 알고리즘의 증명을 빌려 확인했다. 다중 생산자·다중 소비자 큐나 seqlock 은 빌릴 증명이 없어 넣지 않았다(47장).

34.6 그 밖의 그릇#

모듈	한 줄
`strmap`	바이트열 → `u64` 해시맵. 키 바이트도 호출자의 슬라이스에 담는다
`mapgen`	제네릭 해시맵 `table k v`. 스스로 다시 뿌린다
`vecs` · `growvec`	자라는 바이트 벡터. `growvec` 은 `vecgen.vec u8` 의 짧은 이름이다
`nodelist`	고정 크기 침입형(intrusive) 목록
`soa`	구조체 배열을 칸별 배열로 두는 배치의 실험

표 34.1 — 그 밖의 그릇 모듈

34.7 흔한 실수#

반례. 정렬하지 않은 슬라이스를 이진 탐색한다

examples/ch34/mistake_unsorted.low

module mistake_unsorted .
rem run: find42 0

use searchlib .

proc find42 input al cap allocator . output u64 . effects alloc .
do
  let g option mut slice u8 be alloc_bytes al capacity 40 .
  guard is_some g . else return 255 .
  var xs mut slice u64 be view_array u64 (some_value g) .
  set (index xs 0) 42 .
  set (index xs 1) 7 .
  set (index xs 2) 19 .
  set (index xs 3) 3 .
  set (index xs 4) 25 .
  rem ✘ 정렬하지 않고 이진 탐색한다 --- 42 가 있는데 못 찾는다
  let at option u64 be searchlib.bsearch xs 42 .
  guard is_some at . else return 99 .
  return some_value at .
end

실행 결과

$ lowentc --run find42 mistake_unsorted.low 0
find42(0) = 99

42 는 0 번 칸에 있지만 bsearch 는 99(못 찾음)를 낸다. 이진 탐색은 가운데 값과 견주어 절반을 버리는데, 정렬되지 않았으면 버린 절반에 답이 있을 수 있다. 멈추지도 경고하지도 않으므로 가장 찾기 어려운 종류의 결함이다. 운이 좋으면 찾기도 한다(같은 슬라이스에서 19 는 찾는다). 이진 탐색 앞에는 언제나 sortlib.sort 가 있어야 하고, 정렬된 상태를 지키는 코드가 흩어져 있다면 lower_bound 로 넣을 자리를 찾아 정렬을 유지한다.

반례. less 를 ge 처럼 엄격하지 않게 적는다

examples/ch34/mistake_lessge.low

module mistake_lessge .
rem run: order_strict 0
rem run: order_loose 0

use sortgen .

struct strict_score do
  satisfies sortgen.ordered .
  points u64 .
  id u64 .
end

struct loose_score do
  satisfies sortgen.ordered .
  points u64 .
  id u64 .
end

fn strict_score.less input a strict_score . input b strict_score . output bool .
do
  return gt (field a points) (field b points) .
end

rem ✘ "앞" 을 `ge` 로 적었다 --- 같은 점수끼리도 서로 앞이 된다
fn loose_score.less input a loose_score . input b loose_score . output bool .
do
  return ge (field a points) (field b points) .
end

proc order_strict input al cap allocator . output u64 . effects alloc .
do
  let g option mut slice u8 be alloc_bytes al capacity 48 .
  guard is_some g . else return 255 .
  var rs mut slice strict_score be view_array strict_score (some_value g) .
  set (index rs 0) (make strict_score do points 70 . id 1 . end) .
  set (index rs 1) (make strict_score do points 70 . id 2 . end) .
  set (index rs 2) (make strict_score do points 70 . id 3 . end) .
  sortgen.sort_by strict_score rs .
  return add (mul (field (index rs 0) id) 100) (add (mul (field (index rs 1) id) 10) (field (index rs 2) id)) .
end

proc order_loose input al cap allocator . output u64 . effects alloc .
do
  let g option mut slice u8 be alloc_bytes al capacity 48 .
  guard is_some g . else return 255 .
  var rs mut slice loose_score be view_array loose_score (some_value g) .
  set (index rs 0) (make loose_score do points 70 . id 1 . end) .
  set (index rs 1) (make loose_score do points 70 . id 2 . end) .
  set (index rs 2) (make loose_score do points 70 . id 3 . end) .
  sortgen.sort_by loose_score rs .
  return add (mul (field (index rs 0) id) 100) (add (mul (field (index rs 1) id) 10) (field (index rs 2) id)) .
end

실행 결과

$ lowentc --run order_strict mistake_lessge.low 0
order_strict(0) = 123
$ lowentc --run order_loose mistake_lessge.low 0
order_loose(0) = 321

세 점수가 모두 70 이다. gt 로 적은 strict_score 는 넣은 차례 1·2·3 을 지켜 123 을 내고, ge 로 적은 loose_score 는 같은 점수끼리도 “앞” 이라 서로 자리를 바꿔 321 을 낸다. 안정 정렬이 약속한 “같은 것의 차례가 바뀌지 않는다” 가 깨진 것이다. 다른 정렬 알고리즘에서는 멈추지 않거나 틀린 차례를 낼 수도 있다. 트레이트는 less 가 있는지만 검사하므로, “자기 자신보다 앞일 수 없다” 는 성질은 적는 사람이 지킨다.

반례. 이미 할당기를 든 그릇에 using 을 또 적는다

examples/ch34/mistake_usingappend.low

module mistake_usingappend .
rem expect: E-ALLOC-USING-UNUSED

use allocs .
use vecgen .

proc main input h cap heap . output u8 . effects heap state .
do
  var hb allocs.heap_bytes be spawn actor allocs.heap_bytes .
  let vo option (vecgen.vec u32 allocs.heap_bytes) using hb be vecgen.open u32 4 .
  guard is_some vo . else return 255 .
  var v vecgen.vec u32 allocs.heap_bytes be some_value vo .
  var i u32 be 0 .
  while lt i 100 . do
    rem ✘ 벡터가 이미 할당기를 들고 있는데 `using` 을 또 적었다
    let pushed bool using hb be vecgen.append u32 allocs.heap_bytes v (mul i 2) .
    guard pushed . else return 254 .
    set i (add i 1) .
  end
  let x option u32 be vecgen.at u32 allocs.heap_bytes v 50 .
  guard is_some x . else return 253 .
  return narrow u8 (some_value x) .
end

실행 결과

$ lowentc --check mistake_usingappend.low
16:27 E-ALLOC-USING-UNUSED: this binding says which allocator to use, but the call it initialises does not draw from one (no `using` clause on that op). An object that already carries its allocator — like `vecgen.append` on a vector — does not take the caller's choice (RFC-0112 D8(5))

vecgen.open 은 할당기를 받아 벡터 안에 넣어 둔다. 그 뒤의 append 는 벡터가 든 할당기를 쓰므로 바인딩의 using hb 는 아무 뜻이 없다. 뜻 없는 표시는 “이 호출이 hb 에서 깎는다” 는 거짓 정보가 되므로 E-ALLOC-USING-UNUSED 로 거절된다. using 은 할당기를 처음 받는 자리(open)에만 적는다.

흔한 오해. hashmap 에는 어떤 u64 든 키로 넣을 수 있다

examples/ch34/hashmap_topkeys.low

module hashmap_topkeys .
rem run: main

use hashmap .

proc main input al cap allocator . output u8 . effects alloc .
do
  let g option mut slice u8 be alloc_bytes al capacity 160 .
  guard is_some g . else return 255 .
  var slots mut slice u64 be view_array u64 (some_value g) .
  rem 가장 큰 키 둘은 빈칸·묘비 표시에 쓰이므로 넣을 수 없다
  let a bool be hashmap.put slots 18446744073709551615 40 .
  let b bool be hashmap.put slots 18446744073709551614 50 .
  let c bool be hashmap.put slots 18446744073709551613 60 .
  var r u8 be 0 .
  if a . do set r (add r 1) . end
  if b . do set r (add r 2) . end
  if c . do set r (add r 4) . end
  return r .
end

실행 결과

$ lowentc --run main hashmap_topkeys.low
main() = 4

결과 4 는 셋째 put 만 성공했다는 뜻이다. 가장 큰 키 둘(18446744073709551615·18446744073709551614)은 빈칸과 묘비를 표시하는 데 쓰이므로 넣을 수 없고 put 이 false 를 준다. 이 대가는 모듈 문서 첫머리에 적혀 있다. 키가 전 범위를 쓸 수 있으면 키를 구조체에 담아 mapgen 을 쓴다.

34.8 이 장의 문법 한눈에#

모양	뜻	왜 이렇게
`sortlib.sort xs` · `searchlib.bsearch xs k`	`u64` 제자리 정렬 · 정렬된 입력에서 탐색(`option`)	할당하지 않는다 — 탐색은 정렬을 믿는다
`struct score do satisfies sortgen.ordered . … end` + `fn score.less`	타입이 정렬 기준을 들고 온다	모드 인자 대신 타입 — `less` 는 엄격하게
`sortgen.sort_by score rs` · `sort_fast`	안정 삽입정렬 · 큰 배열용 quicksort	고르는 기준이 이름에 있다
`hashmap.put slots k v` · `lookup` · `del`	호출자 슬라이스 위의 `u64 → u64` 맵	가득 차면 `false` — 삭제는 묘비
`let vo … using hb be vecgen.open u32 4 .`	할당기를 받아 자라는 벡터를 연다	`using` 은 처음 받는 자리에만
`vecgen.append u32 allocs.heap_bytes v x`	자라며 넣는다 — 실패하면 `false`	효과가 할당기 타입을 따라간다(`state via a`)
`spsc`	락 없는 단일 생산자·단일 소비자 링 버퍼	원자 연산 — 증명을 빌렸다

표 34.2 — 그릇과 정렬의 모양 — 모양 · 뜻 · 왜 이렇게 생겼나

복습 정리

sortlib·searchlib 는 u64 슬라이스를 제자리에서 정렬·탐색하고, sortgen 은 ordered 를 갖춘 타입이 기준을 들고 온다. hashmap·strmap 은 호출자의 슬라이스 위에서 묘비로 삭제하는 고정 그릇이다. vecgen·mapgen 은 할당기를 using 으로 받아 자라며, 효과가 할당기 타입을 따라간다. spsc 는 원자 연산으로 흐름 사이에 값을 넘기고 그 정확성은 빌린 증명으로 확인했다.

← 이전목차로다음 →