동적 Linq 연산 #1 – OrderBy

배경

최근에 codeproject.com에서 정렬 키 속성 이름을 입려받아 동적으로 시퀀스에 OrderBy 연산을 적용하는 방법에 대한 포스트를 접했습니다. 데이터를 보여주고 분석하는 프로그램에서 동적으로 속성을 입력받는 상황은 흔히 발생합니다. 실제로 몇 주 전에 팀 동료로부터 서비스 프로그램에서 외부 컴포넌트에서 입력받는 값에 따라 지정된 속성으로 데이터를 필터링하는 방법에 대한 문의를 받은 적이 있습니다. 두 개의 포스트를 통해 이러한 상황에서 사용할 수 있는 정렬과 필터링 연산에 대해 정리해 봅니다.

OrderBy 연산 구현

우선 codeproject.com 포스트의 코드를 일반화해보겠습니다. 아래와 같은 확장 메서드로 정의될 수 있겠죠.

public static IEnumerable<T> OrderBy<T>(this IEnumerable<T> s, string propertyName)
{
    var prop = typeof(T).GetProperty(propertyName);
    if (prop == null)
        throw new InvalidOperationException("Property Not Found");
    return s.OrderBy(e => prop.GetValue(e));
}

이 확장 메서드를 사용하면 다음 처럼 동적으로 정렬 키를 지정해 시퀀스를 정렬 할 수 있습니다.

Random r = new Random();
var s = Enumerable.Range(0, 100000).Select(i => Tuple.Create(i, r.Next())).ToArray();
var propertyName = "Item2";
foreach (var t in s.OrderBy(propertyName))
{
    Console.WriteLine(t);
}

// Output:
//   (36370, 50810)
//   (47588, 89119)
//   (27861, 99621)
//   (11502, 119754)
//   (55197, 124970)
//   (77734, 133697)
//   ...

이렇게 문자열 버전의 OrderBy 확장 메서드를 사용하면 사용자 인터페이스에서 속성 이름을 입력받거나 하는 식으로 런타임에 필요한 데이터 정렬 작업이 가능해집니다. 전체 코드는 여기에서 실행해 볼 수 있습니다. 그런데 이 버전의 OrderBy 동적 연산은 한 가지 치명적인 결점을 가지고 있습니다.

성능 개선

우리의 첫 번째 버전 OrderBy 확장 메서드는 리플렉션(reflection)을 사용합니다. 속성 이름을 통해 해당하는 속성에 접근하려면 System.Reflection.PropertyInfo 개체를 사용해야 합니다. 하지만 리플렉션은 비용이 높은 작업이기 때문에 시간 복잡도 O(Nlog2N)OrderBy 연산이 수행되는 동안의 모든 속성 접근에 리플렉션에 적용된다면 효율이 떨어질 수 밖에 없습니다. 이것은 codeproject.com 포스트의 코드 역시 가지고 있는 단점입니다.

CreateDelegate

이 문제에 대한 개선책으로 System.Delegate.CreateDelegate 메서드 사용은 좋은 대안입니다. 대리자를 만드는 작업은 비용이 높지만 한 번 만들어진 대리자를 사용해 속성에 접근하는 것은 정적으로 빌드된 코드와 비슷하거나 약간 더 높은 성능을 보여줍니다. OrderBy 연산은 그 자체로 비용이 높기 때문에 대리자를 이용한 비용감소가 다른 연산에 비해서는 비중이 비교적 적지만 분명 큰 성능 향상을 보여주며 시퀀스의 요소가 많을 수록 이 차는 벌어집니다. 이와 관련해서 codeproject.com 포스트에도 대리자를 이용한 성능 개선 버전을 댓글로 제시한 바 있습니다.

* 메서드 호출 성능에 대해서는 https://github.com/gyuwon/csharp-seminar-demos/blob/master/README.md#v-10의 Delegates를 참조하세요.

자, 그럼 개선된 버전의 OrderBy 확장 메서드입니다.

private static MethodInfo orderByTemplate = typeof(Enumerable)
    .GetMember("OrderBy")
    .OfType<MethodInfo>()
    .Single(m => m.IsGenericMethodDefinition && m.GetParameters().Length == 2);

private static Delegate GetGetter<T>(PropertyInfo prop)
{
    var funcType = typeof(Func<,>).MakeGenericType(typeof(T), prop.PropertyType);
    return Delegate.CreateDelegate(funcType, prop.GetGetMethod());
}

public static IEnumerable<T> OrderBy<T>(this IEnumerable<T> s, string propertyName)
{
    var prop = typeof(T).GetProperty(propertyName);
    if (prop == null)
        throw new InvalidOperationException("Property Not Found");
    var operation = orderByTemplate.MakeGenericMethod(typeof(T), prop.PropertyType);
    var keySelector = GetGetter<T>(prop);
    return (IEnumerable<T>)operation.Invoke(null, new object[] { s, keySelector });
}

새로운 버전의 OrderBy 메서드 역시 GetProperty 메서드를 사용해 PropertyInfo 개체를 가져오지만 그대로 OrderBy Linq 연산에 사용하는 것이 아니라 이를 이용해 속성 값을 가져오는 대리자와 속성 형식에 맞는 버전의 메서드 인스턴스를 만들어 실행합니다. 즉 Linq 연산 준비과정에 약간의 리플렉션 작업이 수행되지만 Linq 연산 자체는 리플렉션 없이 강력한 형식을 기반으로 실행되어 성능 최적화를 달성합니다. 개선된 버전의 OrderBy 메서드는 여기에서 실행해 볼 수 있습니다.

다음은…

이번 포스트에서는 Linq가 기본적으로 제공하는 정렬 기능이 다루지 않는 사용성을 제공하면서 추가 비용을 최소화한 버전의 OrderBy 메서드 구현 방법을 살펴봤습니다. Linq에서 정렬 연산과 더불어 많이 사용되는 것이 필터링입니다. 동적 연산을 구현함에 있어서 Where 메서드는 OrderBy 메서드보다 다루기 약간 더 까다롭습니다. 2개의 제네릭 매개변수가 필요하기 때문인데요, 다음 포스트에서 Where 연산의 동적 버전을 어떻게 구현해야 하는지 살펴보겠습니다.

Advertisements

동적 Linq 연산 #1 – OrderBy”에 대한 3개의 생각

  1. kevin

    본문에서 궁금한 사항이 하나 있는데요. ^^ “리플렉션은 비용이 높은 작업이기 때문에 시간 복잡도 O(Nlog2N)의 OrderBy 연산이 수행되는 동안의 모든 속성 접근에 리플렉션에 적용된다면” 이라는 문구가 있는데, 어차피 OrderBy 연산은 한번만 수행되기 때문에 시간 복잡도랑은 그다지 상관없는 것 아닌가요? 어떤 의미로 그런 문장을 사용했는지 잘 이해가 안되어서 덧글 남깁니다. ^^

    응답
    1. Gyuwon 글의 글쓴이

      양질의 질문입니다. 🙂 첫 번째 버전의 OrderBy 메서드의 마지막 줄을 보면

      return s.OrderBy(e => prop.GetValue(e));

      GetValue 리플렉션 메서드를 호출하는 대리자를 Linq OrderBy 연산에 전달하는데 이 대리자가 O(Nlog2N) 만큼 반복적으로 호출됩니다. 이것을 의미하는 것입니다. 답변이 되었나요?

      응답
      1. kevin

        아… 제가 대충 읽었군요. ^^ OrderBy 확장 메서드 내부의 OrderBy에 전달되는 인자를 간과해서 그런 질문이 나왔습니다. ^^

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중