Kori 11월 16일, 2020에 포스트됨 공유하기 11월 16일, 2020에 포스트됨 << DelphiCon 2020 목록으로 이동 DelphiCon 의 2020 시리즈 중, High Performance Delphi - Primož Gabrijelčič 의 한글 요약본입니다. 델파이 고성능 구현 ‘Delphi High Performance’ 도서 저자가 직접 성능 개선을 데모와 함께 설명합니다. 발표자 (Primož Gabrijelčič)는 1980년대 8비트 시절부터 파스칼 코드를 써오고 있습니다. 주로 방송용 고가용성 서버 프로그램을 개발하고 있으며, 수준높은 주제를 다루는 수많은 기고를 해오고 있습니다. (발표자의 웹페이지: http://thedelphigeek.com) 발표자가 저술한 도서 디자인 패턴을 델파이에서 실습하기 델파이 고성능 구현 (Delphi High Performance) 옴니쓰레드라이브러리를 활용한 병렬 프로그래밍 (Parallel programming with OmniThreadLibrary) 원본 비디오(YouTube) 보기 (56 min)를 권장합니다 목차 성능 향상 개요 알고리즘 향상 알고리즘 복잡도와 성능 빅오(Big-O) 표기법 알고리즘 별로 데이터 증가와 복잡도(성능 저하)의 관계를 파악 더 좋은 알고리즘으로 바꾸기 예제: 무작위 단어 검색 프로그램의 성능을 향상해보자 알고리즘 별로 성능 차이 비교 개선 전: 정렬되지 않은 TStringList 검색 개선 1: 정렬된 TStringList 검색 개선 2: TDictionary 검색 개선 3: 글자 수별로 TStringList를 따로 만들고, 이 TStringList를 다시 오브젝트 리스트에 모아두고 사용하기 코드가 지나치게 많이 실행되는 것을 방지하기 예제: 2GB 파일을 1KB 단위로 읽고, 진행률을 표시하는 프로그램을 개선해보자 개선 전(흔한 코드): “화면에 진행율을 표현하는 코드”가 성능을 크게 떨어뜨리고 있었다. 개선 후(화면 업데이트를 필요한 만큼만 실행): “화면에 진행율을 표현하는 코드”는 100번만 실행하면 충분하다. 예제: TListBox와 TMemo에 각각 항목을 10,000 개씩 넣는 프로그램을 개선해보자. 코드 개선 전/후의 소요 시간 비교표 개선 전: 10,000 항목 x 2개 컨트롤 = 20,000번 윈도우와 메시지 교환 개선 1: 루프 앞뒤에 BeginUpdate와 EndUpdate 호출하여 윈도우와 메시지 교환을 2번으로 줄인다. 개선 2.1-TMemo: 해당 루프 안에서는 항목을 화면을 사용하지 않는 오브젝트인 TStringList에 넣고, 루프 밖에서 TStringList를 TMemo에 바인딩하여 모든 항목을 한번에 넣기 개선 2.2-TListBox를 가상 모드로 사용하여 필요할 때 데이터를 추가하기 불필요한 코드 실행 없애기 예제: (캐싱) 지역변수를 활용한 캐싱 예제: 피노나치 수열 계산 프로그램 개선하기 개선 전 (기존 코드): 피보나치 수열을 계산 수학식을 그대로 코드에 넣으면 심각한 성능 문제가 발생 개선1(캐싱): 재귀 호출을 하되, 적어도 동일한 연산은 반복하지 않도록 한번 연산된 것은 결과를 캐시(저장)해 두었다가 재사용 하자. 개선2: 재귀 호출 알고리즘을 순차적 반복 호출 알고리즘으로 바꾸어서 해소 알고리즘 향상에 관심이 있는 개발자에게 권장하는 자료 성능 향상 개요 ‘성능 향상 작업’을 하는 순서 (’성능 향상’이 의미하는 바는 사람들마다 다를 수 있지만, 순서는 거의 같다.) 문제 식별 (‘측정’이 중요하다!) TStopwatch, 성능 카운터, GetTickCount 등을 활용하여 명시적으로 측정하자. AQTime 등 전문 프로파일링 도구를 사용하는 것도 좋다. ‘알고리즘 향상’: 가장 좋은 방법! 이 세션에서 다룰 내용이다! 세부적인 코드 튜닝 병렬 처리 적용 외부 라이브러리 사용 더 좋은 알고리즘을 제공하는 라이브러리를 도입하여 빠르게 문제 해결 가능. 주의할 점: 외부 라이브러리 제작자가 유지보수를 하지 않는 상황에 대한 대비가 필요 (성능 향상이 필요한 특정 부분을) 어셈블리어와 같은 저수준 언어로 대체 주의할 점: 10년 후에는 지금보다도 저수준 언어 개발자 찾기가 더 어려워 진다는 점을 고려해야 함 알고리즘 향상 알고리즘의 복잡도와 성능 빅오(Big-O) 표기법 알고리즘 별로 데이터 증가와 복잡도(성능 저하)의 관계를 파악 성능 향상 방법 더 좋은 알고리즘으로 바꾸기 코드가 불필요하게 많이 실행되는 상황을 찾아서, 실행 횟수를 줄이기 코드가 실행하지 않아도 되는 상황을 찾아서, 실행되지 않도록 하기 알고리즘 복잡도와 성능 빅오(Big-O) 표기법 컴퓨터 과학에서 빅 O 표기법은 입력 크기가 커짐에 따라 실행 시간 또는 공간 요구 사항이 어떻게 증가하는 지를 파악함으로써 알고리즘을 분류하는 데 사용된다. 데이터가 증가할 수록 프로그램의 속도가 얼마나 느려지는 지를 판단할 때에도 유용하다. 프로그램의 성능 문제는 데이터가 많아지면서 발생되는 경향이 크다. 관련 웹페이지 추천: 알고리즘 별 복잡도가 잘 정리된 웹 문서: http://bigocheatsheet.com 다양한 데이터 구조를 자세히 비교한 웹 문서: https://geeksforgeeks.org/data-structures 알고리즘 별로 데이터 증가와 복잡도(성능 저하)의 관계를 파악 O(1)은 데이터가 아무리 증가해도 성능이 저하되지 않는다. 반면에, 피보나치 수열 재귀호출은 복잡도 즉 성능이 급격하게 저하된다 (역자 주: 재귀 호출은 매우 강력하지만, 코딩에 적용하기 전에 주의해야 합니다. 뒤에서 재귀 호출과 관련된 예시와 개선 방향이 제시됩니다) 더 좋은 알고리즘으로 바꾸기 예제: 무작위 단어 검색 프로그램의 성능을 향상해보자 (비디오 13분 30초부터 보기) 프로그램: 글자수가 주어지면,그 글자수에 해당하는 영어 단어를 무작위로 만들고, 37만개 단어가 들어있는 목록 안에 있는 단어인지를 알려준다. 모든 목록은 동일한 파일(37만 단어)을 읽어서 만든다. 목록 생성은 한번만 실행되면 되지만, 검색은 훨씬 더 많이 실행된다는 점을 고려하자. 알고리즘 별로 성능 차이 비교 알고리즘 글자수 증가에 따른 결과 비고 일반적인 코드 정렬되지 않은 TStringList 검색 4글자 단어까지는 1초 이내 완료 5글자 단어는 1초 이상 소요 6글자 단어부터는 시간 초과 IndexOf 함수에서 RTL은 순차 탐색을 한다.: O(n)에 해당 최악의 경우, 37만번째 단어까지 찾아봐야 결과를 알 수 있다. 개선1 정렬된 TStringList 검색 6글자 단어까지는 1초 이내 완료 7글자 단어는 1초 이상 소요 8글자 단어부터는 시간 초과 IndexOf 함수에서 RTL은이분 탐색을 한다: O(log n)에 해당 정열된 StringList는 처음 만드는데 걸리는 시간은 더 길지만, 검색 속도는 더 빠르다. 개선2 TDictionary 사용 7글자 단어까지는 1초 이내 완료 8글자 단어는 1초 이상 소요 9글자 단어부터는 시간 초과 델파이 Disctionary의 ContainsKey 함수는 Array보다 검색이 빠르지는 않지만, 목록이 클 경우StringGrid의 IndexOf 함수보다는 검색이 빠르다. 개선3 글자 수 별로 TStringList를 따로 만들어서 사용 글자수와 관계없이 1초 이내 완료 성능 개선을 위한 알고리즘을 창의적으로 만들자. 검색 시에는 해당 글자수에 맞는 TStringList를 찾고 그 안에서만 검색한다. 개선 전: 정렬되지 않은 TStringList 검색 // 목록을 생성하는 코드 FWordsUnsorted := TStringList.Create; FWordsUnsorted.Assigned(wordList); … // 목록 안을 검색하는 코드 FindGoodWord ( function (const word: string): boolean begin Result := FWordsUnsorted.IndexOf(word) >= 0; end); 개선 1: 정렬된 TStringList 검색 // 목록을 생성하는 코드 FWordsSorted := TStringList.Create; FWordsSorted.Assigned(wordList); FWordsSorted.Sorted := True; … // 목록 안을 검색하는 코드 FindGoodWord ( function (const word: string): boolean begin Result := FWordsSorted.IndexOf(word) >= 0; end); 개선 2: TDictionary 검색 // 목록을 생성하는 코드 FWordsDictionary := TDictionary.Create(wordList.Count); for word in wordList do FWordsDictionary.Add(word, True); //Key에 단어를 넣고, Value에는 그냥 True로 모두 넣는다. … // 목록 안을 검색하는 코드 FindGoodWord ( function (const word: string): boolean begin Result := FWordsDictionary.ContainsKey(word) >= 0; end); 개선 3: 글자 수별로 TStringList를 따로 만들고, 이 TStringList를 다시 오브젝트 리스트에 모아두고 사용하기 // 목록을 생성하는 코드 FWordsLOL := TObjectList.Create; FWordsLOL.Add(nil); for word in wordList do begin while FWordsLOL.Count <= Length(word) do FWordsLOL.Add(TStringList.Create); FWordsLOL[Length(word)].Add(word); end; … // 목록 안을 검색하는 코드 wordLen := inpWordLength.Value; if (wordLen < 1) or (wordLen >= FWordsLOL.Count) then //글자수에 해당하는 목록 자체가 없으면 검색할 필요도 없다. idx := -1 else //글자수에 해당하는 목록이 있으면, 해당 검색할 문자를 만들고, 해당 글자수로 된 단어를 모아둔 리스트에서 검색한다. idx := Random(FWordsLOL[wordLen].Count); if (idx >= 0) and (idx < FWordsLOL[wordLen].Count) then lbWords.ItemIndex := lbWords.Items.Add(Format('%s (%d ms)', [FWordsLOL[wordLen][idx], time.ElapsedMilliseconds])) else lbWords.ItemIndex := lbWords.Items.Add(Format('No such word (%d ms)', [time.ElapsedMilliseconds])); 코드가 지나치게 많이 실행되는 것을 방지하기 (일반적인 GUI 프로그램에서는) 초당 수천번씩 화면을 업데이트하지 말자. 루프 앞뒤에 BeginUpdate와 EndUpdate 호출하여 윈도우와 메시지 교환을 최소화하자. (멀티 쓰레드 사용 시) 초당 수백만번 씩 운영체제에 메시지를 보내지 말자. 예제: 2GB 파일을 1KB 단위로 읽고, 진행률을 표시하는 프로그램을 개선해보자 개선 전(흔한 코드): “화면에 진행율을 표현하는 코드”가 성능을 크게 떨어뜨리고 있었다. ProgressBar1.Max := CFileSize; ProgressBar1.Position := 0; total := 0; while total < CFileSize do begin block := CFileSize - total; if block > 1024 then block := 1024; … // 해당 1KB짜리 'block’을 읽는 코드 Inc(total, block); ProgressBar1.Position := total; ProgressBar1.Update; //문제 지점!!!: 2백만번이나 화면을 업데이트하고 있었다 (여기를 주석처리하고 실행하면 훨씬 빨라진다) end; 개선 후(화면 업데이트를 필요한 만큼만 실행): “화면에 진행율을 표현하는 코드”는 100번만 실행하면 충분하다. ProgressBar1.Max := 100; ProgressBar1.Position := 0; lastPct := 0; total := 0; while total < CFileSize do begin block := CFileSize - total; if block > 1024 then block := 1024; … // 해당 1KB짜리 'block’을 읽는 코드 Inc(total, block); // 문제 지점을 해소하자. currPct := Round(total / CFileSize * 100); //백분율을 미리 계산하고 if currPct > lastPct then //1% 단위로만 (총 100번) 화면 업데이트 begin lastPct := currPct; ProgressBar1.Position := currPct; ProgressBar1.Update; end; end; 예제: TListBox와 TMemo에 각각 항목을 10,000 개씩 넣는 프로그램을 개선해보자. UI 컨트롤에 항목을 하나씩 추가한다는 것은 그만큼 프로그램과 윈도우 운영체제가 서로 메시지를 주고 받는다는 의미이다. 그 횟수를 줄이자. 코드 개선 전/후의 소요 시간 비교표 코드 (컨트롤에 10,000개 항목 추가) TListBox 실행 시간 TMemo 실행 시간 일반적인 코드 루프 안에서 컨트롤에 항목을 추가 7초 28초 개선1 해당 루프 앞뒤에 BeginUpdate와 EndUpdate 호출 0.5초 3초 개선2-TMemo 해당 루프 안에서는 화면을 사용하지 않는 TStringList에 항목을 여기에 넣고 루프 밖에서 TStringList를 컨트롤에 바인딩하여 모든 항목을 한번에 넣기 (해당 없음) 0.2초 개선2-TListBox 가상 리스트 박스 사용 (이것은 불필요한 코드 실행 없애기에서 따로 설명) 0.003초 (해당 없음) 개선 전: 10,000 항목 x 2개 컨트롤 = 20,000번 윈도우와 메시지 교환 for i := 1 to CNumLines do Memo1.Lines.Add('Line ' + IntToStr(i)); for i := 1 to CNumLines do ListBox1.Items.Add('Line ' + IntToStr(i)); 개선 1: 루프 앞뒤에 BeginUpdate와 EndUpdate 호출하여 윈도우와 메시지 교환을 2번으로 줄인다. 델파이는 (뭔가 변경을 시작할께요 라는 표시인) BeginUpdate 코드를 만나면 윈도우 운영체제에 메시지를 보내는 작업을 중단하고, (프로그램이 변경이 다 끝났어요 라는 표시인) EndUpdate를 만나면) 윈도우에 메시지를 보낸다. // [BeginUpdate, EndUpdate만 사용해도 성능이 개선된다] // TMemo는 (10,000 개 항목인 경우 기존 28초에서 3초로 속도가 향상됨) Memo1.Lines.BeginUpdate; for i := 1 to CNumLines do Memo1.Lines.Add('Line ' + IntToStr(i)); Memo1.Lines.EndUpdate; // TListBox는 (10,000 개 항목인 경우 기존 7초에서 0.5초로 속도가 향상됨) ListBox1.Items.BeginUpdate; for i := 1 to CNumLines do ListBox1.Items.Add('Line ' + IntToStr(i)); ListBox1.Items.EndUpdate; 개선 2.1-TMemo: 해당 루프 안에서는 항목을 화면을 사용하지 않는 오브젝트인 TStringList에 넣고, 루프 밖에서 TStringList를 TMemo에 바인딩하여 모든 항목을 한번에 넣기 (비디오 34분 45초부터 보기) // 루프 안에서는 TStringList에 항목을 넣는다. sl := TStringList.Create; for i := 1 to CNumLines do sl.Add('Line ' + IntToStr(i)); Memo1.Text := sl.Text; FreeAndNil(sl); // TMemo에는 루프 밖에서 한번에 넣는다. 개선 2.2-TListBox를 가상 모드로 사용하여 필요할 때 데이터를 추가하기 리스트박스에 항목이 10,000 개 있어도, 실제로 화면에서 한번에 표시되는 항목은 18개이다. 다른 항목을 보려면 스크롤해야 보인다. 따라서, 그렇다면 스크롤에 맞는 항목만 즉시 제공할 수 있다면, 10,000개 항목을 미리 가지고 있는 것과 사용자에게는 다를 바가 없다. 그렇게 한 결과, 같은 기능을 가진 리스트박스가 0.007초 만에 실행됨 가상 리스트박스 구현 방법 TListbox 설정 변경 프로퍼티: Style 프로퍼티를 lbVirtual로 변경 (기본값은 lbStandard) 이벤트: OnData, OnDataFind, OnDataObject 구현 OnData: 리스트박스에 값이 제공되는 이벤트 OnDataFind: Listbox.Items.IndexOf 함수가 사용될 때 호출되는 이벤트 OnDataObject: 리스트박스에 오브젝트가 들어가 있는 경우 사용한다. (지금은 생략) TListbox를 준비하는 코드와 OnData와 OnDataFind 이벤트를 처리하는 코드 // 10,000개 항목은 TStringList에만 넣어둔다. FList.Capacity := CNumLines; for i := 1 to CNumLines do FList.Add('Line ' + IntToStr(i)); //리스트박스의 항목 갯수는 전체 항목수인 10,000으로 지정한다. ListBox1.Count := CNumLines; //리스트박스는 항목을 표시하려고 할 때, 리스트박스는 OnData 이벤트가 발생하고 표시할 항목의 인덱스 번호를 전달한다. procedure TfrmVirtualListBox.ListBox1Data(Control: TWinControl; Index: Integer; var Data: string); begin Data := FList[Index]; //TStringList의 해당 인덱스에 해당하는 문자열을 반환하여 ListBox에 표현도록 한다. // 실제 호출되는 인덱스를 로그로 남겨서 확인해보자 // 처음에는 18개 항목만, 스크롤 하면 그에 맞는 항목만 가져오는 것을 알 수 있다. //OutputDebugString(PChar(Index.ToString)); //일단 주석처리 함 end; // DataFind 즉, (TListbox).Items.IndexOf([찾고자 하는 값]) 코드가 사용되는 경우를 대비한다. // 리스트박스에는 실제로 항목이 들어있지 않다는 점을 명심하자 function TfrmVirtualListBox.ListBox1DataFind(Control: TWinControl; FindString: string): Integer; begin Result := FList.IndexOf(FindString); //데이터를 실제 가지고 있는 곳인 TStringList의 IndexOf 결과를 반환한다. end; 팁! 이처럼 성능이 문제가 있을 때, 먼저 문제되는 코드를 아예 사용하지 않을 방법이 있는가를 생각해 보자. (이 예제에서는 10,000개 항목을 리스트박스에 넣는 부분을 아예 없애버렸다) 불필요한 코드 실행 없애기 예제: (캐싱) 지역변수를 활용한 캐싱 누구나 알고 있는데도, 실제로는 의외로 많은 코드에서 이런 부분이 간과되어 있는 방식이다. 특히, 값을 계산하거나 가져오는 시간이 오래 걸리는 것일 수록 지역변수를 활용한 캐시 효과는 크다. 앞서 사용한 FindGoodWord 함수에서 사용자가 지정한 단어의 글자수는 코드에서 여러번 사용된다. 개선 전: 글자 수를 매번 TSpinEdit에서 읽어온다 (그만큼 윈도우와 메시지를 교환하게 된다). 개선 후: 대신 한번만 읽고 WordLen이라는 지역변수에 넣고, 코드의 나머지 부분에서는 이 지역 변수를 사용하자. 예제: 피노나치 수열 계산 프로그램 개선하기 개선 전 (기존 코드): 피보나치 수열을 계산 수학식을 그대로 코드에 넣으면 심각한 성능 문제가 발생 피보나치 수열 계산 원리는 재귀 호출이다. 하지만, 프로그래밍에서 그대로 재귀 호출로 구현하는 것은 비효율적이다. 재귀 호출로 인한 성능 문제를 해소하기 위해서는 알고리즘을 개선하는 것이 좋다. // 문제점: (1) 재귀 호출이 되고, (2) 동일한 연산도 여러번 반복된다. function TfrmFibonacci.FibonacciRecursive(element: int64): int64; if element < 3 then Result := 1 else Result := FibonacciRecursive(element - 1) + FibonacciRecursive(element - 2); end; 개선1(캐싱): 재귀 호출을 하되, 적어도 동일한 연산은 반복하지 않도록 한번 연산된 것은 결과를 캐시(저장)해 두었다가 재사용 하자. (비디오 52분 17초부터 보기) 더좋은 알고리즘이 떠오르지 않을 때는 이처럼 캐싱을 검토해보는 것이 좋다. function TfrmFibonacci.FibonacciRecursiveMemorized(element: int64): int64; if FFibonicciTable[element] >= 0 then Result = FFibonicciTable[element] else begin if element < 3 then Result := 1 else Result := FibonacciRecursiveMemorized(element - 1) + FibonacciRecursiveMemorized(element - 2); FFibonicciTable[element+1] := Result; end; 개선2: 재귀 호출 알고리즘을 순차적 반복 호출 알고리즘으로 바꾸어서 해소 (비디오 54분 01초부터 보기) 재귀 호출은 대체로 순차적 반복 호출로 대체할 수 있다. 재귀 호출 시 같은 계산을 반복하지 않으면. 기하급수적인 복잡도 증가가 아니라, 순차적인 복잡도 증가 즉 O(1)이 된다. function TfrmFibonacci.FibonacciIterative(element: int64): int64; var a, b: int64; begin a := 1; b := 0; repeat if element = 1 then Exit(a); b := b + a; if element = 2 then Exit(b); a := a + b; Dec(element, 2); until false; end; GbLists.pas: O(1)을 구현한 캐싱 딕셔너리이며 사용하기도 쉽다: https://github.com/gabr42/GpDelphiUnits 에 있다. 알고리즘 향상에 관심이 있는 개발자에게 권장하는 자료 도서 Julian Bucknall, Algorithms and Data Structures PrimožGabrijelčič, DelphiHighPerformance RobertSedgewick&KevinWayne, Algorithms 웹 Algorithms, 4th Edition, https://algs4.cs.princeton.edu/home/ Udacity,edX,Udemy,Coursera... https:www.geeksforgeeks.org/data-structures/ https:www.geeksforgeeks.org/fundamentals-of-algorithms 포럼 Delphi-PRAXIS: en.delphipraxis.net << DelphiCon 2020 목록으로 이동 View full 엠바카데로 기술자료 인용하기 이 댓글 링크 다른 사이트에 공유하기 더 많은 공유 선택 사항
Recommended Posts
이 토의에 참여하세요
지금 바로 의견을 남길 수 있습니다. 그리고 나서 가입해도 됩니다. 이미 회원이라면, 지금 로그인하고 본인 계정으로 의견을 남기세요.