패딩 낭비는 배치 문제가 아니었다

5편에서 요청 길이가 흩어지면 패딩 낭비가 50% 로 수렴한다고 썼다. 배치를 키울수록 그 안의 최대 길이가 상한에 붙기 때문이다. 해법은 이름만 대고 넘어갔다.

그 숫자에는 말하지 않은 전제가 하나 있었다. 온 순서대로 묶는다는 것이다. 순서를 바꿀 수 있다면 질문 자체가 달라진다.

배치가 아니라 고인 양

배치를 32 로 고정하고, 묶기 전에 몇 개나 모아 두었는지만 바꿔 본다. 길이는 1에서 128 사이 균등분포이고, 모인 것을 길이순으로 정렬한 뒤 앞에서부터 32개씩 자른다.

고인 요청   묶음 수   낭비(정렬)   낭비(도착순)
      32        1       47.4%        47.4%
      64        2       32.2%        48.0%
     128        4       18.7%        46.8%
     256        8       10.4%        46.6%
     512       16        5.5%        47.3%
    1024       32        2.9%        47.6%
    4096      128        0.7%        47.9%

배치는 내내 32 다. 바뀐 것은 그 앞에 몇 개가 고여 있느냐뿐인데, 낭비가 47.4% 에서 0.7% 로 간다.

묶음이 하나면 정렬이 아무것도 못 한다. 32개를 정렬해서 32개짜리 한 묶음을 만들면 순서만 바뀌고 최대 길이는 그대로다. 묶음이 둘이 되는 순간 긴 것끼리 짧은 것끼리 갈라지기 시작하고, 묶음이 128개면 각 묶음 안의 길이 폭이 1 언저리로 좁아진다.

도착 순서 쪽은 요청이 아무리 많이 와도 47% 에서 안 움직인다. 무작위로 32개를 뽑으면 그중 최댓값은 항상 상한 근처이고, 몇 개 중에서 뽑았는지는 상관없다.

5편의 50% 는 배치의 성질이 아니라 순서를 안 바꾼다는 선택의 결과였다.

값은 기다림으로 낸다

공짜가 아니다. 4096개를 모으려면 4096개가 올 때까지 기다려야 한다. 먼저 온 요청은 자기와 길이가 비슷한 것들이 도착할 때까지 줄에 서 있고, 그 시간은 그대로 지연이 된다.

5편에서 처리량과 지연을 맞바꾼 것과 같은 거래인데, 손잡이가 다르다. 거기서는 배치를 키워서 지연을 샀고, 여기서는 기다려서 낭비를 산다. 배치는 32 로 고정한 채였다.

낭비를 다 없애도 시간은 절반만 준다

여기서 한 가지를 더 재야 한다. 낭비를 47% 에서 0.7% 로 줄이면 시간도 그만큼 주는가. 아니다.

배치를 32로 두고 캐시 길이만 바꿔 한 걸음을 재면

캐시 길이   시간(us)
      1         723
     16         901
     32         873
     64        1171
    128        1398

1 에서 128 로 가며 675 us 늘었다. 걸음의 48.3% 만 길이에 달려 있고 나머지 51.7% 는 무관하다. 선형층은 캐시가 얼마나 길든 토큰 하나만 통과시키고, 5편의 고정 오버헤드 a 도 그대로다. 패딩이 붙는 곳은 어텐션뿐이다.

그래서 요청 256개를 배치 32로 처리할 때 낭비를 46.4% 에서 10.2% 로 줄여도 예측되는 시간 이득은 1.24 배다. 줄인 것이 걸음의 절반뿐인 부분의 40% 였다.

실측으로 그 1.24 배를 확인하려 했지만 이 노트북에서는 분간이 안 된다. 도착순과 정렬을 번갈아 일곱 쌍 재고 중앙값을 냈더니 배치 32에서 1.36, 범위가 0.87~1.68 이다. 대부분의 배치에서 범위가 1.0 을 걸친다. 처음 한 번은 1.22 배가 나와 예측과 잘 맞았지만 같은 설정을 다시 재니 0.91 배였고, 한 번 맞은 숫자를 결과로 쓸 수는 없다. 낭비 비율은 길이 목록이 정해지면 정확히 재현되므로, 이 편의 표들은 그쪽에 기대고 있다.

남는 것

정렬은 한 번 묶고 나면 끝이다. 실제로는 요청마다 끝나는 시점이 달라서, 짧은 요청이 비운 자리가 긴 요청이 끝날 때까지 남는다. 그 자리에 새 요청을 바로 끼워 넣는 것이 연속 배치이고, 이 실험은 거기까지 가지 않았다.

그리고 여기서 쓴 길이 분포는 1에서 128 사이 균등이다. 실제 요청 길이는 짧은 쪽에 몰려 있고 꼬리가 길다. 그런 분포에서는 도착순의 낭비가 더 커지고 정렬의 이득도 더 커질 것이다 - 재지는 않았다.

그래서

• 50% 는 배치의 성질이 아니었다. 순서를 안 바꾼다는 전제의 결과다
• 배치를 32 로 고정한 채 고인 요청만 32 에서 4096 으로 늘리면 낭비가 47.4% 에서 0.7% 로 간다
• 묶음이 하나면 정렬은 아무것도 못 한다. 갈라 놓을 다른 묶음이 있어야 한다
• 도착 순서는 몇 개가 오든 47% 다. 무작위 32개의 최댓값은 언제나 상한 근처다
• 대가는 기다림이다. 5편은 배치로 지연을 샀고 여기서는 고임으로 낭비를 산다
• 낭비를 다 없애도 시간은 절반만 준다. 걸음의 48.3% 만 길이에 달려 있다