Repeat(s string, count int) string
strings.Repeat("hi", 5)
--> "hihihihihi"Golang 기본 라이브러리 strings의 Repeat 메서드는 넘긴 s 문자열을 count 번 반복하고, 그 문자열을 리턴하는 메서드다. 최적화 전 기존 코드를 먼저 보자.
func Repeat(s string, count int) string {
if count == 0 {
return ""
}
// Since we cannot return an error on overflow,
// we should panic if the repeat will generate
// an overflow.
// See Issue golang.org/issue/16237
if count < 0 {
panic("strings: negative Repeat count")
} else if len(s)*count/count != len(s) {
panic("strings: Repeat count causes overflow")
}
n := len(s) * count
var b Builder
b.Grow(n)
b.WriteString(s)
for b.Len() < n {
if b.Len() <= n/2 {
b.WriteString(b.String())
} else {
b.WriteString(b.String()[:n-b.Len()])
break
}
}
return b.String()
}입력한 문자열 길이 * 반복 횟수 값을 Builder의 Cap을 증가시키는 Grow 메서드 파라미터로 넘긴다. 그 후 입력한 문자열을 1회 채워주고 루프를 시작한다.
s = "abc", count = 10
n = 3 * 10 = 30
Builder.WriteString("abc") // Len(): 3
#1: 3 < 30
if 3 <= 15 {
Builder.WriteString(Builder.String()) // 3 + 3
}
#2: 6 < 30
if 6 <= 15 {
Builder.WriteString(Builder.String()) // 6 + 6
}
#3: 12 < 30
if 12 <= 15 {
Builder.WriteString(Builder.String()) // 12 + 12
}
#4: 24 < 30
if 24 <= 15 {
// noop
} else {
Builder.WriteString(Builder.String()[:n - Len()])
// Builder.WriteString(Builder.String()[:30-24])
// Builder.WriteString(Builder.String()[:6]) // 24 + 6
}
#5: 30 < 30
END중간값보다 작은 경우 거듭해서 더해주며, 중간값보다 커진 경우 else문으로 빠져 마지막 WriteString을 수행하게 된다.
단순히 생각했을 때는 s를 count 번 루프를 돌며 Builder에 더해주고 결과값을 리턴 하나 싶었는데, 최적화를 통해 더 적은 횟수로 결과값을 구할 수 있다.
그러면 해당 코드는 더 최적화할 여지가 없을까?
이번에는 문자열이 매우 긴 경우를 고민해보자. s로 넘어온 문자열 길이가 100,000이고 count가 400이라면?
로직 자체는 사실 문제될 것이 없다. 결과값도 제대로 나올 것이다.
위 로직에선 중간값보다 작은 경우 Builder에 누적된 문자열을 그대로 이어붙이는 방식인데, 위 사례의 중간값의 크기를 구해보자.
100,000 * 400 / 2 = 20,000,000
2천만 바이트로, 가장 마지막 else문에서는 대략 2천만 바이트의 크기 Builder + 나머지 부족한 바이트를 더해주게 된다. 우리는 시선을 조금 돌려 데이터가 어디에 저장되어 있는지 고민해볼 필요가 있다. 로직이 실행되는 동안 Builder는 메모리에 적재되어 있고, 연산할 때 CPU가 메모리로부터 값을 가져와 연산한다.
하지만 CPU가 매번 메모리로부터 값을 가져올까? CPU와 메모리 사이에는 속도 간극을 줄여주는 완충재 역할을 하는 캐시가 존재한다. 캐시의 핵심 개념은 데이터 지역성으로, 미리 쓸만한 데이터를 메모리에서 캐시로 옮겨 시간을 최적화 하는 것이다 (캐시가 훨씬 빠르기 때문에). 예상이 적중하여 필요한 값이 캐시에 존재하는 경우를 Hit 라고 하고, 없는 경우를 Miss라고 한다. 이를 적중시킨다면 메모리로부터 값을 가져오는 것보다 매우 빠른 결과를 낼 수 있다.
캐시에 많은 데이터를 적재한다면 적중률이 높겠지만, 일반적으로 캐시는 비싼 자원이기 때문에 한정된 양을 갖고 있기 때문에 캐시에 어떤 데이터를 적재시킬지가 최적화 대상이다.
위 예시로 돌아와, 이번에는 CPU 캐시까지 고려를 해보자. 약 2천만 바이트의 데이터가 CPU의 캐시에 모두 담길 수 있을까? 만약 모두 담을 수 있다면 메모리에서 값을 가져올 필요 없이 캐시에 누적된 값을 이용해 바로 연산을 할 수 있을 것이다.
모두 담지 못한다면? 루프의 전반부에서 데이터를 캐싱하지만, 루프가 끝날 때 캐시는 후반부에 접근한 데이터로 덮어씌워진 상태가 된다. 그래서 두 번째 루프를 돌 때는 전반부 데이터를 다시 캐싱해야 한다. 캐싱한 데이터에 다시 접근하기도 전에 캐시 블록 전체가 교체되어 버리는 것이다.
(+ 적은 글만 보면, 캐시에 존재하지 않는 경우 바로 메모리에서 원하는 값을 적재하는 것처럼 느껴지겠지만 캐시도 여러 레벨이 존재한다. L1 캐시에 값이 없으면 L2 캐시, L2 캐시에 없으면 L3 캐시... 하지만 다음 레벨로 가야할 수록 속도가 늦어지는 것은 변함없음)
캐시에 2천만 바이트를 적재할 수 있어 해당 예시를 빠르게 처리할 수 있었다고 해보자. 하지만 캐시의 리소스는 한정되어있기 때문에 결국에는 위 그림과 같은 상황이 발생할 것이다.
따라서 우리는 캐시의 크기를 넘지 않을 만큼씩 잘라 루프를 도는 방법을 생각해볼 수 있다. 이 방법은 더욱 많은 루프를 돌겠지만, 메모리(혹은 L2, L3 캐시)에 접근하는 것보다 낫다. 즉, 루프를 도는 횟수는 늘지만, 캐시 히트 비율은 더 높아진다.
이는 데이터 지역성 중 시간 지역성, 한번 참조된 데이터는 잠시 후에 또 참조될 가능성이 높다는 가정을 기반으로 최적화하려는 시도이다.
이번에는 CPU 캐시의 시간 지역성에 대한 최적화가 적용된 strings.Repeat 코드를 보자.
func Repeat(s string, count int) string {
switch count {
case 0:
return ""
case 1:
return s
}
// Since we cannot return an error on overflow,
// we should panic if the repeat will generate an overflow.
// See golang.org/issue/16237.
if count < 0 {
panic("strings: negative Repeat count")
}
if len(s) >= maxInt/count {
panic("strings: Repeat output length overflow")
}
n := len(s) * count
if len(s) == 0 {
return ""
}
const chunkLimit = 8 * 1024
chunkMax := n
if n > chunkLimit {
chunkMax = chunkLimit / len(s) * len(s)
if chunkMax == 0 {
chunkMax = len(s)
}
}
var b Builder
b.Grow(n)
b.WriteString(s)
for b.Len() < n {
chunk := n - b.Len()
if chunk > b.Len() {
chunk = b.Len()
}
if chunk > chunkMax {
chunk = chunkMax
}
b.WriteString(b.String()[:chunk])
}
return b.String()
}
로직의 큰 변화는 없고, 중간에 chunk라는 변수를 추가하여 이어붙일 문자열의 최대 크기가 고정되며, 사용하는 값이 Builder의 맨 앞에서 최대 chunk만큼으로 고정되어 있어 매 루프에서 캐싱된 데이터를 사용(Hit)할 수 있게 된다.
우리가 위에서 말했던 CPU 캐시의 시간 지역성을 고려한 내용이 코드에 그대로 적용되어있다. 그렇다면 성능은 얼마나 차이가 날까?
('chunkLimit = 8 * 1024'는 해당 PR을 제출한 사람이 실용적으로 테스트해보았을 때 가장 성능이 좋았던 값이라고 함)
name old speed new speed delta
RepeatLarge/256/1-16 1.73GB/s ± 1% 1.73GB/s ± 0% ~ (p=0.556 n=5+4)
RepeatLarge/256/16-16 2.02GB/s ± 0% 1.95GB/s ± 8% ~ (p=0.222 n=5+5)
RepeatLarge/512/1-16 2.30GB/s ±13% 2.47GB/s ± 1% ~ (p=0.548 n=5+5)
RepeatLarge/512/16-16 2.38GB/s ±16% 2.77GB/s ± 1% +16.27% (p=0.032 n=5+5)
RepeatLarge/1024/1-16 3.17GB/s ± 1% 3.18GB/s ± 0% ~ (p=0.730 n=4+5)
RepeatLarge/1024/16-16 3.39GB/s ± 2% 3.38GB/s ± 1% ~ (p=0.548 n=5+5)
RepeatLarge/2048/1-16 3.32GB/s ± 2% 3.32GB/s ± 2% ~ (p=1.000 n=5+5)
RepeatLarge/2048/16-16 3.41GB/s ± 4% 3.46GB/s ± 2% ~ (p=0.310 n=5+5)
RepeatLarge/4096/1-16 3.60GB/s ± 4% 3.67GB/s ± 3% ~ (p=0.690 n=5+5)
RepeatLarge/4096/16-16 3.74GB/s ± 3% 3.71GB/s ± 5% ~ (p=0.690 n=5+5)
RepeatLarge/8192/1-16 3.94GB/s ± 4% 4.01GB/s ± 1% ~ (p=0.222 n=5+5)
RepeatLarge/8192/16-16 3.94GB/s ± 6% 4.05GB/s ± 1% ~ (p=0.222 n=5+5)
RepeatLarge/8192/4097-16 4.25GB/s ± 6% 4.32GB/s ± 3% ~ (p=0.690 n=5+5)
RepeatLarge/16384/1-16 4.96GB/s ± 1% 5.02GB/s ± 2% ~ (p=0.421 n=5+5)
RepeatLarge/16384/16-16 4.99GB/s ± 2% 5.07GB/s ± 1% ~ (p=0.421 n=5+5)
RepeatLarge/16384/4097-16 5.15GB/s ± 3% 5.17GB/s ± 1% ~ (p=1.000 n=5+5)
RepeatLarge/32768/1-16 5.44GB/s ± 2% 5.42GB/s ± 1% ~ (p=0.841 n=5+5)
RepeatLarge/32768/16-16 5.46GB/s ± 4% 5.44GB/s ± 1% ~ (p=0.905 n=5+4)
RepeatLarge/32768/4097-16 4.84GB/s ± 2% 4.59GB/s ±12% -5.05% (p=0.032 n=5+5)
RepeatLarge/65536/1-16 5.85GB/s ± 0% 5.84GB/s ± 1% ~ (p=0.690 n=5+5)
RepeatLarge/65536/16-16 5.81GB/s ± 2% 5.84GB/s ± 2% ~ (p=0.421 n=5+5)
RepeatLarge/65536/4097-16 5.38GB/s ± 6% 5.45GB/s ± 1% ~ (p=1.000 n=5+5)
RepeatLarge/131072/1-16 6.20GB/s ± 1% 6.31GB/s ± 1% +1.80% (p=0.008 n=5+5)
RepeatLarge/131072/16-16 6.12GB/s ± 3% 6.25GB/s ± 3% ~ (p=0.095 n=5+5)
RepeatLarge/131072/4097-16 5.95GB/s ± 1% 5.85GB/s ±10% ~ (p=1.000 n=5+5)
RepeatLarge/262144/1-16 6.33GB/s ± 1% 6.56GB/s ± 0% +3.62% (p=0.016 n=5+4)
RepeatLarge/262144/16-16 6.42GB/s ± 0% 6.65GB/s ± 1% +3.58% (p=0.016 n=4+5)
RepeatLarge/262144/4097-16 6.31GB/s ± 1% 6.44GB/s ± 1% +1.94% (p=0.008 n=5+5)
RepeatLarge/524288/1-16 6.23GB/s ± 1% 6.92GB/s ± 3% +11.02% (p=0.008 n=5+5)
RepeatLarge/524288/16-16 6.24GB/s ± 1% 6.97GB/s ± 2% +11.77% (p=0.016 n=4+5)
RepeatLarge/524288/4097-16 6.14GB/s ± 2% 6.73GB/s ± 3% +9.50% (p=0.008 n=5+5)
RepeatLarge/1048576/1-16 5.23GB/s ± 1% 6.53GB/s ± 6% +24.85% (p=0.008 n=5+5)
RepeatLarge/1048576/16-16 5.21GB/s ± 1% 6.56GB/s ± 4% +25.93% (p=0.008 n=5+5)
RepeatLarge/1048576/4097-16 5.22GB/s ± 1% 6.26GB/s ± 2% +20.09% (p=0.008 n=5+5)
RepeatLarge/2097152/1-16 3.95GB/s ± 1% 5.96GB/s ± 1% +51.01% (p=0.008 n=5+5)
RepeatLarge/2097152/16-16 3.94GB/s ± 1% 5.98GB/s ± 2% +51.99% (p=0.008 n=5+5)
RepeatLarge/2097152/4097-16 4.94GB/s ± 1% 5.71GB/s ± 2% +15.63% (p=0.008 n=5+5)
RepeatLarge/4194304/1-16 3.10GB/s ± 1% 5.89GB/s ± 1% +89.90% (p=0.008 n=5+5)
RepeatLarge/4194304/16-16 3.09GB/s ± 1% 5.86GB/s ± 1% +89.89% (p=0.008 n=5+5)
RepeatLarge/4194304/4097-16 3.13GB/s ± 1% 5.89GB/s ± 1% +88.36% (p=0.008 n=5+5)
RepeatLarge/8388608/1-16 3.06GB/s ± 1% 6.31GB/s ±16% +105.84% (p=0.008 n=5+5)
RepeatLarge/8388608/16-16 3.08GB/s ± 1% 6.62GB/s ± 1% +114.66% (p=0.008 n=5+5)
RepeatLarge/8388608/4097-16 3.13GB/s ± 2% 6.87GB/s ± 1% +119.62% (p=0.008 n=5+5)
RepeatLarge/16777216/1-16 3.21GB/s ± 3% 5.88GB/s ± 1% +83.27% (p=0.008 n=5+5)
RepeatLarge/16777216/16-16 3.23GB/s ± 2% 5.84GB/s ± 2% +80.49% (p=0.008 n=5+5)
RepeatLarge/16777216/4097-16 3.30GB/s ± 6% 5.88GB/s ± 2% +78.18% (p=0.008 n=5+5)
RepeatLarge/33554432/1-16 3.71GB/s ± 3% 5.91GB/s ± 2% +59.17% (p=0.008 n=5+5)
RepeatLarge/33554432/16-16 3.67GB/s ± 3% 5.91GB/s ± 2% +61.13% (p=0.008 n=5+5)
RepeatLarge/33554432/4097-16 3.71GB/s ± 1% 5.77GB/s ± 6% +55.51% (p=0.008 n=5+5)
RepeatLarge/67108864/1-16 4.61GB/s ±11% 6.00GB/s ± 5% +30.15% (p=0.008 n=5+5)
RepeatLarge/67108864/16-16 4.62GB/s ± 7% 6.11GB/s ± 2% +32.35% (p=0.008 n=5+5)
RepeatLarge/67108864/4097-16 4.71GB/s ± 2% 6.24GB/s ± 2% +32.60% (p=0.008 n=5+5)
RepeatLarge/134217728/1-16 4.53GB/s ± 8% 6.28GB/s ±11% +38.57% (p=0.008 n=5+5)
RepeatLarge/134217728/16-16 4.78GB/s ± 3% 6.36GB/s ± 3% +33.16% (p=0.008 n=5+5)
RepeatLarge/134217728/4097-16 4.73GB/s ± 6% 6.46GB/s ± 3% +36.63% (p=0.008 n=5+5)
RepeatLarge/268435456/1-16 4.09GB/s ±25% 6.37GB/s ±19% +56.00% (p=0.008 n=5+5)
RepeatLarge/268435456/16-16 4.50GB/s ± 4% 6.86GB/s ± 0% +52.49% (p=0.016 n=5+4)
RepeatLarge/268435456/4097-16 4.73GB/s ± 5% 6.90GB/s ± 0% +45.94% (p=0.008 n=5+5)
RepeatLarge/536870912/1-16 4.38GB/s ±36% 6.52GB/s ± 8% +48.68% (p=0.008 n=5+5)
RepeatLarge/536870912/16-16 4.69GB/s ±12% 6.90GB/s ± 1% +46.97% (p=0.008 n=5+5)
RepeatLarge/536870912/4097-16 4.87GB/s ± 8% 6.98GB/s ± 0% +43.36% (p=0.008 n=5+5)
RepeatLarge/1073741824/1-16 3.87GB/s ±28% 6.96GB/s ± 1% +79.94% (p=0.016 n=5+4)
RepeatLarge/1073741824/16-16 4.79GB/s ± 9% 6.93GB/s ± 0% +44.79% (p=0.008 n=5+5)
RepeatLarge/1073741824/4097-16 4.65GB/s ± 8% 7.02GB/s ± 1% +51.02% (p=0.008 n=5+5)크기가 적은 경우 CPU 캐시에 모두 담을 수 있는 양이기 때문에 성능 차이가 미미하지만, 크기가 커진다면 우리의 예상대로 성능 차이가 커지는 것을 볼 수 있다. 경우에 따라서는 119.62%나 차이가 난다!
최근 웬만한 최적화는 컴파일러가 해준다고 하지만, 여전히 컴퓨터를 이루는 요소들에 대한 지식을 알고 있을 필요가 있다.
참고
go/strings.go at master · golang/go
https://go-review.googlesource.com/c/go/+/419054
https://parksb.github.io/article/29.html
https://woozzang.tistory.com/155
https://wookcode.tistory.com/183
'컴퓨터' 카테고리의 다른 글
| [번역] Anti-Caching: A New Approach to Database Management System Architecture (0) | 2023.08.15 |
|---|---|
| Journaling (0) | 2023.08.13 |
| [Go] 메모리 할당 위치 (0) | 2023.04.11 |
| [번역] An O(1) algorithm for implementing the LFU cache eviction scheme (0) | 2023.03.11 |
| [번역] TIME_WAIT (1) | 2023.03.06 |
