델파이 최적화 가이드라인 (2) – 정수 가이드라인

아래 글은 원래 2002년에  Robert Lee의 홈페이지인 http://www.optimalcode.com 라는 사이트에 실렸던 “Delphi Optimization Guideline”이라는 글의 일부입니다. 지금 이 사이트는 없어진 상태이고 원래의 필자도 전혀 연락이 안되는 상태입니다. 하지만 최근에 예전의 컨텐츠들을 http://delphitools.info 에서 되살렸습니다. 델파이 개발자분들께 도움이 될 부분이 많을 것 같아서 번역을 시작해봅니다. 전체는 4개의 시리즈로 되어 있으며, 이 글은 그중 두번째인 Integer Optimization Guideline 입니다. 

원문:  http://delphitools.info/OptimalCode/integer.htm

사용자 삽입 이미지
Delphi Optimization Guidelines

(1) 일반 가이드라인
(2) 정수 가이드라인
(3) 문자열 가이드라인
(4) 부동소수점 가이드라인

(2) 정수 최적화 가이드라인

스타일 가이드라인

가능한 한 32비트 변수를 사용하라

델파이 2 이후 버전에서 개발된 코드처럼 32비트 코드에서는 32비트 크기를 갖는 값이 모든 면에서 더 낫습니다. 16비트 변수(Word, ShortInt, WideChar)는 프로세서가 해당 변수를 작업하기 위해 일시적으로 16비트 모드로 넘어가기 때문에 특히 더 느립니다. 이 문제 때문에 16비트 값들로 작업할 때는 두 배의 시간을 소모하게 됩니다. 반면 8비트 변수들(Byte, SmallInt, Char)은 32비트 변수와 섞어 쓰지 않는 이상은 그렇게 많이 나쁘지 않습니다. 하지만 8비트 변수는 32비트 레지스터에서 나머지 공간을 0으로 초기화하는 추가적인 명령을 포함하게 되기는 합니다.

호환성 때문에 작은 크기의 타입을 사용해야만 한다면, 가능한 한 32비트로 변환해서 사용하고 필요한 때에 작은 크기로 다시 되돌리는 것이 낫습니다. 단지 32비트 변수에 대입하기만 하면 되죠.

 

부분범위를 피하라

전통적으로 파스칼이 가진 장점들 중 하나는 강력한 타입 체크를 한다는 것입니다. 이로 인해 특수한 부분범위(subrange) 타입을 만들 수 있고 열거형도 여기에 포함됩니다. 불행히도, 부분범위와 열거형은 성능 최적화를 시도할 때 문제를 일으킬 수 있습니다. 문제는, 부분범위나 열거형 변수의 내부적인 크기가 부분범위의 크기에 따른다는 것입니다. 예를 들면, 256개 미만의 요소수를 가진 열거형이나 0에서 255까지의 경계 값을 가진 부분범위는 byte로 저장됩니다. 이 문제로 내부적인 변수의 크기가 효율적으로 처리되지 않을 수 있습니다. 예를 들어, 다음과 같은 부분범위를 살펴봅시다.

TYear 타입의 변수는 16비트 크기로 저장될 것입니다. 앞에서 설명한 것처럼 16비트 변수는 특히 느립니다.

 

최적화 테크닉

 

복잡한 표현식을 나누기 위해 임시 변수 추가를 고려하라

일반적으로, 모든 것을 단 하나의 표현식에 밀어넣으면 최적화에 가장 좋습니다만, 항상 그렇지는 않습니다. 어떤 경우에는 표현식이 너무나 복잡해서 컴파일러가 자체적으로 나누려고 할 수도 있습니다. 여러분이 직접 나눴을 때 컴파일러보다 더 나은 결과가 나오는 경우가 잦습니다. 직접 해보세요.

 

정수 곱셈

펜티엄 II 이전에는 정수 곱셈이 상당히 느렸습니다. 하지만 펜티엄 II 이후로는 정수 곱셈은 대부분의 다른 명령들처럼 한 사이클에 실행되도록 빨라졌습니다. 또한 덧셈이나 시프트 연산, LEA 명령(아래에서 설명)으로 같은 결과를 낼 수 있는 경우 컴파일러는 곱셈을 피합니다. 따라서, 곱셈을 사용할 것인지 아니면 다른 동등한 방법을 사용할 것인지를 선택할 때, 대상 PC의 프로세서를 고려할 필요가 있습니다.

 

변수를 여러 서수 상수들과의 비교하는 경우

이 주제는 어렵게 들리지만 사실 아래와 같은 문에 핵심이 있습니다.

위 두 케이스에는 단 하나의 변수가 있고 그것이 여러 상수들과 비교됩니다. 다음과 같이 표현하면 조금 더 효율적이고, 또 더 명료하게 됩니다.

효율성의 개선은 x가 범위 안에 있을지 아니면 바깥에 있을지의 가능성에 따라 달라집니다. 범위 안에 있을 가능성이 더 크다면, set 표기법이 더 낫습니다. set 표기법의 효율성은 부분범위의 갯수가 많아질 수록 더 높습니다. 하지만 set은 본질적으로 요소 수가 256개로 제한됩니다. 이 제한으로 정수 타입에 대해 이 방법을 사용하는 것은 제한적입니다. 전체 정수 범위에 대해서는 아래의 방법을 사용할 수 있습니다.

이 방법도 동일한 코드를 만들어냅니다만, 그다지 우아해보이지는 않지요.

