몇 주 전에 One Billion Row Challenge를 봤는데, 완전히 넋이 나가 Go로 풀어보기로 했다.

원래 대회는 1월에 열렸으니 나는 좀 늦게 합류한 셈이다. 대회 자체도 Java로 진행됐다. Java 자체에는 별 관심이 없지만, 최적화 Go 코드 에는 한동안 관심이 많았다.

챌린지 자체는 아주 단순하다. 관측소 이름과 기온이 담긴 텍스트 파일을 처리해 관측소별로 최저, 평균, 최고 기온을 출력하면 된다. 더 간단하게 만들기 위한 몇 가지 제약도 있지만, Java 관련 제약은 무시했다.

입력 예시 몇 줄은 다음과 같다:

Hamburg;12.0
Bulawayo;8.9
Palembang;38.8
St. John's;15.2
Cracow;12.6
...

유일한 함정은 입력 파일이 10억 행이라는 점이다. 데이터 양으로 따지면 약 13GB다. 디스크 I/O는 더 이상 병목이 아니라는 걸 이미 확인한 바 있다. 이런 종류의 프로그램에서는 보통 메모리 할당과 파싱이 속도를 떨어뜨린다.

이 글에서는 Go로 작성한 아홉 가지 솔루션을 소개하는데, 뒤로 갈수록 점점 더 빨라진다. 내 머신에서 가장 단순하고 관용적인 첫 번째 솔루션은 1분 45초가 걸리지만, 마지막 솔루션은 3.4초 만에 끝난다. 진행하면서 Go 프로파일러로 어디서 시간이 쓰이는지 확인하는 과정도 보여주겠다.

업데이트: 지인이 내가 만든 커스텀 해시 테이블에 버그가 있다고 알려줬다. 해시 테이블 배열 크기를 100,000으로 잡았는데 이는 2의 거듭제곱이 아닌데도, 해시 인덱스를 구할 때 hash & (len(items)-1)을 사용했다는 것이다. 그 결과 해시 테이블이 필요 이상으로 비어 있었고 충돌도 훨씬 많았다. 코드를 수정했고 수치도 업데이트했다. 실행 시간이 3.9초에서 3.4초로 줄었다.

솔루션 목록은 느린 것부터 빠른 순으로 다음과 같다:

• r1: 단순하고 관용적인 방법
• r2: 포인터 값을 쓰는 map
• r3: 온도를 직접 파싱
• r4: 고정 소수점 정수
• r5: bytes.Cut 제거
• r6: bufio.Scanner 제거
• r7: 커스텀 해시 테이블
• r8: r1 병렬화
• r9: r7 병렬화

모든 솔루션은 표준 라이브러리만 사용하는 이식성 있는 Go 코드로 만들고 싶었다. 어셈블리도, unsafe도, 메모리 맵 파일도 사용하지 않았다. 그리고 3.4초, 즉 초당 3.8GB 처리 속도로도 충분히 만족스러웠다. 비교하자면, 내 머신에서 가장 고도로 최적화된 Java 솔루션은 1초가 채 안 걸린다. 대단하다!

이미 나와 있는 다른 Go 솔루션도 여러 개 있고, 적어도 하나의 훌륭한 정리 글도 있다. 내 솔루션은 일부보다는 빠르지만 가장 빠른 솔루션보다는 약간 느리다. 다만 나는 내 솔루션을 작성하기 전에 다른 어떤 것도 참고하지 않았다. 독립적으로 만들고 싶었다.

수치만 궁금하다면 결과 표로 바로 넘어가면 된다.

베이스라인

먼저 분위기를 잡기 위해 몇 가지 베이스라인 측정값을 살펴보자. 먼저 cat으로 13GB 데이터를 단순히 읽는 데 얼마나 걸리는지 보자:

$ time cat measurements.txt >/dev/null
0m1.052s

이 수치는 다섯 번 중 가장 좋은 기록이며, 파일이 캐시되어 있는 상태를 허용한 것이다. Linux가 13GB 전체를 디스크 캐시에 유지할지는 알 수 없지만, 아마 유지하는 것으로 보인다. 처음 실행했을 때는 6초 가까이 걸렸기 때문이다.

