[💬] 루프가 작을 수록 비용이 크다는데 무슨얘기임?

[익명(112.151)]

어셈블리 단위에서 루프가 작을 수록 branch prediction 연산이 커져서 비효율적이라고 최적화 책에서 말하는데

이거 설명 좀 해주실분?

루프 탈출 조건 테스팅땜에 그런건가

[익명(112.151)]

책에서는 백 브랜치가 일어나면 그때마다 cpu는 유입된 명령어 파이프라인을 덤프하기때문에 성능상 바람직하지 않다는데 뭔 말인지 모르겠음

[오더리움(othereum)]

branching은 굉장히 비싼 연산임을 전제하고 루프는 본문과 조건문으로 구성되어있는데 조건문 branching에 상수시간이 소요된다면 본문이 짧을수록 branching에 소요되는 비중이 커질테니 비효율적이라고 할수있겠지 - dc App

[익명(112.151)]

그러면 윗 댓글은 뭔 말인지 설명해줄 수 있음?

[오더리움(othereum)]

이건 인터넷에 분기예측 검색해서 직접 찾아보는게 빠를거임 - dc App

[해당 댓글은 삭제되었습니다.]

해당 댓글은 삭제되었습니다.

[익명(112.151)]

첫 댓 무슨 얘긴지 알려줘요

[Anonymous(220.86)]

뭐야 여기 로우레벨 숨은고수들 많네 개멋짐 다들...

[123(122.38)]

cpu 파이프라인은 배운거 같은데 왜 브랜치 문제는 생각이 안나지 ㅋㅋㅋ 다 잊어버렸나

[익명(221.146)]

개잡소리 다 필요없고 위에 오더리움이 쓴게 직접적인 답임

[오더리움(othereum)]

[익명(221.146)]

branch prediction을 최소화하기위해 컴파일러 단에서 unraping으로 루프를 최대한 제거하는 최적화도 적용이 되는거고

[익명(221.146)]

첫댓글의 얘기는 오덜이룸이 말한 brancing이 비싼연산인 이유잖아 너 컴퓨터 구조론도 안배운거 같은데 컴공2학년인가에 배우지 않나? 비전공자거나 고딩임? 걍 공부가 부족하니까 뭐가뭔소린지도 모르는거

[익명(112.151)]

그래도 이해안되는데 ... 나 컴파일러 공부하는 대학원생이야 ㅠㅠ

[익명(221.146)]

아니 내가 더 이해 안되는데 컴공계열 대학원생에 그것도 컴파일러면 기본 컴퓨터 구조는 당연히 안다는 얘긴데 저게 뭔소린지를 모른다고? 하... 말이 안되는데 비하하는게 아니라 진짜 어디 개지잡 대학원생임? ㄹㅇ 이해가 안되서 그럼

[익명(221.146)]

어디 대학이든 몇학년이든 컴퓨터 구조론을 배웠다면 당연히 이해해야 정상임/

[익명(221.146)]

그게 고딩이든 중딩이든 컴구를 배웠다면 당연히 이해가야 정상인데 참 미스터리다

[익명(112.151)]

아무리 생각해도 loop unroll해서 얻는 이점하고 branch predictor가 얻는 이점이 비슷할 수 밖에 없을 것 같은데 branch predictor가 켜져도 super pipeline도 같이 활용 가능하니깐 보통 unroll대상 루프는 randomize한 escape condition이 아니니깐 선형 루프를 unroll함으로써 얻는 이점은 branch target buffer를 채우는 prolog 정도밖엔 없고 이건 고정 시간으로 봐도되니깐 루프가 커지면 커질 수록 그 효과는 미미할꺼고 super scalar 연산 hint를 전달 못해서 그렇다는거임?

[익명(112.151)]

그냥 직관적으로 잘 이해가 안되서 그런거 branch predictor가 백브런치에 대해선 instruction stall을 시키지 않는다고 배워서 그런거임

[익명(112.151)]

그냥 unroll 옵션끄고 실험해볼께

[익명(221.146)]

일단 이쪽 전문가는 아니라서 몇가지 용어에 대해 정확히 모르기는 하지만 일단 최대한 대답해보자면 - branch predictor가 백브런치에 대해선 instruction stall을 시키지 않는다 ? 이게 무슨 말이지? back branch 검색해봐도 정보가 없는걸로 봐서는 정식 용어는 아닌거 같은데 기본적으로 branching prediction이 실패하면 instructiond stall이 일어나는게 원칙이고 그렇기 때문에 prediction을 최소화 하도록 unroll을 하는 거라고 알고 있는데 더 깊이 들어가면 뭐가 달라지는건지는 모르겠다만 많약 그렇다면 여기서 그 자세한 정보에 답할수 있는 사람은 없을거임

[익명(221.146)]

내가 보기엔 니가 용어 몇개랑 개념이 섞여서 헷갈려 하는걸로 보이는데 그냥 기본적인 개념은 흐리지 말고 생각해봐

[익명(112.151)]

back branch는 back edge랑 같은 말임 그 머냐 루프의 첫 부분으로 되돌아가는거

[오더리움(othereum)]

좋은 지적임. 그래서 unroll이 효과적인 경우는 극히 제한적임. 내가 위에서 말한것처럼 branching의 비중이 커서 비효율적인 경우에 효과적인 최적화 방법이겠지 - dc App

