동적 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 연산의 동적 버전을 어떻게 구현해야 하는지 살펴보겠습니다.
