누가 틀렸어! 실제 사례로 본 포함 여부 검사§

인터넷에서 누가 틀렸으면 당연히 뭐라도 해야 한다. 이번에는 StackOverflow의 어떤 사람이, n이 충분히 작으면 맵으로 포함 여부를 검사하는 게 그냥 배열을 순회하는 것보다 느리다고 했다.

그 사람은 현실적인 크기에서는 거의 언제나 값을 해싱하는 비용이 배열을 훑는 비용보다 크다고 주장했다. 그 사람 말로는 값이 백만 개를 넘기 전까지는 전부 현실적인 크기였다.

그런데 왜 문제의 그 댓글에 바로 링크를 걸지 않는지 궁금할 수도 있겠다. 이제는 그 댓글을 찾을 수 없기 때문이다. 기억나는 건, 그 댓글을 보고 꽤 짜증이 나서 "인터넷에서 누가 틀렸어!" 하고 외쳤다는 것뿐이다 (xkcd 386, "Duty Calls").

하지만 확신할 수는 없었다. 그 사람의 주장이 말이 될 수도 있었다. 그러니까 n이 something보다 작을 때는 어쩌면 해싱 비용이 순회하며 비교하는 비용보다 클 수도 있었다. 직감으로는 헛소리 같았지만, 확인해 보지도 않고 헛소리라고 단정할 만큼 오만하지는 않다.

어쨌든, 그 댓글을 찾는 것(그리고 틀린 사람한테 틀렸다고 알려 주는 것!)은 중요하지 않다. 중요한 건 진리다. 이 글에서는 세상에서 가장 위대한 언어(과장 아님)인 Go 프로그래밍 언어로 진리를 탐구한다.

TL;DR§

당연히 이 사람은 틀렸다. 확인해 보니 n>1이면 맵으로 포함 여부를 검사하는 쪽이 슬라이스보다 항상 빠르다. 즉, 어떤 경우에도 맵 대신 슬라이스를 쓰면 안 된다.

<insert fancy graph here>

업데이트: 이어지는 테스트들은 string 타입의 집합을 전제로 한다. 같은 테스트를 int 타입으로 해 보면 n \approx 30까지는 슬라이스가 조금 더 빠르다.

문제§

멤버십 검사(포함 여부 검사)란 자료 구조에 어떤 값이 들어 있는지 아닌지를 묻는 것이다. 이를 구현하는 방법은 많지만, 여기서는 두 가지를 다룬다:

맵§

map[value]bool을 쓰고, 값이 맵에 있는지 확인한다:

func isMapMember(m map[string]bool, key string) bool {
  _, ok := m[key]
  return ok
}

슬라이스§

[]value를 쓰고, 모든 값을 순회하면서 찾는 값이 슬라이스에 있는지 확인한다:

func isSliceMember(s []string, key string) bool {
  for _, entry := range s {
    if key == entry {
      return true
    }
  }
  return false
}

질문§

둘 중 어느 쪽이 더 빠를까?

가설§

내 가설은 슬라이스를 쓰는 쪽이 더 빠르다는 것이다. 나는 내가 틀렸다는 걸 직접 증명해 보는 걸 좋아한다.

예측§

내 가설이 정말 맞다면, 슬라이스를 쓰는 쪽이 맵보다 빠른 n이 있을 것이다. 그러면 그 사람이 옳았다는 뜻이 된다. 그리고 실제로 멤버십 검사는 값이 몇 개 안 되는 집합에서 하는 경우가 많다.

실험§

결과에 영향을 줄 만한 변수가 3 4가지 떠오른다.

1. n: 검사 대상 집합의 크기. 그 사람의 주장은 n이 충분히 작으면 슬라이스가 더 빠르다는 것이다.
2. valSize: 집합에 저장된 각 값의 크기. 자료 구조의 성능은 valSize가 클 때와 작을 때 다를 수도 있다.
3. 항목이 집합에 있는지 없는지. 집합에 없다는 걸 확인하는 데는 맵이 더 빠를 수도 있다. 아니면 슬라이스일 수도 있다. 모를 일이다!
4. 업데이트: 집합에 담긴 값의 타입.

방법론§

위의 변수들을 고려해, 멤버십을 검사하는 두 방법을 벤치마크한다.

• n개의 고유한 항목으로 이루어진 집합에서, 집합에 있는 항목 하나를 무작위로 고른다. 이 항목이 집합에 있다는 걸 확인하는 데 걸리는 시간을 잰다.
• n개의 고유한 항목으로 이루어진 집합에서, 집합에 없는 항목 하나를 무작위로 고른다. 이 항목이 집합에 없다는 걸 확인하는 데 걸리는 시간을 잰다.

첫 단계는 n개의 고유한 항목으로 이루어진 집합을 만드는 것이다. 각 항목은 길이가 valSize인 무작위 문자열이다. 아래 함수는 맵과 슬라이스를 한꺼번에 만들지만, 실제 벤치마크 코드에서는 한 번에 한 종류만 돌릴 수 있도록 맵용과 슬라이스용 두 함수로 나눠 놓았다.

func makeRandomSet(n, valSize int) (map[string]bool, []string) {
  mapset := make(map[string]bool, n)
  sliceset := make([]string, 0, n)

  for len(mapset) != n {
    str := makeRandomString(valSize)
    if _, ok := mapset[str]; !ok {
      mapset[str] = true
      sliceset = append(sliceset, str)
    }
  }
  return mapset, sliceset
}

그다음은 두 갈래로 나뉜다: 집합에 있는 경우와 없는 경우.

멤버십§

집합에서 샘플을 하나 뽑는다:

func sampleInSlice(sliceset []string) {
  randIdx := rand.Intn(len(sliceset))
  return sliceset[randIdx]
}

