PySet을 Go답게

게시 2023/10/03

By 박성진

15 분읽는 시간

PySet을 Go답게

PySet은 매우 유용한 자료구조예요. 이를 Go에서 Go답게 구현하기 위해 CPython의 소스코드와 golang 소스코드를 살펴봤어요. set과 map이 어떻게 작동하는지를 분석하고 가장 합리적인 방법으로 집합을 구현해보려고 해요.

문제

Python에는 집합이라는 유용한 구조가 있어요. set 객체는 주로 두 가지 역할을 해요: 중복 값을 제거하고 빠르게 값을 탐색하는 것이에요.

        
      
n = [1, 3, 3, 5, 6, 3, 8]
n = set(n)
print(n)
# {1, 3, 5, 6, 8}

has_three = (3 in n)
print(has_three)
# True

하지만 Go는 set을 기본적으로 제공하지 않아요. 따라서 Go에서 set과 유사하게 작동하는 객체를 만들어보려고 해요.

CPython의 Set 분석

이제 Python의 구현체인 C코드를 살펴볼게요. 코드는 Github-python에 공개되어 있어요.

        
      
typedef struct {
    PyObject *key;
    Py_hash_t hash;             /* Cached hash code of the key */
} setentry;

typedef struct {
    PyObject_HEAD
    Py_ssize_t fill;            /* Number active and dummy entries*/
    Py_ssize_t used;            /* Number active entries */
    Py_ssize_t mask;
    setentry *table;
    Py_hash_t hash;             /* Only used by frozenset objects */
    Py_ssize_t finger;          /* Search finger for pop() */
    setentry smalltable[PySet_MINSIZE];
    PyObject *weakreflist;      /* List of weak references */
} PySetObject;

핵심은 setentry예요. 이 구조체는 key를 가지고 있고, 주석을 통해 key를 해시한다는 것을 알 수 있어요. 즉, PySet은 Hash Table의 구조를 가지고 있다고 추측할 수 있어요.

/* set object implementation

   Written and maintained by Raymond D. Hettinger <python@rcn.com>
   Derived from Lib/sets.py and Objects/dictobject.c.

   The basic lookup function used by all operations.
   This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.

   ...
*/

이 주석은 set이 dict 객체에서 파생되었다고 설명하고 있어요. 이를 통해 set이 Hash Table 구조를 사용한다는 것을 확신할 수 있죠.

쉽게 말해, PySet은 key만 있는 PyDict예요.

Go Map 분석

Go에서는 map이라는 자료구조를 제공해요. 이 자료구조는 {key:value}로 매핑되는 Hash table이에요. 이를 통해 set을 구현할 수 있을 것 같아요. 그러나 value는 필요하지 않아서 value 자리에 zero-value를 넣어 마치 값이 없는 것처럼 만들 수 있어요.

        
      
// nil
map[T]interface{}{}
map[i] = nil

// struct
map[T]struct{}{}
map[i] = struct{}{}

대표적으로 nil과 빈 struct가 있어요. 따라서 둘 중 어떤 값이 더 효과적일지 판단해야 해요.

interface와 메모리 자원

        
      
import (
  "fmt"
  "unsafe"
)

func main() {
  fmt.Println(unsafe.Sizeof(struct{}{}))  
    // 0

  var nilInterface interface{} = nil
  fmt.Println(unsafe.Sizeof(nilInterface))  
    // 16
}

빈 struct는 메모리를 할당받지 않아요. 즉 메모리에 없는 값이에요. 반면 nil interface는 16Byte를 할당받아요.

그럼 빈 struct를 사용하면 메모리 할당이 적은가? 그렇지는 않아요.

Bucket의 작동원리

이제 map의 구현 방식을 살펴볼게요.

        
      
// Map contains Type fields specific to maps.
type Map struct {
  Key  *Type // Key type
  Elem *Type // Val (elem) type

  Bucket *Type // internal struct type representing a hash bucket
}

Map은 key:value 쌍과 Bucket을 갖고 있어요. 특징적인 점은 Bucket을 가진다는 것이에요. 조금 더 깊게 들어가볼게요.

        
      
// A map is just a hash table. The data is arranged
// into an array of buckets. Each bucket contains up to
// 8 key/elem pairs. The low-order bits of the hash are
// used to select a bucket. Each bucket contains a few
// high-order bits of each hash to distinguish the entries
// within a single bucket.
//
// If more than 8 keys hash to a bucket, we chain on
// extra buckets.
//
// When the hashtable grows, we allocate a new array
// of buckets twice as big. Buckets are incrementally
// copied from the old bucket array to the new bucket array.

// mapextra holds fields that are not present on all maps.
type mapextra struct {
  // If both key and elem do not contain pointers and are inline, then we mark bucket
  // type as containing no pointers. This avoids scanning such maps.
  // However, bmap.overflow is a pointer. In order to keep overflow buckets
  // alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
  // overflow and oldoverflow are only used if key and elem do not contain pointers.
  // overflow contains overflow buckets for hmap.buckets.
  // oldoverflow contains overflow buckets for hmap.oldbuckets.
  // The indirection allows to store a pointer to the slice in hiter.
  overflow    *[]*bmap
  oldoverflow *[]*bmap

  // nextOverflow holds a pointer to a free overflow bucket.
  nextOverflow *bmap
}

앞으로는 key:value 쌍을 entry라고 부를게요. bucket은 최대 8개의 entry를 담고 있어요. 그리고 map은 bucket의 배열로 데이터를 저장해요. 만약 bucket 내의 entry가 유효한 포인터를 가지고 있지 않으면 overflow bucket을 생성해 값을 할당해요. overflow bucket에 할당된 entry는 더 이상 GC(Garbage collector)에 스캔되지 않아요.

빈 struct는 포인터를 가질 수 없어요. 따라서 overflow bucket으로 분류될 거예요. 그러면 GC에 의해 스캔되지 않아요. 하지만 nil interface는 포인터가 될 수 있기 때문에 계속해서 GC에 스캔돼서 속도가 느려져요.

반면, 계속해서 overflow bucket을 생성하면서 지속적인 메모리 할당이 발생한다는 단점이 있어요. 이를 해결하려면 map을 초기화할 때 capacity를 크게 설정하면 돼요. map은 메모리 공간이 부족할 때 두 배씩 늘려가며 메모리를 확보해요. 따라서 처음부터 넉넉하게 메모리를 할당해두면 bucket을 생성하는 빈도가 줄어들어요.

결론

결론적으로 빈 struct를 사용하는 것이 성능(속도와 메모리) 면에서 더 뛰어나요. 만약 map의 capacity까지 넉넉하게 초기화해주면 더욱 좋은 성능을 보일 거예요.

참고: memory-allocation-and-performance-in-golang-maps

Go로 구현

이제 PySet의 주요 아이디어만 빌려와서 GoSet을 만들어볼게요.

        
      
map[T]struct{}

Go에서는 이처럼 map을 통해 간단하게 key만 가지는 map을 구현할 수 있어요.

간단한 코드로 GoSet이 잘 작동하는지 확인해볼까요?

        
      
import (
  "fmt"
)

func main() {
  data := []int{7, 3, 3, 5, 6, 1, 5}
    
  set := make(map[int]struct{})
  // add
  for _, n := range data {
    set[n] = struct{}{}
  }

  // print
  for key := range set {
    fmt.Printf("%d ", key)
  }
  // 3 5 6 1 7 
}

예상대로 값이 출력됐어요. 주의할 점은 이때 map의 key는 순서를 유지하지 않는다는 것이에요. 이 부분은 PySet, PyDict도 동일해요.

type으로 구현

추상화를 통해 set을 일반화시켜볼게요. 다양한 타입의 데이터를 담을 수 있도록 Generic을 사용해 작성했어요.

Generic은 Go v1.18에 처음 추가된 기능이에요. 따라서 Go 버전이 1.17 이하라면 정확히 Key의 데이터 타입을 명시한 후 사용해야 해요.

        
      
// Set 구현
type Set[T comparable] struct {
  table map[T]struct{}
}

// 빈 Set 초기화
func NewSet[T comparable]() *Set[T] {
  emptySet := make(map[T]struct{})
  return &Set[T]{emptySet}
}

// Set에 값 추가
func (s *Set[T]) Add(key T) {
  s.table[key] = struct{}{}
}

// Set에 값이 있는지 확인
func (s *Set[T]) Has(key T) bool {
  _, ok := s.table[key]
  return ok
}

// Set에서 값 삭제
func (s *Set[T]) Pop(key T) bool {
  if s.Has(key) {
    delete(s.table, key)
    return true
  }
  return false
}

// Set에 모든 값 출력
func (s *Set[T]) PrintAll() {
  for key := range s.table {
    fmt.Printf("%d ", key)
  }
  fmt.Print("\n")
}

이제 이 Set을 사용해볼게요.

        
      
package main

import "fmt"

func main() {
  data := []int{3, 5, 5, 6, 7, 7}
  set := NewSet[int]()

  for _, n := range data {
    set.Add(n)
  }
  
  set.PrintAll() // 3 5 6 7 
  fmt.Println(set.Has(5)) // true

  ok := set.Pop(7)
  
  if ok {
    set.PrintAll() // 5 6 3 
  }
}

예상한 대로 잘 작동하는 것을 볼 수 있어요.

GoSet이 slice보다 빠를까?

중복을 제거할 때는 Set이 분명한 장점을 가집니다. 하지만 탐색에서도 정말 빠를까요?

코드의 흐름은 다음과 같아요:

먼저, 총 길이가 9999999인 정수를 각각 slice와 Set에 추가해요.
추가되는 값은 모두 랜덤하게 생성된 최대값이 100인 정수들이에요.
마지막에 slice와 Set에 각각 값을 추가해줘서 탐색 시 slice의 마지막 요소로 위치하도록 해줘요.
그리고 slice와 Set에서 해당 값을 탐색하는 속도를 측정해봐요.

        
      
import (
  "fmt"
  "math/rand"
  "time"
)

func main() {
  
lenData := 9999999
maxRandInt := 100
target := maxRandInt + 1

testSlice(lenData, maxRandInt, target)
testSet(lenData, maxRandInt, target)
}

func testSlice(lenData, maxRandInt, target) {
// Slice 초기화 + 탐색 (최악의 경우)
start := time.Now()

data := make([]int, lenData) // Set과 같은 조건에서 시작

for i := range data { 
data[i] = rand.Intn(maxRandInt)
}

data = append(data, target)

for _, n := range data {
if n == target {
break
}
}

duration := time.Since(start)
fmt.Println("Slice으로 탐색", duration)
}

func testSet(lenData, maxRandInt, target) {
// Set 초기화 + 탐색 
start := time.Now()

set := NewSet[int]()
for i := lenData; i > -1; i-- { 
set.Add(rand.Intn(maxRandInt))
}

set.Add(target)
set.Has(target)

duration := time.Since(start)
fmt.Println("Set으로 탐색", duration)
}

// Slice으로 탐색: 약간의 시간 소모...
// Set으로 탐색: 약간의 시간 소모...

예상대로 Set 탐색이 더 빨랐어요. 하지만 slice의 크기가 작아지면 어떻게 될까요?

lenData를 줄였을 때 실행해봤어요:

        
      
lenData := 약간 줄인 값으로 설정...
// Slice으로 탐색: 매우 빠름!
// Set으로 탐색: 느림...

위 결과로 보아 메모리 초기화 과정에서 map 초기화가 느린 것으로 보입니다.

같은 조건에서 초기화 시간을 제외하고 순수 탐색에 사용한 시간을 측정해 봤어요:

        
      
lenData := 약간 줄인 값으로 설정...
// Slice으로 탐색: 여전히 빠름!
// Set으로 탐색: 매우 빠름!

결론적으로 탐색할 상황이 많다면 Set이 유리하지만 데이터가 충분히 크지 않을 경우에는 slice로 탐색하는 것이 더 효율적일 수 있어요.

Playground

Go Python