테스트한 결과를 추가해봅니다.
arr, i 전역 -> 1100ms
arr 전역 i 메인 -> 1500ms
i 전역 arr 메인 -> 990ms
arr,i 메인 -> 990ms
1806번 - 부분합
로컬 (오토매틱) 변수들은 스택에 있습니다. 힙에는 malloc()이나 new로 생성된 객체들이 들어가죠.
메모리 내의 위치에 따른 속도 차이는 없습니다. 다만 캐시(L1, L2, L3)와 메모리의 차이는 크죠. 제가 보기엔 캐시 적중률 차이로 보입니다. arr, sort 합쳐서 약 800KB 정도 되는데, 채점 머신의 CPU가 뭔지 모르겠지만 일반 가정용 CPU의 경우 저 정도 크기면 L2 캐시에 다 들어가지 않죠. L3 캐시가 있다면 첫번째 루프를 돌면서 다 들어가긴 하겠지만 L3 캐시는 그렇게 빠르지는 않구요.
다만 컴파일러가 어떻게 최적화를 했냐에 따라 메모리 액세스 패턴이 달라지기 때문에 직접 바이너리를 까보기 전에는 확실히 알 수는 없습니다.
지역성이란 것은 메모리에서 비슷한 위치에 있는 값들을 참조하는 것을 말합니다. 메모리 주소가 0부터 127까지 있다고 할 때, 메모리 액세스 패턴이 10, 11, 9, 10, 10, 12, 10, ... 이런 식으로 되면 지역성이 높은 것이고, 0, 115, 40, 66, 77, 1, 101, ... 이런 식으로 되면 지역성이 낮은 것입니다. 캐시에 다 들어갈 수 없는 데이터를 액세스하는데 지역성이 낮으면 캐시 미스 레이트가 높아지겠죠.
그리고 역시 바이너리를 보기 전에는 확언할 수 없지만 모든 변수가 스택에 있을 경우가 캐시 적중률이 약간 더 높을 것으로 보입니다. 메인 함수의 루프 안에서 scanf와 printf를 지속적으로 호출하는데 함수 호출은 스택 영역에서 값을 쓰는 것으로 이루어집니다. 호출될 함수의 주소나 넘겨질 인자의 값 등이 스택에 쓰여지죠.
댓글을 작성하려면 로그인해야 합니다.
yukariko 7년 전 2
상당히 쇼크를 먹은 결과가 있어서 질문합니다..
아래 소스는 1806번을 accept 받은 소스입니다.
효율이 매우 좋지않아 나중엔 고쳤지만, 이 소스로는 1500ms 를 받았습니다.
그런데 단순히 int i,j; 를 전역변수로 빼기만 한 결과 1100ms 를 받았습니다.
우연의 일치인가 싶어서 여러번 테스트를 해봤으나 결과는 마찬가지 네요..
반복적으로 선언이 되는것도아닌데 어떻게 이런 차이가 날 수 있을까요??
이거하나로 시간초과가 날것이 accept 되고 그러네요 ㄷㄷ;