강의의 unsortedbin 부분을 보면 다음과 같은 설명이 있습니다. "smallbin 크기에 해당하는 청크를 할당 요청하면, ptmalloc은 fastbin 또는 smallbin을 탐색한 뒤 unsortedbin을 탐색합니다."
fastbin 크기가 아닌 청크들이 해제될 때는 smallbin 또는 largebin에 보관하지 않고, 우선 unsortedbin에 보관합니다. (강의 내용)
그렇다면 다시 재할당 요청이 들어온다면, unsortedbin을 먼저 탐색해야 재할당 속도를 높일 수 있는 것 아닌가요? (캐시의 역할처럼)
largebin의 경우에는 재할당 시 unsortedbin을 먼저 탐색하는 이유와 smallbin은 그렇지 않은 이유가 궁금합니다!
음... 근원적인 이유는 할당 방식을 그렇게 하겠다고 미리 정했기 때문이랄까요...?
printf 함수는 왜 출력을 해주나요? 와 같은 질문이 아닐까 싶은데요 ㅎㅎ
왜 보다는 어떻게 에 집중하는게 좋지 않을까 싶습니다
음... 그 부분에 대해서는 저도 잘 모르겠습니다.
다만 추측키로는 말 그대로 그런 방식이 가장 빠르고 효율적이지 않았을까 싶습니다.
대충 glibc를 버전별로 뒤져봤는데
초창기 v.1 이나 v.2.0에서는 빈 자체가 없었던걸 볼 수 있었습니다.
컴퓨터가 발전해온걸 보면 예전에 누군가 개인용 컴퓨터는 몇 메가면 충분하다고 할때야 크게 고민 없이 힙을 대충 할당하고 해제하면 됐겠지만 다루는 크기가 커질수록 효율적으로 관리해야했기 때문이고, 이를 위해서 여러 방법 중 현재 선택된 방법이 가장 빨랐기 때문이지 않을까요?
옙 저도 기대하고 있겠습니다.
(혹은 고수님께서 답변 달아주실지도...ㅎ)
위 댓글의 OSORI님의 조언대로 코드를 찾아봤더니 많은 도움이 되었고, 내용을 공유하려고 합니다. 도움이 될 진 모르겠네요 ㅎㅎ
메모리 할당을 할 때 bin을 찾아보는 순서는 tcache -> fastbin -> smallbin -> unsortedbin -> largebin 입니다.
메모리 해제를 할 때 bin에 들어가는 순서는 tcache -> fastbin -> unsortedbin 입니다.
이해가 되지 않았던 부분은, 해제를 할 때는 smallbin에 넣는 것이 아니라 unsortedbin에 넣는데, 할당을 하려고 할 때는 smallbin을 먼저 찾아본다는 것이었습니다. 넣은 곳을 먼저 보는 것이 빨리 찾는 길이 아닌가? 라고 생각했던 것입니다. 아니면 smallbin을 먼저 찾기 때문에 넣을 때도 smallbin에 먼저 넣는 것이 더 빠르지 않을까? 라고 생각했습니다.
-
smallbin은 chunk의 크기가 정해져 있기 때문에 단 한 번의 시도 만으로 원하는 크기의 chunk에 접근이 가능합니다. 이와 달리 largebin은 chunk의 크기가 정해져 있지 않습니다. (범위로 저장) 따라서 원하는 크기의 chunk를 찾기 위해 더 많은 시간을 소요합니다.
-
unsortedbin에 여러 개의 small chunk들이 있고 특정 크기의 small chunk를 할당하는 경우를 가정합니다. 구체적으로 0x90 3개와 0x100 3개를 예로 들겠습니다. 0x90 크기를 요청한다면, unsortedbin에 있는 0x90 크기의 chunk를 하나 할당해준 후, 나머지 2개의 0x90 chunk는 tcache로 들어갑니다. 또 같은 bin 범위(smallbin)에 해당하는 0x100 크기의 chunk들은 smallbin으로 이동합니다.
-
위처럼 설계한 이유는 지역성을 고려했기 때문입니다. smallbin에 해당하는 크기를 요청했다면, 다음 번에도 smallbin에 해당하는 chunk를 요청할 확률이 높다는 것입니다. 같은 bin을 공유하는 크기 중에서도 정확히 같은 크기의 chunk를 요청할 확률이 높다고 예측하는 것이죠. 2번 과정에서 만약 0x90 크기의 chunk를 단 한 번만 할당한다고 한다면 smallbin을 먼저 찾는 것이 유리하겠습니다. 하지만 이 차이는 단 한 번의 접근 차이밖에 나지 않기 때문에 무시를 해도 좋다고 보는 것 같습니다. 이보다는 unsortedbin에 먼저 저장했을 경우의 장점을 생각해보면, 만약 unsortedbin에 0x90이 3개 있는 상황에서, 0x50을 요청한다면 0x90 하나를 분할해서 할당해준 후 나머지는 unsortedbin에 그대로 두고 2개는 smallbin으로 이동합니다. 이 후의 지역성까지 고려하면서 분할해서 할당했기 때문에 추가 탐색을 하지 않았습니다. 하지만 0x90 3개가 smallbin에 있었다면, chunk를 재활용하지 않고 새로운 공간을 만들어서 할당해줬어야 합니다.
정리를 하면 unsortedbin은 분할 할당이 가능해 smallbin보다 할당 시 제약이 덜하면서도, 할당 시 같은 크기의 chunk를 tcache로 보내면서 같은 크기 영역(bin)의 chunk는 해당 bin으로 보내 지역성까지 챙긴 것입니다. 또한 할당 시 smallbin을 먼저 찾게 함으로써 더 빠른 탐색(확률 상)을 완성시킨 것이죠. 이것이 메모리 해제 시에는 unsortedbin에 우선 집어 넣고, 할당 시에는 smallbin을 먼저 찾는 이유인 것 같습니다.