테스트한 결과를 추가해봅니다.

arr, i  전역 -> 1100ms

arr 전역 i 메인 -> 1500ms

i 전역 arr 메인 -> 990ms

arr,i 메인 -> 990ms

변수에 접근할 때 참조하는 메모리 영역 순서때문에 그런것 같네요.

제가 알기로 전역변수나 static은 data쯤에 있고, 나머지 로컬 변수들은 heap에 있는 걸로 아는데

전역에 있으면 조금 더 빨리 참조하니까 그런거 아닐까요?

더군다나 for 같은 반복문 내에 있었다면 로컬리티가 높으니까요.

그러면 i가 전역이고 arr이 메인일때의 경우를 설명할 수 없지 않나요?

이 경우도 i 와 arr의 변수 위치가 달라지니까요.

문제가 로컬리티에 있는건 맞는거같은데 앞서말한 예외들이 문제네요..

로컬 (오토매틱) 변수들은 스택에 있습니다. 힙에는 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를 지속적으로 호출하는데 함수 호출은 스택 영역에서 값을 쓰는 것으로 이루어집니다. 호출될 함수의 주소나 넘겨질 인자의 값 등이 스택에 쓰여지죠.

전역, 지역 때문보다는 캐시 적중률이 더 차이가 있죠...

좋은 지식 배워갑니다