레이아웃의 로드 및 업데이트의 빠른 속도 유지는 매우 중요합니다.

ListView, TreeView 또는 Datagrid와 같은 항목 컨트롤을 개발할 때 컨트롤에 잠재적으로 많은 수의 항목이 포함될 수 있기 때문입니다.

최적의 성능을 달성하기 위해 사용자가 항목을 통해 스크롤 할 때, UI 요소를 재생하는 'UI 가상화' 기법이 사용됩니다. 

하지만 UI 가상화로 인해, 목록 내 깊게 위치한 항목의 오프셋을 얻는 것과 같이 새로운 문제가 발생할 수 있습니다.

이번 블로그에서는 자체 사용자 정의 컨트롤에서 이 문제를 해결하는 방법을 설명합니다.

.NET UI 가상화를 사용하는 이유에 관한 자세한 배경 정보는 이전 블로그 .NET WPF Datagrid 성능 벤치마크 분석을 확인해 보시길 바랍니다.

UI 가상화의 오프셋 문제 

이 문제를 더 효과적으로 파악하기 위해 많은 숫자의 목록이 있고, 특정 인덱스의 오프셋(또는 위치)을 확인한다고 가정해 보겠습니다.

UI 가상화를 사용하고 있으므로 목록의 모든 요소가 한 번에 렌더링되는 것이 아니므로, 단순히 오프셋을 얻을 수 없습니다.

요소의 위치를 확인하려면 계산이 필요합니다. 요소의 크기가 고정된 경우에는 위치 계산이 간단합니다.

항목의 인덱스에 고정 길이를 곱하면 문제가 해결됩니다.

하지만 모든 요소의 크기가 다르거나 배치된 하위 요소에 따라 크기가 달라지는 경우, 요소의 위치는 모든 이전 요소의 크기에 따라 계산됩니다.

이전 길이를 모두 더하면 많은 수의 항목을 렌더링할 때 성능 문제가 발생합니다.

성능 문제 외에도 항목 수가 많은 경우(예를 들어 100억 개), 모든 항목의 길이를 저장하면 메모리 문제도 발생합니다.

대부분의 경우, 많은 수의 항목에 바인딩하면 대부분의 항목을 방문하지 않으므로 값을 저장할 필요가 없습니다.

대신 항목을 최종 방문할 때까지 예상 크기를 사용할 수 있습니다.

오프셋 솔루션 

원하는 항목 이전의 모든 항목의 합계를 구하는 데는 많은 비용이 들기 때문에 특정 부분의 합계를 미리 구할 수 있는 방법이 필요합니다.

상위 노드에서 하위 요소의 집계된 값을 캐싱하는 배열 길이가 고정된 트리 구조를 사용할 수 있습니다.

구조 내 항목의 위치는 다음 코드를 통해 컬렉션 내 인덱스에서 수학적으로 계산됩니다.

private int[] GetIndexArray(int index)
{
    var indexArray = new int[_depth];
    for (int i = _depth - 1; i >= 0; i--)
    {
        indexArray[i] = index % _partitionLength;
        index = index / _partitionLength;
    }
    return indexArray;
}

반환된 배열에는 항목을 찾기 위해 각 수준에서 탐색할 인덱스가 포함됩니다.

예를 들어, (파티션의) 배열 크기가 3이고 검색된 인덱스가 8인 경우, 반환된 배열이 [2,2]이면 인덱스 2까지 모두 합계를 구한 후 다음 하위 수준에서 2 개 더 합계를 구한다는 것을 의미합니다.

합계는 15+14+1+6=36이 됩니다. 8개 대신 4개 숫자의 합계를 구합니다.

이 샘플은 그래픽 상의 이유로 길이가 3인 배열을 사용하지만, 실제 사례에서는 배열이 훨씬 더 클 수 있으므로 성능 향상이 더 눈에 띌 것입니다.

반면에, 이 데이터 구조는 기본 길이 값을 정의하고 기본값과 동일한 모든 값을 저장하지 않아 메모리를 줄이는 데 사용할 수 있습니다.

예를 들어, 기본값이 5이고 9 개 값의 목록이 있다고 가정하겠습니다.

처음에 상위 수준 노드는 값 45(항목 9개 x 길이 5)를 저장합니다. 그리고 5와 다른 값을 설정할 때는 해당 값만 구조에 저장됩니다.

두 번째 항목이 8로 설정된다고 가정해 보겠습니다.

이러한 방법으로, 기본값과 다른 항목에 대해서만 메모리가 할당되는 것을 볼 수 있습니다.

성능 비교 

ComponentOne 라이브러리 내에는 해당 기능을 구현하는 C1LengthList라는 List 클래스가 포함되어 있습니다.

이 구조를 사용하는 이점을 시각화하기 위해,

첫 번째 방법으로는 List의 요소의 합계를 구하여 오프셋을 가져오고, 다른 방법으로는 C1LengthList의 GetOffset 메서드를 실행하는 벤치마킹 앱을 제작했습니다.

작은 목록의 경우, 간단한 목록보다 더 빨리 계산되지만, 두 경우 모두 매우 빠릅니다.

목록의 크기가 100만까지 증가하면 모든 항목의 합계를 구할 경우 계산 문제가 발생하지만, C1LengthList는 안정된 성능을 유지합니다.

결론 

이 계층적 데이터 구조를 사용하면 목록을 사용하는 기존 접근 방식의 o(n) 대신, o(log(n))로 목록 내 항목의 오프셋을 효율적으로 가져올 수 있습니다.

유일한 단점은 특정 항목의 길이에 액세스하기 위한 순서도 o(1) 대신 o(log(n))이라는 것입니다. 또한, 이 데이터 구조를 사용하면 대부분의 항목이 기본값과 동일한 목록에 사용되는 메모리를 대폭 줄일 수 있습니다.

고려해야 할 다른 사용 사례는 텍스트 줄바꿈을 처리하는 셀의 UI 스크롤 인덱스 계산입니다.

텍스트 줄 바꿈은 내부 텍스트 글리프 높이로 인해 발생한 셀의 알 수 없는 높이 + 뷰 포트의 너비를 다음 모든 행의 위치에 영향을 미칠 수 있도록 쉽게 전달합니다.  

이러한 경우 스크롤의 정확한 색인이 문제가 될 수 있습니다. 

C1DataCollection 및 ComponentOne WPF Edition의 일부로 C1LengthList를 사용해 볼 수 있습니다 . 

지금 바로 ComponentOne을 다운로드하여 직접 테스트해 보세요!

• ComponentOne 공식 홈페이지
• ComponentOne 튜토리얼 및 샘플
• ComponentOne Q&A
• ComponentOne FAQ