UProLa

Неокріпші думки

Порівняння швидкодії C# і F#. Обчислення CRC32

with 2 comments

Як відомо, платформа .NET не обмежена мовою C#, а є досить універсальною віртуальною машиною. Для демонстрації цього факту були розроблені Visual Basic.NET, IronPython, F# (офіційно підтримуються зі сторони мікрософту) і портовано десятки інших мов.

Як би не так. Ключовою брехнею у вище наведеному абзаці є згадування про F#. Майкрософт хотіли не продемонструвати можливість програмування на функц. мовах, а дати можливість це робити. Після знайомства з O’Caml у мене склалось враження, що компілятори діалектів ML (а F# – майже клон O’Caml, читай “порт O’Caml на .NET” у плані синтаксису) можуть генерувати машинний код, близький по швидкодії до імперативного. В інтернеті можна знайти багато прикладів для цього, тому стало цікаво перевірити дану думку самому.

У якості перевірки взяв алгоритм обчислення CRC-32, тільки тому, що мені на очі потрапила його реалізація на C#, злизана з С++ коду на вікіпедії. Приведу її.

	/// Вычислить хэш
	/// <summary>
	/// <param name="s">Строка</param>
	/// <returns>Хэш в hex-формате</returns>
	public static string GenerateHash(string s)
	{
		var bytes = Encoding.Default.GetBytes(s);
		const uint poly = 0xedb88320;
		var table = new uint[256];
		for (uint i = 0; i < table.Length; ++i)
		{
			uint temp = i;
			for (int j = 8; j > 0; --j)
			{
				if ((temp &amp; 1) == 1)
				{
					temp = (temp >> 1) ^ poly;
				}
				else
				{
					temp >>= 1;
				}
			}
			table[i] = temp;
		}

		uint crc = 0xffffffff;
		for (int i = 0; i < bytes.Length; ++i)
		{
			byte index = (byte)(((crc) & 0xff) ^ bytes[i]);
			crc = (crc >> 8 ) ^ table[index];
		}
		return (~crc).ToString("x");
	}

Підхід №1. Імперативний F#

Цікавою особливістю ML мов є дозвіл імперативного програмування. Цикли, змінні у якості саме змінних, процедури і інфіксні опратори (гиги) дають можливість створити відображення C# -> F# практично без змін:

 
    let GenerateCrc32Hash (s : string) =
        let bytes = Encoding.Default.GetBytes(s)
        let poly : uint32 = 0xedb88320u
        let table : uint32 array = Array.zeroCreate 256
        for i = 0 to table.Length - 1 do
            let mutable temp : uint32 = Convert.ToUInt32 i
            for j = 8 downto 1 do
                if (temp &&& 1u) = 1u
                    then temp <- (temp >>> 1) ^^^ poly
                    else temp <- (temp >>> 1)
                table.[i] <- temp

        let mutable crc : uint32 = 0xffffffffu
        for i = 0 to bytes.Length - 1 do
            let index : byte = (Convert.ToByte (crc &&& 0xffu)) ^^^ bytes.[i]
            crc <- (crc >>> 8 ) ^^^ table.[(Convert.ToInt32 index)]
        (~~~crc).ToString("x")

Якщо ви губитесь у ML, то ось маленькі підказки по коду:

  • За допомогою let можна починати функції або створювати константи
  • За допомогою let mutable можна створювати змінні, а потім за допомогою опертора <- змінювати значення змінної
  • F# по змовчуванню вмикає режим indetation, тобто як і в Пітоні відступами тут позначають локальні блоки одного рівня
  • Бітові операції складаються з потрійного C# еквіваленту

Підхід №2. Функціональний F#

В цьому місці мені довелось повозитись, оскільки я не вмію писати у функціональному стилі. Наслідком стало багаторазове переписування коду, щоб тезис посту був щонайменше неспростованим. Зупинився на такому варіанті (якщо хтось знає спосіб покращити код – буду вдячний):

    /// Порахувати таблицю для CRC32
    let CalcCrc32Table () = 
        let inline calcTemp (current : uint32) =
            if current &&& 1u = 1u
                then (current >>> 1) ^^^ 0xedb88320u
                else current >>> 1
        Array.init 256 (fun i -> uint32 i |> calcTemp |> calcTemp |> calcTemp |> calcTemp |> calcTemp |> calcTemp |> calcTemp |> calcTemp)

    /// Знайти хеш. Таблиця перераховуєтсья при кожному запуску
    let GenerateCrc32Hash2 (s : string) =
        let table = CalcCrc32Table ()
        let byteCrc crc (elem:byte) = 
            let index = int (((byte)crc) ^^^ elem) in
            (crc >>> 8 ) ^^^ table.[index]
        let crcResult = Array.fold byteCrc 0xffffffffu (Encoding.Default.GetBytes(s))
        (~~~crcResult).ToString("x")

Як сказали би функціональщики, такий код більше відображає алгоритм, ніж набір імперативних інструкцій. До-речі, ні цикли, ні рекурсії не було використано жодного разу, функції з модулю Array зробили потрібні нам речі у один виклик. Жалкую тільки про те, що не зміг знайти хорошого способу викликати функцію 8 разів саму на себе…

