tags:

views:

152

answers:

4

Dear ladies and sirs.

Imagine the following simple code:

public void F<T>(IList<T> values) where T : struct
{
  foreach (T value in values)
  {
    double result;
    if (TryConvertToDouble((object)value, out result))
    {
      ConsumeValue(result);
    }
  }
}

public void ConsumeValue(double value)
{
}

The problem with the above code is casting to object, which results in boxing in the loop.

Is there a way to achieve the same functionality, i.e. feeding ConsumeValue with all the values without resorting to boxing in the foreach loop? Note, that F must be a generic method.

I can live with an expensive preparation code as long as it is executed outside the loop just once. For instance, if a fancy dynamic method needs to be emitted, then it is fine if done just once.

EDIT

T is guaranteed to be of some numeric type or bool.

Motivation. Imagine meta data driven application, where an agent reports a data stream, where data item type is dynamically emitted based on the data stream meta data. Imagine also, that there is normalizer engine, which knows to normalize numeric data streams according to some algorithm. The type of the incoming numeric data stream is known only at run time and can be directed to a generic method of that data type. The normalizer, however, expects doubles and produces doubles. This is a very high level description, please do not delve into it.

EDIT2

Concerning the cast to double. Actually we have a method to convert to double with the following signature:

bool TryConvertToDouble(object value, out double result);

I should have used it in the example in the first place, but I wanted to save space and written something that is not going to work. Fixed it now. Thanks for noting.

EDIT3

Guys, the current implementation does box the values. And even if I do not have the profiler's verdict as to performance penalty of it (if any), still I am interesting to know whether there is a solution without boxing (and without converting to string). Let me call it purely academic interest. This really interests me, because things like that are trivial in C++ with templates, but, of course, I am not starting yet another stupid and pointless argument over what is better .NET generics or C++ templates. Please, ignore this last sentence.

EDIT4

Thanks to http://stackoverflow.com/users/267/lasse-v-karlsen who provided the answer. Actually, I have used his code sample to write a simple class like this:

public static class Utils<T>
{
  private static class ToDoubleConverterHolder
  {
    internal static Func<T, double> Value = EmitConverter();

    private static Func<T, double> EmitConverter()
    {
      ThrowIfNotConvertableToDouble(typeof(T));

      var method = new DynamicMethod(string.Empty, typeof(double), TypeArray<T>.Value);
      var il = method.GetILGenerator();

      il.Emit(OpCodes.Ldarg_0);
      if (typeof(T) != typeof(double))
      {
        il.Emit(OpCodes.Conv_R8);
      }
      il.Emit(OpCodes.Ret);

      return (Func<T, double>)method.CreateDelegate(typeof(Func<T, double>));
    }
  }

  public static double ConvertToDouble(T value)
  {
    return ToDoubleConverterHolder.Value(value);
  }
}

Where:

  • ThrowIfNotConvertableToDouble(Type) is a simple method that makes sure the given type can be converted to double, i.e. some numeric type or bool.
  • TypeArray is a helper class to produce new[]{ typeof(T) }

The Utils.ConvertToDouble method converts any numeric value to double in the most efficient way, shown by the answer to this question.

It works like a charm - thanks man.

+1  A: 

You can use the Convert class.

ConsumeValue(Convert.ToDouble(value));

Not sure about ToDouble's internals... but probably the best you can do.

Janus Tøndering
No, I cannot. Convert.ToDouble is not a generic method.
mark
Works fine in C# 3.0 (NET 3.5)
Janus Tøndering
This is because T is cast to object and then Convert.ToDouble(object) overload is called - you have traded explicit boxing to an implicit one. Check for yourself.
mark
A: 

Why not just add a double-specific overload for F alongside the generic version?

public void F(IList<double> values)
{
    foreach (double value in values)
    {
        ConsumeValue(value);
    }
}

Now if you call F(someDoubleList) it'll call the non-generic version, and with any other list the generic one will get called.

tzaman
I have IList<T> instance. It is a given. How do I make it IList<double>?
mark
`if (typeof(T) == typeof(double)) IList<double> dlist = (IList<double>)list`
thecoop
And what if typeof(T) == typeof(int)? or typeof(float) or typeof(uint)?
mark
A: 

Although the scenario still isn't very clear (see my comment), this is never going to work. You will have to provide a custom class or method that can convert from your generic T to a double.

The unboxing isn't even relevant, as the cast in

ConsumeValue((double)(object)value);

will throw an InvalidCastException if value is not a double itself. (see this blog entry by Eric Lippert for the reasons why.)

You'll have to preprocess the input, the generic variant will not work.

Edit:

I'd choose Convert.ToDouble. Only if performance is ab-so-lu-te-ly top priority, I'd go with dynamic method. It adds enough complexitely to avoid it, if possible. The performance gain of around 50% looks significant of course, but, in the scenario given by Lasse, on my machine I gain around 150ms when iterating over 10000000 (ten million) items, saving you 0,000015 millisecond each iteration.

