C# производственное
Jan. 8th, 2014 01:03 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
109по долгу службы неожиданно оказалось нужно оптимизировать относительно тривиальный код (потому что bing pipeline требует, чтобы наш кусок выполнялся за 10 ms, а в этом нашем куске мастурбации с коллекциями по 10К объектов).
в процессе оптимизации открылся ряд вещей, о которых при написании обычного кода просто не задумывается никто.
например, оказалось, что properties are no-go в такого рода коде. за то время, пока происходит доступ - просто доступ - к property, можно десять операций с плавающей точкой сделать.
но вот в кое-что не вторчу никак. например, List[double] размером 10К сортируется за пол-миллисекунды. а List[MyClass] с компарером по тому же double - в десять раз медленнее. wtf? это из-за одного indirection-a? так ведь List[MyStruct] тоже в десять раз медленнее.
в процессе оптимизации открылся ряд вещей, о которых при написании обычного кода просто не задумывается никто.
например, оказалось, что properties are no-go в такого рода коде. за то время, пока происходит доступ - просто доступ - к property, можно десять операций с плавающей точкой сделать.
но вот в кое-что не вторчу никак. например, List[double] размером 10К сортируется за пол-миллисекунды. а List[MyClass] с компарером по тому же double - в десять раз медленнее. wtf? это из-за одного indirection-a? так ведь List[MyStruct] тоже в десять раз медленнее.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
(no subject)
Date: 2014-01-08 09:29 am (UTC)(no subject)
Date: 2014-01-08 11:29 am (UTC)С классами понятно - там случайные блуждания по памяти, они намного медленнее компактного хождения по линейному массиву.
С массивом структур интереснее, там может сказываться и больший их размер (меньше в кэш помещается), и кривой размер (индексация в таком массиве медленнее), и просто отстойность кодогенератора, который не проинлайнил сравнение, например.
(no subject)
Date: 2014-01-08 07:44 pm (UTC)(no subject)
Date: 2014-01-08 02:20 pm (UTC)проперти ведь инлайниться хорошо должны, даже нетривиальные
компарер - посмотри в код листа, там страшненько, три индирекшена получается
(no subject)
Date: 2014-01-08 07:40 pm (UTC)ох-ох. а что делать? задача такая: есть несортированный List[20000] of класс (или struct) со свойством double Rank, надо из него как можно быстрее взять top 10 (или next top 10, но реже), или next next top 10, но ещё реже.
(no subject)
Date: 2014-01-08 08:23 pm (UTC)(no subject)
Date: 2014-01-08 08:25 pm (UTC)(no subject)
Date: 2014-01-08 08:26 pm (UTC)(no subject)
Date: 2014-01-08 08:54 pm (UTC)но мне нужен код, а ни List, ни Linq не умеют partial sort.
(no subject)
Date: 2014-01-08 11:14 pm (UTC)если бы stdlib меньше оглядывался на джаву, а инлайнер был умнее, компареры могли бы иметь 0% оверхед.
причем инлайнера нынешнего даже хватает, можно написать на генериках список с втыкающимся компаратором без оверхеда
но, увы, дефолтный лист этого не делает.
(no subject)
Date: 2014-01-09 01:39 am (UTC)(no subject)
Date: 2014-01-10 04:06 am (UTC)(no subject)
Date: 2014-01-08 10:06 pm (UTC)(no subject)
Date: 2014-01-09 01:36 am (UTC)(no subject)
Date: 2014-01-11 10:25 am (UTC)(no subject)
Date: 2014-01-11 09:14 pm (UTC)(no subject)
Date: 2014-01-09 03:44 am (UTC)1. Формируем список даблов из ранков, попутно округляя значения до 20 бита после запятой и запихивая в младшие биты индекс того элемента в исходном списке, из которого взяли ранк.
2. Сортируем полученный список даблов.
3. Из младших битов первых десяти элементов отсортированного списка выковыриваем индексы Top10 элементов исходного списка.
4. Профит.
(no subject)
Date: 2014-01-09 08:12 am (UTC)(no subject)
Date: 2014-01-09 04:28 pm (UTC)var rnd = new Random();
var items = Enumerable.Range(0, 10000).Select(i => new { DoubleValue = rnd.NextDouble() * 1000000d }).ToArray();
for (int q = 0; q < 3; q++)
{
// a
var rank = items.Select((i, idx) => { var d = i.DoubleValue; var f = Math.Floor(d); return f * 100000 + idx + d - f; }).ToList();
// b
rank.Sort();
// c
var sorted = items.OrderBy(i => i.DoubleValue).ToArray();
}
#0
a: 4.4031 ms
b: 1.0667 ms
c: 6.1935 ms
#1
a: 0.8753 ms
b: 1.1806 ms
c: 4.4381 ms
#2
a: 0.8472 ms
b: 1.0270 ms
c: 4.3769 ms
(no subject)
Date: 2014-01-09 08:56 pm (UTC)(no subject)
Date: 2014-01-09 09:23 pm (UTC)(no subject)
Date: 2014-01-09 10:03 pm (UTC)(no subject)
Date: 2014-01-09 11:39 pm (UTC)C:\xxx\fastsort>cat fastsort.cs using System; using System.Diagnostics; using System.Linq; using System.Collections.Generic; public class Program { public const int ListSize = 10000; public const int NRuns = 1000; public const int precision = 1 << 23; // Keep single-float's 23 bits of significance private static Random Rng = new Random(); struct WrappedDouble : IComparable<WrappedDouble> { public WrappedDouble(double value) : this() { Value = value; } public double Value; public int CompareTo(WrappedDouble o) { return Value.CompareTo(o.Value); } } public static void Main() { SortList(() => (float)Rng.NextDouble()); SortList(() => Rng.NextDouble()); SortList(() => new WrappedDouble(Rng.NextDouble())); SortStructListFast(); } public static void SortList<T>(Func<T> funGenerateElement) { List<T>[] lists = GenerateManyLists(NRuns, ListSize, funGenerateElement); Stopwatch sw = Stopwatch.StartNew(); for (int i = 0; i < lists.Length; ++i) lists[i].Sort(); Console.WriteLine("Sorting {0}: {1}ms", typeof(T), sw.ElapsedMilliseconds); } public static void SortStructListFast() { List<WrappedDouble>[] lists = GenerateManyLists(NRuns, ListSize, () => new WrappedDouble(Rng.NextDouble())); Stopwatch sw = Stopwatch.StartNew(); for (int i = 0; i < lists.Length; ++i) { // Unrolling elegant Select into ugly for-loop: 40% speedup // List<double> tmp_collection_for_sorting = lists[i].Select((e, j) => (Math.Round(e.Value * precision) + (double)j / precision) / precision).ToList(); List<double> tmp_collection_for_sorting = new List<double>(lists[i].Count); for (int j = 0; j < lists[i].Count; ++j) tmp_collection_for_sorting.Add((Math.Round(lists[i][j].Value * precision) + (double)j / precision) / precision); tmp_collection_for_sorting.Sort(); WrappedDouble[] top10 = tmp_collection_for_sorting.Take(10).Select(e => lists[i][(int)((e * precision - Math.Round(e * precision)) * precision)]).ToArray(); // Validation must be commented out for profiling runs // var expected_top10 = lists[i].OrderBy(e => e.Value).Take(10); // if (!top10.SequenceEqual(expected_top10)) // { // expected_top10.Zip(top10, (e, a) => new { Expected = e.Value, Actual = a.Value }).Dump(); // throw new Exception("BANG!"); // } } Console.WriteLine("Sorting structs fast: {0}ms", sw.ElapsedMilliseconds); } private static List<T>[] GenerateManyLists<T>(int nLists, int listSize, Func<T> funGenerateElement) { return Enumerable.Range(0, nLists).Select(_ => Enumerable.Range(0, listSize).Select(__ => funGenerateElement()).ToList()).ToArray(); } } C:\xxx\fastsort>csc fastsort.cs Microsoft (R) Visual C# Compiler version 4.0.30319.33440 for Microsoft (R) .NET Framework 4.5 Copyright (C) Microsoft Corporation. All rights reserved. C:\xxx\fastsort>fastsort.exe Sorting System.Single: 705ms Sorting System.Double: 651ms Sorting Program+WrappedDouble: 1506ms Sorting structs fast: 834ms(no subject)
Date: 2014-01-10 01:52 am (UTC)public const int precision = 1 << 23; // [For rounding approach] Keep single-float's 23 bits of significance public const ulong Mask = 0xFFFFF; // [For direct bit-hacking approach] Abuse 20 least-significant bits ... public static void SortStructListBitHacking() { List<WrappedDouble>[] lists = GenerateManyLists(NRuns, ListSize, () => new WrappedDouble(Rng.NextDouble())); Stopwatch sw = Stopwatch.StartNew(); for (int i = 0; i < lists.Length; ++i) { List<double> tmp_collection_for_sorting = new List<double>(lists[i].Count); for (uint j = 0; j < lists[i].Count; ++j) { tmp_collection_for_sorting.Add( (BitConverter.Int64BitsToDouble( (long)(((ulong)BitConverter.DoubleToInt64Bits(lists[i][(int)j].Value) & ~Mask) + j)))); } tmp_collection_for_sorting.Sort(); WrappedDouble[] top10 = tmp_collection_for_sorting.Take(10).Select(e => lists[i][(int)((ulong)BitConverter.DoubleToInt64Bits(e) & Mask)]).ToArray(); } Console.WriteLine("Sorting via bit hacking: {0}ms", sw.ElapsedMilliseconds); } C:\xxx\fastsort>fastsort.exe Sorting System.Single: 751ms Sorting System.Double: 708ms Sorting Program+WrappedDouble: 1612ms Sorting via rounding: 893ms Sorting via bit hacking: 783ms(no subject)
Date: 2014-01-10 08:51 am (UTC)private static void PartialSort() { List[] lists = GenerateManyLists(NRuns, ListSize, () => new WrappedDouble(Rng.NextDouble())); Stopwatch sw = Stopwatch.StartNew(); for (int i = 0; i < lists.Length; ++i) { PartialQuickSort(lists[i], 0, lists[i].Count - 1, 10); //var top10 = lists[i].Take(10).ToList(); //var expected_top10 = lists[i].OrderByDescending(e => e.Value).Take(10).ToList(); //if (!top10.SequenceEqual(expected_top10)) //{ // for (int j = 0; j < 10; ++j) // { // Console.WriteLine("actual {0} expected {1}", top10[i].Value, expected_top10[i].Value); // } // throw new Exception("BANG!"); //} } Console.WriteLine("Sorting structs with partial quicksort: {0}ms", sw.ElapsedMilliseconds); } private static void PartialQuickSort(List list, int left, int right, int cnt) { if (left < right) { int pivotIdx = Partition(list, left, right); PartialQuickSort(list, left, pivotIdx - 1, cnt); if (left + cnt > pivotIdx) PartialQuickSort(list, pivotIdx + 1, right, left + cnt - pivotIdx); } } private static void Swap(List list, int index1, int index2) { T t = list[index1]; list[index1] = list[index2]; list[index2] = t; } private static int Partition(List list, int left, int right) where T : IComparable { int i = left, j = right; while (i < j) { if (list[i].CompareTo(list[left]) < 0) { Swap(list, i, j); --j; } else ++i; } if (list[i].CompareTo(list[left]) < 0) i--; Swap(list, left, i); return i; }Результаты (в сравнении с остальными твоими алгоритмами):
(no subject)
Date: 2014-01-10 06:26 pm (UTC)Неожиданно. Спасибо, что не поленился написать. Хорошая иллюстрация к "all we need to remember is that intuition is an ineffective approach to writing efficient code." (c) Alexandrescu
(no subject)
Date: 2014-01-10 07:33 pm (UTC)(no subject)
Date: 2014-01-10 07:31 pm (UTC)