1 <10 비교가 1 <1000000보다 저렴합니까? 수의 비교에서 ALU

z-indexCSS에서 카운트로 ~ 10 억을 사용했으며 계속 해야하는 비교에 대해 생각하고있었습니다. 매우 큰 수와 매우 작은 수의 비교에서 ALU 수준의 성능에 차이가 있습니까?

예를 들어,이 두 스 니펫 중 하나가 다른 것보다 비쌀까요?

snippet 1

for (int i = 0; i < 10000000; i++){
    if (i < 10000000000000) {
        //do nothing
    }
}

snippet 2

for (int i = 0; i < 10000000; i++){
    if (i < 1000) {
        //do nothing
    }
}



답변

내가 작업 한 모든 프로세서는 피연산자 중 하나를 다른 피연산자에서 빼고 결과를 버리고 프로세서의 플래그 (0, 음수 등)를 그대로 두어 비교합니다. 빼기는 단일 연산으로 수행되므로 피연산자의 내용은 중요하지 않습니다.

확실하게 질문에 대답하는 가장 좋은 방법은 코드를 어셈블리로 컴파일하고 생성 된 명령어에 대해서는 대상 프로세서의 설명서를 참조하십시오. 현재 인텔 CPU의 경우 인텔 64 및 IA-32 아키텍처 소프트웨어 개발자 매뉴얼이 될 것 입니다.

의 설명 CMP( “비교”) 명령은 볼륨 2A, 3-126 페이지, 또는 페이지의 PDF (618)에 있고, 같은 동작을 설명한다 :

temp ← SRC1 − SignExtend(SRC2);
ModifyStatusFlags; (* Modify status flags in the same manner as the SUB instruction*)

즉, 필요한 경우 두 번째 피연산자가 부호 확장되어 첫 번째 피연산자에서 빼고 결과는 프로세서의 임시 영역에 배치됩니다. 그런 다음 상태 플래그는 SUB( “빼기”) 명령어 와 동일한 방식으로 설정됩니다 (PDF의 1492 페이지).

피연산자 값이 대기 시간과 관련이 있다는 문서 CMP또는 SUB설명서 에는 언급이 없으므로 사용하는 모든 값이 안전합니다.


답변

매우 큰 수와 매우 작은 수의 비교에서 ALU 수준의 성능에 차이가 있습니까?

많은 수의 소수에서가는 당신의 숫자 형식을 변경하지 않는 한 그것은 매우 가능성이있어,에서 말하는 intA와 long. 그럼에도 불구하고 그 차이는 크지 않을 수 있습니다. 프로그래밍 언어 가 덮개 아래에서 임의의 정밀 산술 로 자동 전환되면 차이가 발생할 가능성이 큽니다 .

그럼에도 불구하고 특정 컴파일러는 사용자가 모르는 영리한 최적화를 수행하고있을 수 있습니다. 당신이 알아내는 방법은 측정 하는 것입니다. 코드에서 프로파일 러를 실행하십시오. 어느 비교가 가장 오래 걸리는지보십시오. 또는 단순히 타이머를 시작하고 중지하십시오.


답변

많은 프로세서에는 “작은”명령어가 있는데,이 명령어는 비교를 포함하여 특정 즉시 지정된 피연산자에 대한 산술 연산을 수행 할 수 있습니다. 이러한 특수 값 이외의 피연산자는 더 큰 명령어 형식을 사용하거나 경우에 따라 “메모리에서 값로드”명령어를 사용해야합니다. 예를 들어 ARM Cortex-M3 명령어 세트에는 값을 상수와 비교할 수있는 방법이 5 가지 이상 있습니다.

    cmp r0,#1      ; One-word instruction, limited to values 0-255

    cmp r0,#1000   ; Two-word instruction, limited to values 0-255 times a power of 2

    cmn r0,#1000   ; Equivalent to comparing value with -1000
                   ; Two-word instruction, limited to values 0-255 times a power of 2

    mov r1,#30000  ; Two words; can handle any value 0-65535
    cmp r0,r1      ; Could use cmn to compare to values -1 to -65535

    ldr r1,[constant1000000] ; One or two words, based upon how nearby the constant is
    cmp r0,r1
    ...

constant1000000:
    dd  1000000

첫 번째 형태는 가장 작습니다. 제 2 및 제 3 형태는 코드가 페치되는 메모리의 속도에 따라 빠르게 실행되거나 실행되지 않을 수있다. 네 번째 형식은 처음 세 가지 형식보다 거의 느리고 다섯 번째 형식은 훨씬 느리지 만 두 번째 형식은 32 비트 값으로 사용할 수 있습니다.

구형 x86 프로세서에서는 짧은 형식 비교 명령이 긴 형식의 명령보다 빠르게 실행되지만 많은 최신 프로세서는 처음 가져올 때 긴 형식과 짧은 형식을 모두 동일한 표현으로 변환하여 캐시에 균일 한 표현을 저장합니다. 따라서 임베디드 컨트롤러 (많은 모바일 플랫폼에서 사용되는 것과 같은)는 속도 차이가 있지만 많은 x86 기반 컴퓨터는 그렇지 않습니다.

또한 루프 내에서 상수를 많이 사용하는 많은 경우에 컴파일러는 루프가 시작되기 전에 타이밍 차이를 렌더링하여 레지스터에 상수를 한 번만로드하면됩니다. 반면에 작은 루프에서도 상황이 항상 발생하지는 않습니다. 루프가 작지만 많이 실행되는 경우, 짧은 값이 짧은 비교와 더 긴 값이 비교되는 경우가 종종 있습니다.


답변