비교를 위해, 파일로 실제로 무언가를 하는 작업은 훨씬 더 느리다. wc는 거의 1분이 걸린다:

$ time wc measurements.txt 
 1000000000  1179173106 13795293380 measurements.txt
0m55.710s

이 문제에 대한 간단한 솔루션이라면 아마 AWK부터 시작할 것이다. 이 솔루션은 출력 정렬이 더 쉬운 Gawk의 asorti 함수를 사용하기 때문에 Gawk를 사용한다. 바이트 단위 문자 처리 모드인 -b 옵션을 사용했는데, 이렇게 하면 조금 더 빠르다:

$ time gawk -b -f 1brc.awk measurements.txt >measurements.out
7m35.567s

아무리 단순한 Go 솔루션이라도 7분보다는 빠를 것 같으니, 여기서 시작해보자.

먼저 순차적, 싱글 코어 버전을 최적화하고(솔루션 1~7), 그 다음 병렬화할 것이다(솔루션 8과 9). 모든 결과는 빠른 SSD와 32GB RAM을 갖춘 linux/amd64 노트북에서 Go 1.21.5로 측정한 것이다.

내 솔루션 대부분과 가장 빠른 솔루션 대부분은 입력이 유효하다고 가정한다. 예를 들어 기온이 소수점 첫째 자리까지 정확히 표기되어 있다는 식이다. 입력이 유효하지 않으면 내 솔루션 중 몇 개는 런타임 패닉을 일으키거나 잘못된 출력을 낼 것이다.

솔루션 1: 단순하고 관용적인 Go

첫 번째 버전은 Go 표준 라이브러리의 도구를 활용한 단순하고 직관적인 코드로 만들고 싶었다. 줄을 읽기 위한 bufio.Scanner, ';' 기준으로 나누기 위한 strings.Cut, 온도 파싱을 위한 strconv.ParseFloat, 그리고 결과를 누적하기 위한 일반적인 Go map을 사용했다.

첫 번째 솔루션은 전체 코드를 싣겠지만(그 이후부터는 핵심 부분만 보여준다):

func r1(inputPath string, output io.Writer) error {
    type stats struct {
        min, max, sum float64
        count         int64
    }

    f, err := os.Open(inputPath)
    if err != nil {
        return err
    }
    defer f.Close()

    stationStats := make(map[string]stats)

    scanner := bufio.NewScanner(f)
    for scanner.Scan() {
        line := scanner.Text()
        station, tempStr, hasSemi := strings.Cut(line, ";")
        if !hasSemi {
            continue
        }

        temp, err := strconv.ParseFloat(tempStr, 64)
        if err != nil {
            return err
        }

        s, ok := stationStats[station]
        if !ok {
            s.min = temp
            s.max = temp
            s.sum = temp
            s.count = 1
        } else {
            s.min = min(s.min, temp)
            s.max = max(s.max, temp)
            s.sum += temp
            s.count++
        }
        stationStats[station] = s
    }

    stations := make([]string, 0, len(stationStats))
    for station := range stationStats {
        stations = append(stations, station)
    }
    sort.Strings(stations)

    fmt.Fprint(output, "{")
    for i, station := range stations {
        if i > 0 {
            fmt.Fprint(output, ", ")
        }
        s := stationStats[station]
        mean := s.sum / float64(s.count)
        fmt.Fprintf(output, "%s=%.1f/%.1f/%.1f", station, s.min, mean, s.max)
    }
    fmt.Fprint(output, "}\n")
    return nil
}

이 기본 솔루션은 10억 행을 처리하는 데 1분 45초가 걸린다. AWK 솔루션의 7분보다는 확실히 개선됐다.

솔루션 2: 포인터 값을 쓰는 map

단어 세기 프로그램을 만들면서 필요 이상으로 해싱을 많이 하고 있다는 걸 알게 됐다. 각 줄마다 문자열을 두 번 해싱하고 있다. 한 번은 map에서 값을 가져올 때, 또 한 번은 map을 업데이트할 때다.

