명령 경로 길이

컴퓨터 성능에서 명령 경로 길이는 컴퓨터 프로그램의 섹션을 실행하는 데 필요한 기계 코드 명령의 수입니다.전체 프로그램의 총 경로 길이는 특정 컴퓨터 하드웨어에서 알고리즘의 성능을 측정하는 척도로 간주될 수 있습니다.단순 조건부 명령의 경로 길이는 보통 ^{[citation needed]}2로 간주되며, 한 명령어는 비교를 수행하고 다른 명령어는 특정 조건이 충족되면 브랜치를 취합니다.각 명령을 실행하는 시간은 일반적으로 경로 길이를 결정할 때 고려되지 않으므로 경로 길이는 절대적인 의미가 아니라 상대적인 성능을 나타내는 데 불과합니다.

벤치마크 프로그램을 실행할 때 대부분의 명령 경로 길이는 일반적으로 프로그램의 내부 루프 안에 있습니다.

캐시가 도입되기 전에는 경로 길이가 실행 시간의 근사치였지만 캐시가 있는 최신 CPU에서는 데이터가 캐시에 없을 때 수백 사이클이 걸리거나 캐시에 있을 때 훨씬 더 빠른 로드 명령이 있을 수 있습니다(루프의 다른 라운드에서 동일한 명령도 마찬가지).

어셈블리 프로그램

일반적으로 어셈블리 명령과 기계 명령 사이에는 일대일 관계가 있기 때문에 명령 경로 길이는 함수 또는 코드의 특정 섹션을 수행하기 위해 필요한 어셈블리 명령의 수로 간주됩니다.1,000개의 엔트리의 정렬되지 않은 목록에서 단순 테이블 검색을 수행하는 경우 약 2,000개의 머신 명령이 필요할 수 있습니다(입력 값의 균일한 분포를 가정할 경우). 한편, 바이너리 검색 알고리즘을 사용하여 정렬된 목록에서 동일한 검색을 수행하는 경우 약 40개의 머신 명령이 필요할 수 있으므로 상당한 절약이 가능합니다.명령 경로 길이로 표현하면 이 메트릭은 이 경우 50이라는 대규모 계수만큼 감소합니다.이 때문에 실제 명령 타이밍은 보다 짧은 경로 길이를 필요로 하는 알고리즘에 비해 2차 고려사항이 될 수 있습니다.

어셈블리 언어 프로그램의 명령 경로 길이는 일반적으로 해당 프로그램의 코드 소스 행 수와는 크게 다릅니다. 명령 경로 길이는 특정 입력에 대해 실행된 제어 흐름에 코드만 포함하며 특정 입력과 관련이 없는 코드 또는 도달 불가능한 코드를 포함하지 않기 때문입니다.

고급 언어(HLL) 프로그램

높은 수준의 언어로 작성된 하나의 문장이 변수 숫자의 여러 기계 명령을 생성할 수 있기 때문에, 예를 들어 시뮬레이션 중에 '실행된' 명령의 수를 셀 수 있는 명령 집합 시뮬레이터 없이 명령 경로 길이를 결정하는 것이 항상 가능한 것은 아닙니다.고급 언어가 '어셈블리 목록'을 지원하고 선택적으로 생성하는 경우, 이 목록을 검토하여 명령 경로 길이를 추정할 수 있습니다.