Willem van Rumpt
You are right. I just wanted to give as simple an example as possible and ended up with just plain bad code. Edited the question to correct this unfortunate mistake.
mark
You could use the Convert.ToDouble suggested by other answers. But as I understand you're concerned by the performance issue caused by boxing / unboxing. In that case Convert.ToDouble might be a worse choice. Still, unless tests have already shown that the conversions are really a bottleneck, I would go for it.
Willem van Rumpt
Edited my question yet again.
mark
+3  A: 

NOTE: There was a bug in my initial code for instance-based code generation. Please re-check the code below. The changed part is the order of loading values onto the stack (ie. the .Emit lines). Both the code in the answer and the repository has been fixed.

If you want to go the route of code generation, as you hint to in your question, here's sample code:

It executes ConsumeValue (which does nothing in my example) 10 million times, on an array of ints and an array of booleans, timing the execution (it runs all the code once, to remove JIT overhead from skewing the timing.)

The output:

F1 ints = 445ms         <-- uses Convert.ToDouble
F1 bools = 351ms
F2 ints = 159ms         <-- generates code on each call
F2 bools = 167ms
F3 ints = 158ms         <-- caches generated code between calls
F3 bools = 163ms

Roughly 65% less overhead with code generation.

The code is available from my Mercurial repository here: http://hg.vkarlsen.no/hgweb.cgi/StackOverflow, browse it by finding your SO question number.

The code:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Reflection;
using System.Reflection.Emit;

namespace ConsoleApplication15
{
    class Program
    {
        public static void F1<T>(IList<T> values) where T : struct
        {
            foreach (T value in values)
                ConsumeValue(Convert.ToDouble(value));
        }

        public static Action<T> GenerateAction<T>()
        {
            DynamicMethod method = new DynamicMethod(
                "action", MethodAttributes.Public | MethodAttributes.Static,
                CallingConventions.Standard,
                typeof(void), new Type[] { typeof(T) }, typeof(Program).Module,
                false);
            ILGenerator il = method.GetILGenerator();

            il.Emit(OpCodes.Ldarg_0); // get value passed to action
            il.Emit(OpCodes.Conv_R8);
            il.Emit(OpCodes.Call, typeof(Program).GetMethod("ConsumeValue"));
            il.Emit(OpCodes.Ret);

            return (Action<T>)method.CreateDelegate(typeof(Action<T>));
        }

        public static void F2<T>(IList<T> values) where T : struct
        {
            Action<T> action = GenerateAction<T>();
            foreach (T value in values)
                action(value);
        }

        private static Dictionary<Type, object> _Actions =
            new Dictionary<Type, object>();
        public static void F3<T>(IList<T> values) where T : struct
        {
            Object actionObject;
            if (!_Actions.TryGetValue(typeof(T), out actionObject))
            {
                actionObject = GenerateAction<T>();
                _Actions[typeof (T)] = actionObject;
            }
            Action<T> action = (Action<T>)actionObject;
            foreach (T value in values)
                action(value);
        }

        public static void ConsumeValue(double value)
        {
        }

        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();

            int[] ints = Enumerable.Range(1, 10000000).ToArray();
            bool[] bools = ints.Select(i => i % 2 == 0).ToArray();

            for (int pass = 1; pass <= 2; pass++)
            {
                sw.Reset();
                sw.Start();
                F1(ints);
                sw.Stop();
                if (pass == 2)
                    Console.Out.WriteLine("F1 ints = "
                        + sw.ElapsedMilliseconds + "ms");

                sw.Reset();
                sw.Start();
                F1(bools);
                sw.Stop();
                if (pass == 2)
                    Console.Out.WriteLine("F1 bools = "
                        + sw.ElapsedMilliseconds + "ms");

                sw.Reset();
                sw.Start();
                F2(ints);
                sw.Stop();
                if (pass == 2)
                    Console.Out.WriteLine("F2 ints = "
                        + sw.ElapsedMilliseconds + "ms");

                sw.Reset();
                sw.Start();
                F2(bools);
                sw.Stop();
                if (pass == 2)
                    Console.Out.WriteLine("F2 bools = "
                        + sw.ElapsedMilliseconds + "ms");

                sw.Reset();
                sw.Start();
                F3(ints);
                sw.Stop();
                if (pass == 2)
                    Console.Out.WriteLine("F3 ints = "
                        + sw.ElapsedMilliseconds + "ms");

                sw.Reset();
                sw.Start();
                F3(bools);
                sw.Stop();
                if (pass == 2)
                    Console.Out.WriteLine("F3 bools = "
                        + sw.ElapsedMilliseconds + "ms");
            }
        }
    }
}