이를 피하기 위해 map[string]*stats(포인터 값) 형태로 만들고, 가리키는 구조체를 업데이트하는 방식을 쓸 수 있다. map[string]stats 형태로 해시 테이블 자체를 업데이트하는 대신 말이다.

다만 먼저 Go 프로파일러로 확인해보고 싶었다. Go 프로그램에 CPU 프로파일링을 추가하는 건 몇 줄이면 충분하다.

$ ./go-1brc -cpuprofile=cpu.prof -revision=1 measurements-10000000.txt >measurements-10000000.out
Processed 131.6MB in 965.888929ms
$ go tool pprof -http=: cpu.prof
...

위 명령으로 축소된 1천만 행짜리 입력 파일에 대해 실행한 솔루션 1의 프로파일은 다음과 같다:

map 연산이 전체 시간의 30%를 차지한다. 할당(assign)이 12.24%, 조회가 17.35%다. 포인터 값을 사용하면 map 할당 시간 대부분을 없앨 수 있을 것이다.

참고로 이 프로파일 이미지는 나머지 시간이 어디에 쓰이는지도 보여준다:

• Scanner.Scan으로 줄을 스캔하는 시간
• strings.Cut으로 ';'을 찾는 시간
• strconv.ParseFloat으로 온도를 파싱하는 시간
• 줄에 대한 문자열을 할당하고 복사하는 Scanner.Text 호출 시간

어쨌든 두 번째 솔루션은 map 연산을 살짝 손본 것이다:

stationStats := make(map[string]*stats)
scanner := bufio.NewScanner(f)
for scanner.Scan() {
    // ...
    s := stationStats[station]
    if s == nil {
        stationStats[station] = &stats{
            min:   temp,
            max:   temp,
            sum:   temp,
            count: 1,
        }
    } else {
        s.min = min(s.min, temp)
        s.max = max(s.max, temp)
        s.sum += temp
        s.count++
    }
}

관측소가 이미 map에 있는 일반적인 경우, 이제 map 연산은 s := stationStats[station] 한 번만 수행하므로 관측소 이름을 해싱하고 해시 테이블에 접근하는 작업을 한 번만 하면 된다. 이미 map에 있다면 — 10억 행에서는 대부분 그럴 것이다 — 기존에 가리키고 있던 구조체를 바로 업데이트한다.

효과가 엄청나진 않지만 그래도 성과는 있다. map에 포인터 값을 사용하니 시간이 1분 45초에서 1분 31초로 줄었다.

솔루션 3: strconv.ParseFloat 제거

세 번째 솔루션에서는 좀 더 본격적으로 들어가, strconv.ParseFloat 대신 커스텀 코드로 온도를 파싱한다. 표준 라이브러리 함수는 우리 입력의 단순한 온도 — 1.2나 34.5 같은 형태의 2~3자리 숫자(앞에 마이너스 부호가 붙는 경우도 있음) — 에는 필요 없는 수많은 엣지 케이스를 처리한다.

또한 strconv.ParseFloat은 string 인자를 받는데, 이제 이를 호출하지 않게 됐으니 Scanner.Text로 문자열을 할당·복사하는 대신 Scanner.Bytes에서 나온 바이트 슬라이스를 그대로 쓸 수 있다.

이제 온도를 이렇게 파싱한다:

negative := false
index := 0
if tempBytes[index] == '-' {
    index++
    negative = true
}
temp := float64(tempBytes[index] - '0') // parse first digit
index++
if tempBytes[index] != '.' {
    temp = temp*10 + float64(tempBytes[index]-'0') // parse optional second digit
    index++
}
index++ // skip '.'
temp += float64(tempBytes[index]-'0') / 10 // parse decimal digit
if negative {
    temp = -temp
}

예쁘진 않지만 그렇다고 로켓 과학도 아니다. 덕분에 시간은 1분 31초에서 1분 이내인 55.8초로 줄었다.

솔루션 4: 고정 소수점 정수

옛날에는 부동소수점 연산이 정수 연산보다 훨씬 느렸다. 요즘은 조금 느린 정도지만, 가능하면 피하는 게 여전히 이득이다.