이 질문에 대한 짧은 대답은 아니오입니다 . 두 데이터가 동일한 데이터 형식 (예 : 32 비트 정수 또는 64 비트 길이)으로 저장되어 있다고 가정 할 경우 두 숫자를 비교할 때 시차가 없습니다.

또한 ALU 의 워드 크기 까지는 두 정수를 서로 비교하는 것이 빼기와 동등한 사소한 연산이기 때문에 1 클럭 사이클 이상이 걸리지 않을 것입니다. 내가 다루었던 모든 아키텍처에는 단일 사이클 정수 비교가 있다고 생각합니다.

두 숫자의 비교가 단일 사이클 작업이 아닌 경우에 만난 것으로 생각할 수있는 유일한 경우는 다음과 같습니다.

  • 피연산자를 가져 오는 데 실제로 메모리 대기 시간이 있지만 비교 자체의 작동 방식과 관련이없는 지침 (일반적으로 x86 / x64와 같은 CISC 디자인에서는 가능하지만 RISC 아키텍처에서는 불가능 함)
  • 부동 소수점 비교는 아키텍처에 따라 다중주기 일 수 있습니다.
  • 문제의 숫자는 ALU의 단어 크기에 맞지 않으므로 비교를 여러 명령으로 나눠야합니다.

답변

@RobertHarvey의 답변 은 좋습니다. 이 답변을 그의 보충 자료로 생각하십시오.


분기 예측 도 고려해야합니다 .

컴퓨터 아키텍처에서, 분기 예측기는 분기 (예를 들어 if-then-else 구조)가 어떤 방식으로 진행 될지 추측하기 위해 시도하는 디지털 회로입니다. 분기 예측기의 목적은 명령 파이프 라인의 흐름을 개선하는 것입니다. 지점 예측자는 x86과 같은 많은 최신 파이프 라인 마이크로 프로세서 아키텍처에서 높은 효과적인 성능을 달성하는 데 중요한 역할을합니다.

기본적으로 예제 if에서 루프 내부 의 명령문이 항상 동일한 응답을 리턴하면 시스템은 분기 방식을 올바르게 추측하여 최적화 할 수 있습니다. 예를 들어, if첫 번째 경우 의 명령문은 항상 동일한 결과를 리턴하므로 두 번째 경우보다 약간 빠르게 실행됩니다.

주제에 대한 탁월한 스택 오버플로 질문


답변

구현에 따라 다르지만 매우 가능성이 적습니다 .

다양한 브라우저 엔진의 구현 세부 사항을 읽지 않았으며 CSS는 숫자에 대한 특정 유형의 저장소를 지정하지 않습니다. 그러나 모든 주요 브라우저가 CSS에서 숫자 요구 사항을 대부분 처리하기 위해 64 비트 배정 밀도 부동 소수점 숫자 ( “doubles”, C / C ++에서 용어를 빌리기 위해)를 사용한다고 가정하는 것이 안전하다고 생각합니다 이는 자바 스크립트가 숫자에 사용하는 방식이므로 동일한 유형을 사용하면 통합이 더 쉬워집니다.

컴퓨터의 관점에서 볼 때, 모든 복식은 값이 1 또는 -3.14 또는 1000000 또는 1e100이든 상관없이 동일한 양의 데이터 (64 비트)를 전달합니다 . 이 숫자에 대해 작업을 수행하는 데 걸리는 시간은 항상 같은 양의 데이터에서 작업하기 때문에 해당 숫자의 실제 값에 의존하지 않습니다. 이러한 방식으로 작업을 수행하는 데있어 상충 관계가 있습니다. 복수는 모든 숫자 (또는 범위 내의 모든 숫자)를 정확하게 나타낼 수는 없지만 대부분의 문제에 충분히 가까워 질 수 있으며 CSS가 수행하는 종류의 숫자는 아닙니다. -그보다 더 정밀해야 할만큼 충분히 요구합니다. 이것을 JavaScript와의 직접적인 호환성의 이점과 결합하면 두 배의 경우가 있습니다.

누군가가 숫자에 가변 길이 인코딩을 사용하여 CSS를 구현하는 것은 불가능하지 않습니다. 누군가가 가변 길이 인코딩을 사용하는 경우 작은 숫자 비교하는 것이 큰 숫자를 비교하는 것보다 비용이 적게 듭니다. 큰 숫자는 더 많은 데이터를 처리하기 때문 입니다. 이러한 종류의 인코딩은 이진보다 더 정확할 수 있지만 속도가 훨씬 느리며 특히 CSS의 경우 정확도 게인이 성능 저하의 가치가 충분하지 않을 수 있습니다. 모든 브라우저가 이런 식으로 작동한다는 것을 알게되어 매우 놀랐습니다.

이론적으로는 위에서 언급 한 모든 것에 예외가있을 수 있습니다. 0과 비교하는 것이 다른 숫자와 비교하는 것보다 빠릅니다 . 이것은 0이 짧기 때문이 아닙니다 (이유가 원인이라면 1이 빠르지 만 그렇지는 않습니다). 제로가 당신을 속일 수 있기 때문입니다. 모든 비트가 꺼져있는 유일한 숫자이므로 값 중 하나가 0임을 알면 다른 값을 숫자로 볼 필요조차 없습니다. 비트 중 하나가 있으면 같지 않습니다. 0이면 1 비트 만보고 0보다 크거나 작은 지 확인해야합니다.


답변

이 코드가 실행될 때마다 해석되는 경우 10000000000000와 비교하여 토큰 화하고 해석하는 데 시간이 오래 걸리므로 차이 가 1000있습니다. 그러나 이것은이 경우 통역사의 첫 번째 최적화입니다 : 한 번 토큰 화하고 토큰을 해석하십시오.