[최적화] 계산하는데 10분이나 걸려요

동료가 고객사에서 "2~3분 걸리는 작업을 10분 걸린다고 말한다"며 화면에 걸리는 시간을 표시해야겠다고 합니다.
10분은 아니지만 2~3분도 사용자의 인내심을 요구하는 시간이기 때문에 프로그램 최적화를 하기로 했습니다.
아래는 진행중인 프로젝트(Cable AutoRouting) 대상으로 진행한 최적화에 대한 내용입니다.

1. 상황에 맞는 자료 구조를 선택해야 합니다.

Map 클래스의 Node 접근이 빈번하게 일어난다고 할때,

Nodes 자료 구조로 List를 사용했다고 하면 접근을 위해 아래와 같은 코드가 필요합니다.

return map.Nodes.Cast<Node>().Where(c1 => c1.ObjectID == oFeature.ObjectID).FirstOrDefault();

이때 걸리는 시간은 $O(n)$이 됩니다.

하지만 자료 구조를 Dictionary를 사용한다면 접근하는데 걸리는 시간은 $O(1)$이 됩니다.

if(this._Nodes.ContainsKey(oFeature))
{
	return this._Nodes[oFeature];
}

2. 속도를 위해 공간을 희생합니다.
계산을 시작하기 전에 필요한 모든 정적 데이타를 메모리에 올리는 것이 속도에 이득이 됩니다.
처음에는 에지를 생성하면서 노드를 생성하는 로직이었는데 모든 노드를 생성한 후에 노드간 에지를 연결하는 방식으로 바꾸었습니다.
이렇게 함으로 에지를 생성하기 위해 노드를 찾는 부분을 제거할 수 있었습니다. 그리고 로직도 좀더 단순화 되었습니다.

3. 빈번하게 호출되는 부분을 최소화합니다.

빈번하게 호출되는 함수의 결과를 저장하여 재사용하는 것이 속도를 높일 수 있습니다. 그리고 이 함수를 캡슐화하여 외부로부터 숨기는 것이 디자인 측면에서 좋습니다. 함수 호출보다 저장해둔 결과를 사용하도록 유도해야 합니다.

아래 코드는 OrientedRangeBox 속성을 참조할때마다 GetOrientedRangeBox 함수를 호출하여 OrientedRangeBox를 구하고 있습니다.

public virtual OrientedRangeBox OrientedRangeBox
{
    get
    {
        return CommonUtil.GetOrientedRangeBox(this._oFeature);
    }
}

아래와 같이 바꾸면 처음 OrientedRangeBox 속성을 참조할때만 계산을 하고 나머지는 계산된 결과를 사용하게 됩니다.

protected OrientedRangeBox _OrientedRangeBox = null;
public virtual OrientedRangeBox OrientedRangeBox
{
    get
    {
        if(this._OrientedRangeBox == null)
        {
            this._OrientedRangeBox = CommonUtil.GetOrientedRangeBox(this._oFeature);
        }          
        return this._OrientedRangeBox;
      }
 }

4. 비용이 많이 드는 호출을 최소화합니다. 

OrientedRangeBox의 Intersects 함수는 RangeBox의 Intersects 함수보다 비용이 많이 듭니다.
따라서 OrientedRangeBox의 Intersects를 사용하기 전에 미리 RangeBox의 Intersects를 이용하여 OrientedRangeBox의 Intersects 함수 사용을 최소화합니다.

모든 노드의 OrientedRangeBox의 Intersects를 호출하는 것이 아니라 RangeBox의 Intersects를 호출하여 교차 가능성이 있는 노드들에 대해 다시 OrientedRangeBox의 Intersects를 호출하여 최종 교차 여부를 판단합니다.

List<Node> oIntersectsWithRangeBox = Map.Nodes.Where(x => x.Range.Intersects(oVirtualNode.Range)).ToList();
  List<Node> oIntersectsWithOrientedRangeBox = oIntersectsWithRangeBox.Where(x => x.IntersectsWithOrientedRangeBox(oVirtualNode)).ToList();

5. 프로파일러을 이용하여 병목 부분을 확인하고 최적화를 진행합니다.

VS의 성능 프로파일러를 통하여 가장 호출 빈도수가 높은 부분을 확인하여 최적화를 진행합니다. 여기서는 GetConnectedNodesByFeature 함수의 호출 빈도수가 높게 나왔습니다.

최적화 후에 기존 2분이 소요되던 부분이 30초로 줄어들었습니다.