[익명(221.146)]

pipeline 최적화로 stall없이 진행될수도 있었었나 그렇다고 해도 그리고 니가 첫댓글에 쓴것만 봐도 백브랜치가 일어났을 때 뭔가 성능상 안좋은 일이 일어나는거기 때문에 루프를 최소화 하는게 성능상 이점이 된다는건 확실한거고 -> 그래서 unroll을 하는게 성능상 도움이 된다는거고, 이 간단한게 이해가 안되는거면 지금 머리가 ㅈㄴ 복잡한거일듯

[익명(112.151)]

한 숨 돌리고 다시 한 번 생각해볼께 답변들 고마워

[익명(221.146)]

너 설마 unroll 이랑 predictor의 실행시간이 다른건 알고 있는거지? unroll은 컴파일러에서 하는거고 predictor는 cpu에서 하는거잖아 당연히 unroll이 이미 되있는 코드면 cpu의 부담이 줄어드는거지 왜 이점이 비슷하다고 생각하는거지? 명백히 처리시간대가 다른데 unroll이 된 코드는 무조건 cpu에서 더 효율적일 수밖에 없음 이거 헷갈린거 아닌지 생각해봐라 그럼 난 간다

[익명(112.151)]

그건알지 ㅋㅋ 나도 그건 당연한거라고 생각하고 있었는데, 이번에 최적화 쪽 공부하면서 의문생겨서 질문한거야 게임 플밍하는 사람들 최적화 잘하는 거 많이 봐서 질문하러온거

[익명(175.214)]

가슴속에 열이 가득한 친구네

[익명(14.52)]

브랜치 프리딕션 레벨까지 간다는거는 엄청 로우한 레벨수준의 최적화를 신경쓰겠다는건데 솔직히 별로 신경 안써도 됨.. 내가 아는 바를 풀어보자면 CPU가 로직을 최적화 하는 방식 중에는 서로 얽히지 않는 로직들을 병렬로 처리하는게 있음. a = 1 + 1; b = c + 2; 프로그램 로직은 선형적으로 이루어 지지만 위의 두 줄 처럼 서로 연관이 없는 로직들은 동시에 계산해도 상관이 없기 때문에 내부적으로 동시에 계산이 진행되는거지. 그런데 if같은 로직들은 이런 동시 진행을 처리하는데 매우 귀찮은 문제를 발생시키는데 결과가 나와봐야 어느 로직을 탈지 판단이 된단 말이야. 그렇기 때문에 내부적으로는 왠만하면 들어갈 것 같은 쪽을 미리 계산해 두고 최종적으로 그 예측이 맞았으면 그대로 진행

[익명(14.52)]

틀렸으면 반대쪽을 그때 계산하는 식으로 진행이 되.. 그렇기 때문에 if같은 조건문들이 최적화에 큰 비용을 발생시킨다는 얘기가 나오는 거야.. 근데 솔직히 인디겜 만드는 레벨에서 여기를 신경쓸 필요가 있느냐? 라고 물으면 그냥 대충 개발해도 됨..

[오더리움(othereum)]

알 필요는 없지만 알면 좋은, 프로그래밍 계의 '교양' 같은 느낌이지

[오더리움(othereum)]

질문자는 걍 대학교 공부하다가 막혀서 질문한듯

[익명(14.52)]

그런듯 위에 댓글 좀 봤는데 이미 내 수준은 넘은듯

[익명(110.70)]

윗 댓글 읽어보니까 니가 생각하는게 branch predictor로 어짜피 instruction stall이 일어나지 않아서 딱히 의미있게 비용이 줄어들지 않는다고 생각하는데. 니가 말하는 branch predictor 계산 자체가 루프 마다 하는데 당연히 그 루프가 많이 돌면 돌수록 예측계산을 자주해서 안좋다 라고 책에서 말하는걸로 보이네.

[익명(110.70)]

내가말한 루프를 많이 돈다 라는 전제 자체가 특정 루프를 강제로 unroll해서 풀어서 루프 내에 양 자체를 늘리고 루프 자체는 적게 도는 상황을 하지 않을때 얘기고

[익명(110.70)]

동일한 작동을 하는 코드를 루프를 적게 돌게 짜느냐 많이 돌게 짜느냐 라는 전제임

[익명(110.70)]

그 의미있게 비용이 줄어드느냐 아니냐는 제쳐두고 줄어들긴 한다 라는 내용인듯

[익명(112.151)]

그렇다면 그 branch predictor의 예측 계산이 instruction pipeline에 어떤 영향을 미치는 지가 궁금하네 예측 연산 때문에 branch 후의 instruction들이 1.5 cycle 이상 밀려버리면 어쨋듯 unroll 보다는 손해니깐 답변 고마워!

[익명(110.70)]

난 파이프라이닝 된 상황에서 각 스테이지에 걸리는 시간은 항상 상수인가 아닌가가 헷갈리네. 나는 만약 상수면 branch prediction을 하든 말든 상관없이 똑같은 시간이 걸리니까 니가 말한것 처럼 의미 없어질테고

[익명(110.70)]

뭐 책에서 말한대로면 변동이 있다고 봐야겠지?