Підхід №3. Ще більш функціональний F#

Якщо не брати до уваги швидкодію, а спробути зробити код зрозумілішим, то я пропоную наступний варіант:

    /// Паттерн, який показує значення останнього (молодшого) біту
    let (|LastBitIs_0|LastBitIs_1|) = function
        | num when num &&& 1u = 0u -> LastBitIs_0
        | _ -> LastBitIs_1

    /// Порахувати таблицю для CRC32
    let CalcCrc32Table2 () = 
        let calcTemp current =
            match current with
            | LastBitIs_1 -> (current >>> 1) ^^^ 0xedb88320u
            | LastBitIs_0 -> current >>> 1
        Array.init 256 (fun i -> uint32 i |> calcTemp |> calcTemp |> calcTemp |> calcTemp |> calcTemp |> calcTemp |> calcTemp |> calcTemp)

    /// Знайти хеш. Таблиця перераховуєтсья при кожному запуску
    let GenerateCrc32Hash3 (s : string) =
        let table = CalcCrc32Table2 ()
        let byteCrc crc elem = 
            let index = int (((byte)crc) ^^^ elem) in
            (crc >>> 8 ) ^^^ table.[index]
        let crcResult = ~~~(Array.fold byteCrc 0xffffffffu (Encoding.Default.GetBytes s)) in
        crcResult.ToString "x"

Порівняння

Порівняння я робив у двох режимах – побудова таблиці і обчислення хешу. У першому режимі я багато разів (10 000) викликав функцію хешування на вхідному рядку нульової довжини. У другому режимі я викликав функцію хешування всього лиш один раз, але на рядку довжини 10 000 000. Результати я перевірив для режиму Debug, Release x86 і Release x64. (Release – це включення усіх можливих оптимізацій компілятора)

using System;
using System.Diagnostics;

namespace CryptTester
{
    class Program
    {
        static Stopwatch sw = new Stopwatch();
        static string input = new string('x', 0);
        static int count = 1;

        static long test(Func<string, string> testFunc)
        {
            sw.Restart();
            for (int i = 0; i < count; i++) testFunc(input);
            sw.Stop();
            return sw.ElapsedMilliseconds;
        }

        static void Main(string[] args)
        {
            Console.WriteLine("C# test result: {0,10} milliseconds", test(CSharp.Crypt.GenerateCrc32Hash));
            Console.WriteLine("F# test result: {0,10} milliseconds", test(FSharp.Crypt.GenerateCrc32Hash));
            Console.WriteLine("F# opt result:  {0,10} milliseconds", test(FSharp.Crypt.GenerateCrc32Hash2));
            Console.WriteLine("F# func result: {0,10} milliseconds", test(FSharp.Crypt.GenerateCrc32Hash3));

            // Debug, table build test
            //C# test result:        717 milliseconds
            //F# test result:        826 milliseconds
            //F# opt result:        1031 milliseconds
            //F# func result:       4337 milliseconds

            // Release x86, table build test
            //C# test result:        546 milliseconds
            //F# test result:        623 milliseconds
            //F# opt result:         589 milliseconds
            //F# func result:       2536 milliseconds

            // Release x64, table build test
            //C# test result:        568 milliseconds
            //F# test result:        839 milliseconds
            //F# opt result:         530 milliseconds
            //F# func result:       3339 milliseconds

            // Debug, crc count test
            //C# test result:       1016 milliseconds
            //F# test result:       1178 milliseconds
            //F# opt result:        1051 milliseconds
            //F# func result:       1046 milliseconds

            // Release x86, crc count test
            //C# test result:        609 milliseconds
            //F# test result:        837 milliseconds
            //F# opt result:         785 milliseconds
            //F# func result:        789 milliseconds

            // Release x64, crc count test
            //C# test result:        600 milliseconds
            //F# test result:        825 milliseconds
            //F# opt result:         782 milliseconds
            //F# func result:        787 milliseconds

            Console.ReadKey();
        }
    }
}

Звісно, по хорошому потрібно було робити багато тестів а потім усереднювати, а результати представити у вигляді гістограми… Думаю, навіть по цим результатам можна уже робити певні висновки.

  • Використання конструкції match зовсім не прикольне при написанні оптимізованих по часу виконання алгоритмів, як видно з тестів побудови таблиці CRC
  • Імператив у F# в цілому повільніший ніж імператив у C# (або я криво написав?)
  • Оптимізатор F# робить своє діло (Release тестування), варіації можна пояснити фазами місяця, і завантаженістю процесора. Проте по тестам дуууже довгих вхідних рядків можу сказати наступне: великі об’єми даних погано впливають на код. Бувало заповільнення у 3 рази в порівнянні з С# (не показано у пості, щоб не зпричинювати паніку)
  • Автомтичне виначення типів працює достатньо добре
  • Я здивований, як непросто знайти реалізацію CRC-32 на F# або O’Caml. Взагалі, досить небагато доступно практичного коду в інтернеті для цих мов. Зате туторіалів та мануалів – хоч лопатою загрібай.

