큰 레코드의 TList를 반복 할 때 긴 지연이 발생했습니다.

Question

Windows 10에서 Delphi 10.1 Berlin을 사용합니다.

크기가 다른 두 개의 레코드가 있습니다. 나는이 두 개의 레코드를 두 번 반복하여 경과 시간을 테스트하는 코드를 작성했다. 큰 레코드 목록을 반복하면 훨씬 느리게 실행됩니다.

누구나 이유를 설명하고 루프를 빠르게 실행할 수있는 솔루션을 제공 할 수 있습니까?

type 
    tTestRecord1 = record 
    Field1: array[0..4] of Integer; 
    Field2: array[0..4] of Extended; 
    Field3: string; 
    end; 

    tTestRecord2 = record 
    Field1: array[0..4999] of Integer; 
    Field2: array[0..4999] of Extended; 
    Field3: string; 
    end; 

procedure TForm1.Button1Click(Sender: TObject); 
var 
    _List: TList<tTestRecord1>; 
    _Record: tTestRecord1; 
    _Time: TTime; 
    i: Integer; 
begin 
    _List := TList<tTestRecord1>.Create; 

    for i := 0 to 4999 do 
    begin 
    _List.Add(_Record); 
    end; 

    _Time := Time; 

    for i := 0 to 4999 do 
    begin 
    if _List[i].Field3 = 'abcde' then 
    begin 
     Break; 
    end; 
    end; 

    Button1.Caption := FormatDateTime('s.zzz', Time - _Time); // 0.000 

    _List.Free; 
end; 

procedure TForm1.Button2Click(Sender: TObject); 
var 
    _List: TList<tTestRecord2>; 
    _Record: tTestRecord2; 
    _Time: TTime; 
    i: Integer; 
begin 
    _List := TList<tTestRecord2>.Create; 

    for i := 0 to 4999 do 
    begin 
    _List.Add(_Record); 
    end; 

    _Time := Time; 

    for i := 0 to 4999 do 
    begin 
    if _List[i].Field3 = 'abcde' then 
    begin 
     Break; 
    end; 
    end; 

    Button2.Caption := FormatDateTime('s.zzz', Time - _Time); // 0.045 

    _List.Free; 
end; 

Answer 1

우선, 전체 코드를 고려해보고 싶습니다. 목록에 채워지는 코드도 고려해야합니다. 두 번째 레코드의 크기가 더 크기 때문에 해당 레코드 유형을 할당 할 때 더 많은 메모리를 복사해야합니다. 또한 목록에서 읽을 때 큰 레코드는 성능에 영향을 미치는 작은 레코드보다 캐시 친화적입니다. 후자의 효과는 이전의 효과보다 덜 중요합니다.

관련 항목이 추가되면 목록의 내부 레코드 배열의 크기를 조정해야합니다. 경우에 따라 크기를 조정하면 내부에서 수행 할 수없는 재 할당이 발생할 수 있습니다. 이 경우 새로운 메모리 블록이 할당되고 이전 내용이이 새 블록에 복사됩니다. 그 사본은 분명히 더 큰 기록을 위해 비싸다. 배열 길이를 알면 배열을 한 번 위로 할당하여이 문제를 줄일 수 있습니다. 목록 Capacity을 사용하는 메커니즘입니다. 물론, 항상 미리 길이를 알지는 못합니다.

프로그램은 메모리 할당과 메모리 액세스를 거의하지 않습니다. 따라서 이러한 메모리 연산의 성능이 우세합니다.

이제 타이밍은 목록에서 읽는 코드에만 적용됩니다. 따라서 인구에 대한 메모리 복사 성능 차이는 수행 한 벤치마킹의 일부가 아닙니다. 당신의 타이밍 차이는 주로 아래에서 설명 할 것입니다. _List[i] 레코드, 값 유형이

if _List[i].Field3 = 'abcde' then 

때문에, 전체 기록이 암시 숨겨진 지역 변수에 복사됩니다 :

이 코드를 생각해 보자. 코드는 실제로하는 것과 같습니다

var 
    tmp: tTestRecord2; 
... 
tmp := _List[i]; // copy of entire record 
if tmp.Field3 = 'abcde' then 

이 사본 피하기 위해 몇 가지 방법이 있습니다 :

1. 변경 참조 형식이 될 수있는 기본 유형. 이것은 메모리 관리 요구 사항을 변경합니다. 그리고 가치 유형을 사용하려는 정당한 이유가있을 수 있습니다.
2. 항목 복사본이 아닌 항목의 주소를 반환 할 수있는 컨테이너 클래스를 사용합니다.
3. TList<T>에서 동적 배열 TArray<T>으로 전환하십시오. 이 간단한 변경으로 컴파일러는 전체 레코드를 복사하지 않고도 개별 필드에 직접 액세스 할 수 있습니다.
4. TList<T>.List을 사용하면 데이터를 보유하고있는 목록 개체의 기본 배열에 액세스 할 수 있습니다. 이전 항목과 동일한 효과가 있습니다.

위의 항목 4는 큰 차이점을 확인할 수있는 가장 간단한 변경입니다.당신은

if _List.List[i].Field3 = 'abcde' then 

와

if _List[i].Field3 = 'abcde' then 

을 대체 할 그 성능이 매우 중요한 변화를 산출한다.

{$APPTYPE CONSOLE} 

uses 
    System.Diagnostics, 
    System.Generics.Collections; 

type 
    tTestRecord2 = record 
    Field1: array[0..4999] of Integer; 
    Field2: array[0..4999] of Extended; 
    Field3: string; 
    end; 

procedure Main; 
const 
    N = 100000; 
var 
    i: Integer; 
    Stopwatch: TStopwatch; 
    List: TList<tTestRecord2>; 
    Rec: tTestRecord2; 
begin 
    List := TList<tTestRecord2>.Create; 
    List.Capacity := N; 

    for i := 0 to N-1 do 
    begin 
    List.Add(Rec); 
    end; 

    Stopwatch := TStopwatch.StartNew; 
    for i := 0 to N-1 do 
    begin 
    if List[i].Field3 = 'abcde' then 
    begin 
     Break; 
    end; 
    end; 
    Writeln(Stopwatch.ElapsedMilliseconds); 
end; 

begin 
    Main; 
    Readln; 
end. 

I 메모리 부족 조건을 방지하기 위해 64 비트에 대한 컴파일했다 :

이 프로그램을 고려하십시오. 내 컴퓨터의 출력은 약 700입니다. List[i].Field3을 List.List[i].Field3으로 변경하면 출력이 단일 숫자로 표시됩니다. 타이밍은 다소 미숙한데, 이것이 그 점을 입증 해 준다고 생각합니다.

---

캐시 친화적이지 않은 큰 레코드의 문제는 여전히 남아 있습니다. 이는 처리하기가 더 복잡하며 실제 코드가 데이터에서 어떻게 작동하는지에 대한 자세한 분석이 필요합니다.

---

성능 측면에 신경 쓰면 Extended을 사용하지 않습니다. 2의 거듭 제곱이 아닌 크기가 10이기 때문에 메모리 액세스는 종종 잘못 정렬됩니다. Double 또는 Real을 Double의 별명으로 사용하십시오.