252004 11 25 09 47 12Chap26 Techniques

33 %
67 %
Information about 252004 11 25 09 47 12Chap26 Techniques
Education

Published on February 20, 2008

Author: Manfred

Source: authorstream.com

CODE COMPLETE 26. Code-Tuning Techniques:  CODE COMPLETE 26. Code-Tuning Techniques 2004.11.18 박치민 Table of Contents:  Table of Contents Introduction Logic Loops Data Transformations Expressions Routines Recoding in a Low-Level Language The More Things Change, the More They Stay the Same Introduction:  Introduction 튜닝의 목표 속도를 높이거나, 크기를 줄인다. 작은 부분을 변화 시켜서 속도를 올리는데 중점을 둔다. 주의사항 복사해서 쓸 수 있는 예제가 아닌, 방법을 일러주는 예제이다. 대부분이 바로 복사해서 쓸 만큼 일반적이지는 않는다. 시도해 볼만한 것들을 제시한다.->측정 필요하다. Logic(1/5):  Logic(1/5) 논리적인 부분을 조작하여서 성능을 향상시킨다. Stop Testing When You Know the Answer 결과를 알아낸 이후에 불필요한 처리를 하지 말아라 Short-circuit evaluation: 필요한 것까지만 평가한다. C++’s standard operators Java’s “conditional” operators c.f.) 19.1 “Knowing How Boolean Expressions Are Evaluated” 조건이 만족하면 반복문을 중지한다. For( I = 0; I < count; I++ ) { if( input[ I ] < 0 ) negativeFound = true; } 음수를 찾았으면 break를 하거나 goto로 분기 if ( 5 < x ) and ( x < 10 ) then … if ( 5 < x ) then if ( x < 10 ) then … Logic(2/5):  Logic(2/5) Order Test by Frequency (Visual Basic 소스) Select ch Case “+”, “=“ ProcessMathSymbol( ch ) Case “0” To “9” ProcessDigit( ch ) Case “A” To “Z”, “a” To “z” ProcessAlpha( ch ) Case Else Error() End Select C/C++, Java 는 이런 형태의 구문이 안됨 Logic(3/5):  Logic(3/5) Compare Performance of Similar Logic Structures 언어에 따라 툴에 따라 비슷한 구문도 다른 성능을 나타낸다. 믿을 수 있는 것은 측정된 결과 뿐이다. Logic(4/5):  Logic(4/5) Substitute Table Lookups for Complicated Expressions 복잡한 관계를 테이블로 정리하라 0 1 3 2 2 2 1 1 A B C If ( ( a && !c ) || ( a && b && c ) ) category = 1; Else if ( ( b && !a ) || ( a && c && !b ) ) category = 2; Else if ( c && !a && !b ) category = 3; Else category = 0 Static int categoryTable[ 2 ][ 2 ][ 2 ] = { // !b!c !bc b!c bc 0, 3, 2, 2, // !a 1, 2, 1, 1 // a }; … Category = categoryTable[ a ][ b ][ c ]; Logic(5/5):  Logic(5/5) Use Lazy Evaluation 기다리다 보면 해야 할 일만 남는다. 데이타를 시작 시점에 읽어 들임으로 인해 쓰지도 않는 데이타 로딩에 시간을 빼앗기는 것 보다, 필요한 상황까지 기다렸다가 로딩을 하는 것이 낭비가 적다. Loops(1/7):  Loops(1/7) Unswitching for ( I = 0; I < count; i++ ) { if ( sumType == SUMTYPE_NET ) netSum = netSum + amount[ I ]; else grossSum = grossSum + amount[ I ]; } if ( sumType == SUMTYPE_NET ) for ( I = 0; I < count; i++ ) netSum = netSum + amount[ I ]; else for ( I = 0; I < count; i++ ) grossSum = grossSum + amount[ I ]; 매 반복마다 불필요한 체크 수행 별 차이 없음 [코드 단편화 작업] 코드 품질과 성능을 맞바꾼다. Loops(2/7):  Loops(2/7) Jamming For I = 0 to count -1 Name( I ) = “” Next …. For I = 0 to count -1 Earning( I ) = 0 Next For I = 0 to count -1 Name( I ) = “” Earning( I ) = 0 Next 두 개의 루프를 하나의 루프로 합침 Loops(3/7):  Loops(3/7) Unrolling i = 0; While ( I < count ) { a[ I ] = I; I = I + 1; } I = 0; While ( I < count – 1 ) { a[ I ] = I; a[ I + 1 ] = I + 1; I = I + 2; } If ( I == count ) a[ count – 1 ] = count – 1; 한번에 2개씩 처리한다. 풀어줬을 때 큰 효과가 없으면 적당한 선에서 그만 두는 것이 좋다. 풀어줄수록 가독성이 떨어지기 때문이다. Loops(4/7):  Loops(4/7) Minimizing the Work Inside Loops For( I = 0; I < count; i++ ) netRate[ I ] = baseRate[ I ] * rates->discounts->factors->net; Discount = rates->discounts->factors->net; For( I = 0; I < count; i++ ) netRate[ I ] = baseRate[ I ] * Discount; 루프 안에서 할 작업을 최소화 Java를 제외하고는 큰 성능 향상이 없었지만, 가독성도 같이 증가하기 때문에 이 기교를 적용해 주는 것이 좋다. Loops(5/7):  Loops(5/7) Sentinel Values found = false; I = 0; while ( ( !found ) && ( I < count ) ) { if ( item[ I ] == testValue ) found = true; else I++; } if ( found ) { … initialValue = item[ count ]; item[ count ] = testValue; I = 0; while( item[ I ] != testValue ) { I++; } if ( I < count ) { … 파수병(testValue)를 삽입한다 Loops(6/7):  Loops(6/7) Putting the Busiest Loop on the Inside 이중 반복문에서 안쪽 반복문의 초기화 작업이 바깥 반복문의 횟수만큼 발생한다. for ( column = 0; column < 100; column++ ) { for ( row = 0; row < 5; row++ ) sum = sum + table[ row ] [ column ]; } for ( row = 0; row < 5; row++ ) for ( column = 0; column < 100; column++ ) { sum = sum + table[ row ] [ column ]; } Loops(7/7):  Loops(7/7) Strength Reduction for I = 0 to count – 1 commission( I ) = (I + 1) * revenue * baseCommission * discount Next incrementalCommission = revenue * baseCommission * discount cumulativeCommission = incrementalCommission for I = 0 to count – 1 commission( I ) = cumulativeCommission cumulativeCommission = cumulativeCommission + incrementalCommission Next I+1만큼 곱하는 것을 누적해서 더하는 방식으로 바꾸었다. Data Transformations(1/5):  Data Transformations(1/5) Use Integers Rather Than Floating-Point Numbers Dim x As Single For x = 0 to 99 a( x ) = 0 Next Dim I As Integer For x = 0 to 99 a( I ) = 0 Next 단정도 부동소수점을 정수형으로 바꾸었다. Data Transformations(2/5):  Data Transformations(2/5) Use the Fewest Array Dimensions Possible for ( row = 0; row < numRows; row++ ) { for ( column = 0; column < numColumns; column++ ) matrix[ row ][ column ] = 0; } for ( entry = 0; entry < numRows * numColumns ; entry++ ) { matrix[ entry ] = 0; } Data Transformations(3/5):  Data Transformations(3/5) Minimize Array References for ( discountType = 0; discountType < typeCount; discountType++ ) { for ( discountLevel = 0; discountLevel < levelCount; discountLevel++ ) rate[ discountLevel ] = rate[ discountLevel ] * discount[ discountType ]; } for ( discountType = 0; discountType < typeCount; discountType++ ) { thisDiscount = discount[ discountType ]; for ( discountLevel = 0; discountLevel < levelCount; discountLevel++ ) rate[ discountLevel ] = rate[ discountLevel ] * thisDiscount; } 내부 반복문 안에서 바뀌지 않는 discount[ discountType ]를 변수로 바꿈 C++인데 드물게도 성능 감소 Data Transformations(4/5):  Data Transformations(4/5) Use Supplementary Indexes 원하는 데이타에 좀 더 쉽게 접근할 수 있는 부가적인 index String-Length Index string의 길이를 구할 때와 같이, 가변길이 데이타에 대하여 그 길이를 계속적으로 관리하는 변수를 추가함으로써 매번 길이를 새로 계산하는 비용을 줄인다. Independent, Parallel Index Structure 데이타를 이동시키는 것이 아닌 데이타에 대한 인덱스를 이동시킨다. sorting이나 searching등에서 사용한다. Data Transformations(5/5):  Data Transformations(5/5) Use Caching double Hypotenuse( double sideA, double sideB ) { return Math.sqrt( (sideA * sideA ) + ( sideB * sideB ) ); } private double cachedHypotenuse = 0; private double cachedSideA = 0; private double cachedSideB = 0; public double Hypotenuse( double sideA, double sideB ) { if( ( sideA == cachedSideA ) && ( sideB == cachedSideB ) ) return cachedHypotenuse; cachedHypotenuse = Math.sqrt( (sideA * sideA ) + ( sideB * sideB ) ); cachedSideA = sideA; cachedSideB = sideB; return cachedHypotenuse; } Expressions(1/9):  Expressions(1/9) “복잡한 표현은 비싸다” Exploit Algebraic Identities “not a and not b”보다 “not (a or b)”가 좋다. sqrt(x) < sqrt(y)를 그냥 비교하는 것 보다. x < y인 경우에만 그것을 비교하는 것이 좋다. Expressions(2/9):  Expressions(2/9) Use Strength Reduction 일반적인 기법들 곱하기를 더하기로 대체한다.(앞에서 나왔다.) 지수승을 곱하기로 대체한다. trigonometric(삼각) 루틴을 그들의 trigonometric identity로 대체한다. longlong 정수를 longs나 ints로 바꾼다. 단, native-length를 사용할 때와 non-native-length를 사용할 때의 성능 평가를 해둔다.) 부동소수점을 고정소수점 숫자나 정수로 바꾼다. 배정도 부동소수점을 단정도 부동소수점으로 바꾼다. 정수에 대한 2의 배수 곱샘/나눗샘을 shift연산자로 바꾼다. Expressions(3/9):  Expressions(3/9) value = coefficient( 0 ) For power = 1 To order value = value + coefficient( power ) * x^power Next value = coefficient( 0 ) powerOfX = x For power = 1 To order value = value + coefficient( power ) * powerOfX powerOfX = powerOfX * x Next value = 0 For power = order to 1 step -1 value = ( value + coefficient( power ) ) * x Next value = value + coefficient( 0 ) VB에서 -1로 루프 도는 게 성능을 감소시킨다? -> YES. 측정해보는 수 밖에 없다. Expressions(4/9):  Expressions(4/9) Initialize at Compile Time named constant나 magic number가 사용되는 경우 다음은 밑이 10인 로그함수만 사용 가능한 경우의 예제이다. unsigned int Log2( unsigned int x ) { return (unsigned int) ( log( x ) / log( 2 ) ); } const double LOG2 = 0.69314718; … unsigned int Log2( unsigned int x ) { return (unsigned int) ( log( x ) / LOG2 ); } Expressions(5/9):  Expressions(5/9) Be Wary of System Routines 기존에 제공되는 함수들은 필요 이상으로 정확하게 계산하는 경우가 있다. 그 후 그 미세한 값들은 버리게 된다. int값을 반환하는 Log2()가 필요한 경우 기존 float형을 반환하는 Log2()의 정확도가 필요 없으므로 재 작성하여 많은 시간을 줄일 수 있다. unsigned int Log2( unsigned int x ) { if ( x < 2 ) return 0; if ( x < 4 ) return 1; if ( x < 8 ) return 2; … if ( x < 2147483648 ) return 30; return 31; } unsigned int Log2( unsigned int x ) { unsigned int I = 0; while ( ( x = ( x >> 1 ) ) != 0 ) i++; return I; } 2.4초 걸린다. 그러나 32-bit, 64-bit머신 등에 적용하기 쉽다. Expressions(6/9):  Expressions(6/9) Use the Correct Type of Constants 상수를 설정할 때 잘못된 상수를 설정하여서 형 변환이 일어나는 경우를 없앤다. float x; int I; x = 5; I = 3.14; float x; int I; x = 3.14; I = 5; Expressions(7/9):  Expressions(7/9) Precompute Results 사용될 계산값이 예상 가능한 적은 개수이면 미리 계산해둔다. loanDivisor를 미리 계산함으로써 복잡한 계산 시간을 줄인다. 이자율은 5~20범위에 0.25단위(61개 변위) 기간은 12~72개월(61개 변위) double computePayment ( long loanAmount, int months, double interestRate ) { return loanAmount / ( (1.0 – Math.pow( ( 1.0 + (interestRate / 12.0 ) , -months ) )/ ( interestRate / 12.0 ) ); } double computePayment ( long loanAmount, int months, double interestRate ) { int interestIndex = Math.round( ( interestRate – LOWEST_RATE ) * GRANULARITY * 100.00 ); return loanAmount / loanDivisor[ interestIndex ][ months ]; } Expressions(8/9):  Expressions(8/9) precomputation을 처리하는 형태 실행전에 계산해서, 컴파일시에 상수값으로 사용 실행전에 계산해서, 하드코딩함 실행전에 계산해서, 파일에 기록한 후에 이 파일을 읽어서 사용 시작때 한번 계산해서 이후 그 값을 사용 루프 전에 가능한 많이 계산해 두고, 루프 안에서의 계산을 줄임 값이 필요한 최초 시점에 계산한 후에, 이것을 사용(caching) Expressions(9/9):  Expressions(9/9) Eliminate Common Subexpressions 공통되는 계산을 빼내서 한번만 계산한다. payment = loanAmount / ( (1.0 – Math.pow( ( 1.0 + (interestRate / 12.0 ) , -months ) )/ ( interestRate / 12.0 ) ); monthlyInterest = interestRate / 12.0; payment = loanAmount / ( (1.0 – Math.pow( ( 1.0 + monthlyInterest, -months ) )/ monthlyInterest ); 컴파일러가 이미 Subexpressions을 했을 수도 있다. Routines:  Routines 나뉘어 있는 루틴이 관리하거나 튜닝하기 쉽다. Rewrite Routines Inline 초기에는 호출 비용이 컸었다. 현재는 이 비용이 많이 줄어서 큰 차이가 없을 수도 있다. Recoding in a Low-Level Language(1/3):  Recoding in a Low-Level Language(1/3) 일반적인 Low-Level Language 적용 순서 전체를 high-level 언어를 써서 완전하게 작성한다. 전체를 테스트 해서 정확하게 돌아가는 것을 검증한다. 프로파일러로 hot spot을 검출한다. 일반적으로 코드의 5%가 성능의 50%를 잡아먹으므로 작은 부분만이 hot spot으로 검출될 것이다. 작은 부분만을 low-level 언어로 작성한다. 효과는 있다! DES 구현에서, 저자가 아는 모든 튜닝기법을 적용한 후에 마지막 선택으로, 기초적은 어셈블리 실력을 갖고 어셈을 적용 후 50%의 성능 향상을 얻었다. Recoding in a Low-Level Language(2/3):  Recoding in a Low-Level Language(2/3) procedure HexExpand( var source: ByteArray; var target: WordArray; byteCount: word ); var index: integer; lowByte: byte; upperByte: byte; targetIndex: integer; begin targetIndex := 1; for index := 1 to byteCount do begin target[ targetIndex ] := ( (source[ index ] and $F0) shr 4 ) + $41; target[ targetIndex+1 ] := (source[ index ] and $0f) + $41; targetIndex := targetIndex + 2; end; end; Recoding in a Low-Level Language(3/3):  Recoding in a Low-Level Language(3/3) procedure HexExpand( var source; var target; byteCount: Integer ); label EXPAND; asm MOV ECX, byteCount // load number of bytes to expand MOV ESI, source // source offset MOV EDI, target // target offset XOR EAX, EAX // zero out array offset EXPAND: MOV EBX, EAX // array offset MOV DL, [ESI+EBX] // get source byte MOV DH, DL // copy source byte AND DH, $F // get msbs ADD DH, $41 // add 65 to make upper case SHR DL, 4 // move lsbs into position AND DL, $F // get lsbs ADD DL, $41 // add 65 to make upper case SHL BX, 1 // double offset for target array offset MOV [EDI+EBX], DX // put target word INC EAX // increment array offset LOOP EXPAND // repeat until finished end; The More Things Changes, the More They Stay the Same:  The More Things Changes, the More They Stay the Same 1판을 낼 때에 비해서 속도나 메모리가 많이 증가했다. PC에서, 측정할만한 값을 얻기 위해서, 첫판에서 1만~5만번 반복하던 것을 1백만~1억 번을 반복했다. 1억번이나 돌려야 값이 차이나는 것을 튜닝할 필요가 있을까? -> 대부분의 경우에 필요 없다. 임베디드, 실시간, 제한된 시간/공간의 환경 등에선 필요하다. 코드 튜닝은 복잡도, 가독성, 단순성, 관리용이성 등을 희생하게 된다. 프로파일러에 의미있는 정도로 검출는 부분에 대해서만 튜닝을 한다. Additional Resources:  Additional Resources Writing Efficient Programs (Bentley) A Sourcebook for Fast 32-bit Software Development, 1997 Software Optimization Cookbook: High-Performance Recipes for the Intel Architecture, 2002 Performance Tuning and Optimizing ASP.NET Applications. 2003 Web Performance Tuning. 2002 Java2 Performance and Idiom Guide. 2000 Java Performance Tuning. 2000 Java Platform Performance: Strategies and Tactics.2000 Checklist:  Checklist Improve Both Speed and Size Substitute table lookups for complicated logic Jam loops Use integer instead of floating-point variables Initialize data at compile time Use constants of the correct type Precompute results Eliminate common sub expressions Translate key routines to a low-level language Checklist:  Checklist Improve Speed Only Stop testing when you know the answer. Order tests in case statements and if-then-else chains by frequency. Compare performance of similar logic structures. Use lazy evaluation. Unswitch loops that contain if tests. Unroll loops. Minimize work performed inside loops. Use sentinels in search loops. Put the busiest loop on the inside of nested loops. Checklist:  Checklist Reduce the strength of operations performed inside loops. Change multiple-dimension arrays to a single dimension. Minimize array references. Augment data types with indexes. Cache frequently used values. Exploit algebraic identities. Reduce strength in logical and mathematical expressions. Be wary of system routines. Rewrite routines inline.

Add a comment

Related presentations

Related pages

Great Pianists' Technique: Agility - YouTube

Great Pianists' Technique: Agility ... 47) Op81a 1:25:09 Gulda ... 11:33. Thomas Lemmon 1,919 views. 11:33 Hanon ...
Read more

09 - Immortal Technique - Reverse Pimpology feat. mojo ...

09 - Immortal Technique - Reverse Pimpology feat. mojo. ... 25. revolutionarytech ... 11 - Immortal Technique ...
Read more

Ergebnisse der Landtagswahlen in der Bundesrepublik ...

25.11.1962: 76,5: 47,5: ... 25.09.1983: 79,7: 51,3: 33,3: 6 9,2 6: 4,6: 1,6: 13.09.1987: 75,6: 50,5: 23,4: ... 11: 6: 25: 2004: 121: 41: 63: 17: 2008: 121 ...
Read more

Kyōiku (album) - Wikipedia, the free encyclopedia

November 25, 2004 () (see release history) Recorded ... wrote the songs as "love letters" to each members' techniques, ... 09. 駅前 A Station: 05. ...
Read more

Baker Bettie | baking techniques, science, and recipes ...

Baker Bettie Baker Bettie Navigation. Home; Blog- Recent Posts; Recipe Index. Sweets. Bars; Brownies; Cakes. ... baking techniques, science, and recipes ...
Read more

47 CFR Ch. I (10-1-04 Edition) Federal Communications ...

Thus, 47 CFR 73.1 refers to title 47, part 73, section 1. Explanation. ... 1964-1972, 1973-1985, or 1986-2000, published in 11 separate volumes.
Read more

Powerball Past Winning Numbers in the Order Drawn

Powerball historical results in the order drawn from the Wisconsin Lottery ... May 09, 2012: 56: 7: 1: 11: 55: 1: X: ... 25: 47: 34: 5: 3X:
Read more

NYX, round lipstick items in JOY's cosmetics store on eBay!

Buy JOY's cosmetics, ... Sep-22 09:53. 1 REAL TECHNIQUES ... Aug-25 11:47. 1 REAL TECHNIQUES ...
Read more

List of Modern Marvels episodes - Wikipedia, the free ...

List of Modern Marvels episodes ... August 25, 2004 () 11-34 "George Washington Bridge" ... 11-47 "Guns of Israel"
Read more

Active_TM- Army Doctrine and Training Publications

Doctrine and Training Publications. FMs, STPs, TCs & TMs (except engineering & medical). For the Army Techniques Publications Wiki . Additional Doctrine ...
Read more