Performance Enhancement

Feb 12, 2008 at 2:36 PM
I just started looking at your code the day before yesterday and found it very interesting and useful. However, I thought if the building of the index was quite so costly it might have wider application. I decided to give a shot at turbo charging the bugger and have found a fairly simple way to decrease the time when initially building the collection by 2 to 4 times. For example, when running your test program on my meager machine, Creating 1,000,000 items took about 69 seconds. With the change applied, the same create loop takes about 18 seconds. I estimate that 13 or 14 seconds of that time would still be there if we had just used the straight non-indexed collection.

Basically what I found was that a big part of the overhead in creating the indexed collection was in get the property value from the contained object. Reflecting on a property does not come without a fairly significant cost. Normally, this cost is negligible (especially given its benefit) in most applications. It is however a severe impact on something like i4o. The way I solved this is to create a new interface IPropertyHelper. This interface has one method, object GetValue(Object target, String propertyName). I then added a new private method CreatePropertyHelper that dynamically creates an assembly (run only, no save) that houses types that can retrieve the property value for the caller at runtime. This eliminates the need to reflect on the types property each time is added and for each index it has.

Here is the relevant code:

private Dictionary<String, IPropertyHelper> _phi = new Dictionary<string, IPropertyHelper>();

static ModuleBuilder modBuilder = null;

private IPropertyHelper CreatePropertyHelper(PropertyInfo[] pInfo)
{
if (pInfo == null || pInfo.Length == 0)
throw new InvalidOperationException("PropertyInfo can not be null and must have at least one item");

// We only need one assembly for all of the types we contain.
if (modBuilder == null)
{
// Must be the first time. Make up a name for us.
AssemblyName assemName = new AssemblyName("i4oPropertyHelper");

// Get the AssemblyBuilder for our new dynamic assembly.
// We only need to be able to run it, and will not persist it.
AssemblyBuilder assemBuilder = AppDomain.CurrentDomain.DefineDynamicAssembly(assemName, AssemblyBuilderAccess.Run);

// Get the the builder for our one and only module.
modBuilder = assemBuilder.DefineDynamicModule(assemName.Name);
}

// Get the name of our new type (same as the type we are containing.
// Just use the first property for the name.
String newTypeName = pInfo0.DeclaringType.Name;

// In case we have done this before, first check and see if
// we already have the type the caller needs.
Type existingType = modBuilder.GetType(newTypeName);
if (existingType != null)
{
// Must have done this before. Create an instance
// and cast it to an IPropertyHelper
return CreatePropertyHelper(existingType);
}

// OK, time to build our handy dandy helper class.
TypeBuilder typeBuilder = modBuilder.DefineType(newTypeName, TypeAttributes.Public | TypeAttributes.Class);

// Since the whole point of doing this is to avoid using Invoke
// we need an interface that we can use with the compiler to aid
// us in using this class. IPropertyHelper is just we need so
// add its interface implementation.
typeBuilder.AddInterfaceImplementation(typeof(IPropertyHelper));

// IPropertyHelper defines just one method, GetValue
MethodBuilder methBuilder = typeBuilder.DefineMethod("GetValue", MethodAttributes.Public | MethodAttributes.Virtual, typeof(Object), new Type[] { typeof(object), typeof(String) });

// Get our IL Generator for this new method.
ILGenerator ilGen = methBuilder.GetILGenerator();

// One jump label for each property we will be supporting.
Label[] jumpLabel = new LabelpInfo.Length;
for (int i=0; i<pInfo.Length; i++)
jumpLabeli = ilGen.DefineLabel();

// Create a default label for the case where we call this
// with a property it doesn't know about and one for going
// to the exit.
Label defLabel = ilGen.DefineLabel();
Label eom = ilGen.DefineLabel();

// Create a simple if check for each property
// Use String.Equals to do the comparison.
for (int i = 0; i < pInfo.Length; i++)
{
// Arg 2 has the String reference for Request Property Name
ilGen.Emit(OpCodes.Ldarg, 2);
// Load the Property Name to compare it to
ilGen.Emit(OpCodes.Ldstr, pInfoi.Name);
// Ask String.Equals to check it
ilGen.EmitCall(OpCodes.Call, typeof(String).GetMethod("Equals", new Type[] { typeof(String) }), new Type[] { });
// If it returns true, branch to the code to get the proper property
ilGen.Emit(OpCodes.Brtrue_S, jumpLabeli);
}
// Nobody matched, jump to our default label
ilGen.Emit(OpCodes.Br_S, defLabel);

// Here is where we create the code to get the requested property value
for (int i = 0; i < pInfo.Length; i++)
{
// Add the label so the branch gets to the right place
ilGen.MarkLabel(jumpLabeli);
// Argument one has the target object instance with the property
ilGen.Emit(OpCodes.Ldarg, 1);

// Not sure we really need to do this cast so I have
// commented it out for now.
// ilGen.Emit(OpCodes.Castclass, pInfoi.DeclaringType);

// Go call the Get Method for this property
ilGen.Emit(OpCodes.Call, pInfoi.GetGetMethod());

// Since we are returning an object, box the return value
// if it is a value type.
if (pInfoi.GetGetMethod().ReturnType.IsValueType)
{
ilGen.Emit(OpCodes.Box, pInfoi.GetGetMethod().ReturnType);
}
// Stack should have our object value so just return to caller.
ilGen.Emit(OpCodes.Ret);
}

// This is where we go when someone calls us with a property name
// that we don't know about.
// For now we just fall through and return a null. That should give
// the rest of the code some heartburn.
ilGen.MarkLabel(defLabel);
//ilGen.Emit(OpCodes.Ldarg);
ilGen.MarkLabel(eom);
ilGen.Emit(OpCodes.Ldnull);
ilGen.Emit(OpCodes.Ret);

// Our code is all written, so create the type
Type t = typeBuilder.CreateType();

// Construct an instance of the object and return its IPropertyHelper
// interface.
return CreatePropertyHelper(t);
}
private IPropertyHelper CreatePropertyHelper(Type t)
{
ConstructorInfo ci = t.GetConstructor(new Type[] { });

IPropertyHelper b = (IPropertyHelper)ci.Invoke(new Object[] { });
return b;
}

