среда, 3 августа 2011 г.

Мне часто доводилось встречать на разных форумах и блогах такое мнение - если вы пишете приложение, критичное к скорости выполнения, то виртуальные функции не для вас. Обычно, в таких случаях советуют применять статический полиморфизм или еще что-то подобное.
На самом деле, с косвенными вызовами в общем и с виртуальными функциями/методами в частности - все хорошо. Современные процессоры умеют предсказывать ветвления даже в случае непрямого вызова, это может свести на нет все накладные расходы, связанные с вызовом виртуальной функции.
Проблема в другом. Часто, виртуальные функции используют следующим образом: создают массив/список указателей на базовый класс, обходят все элементы массива и вызывают виртуальный метод. Это приводит к тому, что количество L1 кэш промахов заметно увеличивается(виртуальный метод может быть переопределен и при каждом новом вызове процессор, в худшем случае, будет выполнять новый код). Помимо этого, такой подход уменьшает вероятность успешного предсказания ветвления.
Я написал небольшой тест, демонстрирующий эти эффекты. Сначала, в список добавляются все элементы одного класса, затем другого и тд. После этого, для каждого элемента списка вызывается виртуальный метод. На моей машине это происходит примерно за 300 миллисекунд. Далее, элементы списка перемешиваются случайным образом, что увеличивает время обхода списка с вызовом метода втрое! И в конце я вызываю, в точно таком же цикле, обычный, не виртуальный метод, который делает ровно тоже самое что и виртуальные методы. Это занимает все те же 300 миллисекунд. Делайте выводы :)

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
 
namespace L1CacheMissDemo
{
    class Program
    {
        static void Main(string[] args)
        {
            var lst = new List<Base>();
 
            for (int i = 0; i < 1000000; i++)
                lst.Add(new Derived1());
            for (int i = 0; i < 1000000; i++)
                lst.Add(new Derived2());
            for (int i = 0; i < 1000000; i++)
                lst.Add(new Derived3());
            for (int i = 0; i < 1000000; i++)
                lst.Add(new Derived4());
 
            var s = new Stopwatch();
            s.Start();
            foreach (var x in lst)
                x.Process();
            s.Stop();
 
            Console.WriteLine("Case 1: {0}", s.ElapsedMilliseconds);
 
            // shuffle elements
            var r = new Random(Guid.NewGuid().GetHashCode());
            for (int i = 0; i < lst.Count; i++)
            {
                var j = r.Next(i, lst.Count);
                var t = lst[i];
                lst[i] = lst[j];
                lst[j] = t;
            }
 
            s.Restart();
            foreach (var x in lst)
                x.Process();
            s.Stop();
 
            Console.WriteLine("Case 2: {0}", s.ElapsedMilliseconds);
 
            var p = new Program();
            s.Restart();
            foreach(var _ in lst)
                p.Process();
            s.Stop();
 
            Console.WriteLine("Case 3: {0}", s.ElapsedMilliseconds);
        }
 
        void Process()
        {
            int k = 0;
            for (int i = 0; i < 100; i++)
                k += i * i;
        }
    }
 
    abstract class Base
    {
        public abstract void Process();
    }
 
    class Derived1 : Base
    {
        public override void Process()
        {
            int k = 0;
            for (int i = 0; i < 100; i++)
                k += i * i;
        }
    }
 
    class Derived2 : Base
    {
        public override void Process()
        {
            int k = 0;
            for (int i = 0; i < 100; i++)
                k += i * i;
        }
    }
 
    class Derived3 : Base
    {
        public override void Process()
        {
            int k = 0;
            for (int i = 0; i < 100; i++)
                k += i * i;
        }
    }
 
    class Derived4 : Base
    {
        public override void Process()
        {
            int k = 0;
            for (int i = 0; i < 100; i++)
                k += i * i;
        }
    }
}

Комментариев нет: