yukariko   2년 전

상당히 쇼크를 먹은 결과가 있어서 질문합니다..

아래 소스는 1806번을 accept 받은 소스입니다.

효율이 매우 좋지않아 나중엔 고쳤지만, 이 소스로는 1500ms 를 받았습니다.

그런데 단순히 int i,j; 를 전역변수로 빼기만 한 결과 1100ms 를 받았습니다.

우연의 일치인가 싶어서 여러번 테스트를 해봤으나 결과는 마찬가지 네요..

반복적으로 선언이 되는것도아닌데 어떻게 이런 차이가 날 수 있을까요??

이거하나로 시간초과가 날것이 accept 되고 그러네요 ㄷㄷ;

yukariko   2년 전

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

arr, i  전역 -> 1100ms

arr 전역 i 메인 -> 1500ms

i 전역 arr 메인 -> 990ms

arr,i 메인 -> 990ms

joonas   2년 전

사용자 삽입 이미지 

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

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

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

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

yukariko   2년 전

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

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

yukariko   2년 전

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

choongmin   2년 전

로컬 (오토매틱) 변수들은 스택에 있습니다. 힙에는 malloc()이나 new로 생성된 객체들이 들어가죠.

메모리 내의 위치에 따른 속도 차이는 없습니다. 다만 캐시(L1, L2, L3)와 메모리의 차이는 크죠. 제가 보기엔 캐시 적중률 차이로 보입니다. arr, sort 합쳐서 약 800KB 정도 되는데, 채점 머신의 CPU가 뭔지 모르겠지만 일반 가정용 CPU의 경우 저 정도 크기면 L2 캐시에 다 들어가지 않죠. L3 캐시가 있다면 첫번째 루프를 돌면서 다 들어가긴 하겠지만 L3 캐시는 그렇게 빠르지는 않구요.

다만 컴파일러가 어떻게 최적화를 했냐에 따라 메모리 액세스 패턴이 달라지기 때문에 직접 바이너리를 까보기 전에는 확실히 알 수는 없습니다.

yukariko   2년 전

그렇군요. 역시 캐시의 문제인가보네요.

메모리 위치에 따른 속도차이가 없다고 하셨는데, 제가 학교에서 배운 바로는 캐시에 적재되는 메모리의 지역성에 따라 성능이 많이 좌우된다고 배웠거든요..

제가 배운것이 잘못된건가요?

그리고 모든 변수를 전역으로 선언하고 푼 경우보다, 모든 변수를 지역으로 선언하고 푼 경우가 훨씬 빨랐는데, 이것은 캐시랑 어떻게 연관이 있는걸까요?

choongmin   2년 전

지역성이란 것은 메모리에서 비슷한 위치에 있는 값들을 참조하는 것을 말합니다. 메모리 주소가 0부터 127까지 있다고 할 때, 메모리 액세스 패턴이 10, 11, 9, 10, 10, 12, 10, ... 이런 식으로 되면 지역성이 높은 것이고, 0, 115, 40, 66, 77, 1, 101, ... 이런 식으로 되면 지역성이 낮은 것입니다. 캐시에 다 들어갈 수 없는 데이터를 액세스하는데 지역성이 낮으면 캐시 미스 레이트가 높아지겠죠.

그리고 역시 바이너리를 보기 전에는 확언할 수 없지만 모든 변수가 스택에 있을 경우가 캐시 적중률이 약간 더 높을 것으로 보입니다. 메인 함수의 루프 안에서 scanf와 printf를 지속적으로 호출하는데 함수 호출은 스택 영역에서 값을 쓰는 것으로 이루어집니다. 호출될 함수의 주소나 넘겨질 인자의 값 등이 스택에 쓰여지죠.

pl0892029   2년 전

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

joonas   2년 전

좋은 지식 배워갑니다

댓글을 작성하려면 로그인해야 합니다.