map에서의 샘플링도 같은 방식이지만, 먼저 맵의 키들을 슬라이스로 뽑아내야 한다. 벤치마크를 위해 이 함수는 실제로는 샘플 하나가 아니라 고유한 샘플 여러 개를 슬라이스로 반환한다. 벤치마크는 그 샘플마다 집합에 있는지 확인하는 데 걸리는 시간을 잰다.

맵을 벤치마크할 때는 이 헬퍼를 쓴다:

func benchMapMembers(b *testing.B, size int, keySize int) {
  m := makeRandomMap(size, keySize)
  samples := sampleFromMap(m, b.N)

  var member string
  var ok bool
  b.ResetTimer()
  for i := 0; i < b.N; i++ {
    member = samples[i]
    ok = isMapMember(m, member)
  }
  _ = ok
}

슬라이스를 벤치마크할 때는 이것을 쓴다:

func benchSliceMembers(b *testing.B, size int, keySize int) {
  s := makeRandomSlice(size, keySize)
  samples := sampleFromSlice(s, b.N)

  var member string
  var ok bool
  b.ResetTimer()
  for i := 0; i < b.N; i++ {
    member = samples[i]
    ok = isSliceMember(s, member)
  }
  _ = ok
}

비멤버십§

집합에 없는 항목을 찾는다:

func sampleNotInMap(mapset map[string]bool, valSize int) (sample string) {
  for {
    str := makeRandomString(valSize)
    if !mapset[str] {
      return str
    }
  }
}

slice에서의 샘플링도 같은 방식이다. 그다음 멤버십 헬퍼와 꽤 비슷한 벤치마크 헬퍼도 만든다.

맵의 경우:

func benchMapNotMembers(b *testing.B, size int, keySize int) {
  m := makeRandomMap(size, keySize)
  samples := sampleNotInMap(m, b.N, keySize)

  var member string
  var ok bool
  b.ResetTimer()
  for i := 0; i < b.N; i++ {
    member = samples[i]
    ok = isMapMember(m, member)
  }
  _ = ok
}

슬라이스의 경우:

func benchSliceMembers(b *testing.B, size int, keySize int) {
  s := makeRandomSlice(size, keySize)
  samples := sampleFromSlice(s, b.N)

  var member string
  var ok bool
  b.ResetTimer()
  for i := 0; i < b.N; i++ {
    member = samples[i]
    ok = isSliceMember(s, member)
  }
  _ = ok
}

맞대결!§

멤버십 헬퍼로 벤치마크를 여러 개 돌린다. n은 (2,3,4,5,6,7,8,9,10, 100, 1000, 10000, 100000, 1000000) 중 하나, valSize는 (10, 100) 중 하나다.

func BenchmarkMap_2key_10bytes(b *testing.B)        { benchMapMembers(b, 2, 10) }
func BenchmarkMap_3key_10bytes(b *testing.B)        { benchMapMembers(b, 3, 10) }
...
func BenchmarkMap_1000000key_100bytes(b *testing.B) { benchMapMembers(b, 1000000, 100) }

func BenchmarkSlice_2key_10bytes(b *testing.B)        { benchSliceMembers(b, 2, 10) }
func BenchmarkSlice_3key_10bytes(b *testing.B)        { benchSliceMembers(b, 3, 10) }
...
func BenchmarkSlice_1000000key_100bytes(b *testing.B) { benchSliceMembers(b, 1000000, 100) }

비멤버십 검사는 준비 비용이 멤버십 검사보다 훨씬 크다. 집합에 없는 무작위 문자열을 따로 만들어야 하기 때문이다. 준비에 시간이 너무 오래 걸려서 이 부분은 몇 가지 값으로만 테스트했다. 집합에 없는 경우도 있는 경우와 같은 경향을 보일 거라고 가정했다. 내가 실제로 측정한 경우들에서도 그런 경향이 보였으니, 이건 받아들일 만한 가정이다.

또, Go는 600초(10분)가 넘게 도는 벤치마크를 강제로 종료한다. 위의 조합들을 돌리는 데 걸린 시간은 600초에 살짝 못 미쳤다(584초).

func BenchmarkMapNot_10key_10bytes(b *testing.B)      { benchMapNotMembers(b, 10, 10) }
func BenchmarkMapNot_1000key_10bytes(b *testing.B)    { benchMapNotMembers(b, 1000, 10) }
func BenchmarkMapNot_1000000key_10bytes(b *testing.B) { benchMapNotMembers(b, 1000000, 10) }

func BenchmarkSliceNot_10key_10bytes(b *testing.B)      { benchSliceNotMembers(b, 10, 10) }
func BenchmarkSliceNot_10000key_10bytes(b *testing.B)   { benchSliceNotMembers(b, 10000, 10) }
func BenchmarkSliceNot_1000000key_10bytes(b *testing.B) { benchSliceNotMembers(b, 1000000, 10) }

결과§

벤치마크를 직접 돌려 볼 수 있는 코드는 github에 있다. 아래는 이 벤치마크를 내 Mac에서 돌린 결과다.

멤버십 결과§

비멤버십 결과§

결과는 분명했다. 내 가설은 틀렸다. n > 1이면, 맵을 쓰는 멤버십 검사가 항상 더 빠르다.

역시 인터넷에서 누가 틀린 게 확실했다!!!!§

업데이트§

위의 내용은 집합에 string을 담는 경우를 전제로 쓴 것이다. 그런데 int 집합에서는 n \approx 30까지 슬라이스가 맵보다 조금 더 빠른 것으로 드러났다.

정수 멤버십§

정수 비멤버십§

인터넷에서 누가 틀린 게 그렇게 확실하지는 않았다!!!!§