2013-08-23 3 views
3

알고리즘에서 흥미로운 문제점을 발견했을 때 개발 사이트에있는 이벤트 뷰어 응용 프로그램의 성능 문제를 조사했습니다. 그런 다음 두 가지 알고리즘을 테스트하기 위해 간단한 테스트 프로젝트를 만들었습니다. 이 프로그램은 기본적으로 EventLog 클래스를 사용하여 Windows 이벤트 로그를 검색 한 다음 해당 로그를 쿼리 가능 EventLogItem 엔티티로 변환합니다.앞으로/뒤로 루프 성능 분석

이 작업은 두 개의 다른 루프를 사용하여 수행되고 시간이 지정됩니다. 첫 번째 (뒤로) 루프는 목록의 마지막 항목의 인덱스에서 시작하여 항목을 변환 한 다음 인덱스를 줄입니다. 이 메서드는 다음과 같이 정의됩니다.

private static void TranslateLogsUsingBackwardLoop() 
{ 
    Stopwatch stopwatch = new Stopwatch(); 
    stopwatch.Start(); 

    var originalLogs = EventLog.GetEventLogs(); 
    var translatedLogs = new List<EventLogItem>(); 

    Parallel.ForEach<EventLog>(originalLogs, currentLog => 
    { 
     for (int index = currentLog.Entries.Count - 1; index >= 0; index--) 
     { 
      var currentEntry = currentLog.Entries[index]; 

      EventLogItem translatedEntry = new EventLogItem 
      { 
       MachineName = currentEntry.MachineName, 
       LogName = currentLog.LogDisplayName, 
       CreatedTime = currentEntry.TimeGenerated, 
       Source = currentEntry.Source, 
       Message = currentEntry.Message, 
       Number = currentEntry.Index, 
       Category = currentEntry.Category, 
       Type = currentEntry.EntryType, 
       InstanceID = currentEntry.InstanceId, 
       User = currentEntry.UserName, 
      }; 

      lock (translatedLogs) 
      { 
       translatedLogs.Add(translatedEntry); 
      } 
     } 
    }); 

    stopwatch.Stop(); 

    Console.WriteLine("{0} logs were translated in {1} using backward loop.", translatedLogs.Count, stopwatch.Elapsed); 
} 

두 번째 (앞으로) 루프는 인덱스 0에서 시작하여 인덱스를 증가시킵니다.

static void Main(string[] args) 
{ 
    TranslateLogsUsingForwardLoop(); 
    Console.WriteLine(); 
    Thread.Sleep(2000); 
    TranslateLogsUsingBackwardLoop(); 
    Console.ReadLine(); 
} 

이것은 내가 무엇을 얻을 것입니다 (이 테스트를 수행 여러 번, 결과는 거의 동일) :

private static void TranslateLogsUsingForwardLoop() 
{ 
    Stopwatch stopwatch = new Stopwatch(); 
    stopwatch.Start(); 

    var originalLogs = EventLog.GetEventLogs(); 
    var translatedLogs = new List<EventLogItem>(); 

    Parallel.ForEach<EventLog>(originalLogs, currentLog => 
    { 
     for (int index = 0; index < currentLog.Entries.Count; index++) 
     { 
      var currentEntry = currentLog.Entries[index]; 

      EventLogItem translatedEntry = new EventLogItem 
      { 
       MachineName = currentEntry.MachineName, 
       LogName = currentLog.LogDisplayName, 
       CreatedTime = currentEntry.TimeGenerated, 
       Source = currentEntry.Source, 
       Message = currentEntry.Message, 
       Number = currentEntry.Index, 
       Category = currentEntry.Category, 
       Type = currentEntry.EntryType, 
       InstanceID = currentEntry.InstanceId, 
       User = currentEntry.UserName, 
      }; 

      lock (translatedLogs) 
      { 
       translatedLogs.Add(translatedEntry); 
      } 
     } 
    }); 

    stopwatch.Stop(); 

    Console.WriteLine("{0} logs were translated in {1} using forward loop.", translatedLogs.Count, stopwatch.Elapsed); 
} 

그리고 주요 방법 :이 방법은 다음과 같이 정의된다

enter image description here

내가 테스트 한 서버가 매초마다 이벤트 로그에 기록되므로 번역 된 로그 수가 동일하지 않습니다. 그렇다면 왜 후진 루프가 더 빠릅니까? 처음에는 역 루프 알고리즘에서 currentLog.Entries.Count이 단지 한 번만 평가 되었기 때문에 앞으로 루프에서 계산되고 모든 루프 반복에서 index과 비교되어야하지만 다시 올바른 것으로 보이지 않기 때문에 처음에는 생각했습니다. 어떤 아이디어?

+0

두 의견 :-) 옛날에 사용되는 방법을 예측할 수 있습니다. 타이밍에 항상 번인 루프가 포함됩니다. 프로세서가 예열되도록 (올바르게 조절) 타이밍을 시작하기 전에 일부 작업을 수행하십시오. 그리고'For' 루프 바로 전에 타이머를 시작하고 할당 연산자를 시간을 재는 것이 좋습니다. – ja72

