누군가 틀렸어! 실제 사례로 본 멤버십 검사§

당연히, 인터넷에서 누군가 틀렸을 때는 뭐라도 해야 한다. 이번 경우에는 StackOverflow의 한 개인이, n이 충분히 작으면 멤버십 검사에 맵을 쓰는 것이 그냥 배열을 순회하는 것보다 느리다고 언급했다.

그 사람의 주장은, 실제로 쓰이는 크기 대부분에서, 값을 해싱하는 비용이 배열에서 조회하는 비용보다 크다는 것이었다. 그 사람의 말에 따르면, 실제로 쓰이는 크기란 값이 백만 개를 넘을 때까지를 뜻했다.

이쯤 되면 왜 내가 문제의 댓글에 바로 링크를 걸지 않는지 궁금할지도 모르겠다. 그 댓글을 더는 찾을 수 없어서다. 기억나는 건 그 댓글이 나를 "인터넷에서 누군가 틀렸다!"라고 외치게 만들 만큼 거슬렸다는 것뿐이다(xkcd 386, "Duty Calls").

하지만 그 사람의 주장이 일리가 있을 수도 있겠다는 의심이 들었다. 그러니까 n이 something보다 작을 때는 어쩌면 해싱 비용이 순회하며 비교하는 비용보다 클 수도 있다는 얘기다. 헛소리라는 직감이 들었지만, 실제로 헛소리인지 검증해 보기도 전에 헛소리라고 단언할 만큼 주제넘지는 않다.

어쨌든, 그 댓글을 찾는 것(그리고 잘못을 저지른 자에게 틀렸다고 말해 주는 것!)은 중요하지 않다. 중요한 것은 진리다. 이 글에서 우리는 모든 언어 중 가장 위대한 언어(과장 아님)인 Go 프로그래밍 언어를 사용해 진리를 탐구한다.

TL;DR§

당연히 이 개인은 틀렸다. n>1에 대해 검증한 결과, 멤버십 검사는 맵이 슬라이스보다 항상 빠르다. 이는 곧, 어떤 경우에도 맵 대신 슬라이스를 쓰지 말아야 한다는 뜻이다.

<여기에 멋진 그래프 삽입>

업데이트: 이어지는 테스트는 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가 커지면, 구조들이 더 작은 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는 600s(10min)보다 오래 실행되는 벤치마크를 강제 종료한다. 위 조합들의 실행 시간은 600s에 조금 못 미친다(584s).

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까지 슬라이스가 맵보다 조금 더 빠르다.

정수 멤버십§

정수 비멤버십§

인터넷에서 누군가 그렇게 분명히 틀린 건 아니었다!!!!§