고급 노트: 이 방법은 추가적인 CPU 레지스터를 이용할 수 있습니다.

 

movzx vs xor/mov

32비트보다 작은 값을 레지스터에 로드해야 하는 경우는 종종 있습니다. 이런 값들은 32비트인 레지스터 전체를 덮어쓰지 못하기 떄문에 먼저 레지스터를 0으로 초기화를 할 필요가 있습니다. 그 대신, 내장된 movzx (move with zero extend) 명령을 사용할 수도 있습니다. 펜티엄과 그 이전의 프로세서에서는 이 명령이 reg,reg/mov reg,{value} 보다 느렸었습니다. 하지만 펜티엄 II는 이 명령을 더 능률화하였으므로, xor/mov 명령을 사용하는 것보다 낫습니다. 컴파일러는 이 두가지 방법 중에서 상당히 복잡한 규칙들에 따라 선택을 합니다.

 

LEA 어셈블러 명령을 활용하라

LEA (Load Effective Address)라는 어셈블러 명령이 있는데, 두 개의 동작을 한번에 처리할 수 있습니다. 델파이에서 이 명령을 사용할 수 있는 방법은 한 가지 뿐인데, 배열 표기법을 사용하는 것입니다. 확실히 동작되도록 하기 위해서는 원하는 코드 다음에 배열 변수 자체가 한번 더 사용되어야 합니다. 예로서, 다음의 코드는 PChar 문자열의 길이를 계산하는 루틴(StrLen )의 일부입니다(첫번째 #0 문자의 위치를 찾습니다). 네 개의 문자가 한번에 처리됩니다. r2의 계산에서 q를 사용하는 것을 눈여겨 보십시오.

exstrlen.zip

 

큰 정수 타입의 성능

longint 크기보다 더 큰 정수를 사용해야 하는 경우 몇가지 중 하나를 선택할 수 있습니다(int64, comp, double, extended). 이중 세가지는 실제로는 부동소수 타입입니다. 따라서 이들은 서로 완벽하게 대체가능한 것이 아닙니다. 비교적 최근에 추가된 타입인 int64만이 정수로서 완벽하게 처리됩니다. comp는 하이브리드 타입으로서, int64와 동일하게 8바이트 정수로서 저장되지만 모든 동작은 부동소수점 타입으로 수행됩니다. 볼랜드는 공식적으로 comp 타입을 obsolete로 지정했으며, 그 대신 int64를 추천하고 있습니다. 하지만 아래의 표에서 볼 수 있는 것처럼, comp는 어떤 상황에서는 성능 면에서 상당히 더 뛰어납니다. Extended와 double도 큰 정수를 다룰 때 사용될 수 있지만,
주기적인 반올림의 부족이 축적되어 답을 바뀌지 않도록 주의해야 합니다. 아래는 펜티엄 II CPU에서 일정 범위(0 < x < 2^63)의 랜덤 값들로 각 연산을 측정한 결과입니다. “Ovhd”는 각 타입으로 함수 호출을 하고 대입했을 때의 오버헤드를 의미합니다. LongInt는 비교를 위해서 추가되었습니다.

참고로, 펜티엄 II의 비순차 실행 기능 때문에 각각의 연산에 대한 정확한 시간 측정은 거의 불가능합니다. 따라서 위에서 보여드린 사이클 수는 근사치로만 이해해야 합니다.

int64의 극악스러운 나눗셈 성능을 제외하면, 명백한 최선의 선택은 없습니다. 세 가지 부동소수점 기반 타입들 중에 double이 가장 낫습니다만 약간 적은 자리수를 가지고 있습니다. int64는 comp보다 덧셈에서 더 낫습니다만 다른 연산에서는 나쁜 결과를 보여줍니다.

그럼 어떻게 해야 할까요. 가장 좋은 해답은 섞어 사용하는 것입니다. int64를 기본 타입으로 사용합니다. 나눗셈은 Int64A div Int64B 대신 trunc(Int64A/Int64B)를 사용하면 쉽게 처리할 수 있습니다. 최고의 성능을 얻는 것은 좀 더 복잡합니다. comp와 int64는 동일한 포맷을 가지고 있으므로 둘 사이의 변환이 자유롭습니다. 이것을 이용하면 정수 기반의 곱셈을 부동소수점 곱셈으로 바꿔 계산할 수 있습니다. 아래에서 그 예를 보시죠.

위에서 CA를 사용한 것은 부동소수점수로 연산을 하기 위한 것입니다. 전체 항을 부동소수점으로 계산하도록 강제하기 위해서는 부동소수점 타입은 하나만 있으면 됩니다. 하지만, 항이 여러개일 때는 각각에 대해 부동소수점 변수가 필요합니다.

 

나눗셈에 사용되었던 trunc 대신 round가 사용되었다는 점도 눈여겨 봅시다. 표현식 내에서 정수로 다시 변환하는 것도 가능하겠지만,
round 내에서 덧셈을 두세번씩 하는 경우가 아니라면 일반적으로 속도를 증가시키지 못합니다.

3 comments for “델파이 최적화 가이드라인 (2) – 정수 가이드라인

  1. (2) 정수 최적화 가이드라인

    스타일 가이드라인

    가능한 한 32비트 변수를 사용하라

    델파이 2 이후 버전에서 개발된 코드처럼 32비트 코드에서는 32비트 크기를 갖는 값이 모든 면에서 더 낫습니다. 16비트 변수(Word, ShortInt, WideChar)

답글 남기기

이메일 주소는 공개되지 않습니다.