코드 최적화

알고리즘 트레이닝 초록책 2판을 오늘 받아보았다.

새롭게 추가된 내용이 곳곳에 있을 것이기 때문에 앞에서부터 살펴보았다.

역시나 따로 언급되지 않은 '3.3 코드 최적화'라는 목차가 생겼다.

 

코드 최적화는 고인물들이 아니더라도 통용되고 잘 알려진 기법이다.

하지만, 그 최적화를 깊이있게 이해하는 사람은 드물고, 그냥 입에서 입으로 전해지는 정도인 것 같다.

따라서 최적화의 중요한 부분들을 보충해주는 것이 마음에 들었다. 덕분에 갖고 있던 의문점들도 많이 해결되었다.

 

컴파일러 출력

• 컴파일러 최적화
  • /2, %2 등을 비트연산으로 대체하는 코드들을 보면서 안 예쁘다고 느껴왔었다. 그래서 세그트리 기본문제에다가 비트 연산을 사용한 경우와 그렇지 않은 경우를 비교해 본 바 있다. 하지만 유의미한 속도 차이가 없어 의아했고, 아마도 최적화가 되었을 것이란 믿음으로 /2, %2를 써왔다. 그런데 실제로 그렇다고 한다.
  • 사용하지 않는 변수에 대한 연산을 하는 반복문이나 함수들은 자동으로 제거된다고 한다. 전에 비트연산의 속도를 확인하기 위해 로컬에서 측정한 경험이 있는데, 반복이 매우 많은 코드에서 중도에 0ms에 가까운 속도가 나온 적이 있어서 자동으로 생략되었을 것이란 추측을 했었다. 그런데 실제로 그렇다고 한다. 생각해보니, 사용하지 않은 변수에 대해 컴파일 에러가 뜨는 이유가 이거였나 보다.
• 하드웨어 특정 최적화
  
  • 별로 유용해 보이지는 않는다. __builtin_popcount 연산에 대해 2~3배 속도 향상이 가능하다고 하는데, 프로세서 종류마다 다르게 명령을 지정해야 한다기에 좀 지엽적으로 느껴진다.

프로세서의 특징

• 캐시
  
  • 잘 알려진 최적화 중에 하나다. 캐시 친화적(cache-friendly)인 코드가 더 빠르다는 내용이다. 루프의 순서와 인덱스 순서를 일치하는 것이 좋다고만 나와 있는데, 이는 좀 아쉽다. 왜냐하면 LCA를 구하는 Sparse table에서는 순서가 반대인 것이 결론적으로 더 빠르기 때문이다.
• 병렬화
  • 처음 접한 최적화인데, 노력을 들이는 만큼 배수로 빨라진다. 꽤 유용할 것 같다. 내가 이해한 바로는, 연속된 두 명령이 서로 독립적일 때 병렬적으로 실행이 가능하기 때문에, 반복문에서 $k$개씩 묶어서 처리하는 과정을 거치면 속도가 $k$배 향상된다는 것이다. 자세한 내용은 책 참고. 이 최적화를 이용해 몇몇 코드들에 적용해 보아야겠다.
  • ps. 실패했다 ㅋㅋㅋ 이걸로 최적화해서 시간 줄일 만한 문제들을 찾아봤는데 딱히 없고, 대부분 병렬화로 시간 줄이기에 성공하지 못했다. 자주 쓸 일은 없을 것 같다 ㅋㅋㅋㅋㅋ 그래도 신기하니까 알아둬야지 ㅎㅎ