저는 컴퓨터 게임 기술의 2 학년 학생입니다. 나는 최근에 자신의 패스 파인더의 “종류”의 첫 프로토 타입을 완성했다. (A *를 사용하지 않고 기하학적 인 접근 / 패턴 인식, 패스 파인더는 결정을 내릴 수있는 지형에 대한 지식 만 있으면된다. 지형이 이미 알려진 경우 실제로 탐색 할 수있는 인공 지능을 원했습니다.
어쨌든 내 질문은보다 일반적입니다. 알고리즘 / 루프 / for_each / 등을 최적화하는 방법은 무엇입니까? 일반적인 팁을 환영하지만 어셈블리 사용. 나는이 주제에 관해 좋은 책을 찾기가 정말로 어렵 기 때문에 특히 좋은 책을 찾고 있습니다. 이 같은 거기 몇 가지 작은 기사입니다 이 하나 ,하지만 여전히 알고리즘 / 게임을 최적화 할 수있는 충분한 지식이없는 …
나는 찾을 수 없었던 현대의 좋은 책이 있기를 바랍니다.
답변
나는 여기서 결정에 반대하는 사람이 될 것이며, 최적화, 특히 어셈블리 최적화 및 더 중요하게는 어셈블리 디버깅에 대해 배우기 에는 너무 이르지 않습니다 . 나는 당신이 학생이라면 (즉, 시간 / 돈을 현명하게 잃을 것이 거의 없기 때문에) 그리고 얻을 수있는 모든 것이라면 최대의 이익을 얻을 것이라고 믿습니다.
업계에 있고 조립 과정에서 땜질 작업을하지 않은 경우하지 마십시오. 그렇지 않으면, 당신이 학생이거나 일반적으로 시간이 있다면, 프로그램을 분해하는 법을 배우고 컴파일러보다 더 나은 해결책을 찾을 수 있는지 알아볼 시간이 있습니다. 내가 할 수 없다면 누가 신경 쓰겠 어! 방금 컴파일러뿐만 아니라 작성하는 방법을 배웠으며 릴리스 코드의 버그 (디버그 기호가 없음)에 직면하고 디스 어셈블리를 쳐다 보았을 때 볼 수있는 유일한 것이기 때문에 큰 장점입니다.
대답
이것은 최적화에 대해 배우기 위해 찾은 최고의 리소스 중 하나입니다.
http://www.agner.org/optimize/
그랜트
주요 개발자가 작성한 기사를 읽는 경우 (예를 들어, EASTL 작성의 근거가 있고 코드를 면밀히 검사하면 GCC 가이 if 문 을 인라인하는 것이 끔찍하기 때문에 이와 같은 주석으로 이어질 것 입니다. 사람들 은 컴파일러 가 게임 개발에서 항상 옳지 않다고 신뢰하고 업계에 발을 들여 놓으면 최적화가 일상적인 일이며 어셈블리 출력의 의미가 무엇인지를 알 수 있습니다. 또한 사람들은 게임을 프로파일 링하는 것이 매우 어렵고 항상 정확한 것은 아니라는 사실을 깨닫지 못하는 것 같습니다 (특히 스택 오버플로에서).
그래도 경고가 있습니다. 무언가를 최적화하는 데 시간을 할애하고 나중에는 시간이 낭비되었음을 깨달을 수 있습니다. 그러나 무엇을 배웠습니까? 비슷한 상황에서 같은 실수를 반복하지 않는 법을 배웠습니다.
무엇 SO 지금 복용하는 것은 내 생각에 문을 종교적 입장이다 최적화 프로파일 링하지 않습니다 때까지 하고 걱정을하지, 컴파일러는 더 나은 당신보다 알고있다 . 학습을 방해합니다. 나는 컴파일러가 게임에 나쁘거나 단순히 당신을 도울 수 없기 때문에 게임을 최적화하고 디버깅하기 위해 어셈블리에서 바이올린을 다루는 아주 좋은 돈 (그리고 나는 아주 좋은 돈을 의미 함)을 알고있는 업계의 전문가를 알고 있습니다. (GPU 관련 충돌, 관련된 데이터를 디버거 등에서 읽을 수없는 충돌 등) 불가능!
그렇게하는 것을 좋아하는 사람이 아직 그것을 완전히 깨닫지 못하고 여기에 질문을하고 많은 답변 컴파일러가 당신보다 더 잘 알고있는 답변을 끄거나 끄면 어떻게 될까요? 그리고 돈이 많이 드는 프로그래머가되지 않습니까?
하나의 마지막 생각. 이 작업을 일찍 시작하면 곧 최악의 코드를 작성하기 시작합니다. 컴파일러가 동일한 방식으로 또는 최상의 방식으로 최적화했기 때문에 성능 향상이 전혀 없으며 이제 컴파일러가 최적화 할 수 있기 때문에 성능이 약간 향상되었습니다. . 두 경우 모두 습관이되었으며, 이전보다 코드 작성 속도가 느리지 않습니다. 몇 가지 예는 다음과 같습니다 (더 많은 것이 있습니다).
- 사후 증분을 원하지 않는 한 사전 증분
- 루프 내의 컨테이너에서 size ()를 호출하는 대신 상수 로컬 크기 변수를 사용하여 컨테이너에 대한 루프를 작성합니다.
편집 : 업계에서 8 년 후에 업데이트하십시오. 조립을 배우십시오. 옵티마이 저가 작동하는 방식과 이들이 생성하는 어셈블리에 대해 알아보십시오 (CompilerExplorer는이를위한 훌륭한 도구입니다). 디버그 빌드로도 디버거에 의존 할 수없는 테스트 빌드 (내부 테스트에 최적화 된 빌드)에서 수많은 충돌을 겪었습니다. 컴파일러가 너무 많은 것들을 최적화했으며 크래시 덤프에서 버그를 찾는 유일한 정보 소스는 어셈블리입니다. 운이 좋으면 빌드 큐에서 먼저 각 빌드는 30-40 분이 걸리므로 버그를 격리하기 위해 일부 전통적인 기술에 의존 할 수 없습니다. 멀티 플레이어는 상황을 악화시킵니다. 어셈블리를 알고 최적화 된 어셈블리를 읽는 방법은 팀에게 더 나은 결과를 가져다 줄 것입니다.
답변
당신이 얻는 첫 번째 팁은 이것입니다.
현대의 컴파일러는 실제로 코드 최적화에 정말 능숙하며 작성한 자체 롤링 어셈블리 언어보다 더 나은 작업을 수행 할 가능성이 높습니다.
예외는 컴파일러가 최적화 작업을 제대로 수행하지 않는다고 판단한 경우입니다. 두 번째 팁입니다. 여기에는 일반적인 지침이 없으며, 자신의 코드를 알고, 수행중인 작업을 알고, 해체 할 수 있으며, 컴파일러가 나쁜 일을하고 있는지 확실하게 결정할 수 있습니다.
이 경우에도 여전히 원하지 않을 수 있습니다. 지속적인 유지 관리 오버 헤드가 없는지 확인해야합니다. 6 개월 후에이 코드로 돌아와서 일부를 수정하거나 어셈블리 언어 버전에서 수정하기가 더 어려운 매우 미묘한 버그를 발견 할 수 있습니다. 모든 버그를 해결했다고 생각하더라도 프로그램이 공개 버그로 넘어간 후에는 결코 일어날 수 없다고 생각한 적이있을 것입니다. 그것은 상당히 눈에 띄는 (그리고 겸손한 경험)입니다.
기꺼이 동의하더라도 주요 병목 현상이 프로그램에서 완전히 다를 수 있기 때문에 측정 가능한 성능 개선이 전혀 없다는 것을 여전히 알 수 있습니다. 다시 1 번으로 돌아갑니다. 하지마
답변
일반적으로 확실한 최적화는 Assembly 사용 또는 고급 언어 코드로 미세 최적화를 수행하는 데 의존하지 않습니다. 많은 연구 논문을 읽은 경우 (또는 내가 시도한 것처럼!), 알고리즘의 개선은 종종 “정량적”수준이 아닌보다 광범위한 개념적, “정 성적”수준에 있음을 알 수 있습니다. 미세 최적화 수준. 이 관점에서 또는 기존 솔루션을 벡터화 / 병렬화하여 알고리즘을 살펴보면 크기 차수가 증가 할 가능성이 높다고 강조합니다.
나는 최근에 이런 일 이 일어 났는데 , 이는 게임 개발자를 위해 x86 ASM을 배우는 좋은 길일 수 있습니다.
추가
내 머리 꼭대기에서 두 가지 소스 :
- 알고리즘 디자인 매뉴얼 -Steve Skiena
- 게임 프로그래머를위한 데이터 구조 -Ron Penton 및 Andre LaMothe
또한 연구 논문을 읽는 것이 현명한 사고 과정을 따라 가면서 성능을 향상시키기위한 알고리즘을 최적화하는 훌륭한 방법입니다. 가장 흔히 이익은 다음과 같습니다.
- 가장 비용이 많이 드는 작업 (div, SQRT, trig op 및 조건부)의 사용을 줄입니다.
- 보다 효율적인 데이터 구조, 메모리 정렬 및 감소 된 조건을 사용하여 캐시 성능을 향상시킵니다.
- 성능 향상을 위해 허용 가능한 영역에서 출력 품질 감소
- 벡터화 (SIMD);
- 병렬화 (스레딩, GPU로 작업 전환)
- 그리고 물론 수작업으로 코딩 된 (아주 드물게) 어셈블리입니다. 물론 C / C ++ 어셈블리를 검사하여 컴파일러가 최적의 선택을하지 않는 위치를 확인하십시오. 80 년대와 90 년대 IME의 오래된 논문에서 더 많은 것을 찾을 수 있습니다.
또한 리서치 연구를 통해 해당 지식이 업계에 반영되기를 기다리는 대신 해당 분야의 최첨단을 유지할 수 있습니다.
답변
너무 빠르다고 생각합니다.
어쨌든 컴파일러 자체는 어셈블리와 동등한 코드보다 느린 코드를 생성하지 않는다는 것을 이해하는 것이 중요합니다. 컴파일러와 동일한 어셈블리 코드를 작성해도 성능이 떨어지지 않습니다.
시작하려면 최소한 어셈블리없는 최적화에 집중하십시오. Igor Ostrovsky는 몇 가지 기본 사항을 보여주는 몇 가지 좋은 기사를 제공합니다. http://igoro.com/archive/fast-and-slow-if-statements-branch-prediction-in-modern-processors/
분기의 잘못된 예측과 캐시 누락은 추가 산술 연산을 수행하여 비용을 지불해야하는 경우에도 예측할 수없는 분기를 피하거나 너무 많은 메모리에서 무작위로 읽는 것을 피할 가치가 있습니다.
그리고 가장 중요한 것은 알고리즘을 먼저 최적화하는 것입니다. 빠른 알고리즘의 느린 구현은 느린 알고리즘의 빠른 구현보다 거의 항상 빠릅니다.
답변
이 책은 교과서에 매우 적합합니다. 그러나 최적화를 위해 특별히 고안된 것은 아닙니다.
x86 프로세서 용 어셈블리 언어, 6 판
MASM을 사용하여 어셈블리의 기본 사항을 가르치는 것에 대해 자세히 설명합니다. 그런 다음이 책의 끝 부분에서 c ++로 어셈블리를 인라인하고 더 큰 프로그램에 통합하는 방법에 대해 알아 봅니다.
프로그램을 최적화하는 방법을 배우기 전에 어셈블리의 기초를 배우는 것이 합리적이기 때문에 여기에 넣었습니다.
Irvine이 masm 프로그램 작성에 필요한 도구를 사용하는 방법을 가르쳐주기 때문에이 책이 마음에 듭니다. 그는 특히 IDE (Visual Studio C ++)와 디버거를 사용하는 방법에 대해 설명합니다. 각 장에는 문제 해결을위한 몇 가지 비디오가 있습니다. 이 정보 중 일부는 나열된 웹 사이트에서 자유롭게 사용할 수 있습니다.