이 문제에서는 각 온도가 소수점 한 자리이므로, 고정 소수점 정수로 쉽게 표현할 수 있다. 예를 들어 34.5를 정수 345로 나타내는 식이다. 그리고 결과를 출력하기 직전에 다시 float으로 변환하면 된다.

그래서 네 번째 솔루션은 솔루션 3과 거의 동일하지만, stats 구조체 필드가 다음과 같다:

type stats struct {
    min, max, count int32
    sum             int64
}

그리고 결과를 출력할 때 10으로 나눈다:

mean := float64(s.sum) / float64(s.count) / 10
fmt.Fprintf(output, "%s=%.1f/%.1f/%.1f",
    station, float64(s.min)/10, mean, float64(s.max)/10)

최저·최고 기온은 32비트 정수를 사용했다. 최고 기온이 아무리 높아도 섭씨 50도 정도, 즉 500 정도일 것이기 때문이다. int16을 쓸 수도 있지만, 예전 경험상 최신 64비트 CPU에서는 16비트 정수를 다룰 때가 32비트보다 오히려 약간 느리다. 방금 테스트해보니 측정 가능한 차이는 없었지만, 그래도 32비트를 선택했다.

정수를 사용하니 시간이 55.8초에서 51.0초로 줄었다. 작은 성과다.

솔루션 5: bytes.Cut 제거

솔루션 5를 위해 솔루션 4의 프로파일을 다시 찍어봤다:

이제 점점 어려워진다. map 연산이 대부분을 차지하는데, 커스텀 해시 테이블로 옮겨가는 건 좀 까다롭다. bufio.Scanner를 없애는 것도 마찬가지다. 그러니 미루고 먼저 bytes.Cut을 없애보자.

시간을 아낄 간단한 방법을 떠올렸다. 예를 들어 다음 한 줄을 보자:

New Orleans;11.7

관측소 이름 전체를 훑어 ';'을 찾기보다, 끝에서부터 온도를 파싱하면서 ';'을 찾는 편이 더 빠를 것이다. 다소 지저분하지만 다음 코드가 정확히 그렇게 한다:

end := len(line)
tenths := int32(line[end-1] - '0')
ones := int32(line[end-3] - '0') // line[end-2] is '.'
var temp int32
var semicolon int
if line[end-4] == ';' {          // positive N.N temperature
    temp = ones*10 + tenths
    semicolon = end - 4
} else if line[end-4] == '-' {   // negative -N.N temperature
    temp = -(ones*10 + tenths)
    semicolon = end - 5
} else {
    tens := int32(line[end-4] - '0')
    if line[end-5] == ';' {      // positive NN.N temperature
        temp = tens*100 + ones*10 + tenths
        semicolon = end - 5
    } else {                     // negative -NN.N temperature
        temp = -(tens*100 + ones*10 + tenths)
        semicolon = end - 6
    }
}
station := line[:semicolon]

bytes.Cut을 피하니 시간이 51.0초에서 46.0초로 줄었다. 또 한 번의 작은 성과다.

솔루션 6: bufio.Scanner 제거

이제 bufio.Scanner를 없애보려 한다. 생각해보면, 각 줄의 끝을 찾기 위해 스캐너는 개행 문자를 찾으려고 모든 바이트를 훑어야 한다. 그리고 나서 온도를 파싱하고 ';'을 찾기 위해 많은 바이트를 다시 처리한다. 그러니 이 단계들을 합치고 bufio.Scanner를 아예 버려보자.

솔루션 6에서는 파일을 큰 덩어리로 읽기 위해 1MB 버퍼를 할당하고, 덩어리에서 마지막 개행을 찾아 한 줄이 중간에 잘리지 않도록 한 뒤, 각 덩어리를 처리한다. 코드는 다음과 같다:

