5

If there are n properties, then is the Big-O of .GetProperties O(n) or are there are processes involved in the reflection that add complexity?

Say there is this defined class:

public class Reflector
{
 public string name { get; set; }
 public int number { get; set; }
 public bool flag { get; set; }
 public List<string> etc { get; set; }
}

And then this call is made:

var reflect = new Reflector();
PropertyInfo[] properties = reflect.GetType().GetProperties();

What is the time complexity, i.e. Big-O, of .GetProperties()? Considering that there are 4 properties, would this only take 4 iterations or is it more complex than that? Or, is it O(1) with some standard set of complexity to get to the list - which seems it must still be O(n) just to build the properties array?

Travis J
  • 81,153
  • 41
  • 202
  • 273
  • For iterations of what?.. There may be zero iterations involved, if the array is pre-made for you. – Sergey Kalinichenko Mar 26 '12 at 19:55
  • @dasblinkenlight - iterations of the internal process used to generate the property list. For that part of the question, and from the answers below, I think the answer was `more complex`. – Travis J Mar 26 '12 at 20:00

2 Answers2

3

More complicated than that. The algorithm has to include the base type chain as well. In addition, the implementation might cache the result, so the ammortized cost might actually be O(1).

But in practice, reflection is always pretty slow, so you should probably profile your application and make changes until you meet your performance goals.

marcind
  • 52,944
  • 13
  • 125
  • 111
  • What makes it `always pretty slow`? – Travis J Mar 26 '12 at 19:59
  • 1
    @TravisJ honestly, I don't have a specific reason. my personal experience developing the ASP.NET MVC framework and being responsible for some of the performance optimizations in it is that we typically get higher performance if we can cache the information derived from reflection somehow instead of performing that same reflection all the time. My intuition as to why that might be is because the framework is simply not optimized with that in mind (after all, it's a statically compiled runtime). – marcind Mar 27 '12 at 03:23
3

Big-O is about asymptotic complexity, in other words O(n) is only relevant for large values of n.
A class will never have enough properties to make this relevant.

For practical purposes, you might as well consider it O(1), but with a very big constant.

This kind of issue is expressed in nanoseconds, not Big-O notations.

H H
  • 263,252
  • 30
  • 330
  • 514
  • I realize I may have phrased this improperly, what I was trying to get at was the internal algorithmic complexity of the reflection. – Travis J Mar 26 '12 at 19:58
  • Thanks, I will ask a different question based on the nanoseconds of reflection - or search to see if one exists. – Travis J Mar 26 '12 at 20:01
  • The time will be of the form `T = A + B * n`, I estimate A >> B but you'll have to measure. And it will probably depend on a lot of factors, like base classes, prior Reflection calls etc. – H H Mar 26 '12 at 20:03
  • So it could actually be pretty quick if the class has no parents (i.e. is not nested) and has no inheritance? – Travis J Mar 26 '12 at 20:05
  • I didn't say that. But it could be slower for a class with many base-classes. – H H Mar 26 '12 at 20:07
  • I opened a question about the nanoseconds here: http://stackoverflow.com/q/9878960/1026459. I also made a simple test where a loop of 10,000 calls to .GetProperties() took 16 milliseconds. – Travis J Mar 26 '12 at 20:35