I also modified the BuildIndexes to utilize this code:

public void BuildIndexes()
{
List<PropertyInfo> indexProperties = new List<PropertyInfo>();
PropertyInfo[] allProps = typeof(T).GetProperties();
foreach (PropertyInfo prop in allProps)
{
object[] attributes = prop.GetCustomAttributes(true);
foreach (object attribute in attributes)
if (attribute is IndexableAttribute)
{
// Keep a running list of the properties
// so we can create a property helper later.
indexProperties.Add(prop);
_indexes.Add(prop.Name, new Dictionary<int, List<T>>());
}
}

IPropertyHelper phi = null;

// There is no point in building the property helper
// if the class is not public since we won't be able to
// get the properties later. Will produce a MemberAccessException
if (typeof(T).IsPublic)
{
if (indexProperties.Count > 0)
phi = CreatePropertyHelper(indexProperties.ToArray());
}

foreach (String key in _indexes.Keys)
{
_phi.Add(key, phi);
}
}

I don't have enough room to put the Add method changes here but I can post them later if you like. The only caveat is that you can't use the IPropertyHelper if the class is not public (like in your demo). I let the add code in that case do it the way you had originally (more or less) so that it would work either way, but I think the peformance boost makes it much more desirable in most cases just to make the class public. Here is a small excerpt from the add code:

int hashCode;
IPropertyHelper ph = _phikey;
if (ph != null)
{
hashCode = ph.GetValue(newItem, key).GetHashCode();
}
else
{
PropertyInfo theProp = typeof(T).GetProperty(key);
hashCode = theProp.GetValue(newItem, null).GetHashCode();

Mar 16, 2008 at 2:24 PM
Here is a much much easier way to avoid invoke, C# 3.0 style. What is really needed is a Func<T, int> to convert our T into an int (ie the hashcode of some property). Here is how to do it in five lines of code. It reduces the time taken to add 1 million items from 20 seconds down to 2.

PropertyInfo propInfo = typeof(T).GetProperty("MyPropName" ... // etc)

ParameterExpression expObj = Expression.Parameter(typeof(T), "obj");
Expression expProp = Expression.Property(expObj, propInfo);
Expression expHashCode = Expression.Call(expProp, "GetHashCode", new Type0);

Func<T, int> getHashCode = Expression.Lambda<Func<T, int>>(expHashCode, expObj).Compile();
Coordinator
Mar 23, 2008 at 3:28 PM
Thanks for this! Just catching up on things... but thanks for the contribution!

FYI, I am looking to do another release in mid-April, once I get back from MVP summit and my schedule clears a bit.