Note that if you make GenerationAction, F2/3 and ConsumeValue non-static, you have to change the code slightly:

  1. All Action<T> declarations becomes Action<Program, T>
  2. Change the creation of the DynamicMethod to include the "this" parameter:

    DynamicMethod method = new DynamicMethod(
        "action", MethodAttributes.Public | MethodAttributes.Static,
        CallingConventions.Standard,
        typeof(void), new Type[] { typeof(Program), typeof(T) },
        typeof(Program).Module,
        false);
    
  3. Change the instructions to load the right values at the right times:

    il.Emit(OpCodes.Ldarg_0); // get "this"
    il.Emit(OpCodes.Ldarg_1); // get value passed to action
    il.Emit(OpCodes.Conv_R8);
    il.Emit(OpCodes.Call, typeof(Program).GetMethod("ConsumeValue"));
    il.Emit(OpCodes.Ret);
    
  4. Pass "this" to the action whenever it is called:

    action(this, value);
    

Here's the complete changed program for non-static methods:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Reflection;
using System.Reflection.Emit;

namespace ConsoleApplication15
{
    class Program
    {
        public void F1<T>(IList<T> values) where T : struct
        {
            foreach (T value in values)
                ConsumeValue(Convert.ToDouble(value));
        }

        public Action<Program, T> GenerateAction<T>()
        {
            DynamicMethod method = new DynamicMethod(
                "action", MethodAttributes.Public | MethodAttributes.Static,
                CallingConventions.Standard,
                typeof(void), new Type[] { typeof(Program), typeof(T) },
                typeof(Program).Module,
                false);
            ILGenerator il = method.GetILGenerator();

            il.Emit(OpCodes.Ldarg_0); // get "this"
            il.Emit(OpCodes.Ldarg_1); // get value passed to action
            il.Emit(OpCodes.Conv_R8);
            il.Emit(OpCodes.Call, typeof(Program).GetMethod("ConsumeValue"));
            il.Emit(OpCodes.Ret);

            return (Action<Program, T>)method.CreateDelegate(
                typeof(Action<Program, T>));
        }

        public void F2<T>(IList<T> values) where T : struct
        {
            Action<Program, T> action = GenerateAction<T>();
            foreach (T value in values)
                action(this, value);
        }

        private static Dictionary<Type, object> _Actions =
            new Dictionary<Type, object>();
        public void F3<T>(IList<T> values) where T : struct
        {
            Object actionObject;
            if (!_Actions.TryGetValue(typeof(T), out actionObject))
            {
                actionObject = GenerateAction<T>();
                _Actions[typeof (T)] = actionObject;
            }
            Action<Program, T> action = (Action<Program, T>)actionObject;
            foreach (T value in values)
                action(this, value);
        }

        public void ConsumeValue(double value)
        {
        }

        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();

            Program p = new Program();
            int[] ints = Enumerable.Range(1, 10000000).ToArray();
            bool[] bools = ints.Select(i => i % 2 == 0).ToArray();

            for (int pass = 1; pass <= 2; pass++)
            {
                sw.Reset();
                sw.Start();
                p.F1(ints);
                sw.Stop();
                if (pass == 2)
                    Console.Out.WriteLine("F1 ints = "
                        + sw.ElapsedMilliseconds + "ms");

                sw.Reset();
                sw.Start();
                p.F1(bools);
                sw.Stop();
                if (pass == 2)
                    Console.Out.WriteLine("F1 bools = "
                        + sw.ElapsedMilliseconds + "ms");

                sw.Reset();
                sw.Start();
                p.F2(ints);
                sw.Stop();
                if (pass == 2)
                    Console.Out.WriteLine("F2 ints = "
                        + sw.ElapsedMilliseconds + "ms");

                sw.Reset();
                sw.Start();
                p.F2(bools);
                sw.Stop();
                if (pass == 2)
                    Console.Out.WriteLine("F2 bools = "
                        + sw.ElapsedMilliseconds + "ms");

                sw.Reset();
                sw.Start();
                p.F3(ints);
                sw.Stop();
                if (pass == 2)
                    Console.Out.WriteLine("F3 ints = "
                        + sw.ElapsedMilliseconds + "ms");

                sw.Reset();
                sw.Start();
                p.F3(bools);
                sw.Stop();
                if (pass == 2)
                    Console.Out.WriteLine("F3 bools = "
                        + sw.ElapsedMilliseconds + "ms");
            }
        }
    }
}
Lasse V. Karlsen
Wow. Very interesting, it is going to take me some time to verify it, but sounds promising.
mark
Please make sure that you verify that you're using the right version of the code. I just fixed a bug in the order of instructions emitted.
Lasse V. Karlsen
You could even increase performance by caching the generated action in some singleton-like slot á la `ConvertAction<TAction>.Instance`. That way you won't have to hassle around with a dictionary and worry about thread-safety.
herzmeister der welten
Where/how would I declare such a thing?
Lasse V. Karlsen
@Lasse V. Karlsen - quickly made a pastebin sample: http://csharp.pastebin.com/Bpmj0zzF ... didn't add a performance test, feel free to do so ;-)
herzmeister der welten
Updated my question. Used your code to write generic to double converter. Thank you very much again.
mark
@herzmeister, I didn't consider a new class for it, this was just a sample project anyway. Yes, I know static fields in a generic class will be per type used, just didn't get how to do it without the class :) Thanks.
Lasse V. Karlsen