buf := make([]byte, 1024*1024)
readStart := 0
for {
    n, err := f.Read(buf[readStart:])
    if err != nil && err != io.EOF {
        return err
    }
    if readStart+n == 0 {
        break
    }
    chunk := buf[:readStart+n]

    newline := bytes.LastIndexByte(chunk, '\n')
    if newline < 0 {
        break
    }
    remaining := chunk[newline+1:]
    chunk = chunk[:newline+1]

    for {
        station, after, hasSemi := bytes.Cut(chunk, []byte(";"))
        // ... from here, same temperature processing as r4 ...

bufio.Scanner를 제거하고 직접 스캔하니 시간이 46.0초에서 41.3초로 줄었다. 또 한 번의 작은 성과지만, 감지덕지다.

솔루션 7: 커스텀 해시 테이블

솔루션 7에서는 본격적으로 들어간다. Go의 map 대신 커스텀 해시 테이블을 구현할 것이다. 이렇게 하면 두 가지 이점이 있다:

1. 관측소 이름을 해싱하면서 동시에 ';'을 찾을 수 있어 바이트를 두 번 처리하는 일을 피할 수 있다.
2. 각 키를 바이트 슬라이스로 해시 테이블에 저장할 수 있어, 매 줄마다 키를 string으로 변환하며 할당·복사하는 과정을 없앨 수 있다.

C로 해시 테이블을 구현하는 방법에 대해 쓴 적이 있는데, Go로 만든 “카운터” 해시 테이블도 구현한 적이 있다. 이번 구현은 거기서 가져왔다.

FNV-1a 해시 알고리즘과 선형 탐사를 사용하는 단순한 구현이다. 충돌이 나면 다음 빈 슬롯을 사용한다.

간단하게 하기 위해 해시 버킷을 미리 크게(2의 거듭제곱인 131,072개) 할당해 테이블 크기 조정 로직을 작성하지 않아도 되게 했다. 테이블이 절반 이상 차면 내 코드는 패닉을 일으키도록 했다. 측정해보니 해시 충돌은 약 0.2% 정도 발생한다.

이번에는 코드가 좀 더 많다. 해시 테이블 설정, 해싱 자체, 그리고 테이블 탐사와 삽입 부분이다:

// The hash table structure:
type item struct {
    key  []byte
    stat *stats
}
const numBuckets = 1 << 17        // number of hash buckets (power of 2)
items := make([]item, numBuckets) // hash buckets, linearly probed
size := 0                         // number of active items in items slice

buf := make([]byte, 1024*1024)
readStart := 0
for {
    // ... same chunking as r6 ...

    for {
        const (
            // FNV-1 64-bit constants from hash/fnv.
            offset64 = 14695981039346656037
            prime64  = 1099511628211
        )

        // Hash the station name and look for ';'.
        var station, after []byte
        hash := uint64(offset64)
        i := 0
        for ; i < len(chunk); i++ {
            c := chunk[i]
            if c == ';' {
                station = chunk[:i]
                after = chunk[i+1:]
                break
            }
            hash ^= uint64(c) // FNV-1a is XOR then *
            hash *= prime64
        }
        if i == len(chunk) {
            break
        }

        // ... same temperature parsing as r6 ...

        // Go to correct bucket in hash table.
        hashIndex := int(hash & uint64(numBuckets-1))
        for {
            if items[hashIndex].key == nil {
                // Found empty slot, add new item (copying key).
                key := make([]byte, len(station))
                copy(key, station)
                items[hashIndex] = item{
                    key: key,
                    stat: &stats{
                        min:   temp,
                        max:   temp,
                        sum:   int64(temp),
                        count: 1,
                    },
                }
                size++
                if size > numBuckets/2 {
                    panic("too many items in hash table")
                }
                break
            }
            if bytes.Equal(items[hashIndex].key, station) {
                // Found matching slot, add to existing stats.
                s := items[hashIndex].stat
                s.min = min(s.min, temp)
                s.max = max(s.max, temp)
                s.sum += int64(temp)
                s.count++
                break
            }
            // Slot already holds another key, try next slot (linear probe).
            hashIndex++
            if hashIndex >= numBuckets {
                hashIndex = 0
            }
        }
    }

    readStart = copy(buf, remaining)
}

이 많은 코드에 대한 보상은 크다. 커스텀 해시 테이블 덕분에 시간이 41.3초에서 22.1초로 줄었다.

솔루션 8: 청크를 병렬로 처리하기

솔루션 8에서는 병렬 처리를 추가하고 싶었다. 다만 첫 번째 솔루션의 단순하고 관용적인 코드 — bufio.Scanner와 strconv.ParseFloat를 쓰는 코드 — 로 돌아가 이를 병렬화해보기로 했다. 그러면 최적화와 병렬화 중 어느 쪽이 더 효과적인지 비교할 수 있다. 그리고 솔루션 9에서는 둘 다 적용할 것이다.

이처럼 맵 리듀스 문제는 병렬화하기가 간단하다. 파일을 비슷한 크기의 청크(코어당 하나)로 나누고, 각 청크를 처리할 스레드(Go에서는 고루틴)를 띄운 뒤, 마지막에 결과를 합치면 된다.

개략적인 모습은 다음과 같다:

// Determine non-overlapping parts for file split (each part has offset and size).
parts, err := splitFile(inputPath, maxGoroutines)
if err != nil {
    return err
}

// Start a goroutine to process each part, returning results on a channel.
resultsCh := make(chan map[string]r8Stats)
for _, part := range parts {
    go r8ProcessPart(inputPath, part.offset, part.size, resultsCh)
}

// Wait for the results to come back in and aggregate them.
totals := make(map[string]r8Stats)
for i := 0; i < len(parts); i++ {
    result := <-resultsCh
    for station, s := range result {
        ts, ok := totals[station]
        if !ok {
            totals[station] = r8Stats{
                min:   s.min,
                max:   s.max,
                sum:   s.sum,
                count: s.count,
            }
            continue
        }
        ts.min = min(ts.min, s.min)
        ts.max = max(ts.max, s.max)
        ts.sum += s.sum
        ts.count += s.count
        totals[station] = ts
    }
}

splitFile 함수는 조금 지루하니 여기서는 생략한다. 파일 크기를 보고 원하는 파트 수로 나눈 뒤, 각 파트마다 끝에서 100바이트 앞을 탐색해 마지막 개행을 찾아 각 파트가 완전한 줄로 끝나도록 한다.

r8ProcessPart 함수는 기본적으로 r1 솔루션과 동일하지만, 파트 오프셋으로 seek한 뒤 파트 크기만큼으로 길이를 제한(io.LimitedReader 사용)하는 것부터 시작한다. 처리가 끝나면 자체 stats 맵을 채널로 돌려보낸다:

func r8ProcessPart(inputPath string, fileOffset, fileSize int64,
                   resultsCh chan map[string]r8Stats) {
    file, err := os.Open(inputPath)
    if err != nil {
        panic(err)
    }
    defer file.Close()
    _, err = file.Seek(fileOffset, io.SeekStart)
    if err != nil {
        panic(err)
    }
    f := io.LimitedReader{R: file, N: fileSize}

    stationStats := make(map[string]r8Stats)

    scanner := bufio.NewScanner(&f)
    for scanner.Scan() {
        // ... same processing as r1 ...
    }

    resultsCh <- stationStats
}

입력 파일을 병렬로 처리하니 r1 대비 큰 성과를 얻어 시간이 1분 45초에서 22.6초로 줄었다. 비교하자면 이전의 “최적화된 비병렬” 버전인 솔루션 7은 22.1초가 걸렸다. 따라서 이 경우에는 최적화가 병렬화보다 약간 더 빠르지만, 우연히도 두 결과가 매우 비슷하다.

솔루션 9: 모든 최적화와 병렬화 결합

솔루션 9에서는 마지막 시도로, r1부터 r7까지의 모든 최적화에 r8에서 했던 병렬화를 결합한다.

r8의 splitFile 함수를 그대로 사용했고, 나머지 코드는 r7에서 복사해왔으므로 새로 보여줄 내용은 없다. 결과를 제외하고는 말이다. … 이 최종 버전은 시간을 22.6초에서 3.4초로 줄이며 엄청난 성과를 냈다.

흥미롭게도 이제 모든 실제 처리가 하나의 큰 함수인 r9ProcessPart에 들어가 있어 프로파일 그래프가 더 이상 그다지 도움이 되지 않는다. 지금 모습은 다음과 같다:

보시다시피 시간의 82%가 r9ProcessPart에서 쓰이고, bytes.Equal이 13%, 파일 읽기가 나머지 5%를 차지한다.

더 깊이 프로파일링하려면 그래프 뷰가 제공하는 함수 수준보다 더 깊이 들어가 소스 뷰를 사용해야 한다. 내부 루프는 다음과 같다:

이 리포트는 헷갈린다. 왜 if items[hashIndex].key == nil은 5.01초가 걸렸다고 나오는데 bytes.Equal 호출은 390ms밖에 안 걸렸다고 나오는 걸까? 슬라이스 조회가 함수 호출보다 훨씬 저렴할 텐데 말이다. Go 성능 전문가인데 이를 해석하는 걸 도와줄 수 있다면 정말 감사하겠다!

어쨌든 더 기발한 최적화를 할 수도 있겠지만, 여기서 마무리하기로 했다. 10억 행을 3.4초, 즉 초당 2억 9천만 행 속도로 처리하는 것으로 충분히 만족스러웠다.

결과 표

아래는 동일한 10억 행 입력에 대해 각 솔루션을 실행한 결과(다섯 번 중 최고 기록)를 한곳에 모은 표이며, 가장 빠른 Go* 솔루션과 가장 빠른 Java 솔루션도 함께 실었다.

업데이트 2025년 12월: François Pons가 Go 버전을 만들었는데, 적어도 Go 1.25에서는 AY 버전보다 다소 빠른 것으로 보인다. 특히 sync/atomic을 사용해 map 오버헤드를 최소화하고 “reduce” 단계를 없앤 점이 특징이다.

나는 Alexander Yastrebov의 Go 버전과 비슷한 수준이다. 그의 솔루션도 나와 비슷해 보인다. 파일을 청크로 나누고, 커스텀 해시 테이블을 사용하며(FNV 해싱까지 동일하다), 온도를 정수로 파싱한다. 다만 그는 메모리 맵 파일을 사용하는데, 나는 이식성 때문에 배제했던 부분이다. 아마 그래서 그의 솔루션이 조금 더 빠른 것 같다.

Thomas Wuerthinger는 (다른 사람들의 공로를 인정하며) 원래 챌린지에서 가장 빠른 전체 솔루션을 Java로 만들었다. 내 머신에서는 1초 이내에 실행되며, 내 Go 버전보다 거의 4배 빠르다. 병렬 처리와 메모리 맵 파일 외에도, 루프 언롤링, 분기 없는 파싱 코드 등 저수준 트릭을 사용한 것으로 보인다.

Thomas는 더 빠른 Java 가상 머신이자 AOT 컴파일을 제공하는 GraalVM의 창립자이자 주요 기여자 중 한 명인 것으로 보인다. 분명 해당 분야의 전문가다. 훌륭하다, Thomas와 팀!

마무리

이 모든 게 의미가 있을까?

대부분의 일상적인 프로그래밍 작업에서는 단순하고 관용적인 코드부터 시작하는 것이 보통 가장 좋다. 10억 개의 기온에 대한 통계를 계산하는데 한 번만 답이 필요하다면, 1분 45초도 아마 충분할 것이다.

하지만 데이터 처리 파이프라인을 구축한다면, 코드를 4배, 심지어 29배 더 빠르게 만들 수 있다면 사용자 만족도는 물론 컴퓨팅 비용도 크게 절약할 수 있다. 시스템이 충분히 부하가 걸려 있다면 컴퓨팅 비용이 원래의 1/4 혹은 1/29로 줄어들 수도 있다!

혹은 GraalVM 같은 런타임을 만들거나, 내가 만든 GoAWK 같은 인터프리터를 만든다면, 이런 수준의 성능은 정말 중요하다. 인터프리터를 빠르게 만들면 모든 사용자의 프로그램이 그만큼 더 빨라지기 때문이다.

게다가, 머신의 성능을 최대한 끌어내는 코드를 작성하는 건 그 자체로 재미있다.