Рефлектор

Окремо хотілось би дослідити декомпіляцію і дизасемблювання оптимізованого F# коду. Власне, .NET Рефлектор робить чудеса:

    public static uint[] CalcCrc32Table()
    {
      uint[] numArray = new uint[256];
      for (int i = 0; i < 256; ++i)
      {
        // ISSUE: reference to a compiler-generated method
        numArray[i] = Crypt.f@1(i);
      }
      return numArray;
    }

    public static string GenerateCrc32Hash2(string s)
    {
      return (~ArrayModule.Fold<byte, uint>((FSharpFunc<uint, FSharpFunc<byte, uint>>) new Crypt.byteCrc@2(Crypt.CalcCrc32Table()), uint.MaxValue, Encoding.Default.GetBytes(s))).ToString("x");
    }

    internal class byteCrc@2 : OptimizedClosures.FSharpFunc<uint, byte, uint>
    {
      public uint[] table;

      internal byteCrc@2(uint[] table)
      {
        this.table = table;
      }

      public override uint Invoke(uint crc, byte elem)
      {
        int index = (int) (byte) crc ^ (int) elem;
        return crc >> 8 ^ this.table[index];
      }
    }

Видно, що

  • Array.init чудесно перетворився у цикл for.
  • Обчислення хешу прекрасно виконується в один рядок
  • Замикання перетворюються у окремий клас. Це потрібно для зберігання посилань на власне замкнені змінні

Не показаною є тільки функція Crypt.f@1, яка є насправді ось тією громіздкою конструкцією з 8 викликів calcTemp. Справа в тому, що ця функція по різному компілюється в залежності від модифікатора inline. Ось що буде без нього (рефлектор не спромігся декомпілювати, то приводжу ILdasm лог):

.method assembly static uint32  'f@1'(int32 i) cil managed
{
  .custom instance void [mscorlib]System.Runtime.CompilerServices.CompilerGeneratedAttribute::.ctor() = ( 01 00 00 00 ) 
  // Code size       43 (0x2b)
  .maxstack  3
  IL_0000:  nop
  IL_0001:  ldarg.0
  IL_0002:  call       uint32 FSharp.Crypt::calcTemp@42(uint32)
  IL_0007:  call       uint32 FSharp.Crypt::calcTemp@42(uint32)
  IL_000c:  call       uint32 FSharp.Crypt::calcTemp@42(uint32)
  IL_0011:  call       uint32 FSharp.Crypt::calcTemp@42(uint32)
  IL_0016:  call       uint32 FSharp.Crypt::calcTemp@42(uint32)
  IL_001b:  call       uint32 FSharp.Crypt::calcTemp@42(uint32)
  IL_0020:  call       uint32 FSharp.Crypt::calcTemp@42(uint32)
  IL_0025:  call       uint32 FSharp.Crypt::calcTemp@42(uint32)
  IL_002a:  ret
} // end of method Crypt::'f@1'

Як бачимо, одна й та ж функція викликається 8 разів сама на себе. У випадку же inline, в даному місці ми тільки побачимо 8 разів продубльований код (не буду приводити лістинг, оскільки він складаєть з 8 продубльованих шматків по 15 рядків кожен). Зауважу, що саме використання inline дозволило зробити F# код швидшим за C# на тестах побудови таблиць.

Резюме

Потрібно признати, що до ідеалу компіляторам функціональщини ще далеко. Окрім незрозумілості алгоритму (хмм… я вище казав інші слова…) додаються витрати на збір сміття (хмм… а хіба не я шено порівнював з С#, котрий займається гарбаджколекшоном не в меншій мірі?) і хитрі функціональні конструкції.

Проте, є ще один висновок: якщо продуктивність компіляторів функціональщини уже приближається до компіляторів імперативщини на алгоритмах, то це означає, що ми не отримаємо заповільнення коду при виборі функ. мови як основної на великому проекті. Імперативщина типу С++, C#, Пітон, Луа може стати нішовою, не основною, допоміжною, а функціональщина типу ML – навпаки, мейнстрімом.

Вичитав на fprog.ru, що Lisp – уже давно не цікавий математикам, а зсув відбувся саме в сторону Haskel, ML i Erlang. (Не забуваємо про суперкомпіляцію Рефалу, котрий щоправда ніде не використовується.) Цим самим Lisp поставлено в одну нішу з Python і Forth – динамічні скриптові мови, що можуть іноді компілюватися і кожен з них володіє своєю бібліотекою алгоритмів і своїми стилями програмування. Це мене радує, бо заради функціональних навичок вчити Лісп мені зовсім не хочеться. А OCaml навпаки, мені видався досить “приємним на дотик”, що я навіть закомітив у вікіпедію свій приклад

Written by danbst

Серпень 24, 2011 at 15:58

Оприлюднено в Програмування

Tagged with , ,

Відповідей: 2

Subscribe to comments with RSS.

  1. TL:DR.🙂

    А про функціональні навички – вчи Схему, її вчити не треба.

    bunyk

    Серпень 25, 2011 at 17:53


Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: