[Go] map의 구조

내 경험상, Go로 짠 애플리케이션에서 심각한 성능 부하나 버그를 유발하는 것은 대부분 map의 잘못된 사용에서 나왔다.

뭔가 기본 타입처럼 가볍게 디자인해놔서 생각없이 쓰는 경우가 많은데, map은 그러면 안된다.

심지어 Go에서 메이저한 모듈들도 map을 원시인처럼 써서 무의미한 리소스 병목을 일으키는 경우가 종종 보였다. 특히 logrus라는 로거 모듈이 그랬는데, 필드 할당할때마다 맵을 전체 재할당-리해싱하는 유아기적인 코드를 짜놨더라. 그래서 버렸다.

해시테이블

map은 기본적으로 키-값쌍의 해시테이블이다.
여러개의 버킷을 가지는 리스트로 구현이 된다.

내부 타이핑을 개떡같이 해놔서 이걸로만 알아보기는 어렵다.

그림으로 표현하자면, map은 이런 구조를 가진다.

map 자체는 일단 하나의 배열이다.
키값이 들어오면 그걸 해싱해서 해시값을 배열 인덱스로 삼고, 값을 내부에 저장할 뿐이다.

해시는 당연히 충돌할 수 있으므로 완충장치를 두는데, go의 map에서는 그냥 고정길이 8짜리 배열을 버킷으로 삼아서 심어놓는다. 꽤나 쌈박하고 고전적인 방식이다. 다른 언어들은 bucket에 linked list나 tree를 쓰기도 한다.
그래서 go의 map은 버킷의 평균 길이가 6.5 이상이 되면 미어터지니까 미리 재할당을 시도한다.

growing

map도 내부적으로는 구조가 배열이라고 했다.

그래서 얼마나 쓸지를 모르니, 크기를 미리 지정하지 않을 경우 초기값은 작다. 보통 버킷 1개로 시작하는 것 같더라.
그리고 길이가 가득차면 (평균길이가 6.5 이상이 되면), slice처럼 2배 크기의 새로운 map을 만들고 거기에 값을 옮긴다.

근데 map의 growing은 slice의 growing보다 훨씬 심각하다.
slice는 값을 copy만 하면 되지만, map은 꽤나 무거운 연산인 hash를 잔뜩 때리는 rehashing 과정을 거쳐서 옮겨야 하기 때문이다. 이게 쌓이면 꽤나 무시못할 수준이 된다.

그런 이유에서 이런식으로 map을 무작정 던지고 쌓는 형태는 성능상 좋은 코드가 되기 어렵다.
최소 수백-수천개의 데이터셋을 넣는데 이런식으로 짜면 터져도 할말이 없다.

되도록 위와 같이 cap hint를 줘서 map을 생성하는 것이 좋다. 좀 여유를 줘도 된다.

이러면 300개의 key-value가 들어갈 것이라 추측하고 여유있게 map 공간을 생성하기 때문에, 저 개수보다 많지 않다면 불필요한 growing은 잘 발생하지 않게 된다.

Go map 구현에 대한 코드를 보고 싶다면 아래 링크로 들어가보면 된다.
https://go.dev/src/runtime/map.go

참조
https://go.dev/blog/maps
https://blog.frec.kr/golang/go-hashtable-0/
https://hackernoon.com/some-insights-on-maps-in-golang-rm5v3ywh