[질문]list 관련 질문입니다.
글쓴이: oracle_warden / 작성시간: 수, 2004/11/10 - 5:02오후
제가 이번에 좀 알아볼 게 있어서 실험 하나를 했는데요..
우선, list1, list2, list3 이 3개가 있을 때, 각각의 크기가, 100, 1000, 10000이라고 놓고,
이 3개의 리스트를 nested loop로 순서를 바꿔서 돌려보았습니다.
첫번째 실험은, 크기가 가장 작은 LIST를 가장 바깥쪽에 놓고 실행 시킨 것이고, 두번째 실험은 반대로, 크기가 가장 작은 LIST를 가장 바깥쪽에 놓고 실행시킨 것입니다.
참고로, linux환경에서 ,gcc로 컴파일 했습니다.
첫번째 실험
temp1 = list1;
while(temp1!= NULL){
temp2 = list2;
while(temp2 != NULL){
temp3 = list3;
while(temp3 != NULL){
temp3 = temp3->next;
}
temp2 = temp2->next;
}
temp1 = temp1->next;
}두번째 실험
temp1 = list3;
while(temp1!= NULL){
temp2 = list2;
while(temp2 != NULL){
temp3 = list1;
while(temp3 != NULL){
temp3 = temp3->next;
}
temp2 = temp2->next;
}
temp1 = temp1->next;
}그냥 머릿속에 생각하기로는 두 가지가 시간 차이가 거의 없을 것 같았는데, 실제로 돌려보니, 놀랍게도 첫번째 실험은 평균 11초 정도가 걸리고, 두번째 실험은 평균 6초 정도 걸리더군요..
왜 이런 차이가 나는지 모르겠습니다. 고수 분들 가르쳐주세요~~
PS. 제가 짠 소스코드를 첨부해놓겠습니다. 그럼 많은 답변 부탁 드립니다.
File attachments:
| 첨부 | 파일 크기 |
|---|---|
 test.c | 1.49 KB |
Forums:
루프 횟수에서 차이가 나니까요. :) 첫번째 실험temp1
루프 횟수에서 차이가 나니까요. :)
첫번째 실험
temp1 = temp1->next : 10000
temp2 = temp2->next : 10000 * 1000
temp3 = temp3->next : 10000 * 1000 * 100
두번째 실험
temp1 = temp1->next : 100
temp2 = temp2->next : 100 * 1000
temp3 = temp3->next : 100 * 1000 * 10000
루프 횟수는 같은것 같은데요?(100 * 1000 * 10000
루프 횟수는 같은것 같은데요?
(100 * 1000 * 10000 == 10000 * 1000 * 100)
-------
제가 어줍짢게 추측컨데, 페이징 때문이 아닐까요?
list 의 element 가 얼마나 큰지는 잘 모르겠지만,
링크들을 따라갈때, 제일 안쪽 루프가 100 개인것들보다 10000 개
인 것들이 page fault 가 날 확률이 높아보이네요..
그래서... 그런것이.... 아닐... 까...요?
삽질의 대마왕...
[quote="litdream"]루프 횟수는 같은것 같은데요?(1
temp3의 loop횟수는 두개가 같지만 temp1과 temp2의 처리 횟수는 틀립니다...
그리고 페이징도 가능성이 있긴 한데...list가 페이징에 크게 영향을 받을까요? 잘모르겠군요...
------------------------
http://agbird.egloos.com
음
temp3의 loop횟수는 두개가 같지만 temp1과 temp2의 처리 횟수는 틀린 것 은 맞는 거 같은데, 달라 봤자, temp의 loop 횟수에 비해서는 작은 값이잖아요..
그런데 시간이 저렇게 차이가 많이 나는 걸까요? 단순히 루프 횟수로 인해서만 시간 차이가 나는 거 같지는 않은데..
백만개 안에 10개 루프일때와 10개안에 백만개 루프일때를 비교하면바
백만개 안에 10개 루프일때와 10개안에 백만개 루프일때를 비교하면
바깥루프에서 안쪽루프로 갔다 오는 작업이 백만번 발생하느냐 10번발생하느냐의 차이인것 같네요.
그냥 for 0..백만 {for 0..10}으로 비교해도 차이가 확실히 납니다.
잘은 모르겠지만...
정확한 지식을 가지고 말씀드리는 것은 아니지만,
branch prediction과 관계가 있는 것은 아닐까 추측해 봅니다.
첫번째 실험은, 100 짜리 loop를 10000*1000번 한 것이고,
두번째 실험은, 10000 짜리 loop를 100*1000번 한 것입니다.
그래서 첫번째 실험에서는 10000*1000번의 prediction fail이 일어나고,
두번재 실험에서는 100*1000번 prediction fail이 일어나는 것이 아닐까 조심스럼게 추측해 봅니다.
branch prediction이 성공하면, branch에 걸리는 시간은 거의 zero cycle에 가깝고, 실패하면, pipeline을 clear해야 하므로, pipeline의 길이에 비례해서 cycle손해를 보게 됩니다.
조금 다르게 설명해 보면...
1부터 10까지 세는 1*10 짜리 loop와 10*1 짜리 loop를 비교해 봅시다.
전자는 '무궁화꽃이 피었습니다' 놀이를 하듯이
1 2 3 4 5 6 7 8 9 10이라고 재빨리 셀 수 있고,
후자는 하나씩 쉬어 가면서,
1 쉬고 2 쉬고 3 쉬고 4 쉬고 5 쉬고 6 쉬고 7 쉬고 8 쉬고 9 쉬고 10
이라고 세는 셈이죠.
실제로 그런 것인지는 잘 모르겠지만...
그리고, 앞선 분들의 의견에 약간 설명을 덧붙여 보자면...
당연히 가장 안쪽 loop 말고는 looping 방법에 따라 시간의 차이가 있더라도, 이 경우에 대략 계산해 보면, 10%이상 차이가 나는 것을 설명할 수는 없습니다.
그리고, cache 및 cache miss문제라면, 오히려 제일 안쪽 루프가 작은 경우에 cache miss가 훨씬 적거나 (아예 안일어나서) 더 빨라야 합니다. Cache miss가 문제되는 상황이라면, 오히려 첫번째 실험이 더 빨라야 하는데 그런 것도 아니고... 아마도, cache prefetch 때문에 안쪽 loop의 크기가 크더라도 그것이 cache miss를 불러오지는 않을 것입니다.
{ 가 열릴때마다, 새로운 스택을 정의하고, 생성하는데..두번째가 스
{ 가 열릴때마다, 새로운 스택을 정의하고, 생성하는데..
두번째가 스택생성이 더 적어서 그런게 아닐까요?
조금 오래된 주제이긴 하지만...
2패스 컴파일을 하는 _일반적인_ 컴파일러의 경우 루프내에서의 지역변수에 대해서도 크기에 대한 예측이 가능하기 때문에 함수의 entry 포인트에서 한번에 스택할당을 하는걸로 알고있었는데, 그렇지 않나요?
--
이덕희
댓글 달기