+0

테스트에 몇 개의 항목이 있습니까? 또한 정기적 인 (순차적 인) 루프로 시도해 보셨습니까? – ja72

답변

0

maxndex에 비해 againt 0 테스트는 거의 영향을 미치지 않습니다. 그러나 곧 test1을 수행 한 다음 test2를 수행하면 프로세서 캐싱 및/또는 O/S 페이지 캐싱으로 인해 종종 영향을 미치게됩니다. 전달이 마술처럼 뒤쪽보다 빠르게되는지 확인하기 위해 test1/test2를 뒤집을 수 있습니다. 정확한 프로파일 링은 현대 건축물에는 어렵습니다.

좋아요, 그래서 Backwards는 처음 실행될 때 더 빠릅니다. 내 첫 번째 추측은 아니지만 병렬 및 잠금을 사용하고 있기 때문에 잠금 방법과 앞뒤 루프의 차이가있을 수 있습니다.

아마도 후방 루프는 프로세서 분기 예측 (parallism, 프로세서 캐시 등으로 다시 상호 작용할 수 있음)과 함께 더 잘 작동합니다.

멀티 스레드 코드에서 긴밀한 루프가 많이 발생하면 잠금 오버 헤드로 인해 메모리 관리와 이상한 상호 작용이 발생합니다. - 잠금 경합으로 인해 멀티 스레드 솔루션의 속도가 느려지는 경우는 드뭅니다.

시간이 더 균등 해지는 지 알아보기 위해 병렬 및 순차없이 실행 해 볼 수는 있지만 기껏해야 병렬 상호 작용 또는 잠금 경합에 대한 가능성/가능성은 낮습니다. 코드를 프로파일 링하는 것은 암시적일 수 있지만 확실한 답을 찾지 못할 수도 있습니다. 결정적인 대답은이 상황에서 매우 어려울 수 있습니다 (나는 당신이 대부분 호기심/학습 모드에 있다고 생각했습니다).

+0

전화 주문을 취소하려고했습니다. 거꾸로 여전히 빠릅니다. – PoweredByOrange

+0

병렬 루프 대신 일반 루프를 사용할 때 두 알고리즘 간의 차이점을 많이 볼 수 없습니다 ... 왜 이렇게 행동하는지는 아직 확실하지 않습니다. – PoweredByOrange

+0

Acutally, 그 대답의 열쇠입니다. 성능이 기본적으로 앞뒤로 동일하다면 메모리 관리 잠금과의 상호 작용이나 다른 잠금 동작 중 하나 일 가능성이 거의 확실합니다. 개입의 정확한 성격을 털어내는 것은 당신의 환경에 따라 다를뿐만 아니라 매우 어려울 것입니다. –

1

이전의 질문 및이 경우 정확한 이유가되지 않을 수 있지만 루프가 IL 또는 어셈블리로 내려갈 때 또는 언어의 하위 언어가 무엇이든지간에 차이점이 있습니다. 최소한 for 루프를 사용하면 카운트 값을 얻은 다음 모든 루프에서 인덱스 변수와 비교할 수 있습니다.후진 루프에서는 시작점으로 한 번 카운트를 얻은 다음 비교가 항상 0으로 비교하기 쉽고 컴파일러도 최적화 할 수 있습니다. 마일리지는 다를 수 있으며 나머지 코드에 따라 무시할 수있는 차이 일 수 있습니다. 하지만 모든 클럭주기가 필요하다면 역 루프가 굉장합니다.

0

첫 번째 루프는 첫 번째 루프이기 때문에 속도가 느립니다. 전달 루프가 아니기 때문입니다. (레벨 1 및 레벨 2 캐시)에

캐싱

현대 CPU의 캐시 데이터. 데이터가 처음 액세스 될 때 속도가 느려지 며 이후 액세스에는 더 빠릅니다.

var currentEntry = currentLog.Entries[index]; 

느린 RAM에서 L2 캐시로로드되기 때문에 첫 번째 루프가 오래 걸립니다.

L2 캐시에서로드되기 때문에 작성 방법에 관계없이 두 번째 루프가 더 빨라질 것으로 기대합니다.

목록 < T>

목록은 계속 확대되고 배열. 그들은 작게 시작하여 (용량 4) 필요에 따라 용량을 두 배로 늘립니다. 각 재 할당은 매우 느립니다.

var translatedLogs = new List<EventLogItem>(); 
    ... 

    translatedLogs.Add(translatedEntry); 

첫 번째 루프는 상당히 자주 재 할당합니다 : 4, 8, 16, 32, 두 번째 루프는 덜 자주 재 할당합니다 (64)

: 64,

128 그래서 두 번째 루프를 기대 (작성 방법에 관계없이) 더 빠르다. 프로세서가 너무 복잡하기 때문에

CPU 최적화

이상한 일들이 일어난다. 더 이상 코드 속도에게 우리가

Why is processing a sorted array faster than an unsorted array?