[C] C의 qsort는 어떻게 짰을까? (유명 석박사들의 코드 훔쳐보기), shift 연산을 해야하는 이유

반갑습니다!!!

​

오늘은 저녁에 뭔가 인강듣기는 싫고,, 복습하기도 싫어서

C언어의 소스코드는 어떻게 생겼나 훔쳐봤습니다.

​

여러가지를 보다가 재미있는걸 발견했는데, 공유하기 위해서 저도 씁니다^^

​

c++의 sort는 여러가지 소트를 합친걸로 알고있습니다. Tim,intro, heap,quick 등등.. 여러개를 합쳤는데요.

​

예전에 알고리즘 수업에서 과제 중 하나가, 어떤 숫자에서도(숫자 몇십억개가 넘는) 가장 빠른 정렬을 할 수 있는 코드를 짜는게 숙제였습니다.

그걸로 학생들의 시간을 측정해서 차등으로 성적을 매겨줬습니다.

​

그때 굉장히 많이 찾아봤었는데, 저는 median-of-three라는 pivot 설정으로 quicksort를 짰는데, pivot 고르는걸 잘못했는지.. 어디 하자가 있어서 특정 distribution에서 소트를 하지 못하고 터져버렸습니다.

​

이때 그냥 mergesort 하니까 터지는건 없이 안전했는데.. 뭐 이때 생각도 나서 qsort를 봤습니다.

​

그 당시에 항상 거의 ? 대부분 C의 qsort < 내 코드(특정 분포에서 엄청 강함) <= c++ sort함수 였던것 같습니다.

​

https://code.woboq.org/userspace/glibc/stdlib/qsort.c.html

qsort.c source code [glibc/stdlib/qsort.c] - Woboq Code Browser

 

 

여기서 볼 수 있습니다.

​

qsort의 규칙이 있습니다.

1. recursive 멈춰!!!! 명시적인 stack의 pointer를 이용해서 값을 저장하고, 다음 위치로 이동한다고 합니다.

push,pop 등이 있는데, 사실 이건 아직 잘 모르겠어요. 아니 내가 이거까지 다 했으면 석박했지!! 인정합니다.

​

이 스택으로 partioning을 하는것 같아요.

full size로 담으면, 32bit integer 기준으로 32* sizeof(stack_node) == 256byte가 나옵니다

why? 32 * (포인터2개 8byte) = 2^8 = 256byte입니다. 64bit 면 64 * 포인터2개 16byte 여서 =1024byte인가봅니다.

​

근데 저 32,64가 비트당 말하는건지.. 뭔말인가 잘 이해가 안가네요

아무튼 저것만 쓰고도 퀵소트가 된다고하네요. pretty cheap 이럽니다 ㅋ..

​

​

​

2.

median-of-three 로 pivot을 잡는다고 합니다. 이 방식은 검색을 해보시면 될 것 같아요.

저도 가물가물 하네요.. 아무튼 이건 mid pivot, left pivot 이런것보다 좀 더 확률적으로 좋은 피봇을 잡을 확률이 높다고 했습니다.

수학적으로 증명을 해줬는데, 결과만 외웠습니다. 여기까지..

​

*중요한점. Threshold를 4로 줬습니다. 이게 무슨말이냐?

전체 원소 / Threshold 정도의 개수만 남으면, divide 해서 정렬하는것 보다 insertion sort를 사용합니다.

이게 더 빠르기 때문입니다. (이미 대부분 정렬이 되어있어서요)

​

원소가 32개면 약 8개정도남으면 그렇게 하나봐요.

​

참고로 insertion sort는 O(N^2)이지만, 거의 정렬이 되면 O(N) 수준인거 아시죠? 여기서 쓰네요 오우..

​

​

3. 2개의 sub-partition에서 큰걸 먼저 스택에 넣고, 작은걸 먼저 처리하라고 하네요.

이게 스택 사이즈가 log(total_size)보다 클 필요가 없어서 라는데.. 뭔소린지;;

​

차분하게 앉아서 읽어보고 싶은데.. 시간이 1시 30분이라 일단 자야겠습니다

암튼 ..

​

결론 :

qsort는 진짜 말 그대로

quick sort + insertion sort로 구성되어있다.

recursive를 안쓴다, Threshold를 이용해서 insertion으로 전환한다.

스택을 이용한다.

pivot을 median-of-three를 이용한다.

​

재미있는 부분

아 그리고 여기는 2로 나눌때 >> 1로 하더라고요.

비트연산자로 나누는게 속도가 빠른걸로 알았는데, 컴파일러가 컴파일 할때 / 2라고 해도 shift 연산으로 변환을 합니다.

그래서 컴파일 시간만 줄어들고, 실행속도는 차이 없을거라고 알고 있었습니다.(예전에 수업만 듣고 교수님께 질문하기 전에)

컴파일러의 역할을 coder가 대신해주는거죠.

8은 shift arithmetic left num << 3 하는거 보이죠?

4는 right num >> 2 하는거 보이죠??

​

직접 shift를 해보겠습니다.

​

shift로 하면, 뭔가 레지스터로 옮기는 작업들이 적어지는것 같습니다.

라인수가 꽤나 차이나네요? 실행속도도 빠르겠네요 이러면.. 오 좋은거 배워갑니다 오늘!!

​

​

시스템 수업때 교수님한테 연산들을 비트로 대신 처리해주면 속도가 빨라지나요? 였습니다. (물론 제가 그렇게 생각하는 이유 좀 달아서..)

->

그 당시에 답변이, 컴파일러의 부담을 줄여주는 의미도 있고, 컴파일러보다 개발자가 code optimization을 하는것이 좀 더 좋은방법이라고

받아들여지고 있다고 하셨습니다. 대신 readability를 고려해서 주석을 달아줘야 한다고 하셨습니다.

(교수님 1년이 지나서 확인했습니다 죄송합니다..)

​

​

​

그럼 이만..

이제 잡니다 안녕!!