VPF::оптимизация цикла - Форум программистов

nmn

Дата 21.12.2008, 05:10 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 593
Регистрация: 26.11.2005

Репутация: нет
Всего: 1

что лучше

Код


const int count=100;
int[] a=new int[count]
for(int i=0;i<a.Length;i++);

или

Код


const int count=100;
int[] a=new int[count]
for(int i=0;i<count;i++);

Partizan

Дата 21.12.2008, 10:30 (ссылка)

(нет голосов)

Загрузка ...

Let's do some .NET

Профиль
Группа: Модератор
Сообщений: 2828
Регистрация: 19.12.2005
Где: Санкт-Петербург

Репутация: 8
Всего: 67

nmn,

посмотрите msil, который получился в результате smile

мне кажется, что коды эквивалентны и компилятор сам всё оптимизирует smile

--------------------

СУВ,
Partizan.

QryStaL

Дата 21.12.2008, 12:03 (ссылка)

(нет голосов)

Загрузка ...

Intellectual feast

Профиль
Группа: Участник
Сообщений: 914
Регистрация: 30.11.2005

Репутация: 10
Всего: 32

nmn, лучше использовать foreach.

А из перечисленных вами лучший 1-й, так как во втором случае в каждой итерации цикла будет проверка на выход за границы массива. Во первом случае она отсутствует.

--------------------

I don't need a reason being who I am...

mihryak

Дата 21.12.2008, 12:06 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 731
Регистрация: 28.4.2007
Где: С-Пб

Репутация: 10
Всего: 36

проверил, не поленился smile

IL всё же разный, во втором цикле count вшит в проверку
но разница настолько минимальна (110мс на 100.000.000 итерациях), что всерьёз задаваться целью переписать все циклы, право, не стоит
ну разве что весь остальной код оптимизирован настолько, что там возможные потери ещё меньше

_______________

переписал тест, добавил foreach
относительно первых двух результатов картина сильно изменилась
теперь

Код


Iterations count: 10000000
Length: 2068ms
Direct value: 679ms
Foreach: 1384ms

Это сообщение отредактировал(а) mihryak - 21.12.2008, 12:42

nmn

Дата 21.12.2008, 18:42 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 593
Регистрация: 26.11.2005

Репутация: нет
Всего: 1

Цитата(mihryak @ 21.12.2008, 11:06)

переписал тест, добавил foreach
относительно первых двух результатов картина сильно изменилась
теперь

Код


Iterations count: 10000000
Length: 2068ms
Direct value: 679ms
Foreach: 1384ms

а можно код теста?

Добавлено через 8 минут и 7 секунд

Код


const int count=1000*1000;
const int elCount=1000;
int[] a=new int[elCount];

            Stopwatch t = Stopwatch.StartNew();
            for (int i = 0; i < count; i++)
                for (int j = 0; j < elCount; j++) ;
            t.Stop();
            Console.WriteLine("direct: {0}",t.ElapsedMilliseconds);
            t = Stopwatch.StartNew();
            for (int i = 0; i < count; i++)
                foreach (int j in a) ;
            t.Stop();
            Console.WriteLine("foreach: {0}", t.ElapsedMilliseconds);
            t = Stopwatch.StartNew();
            for (int i = 0; i < count; i++)
                for (int j = 0; j < a.Length; j++) ;
            t.Stop();
            Console.WriteLine("length: {0}", t.ElapsedMilliseconds);

Код


direct: 495
foreach: 708
length: 483

knox

Дата 21.12.2008, 20:03 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 51
Регистрация: 1.12.2007

Репутация: нет
Всего: нет

цикл foreach работает в разы дольше for, там же как и если сравнивать as,is и typeof

nmn

Дата 21.12.2008, 20:07 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 593
Регистрация: 26.11.2005

Репутация: нет
Всего: 1

Цитата(knox @ 21.12.2008, 19:03)

цикл foreach работает в разы дольше for, там же как и если сравнивать as,is и typeof

foreach примерно в 1,5 раза медленнее
но вот Array.Length оказался быстрее чем при использовании переменной

mihryak все таки хотелось бы посмотреть на код вашего теста

Это сообщение отредактировал(а) nmn - 21.12.2008, 20:09

mihryak

Дата 21.12.2008, 21:20 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 731
Регистрация: 28.4.2007
Где: С-Пб

Репутация: 10
Всего: 36

вот первый тест, в котором foreach выигрывал у Length

Код


    class Program
    {
        static void Main(string[] args)
        {
            Stopwatch sw = new Stopwatch();
            const int count = 10000000;
            Console.WriteLine();

            int[] a = new int[count];

            for (int j = 0; j < 10; j++)
            {
                Console.WriteLine();
                Console.WriteLine("Iterations count: {0}", count);

                double value = 0;

                sw.Start();
                for (int i = 0; i < a.Length; i++)
                {
                    a[i] = i;
                    value = Math.Sin(value * i + a[i]);
                }
                sw.Stop();

                Console.WriteLine("Length: {0}ms", sw.ElapsedMilliseconds);
                sw.Reset();


                if (value > 1)
                {
                    return;
                }

                value = 0;

                sw.Start();
                for (int i = 0; i < count; i++)
                {
                    a[i] = i;
                    value = Math.Sin(value * i + a[i]);
                }
                sw.Stop();
                Console.WriteLine("Direct value: {0}ms", sw.ElapsedMilliseconds);

                if (value > 1)
                {
                    return;
                }

                value = 0;

                sw.Start();
                foreach (int i in a)
                {
                    a[i] = i;
                    value = Math.Sin(value * i + a[i]);
                }
                sw.Stop();
                Console.WriteLine("Foreach: {0}ms", sw.ElapsedMilliseconds);

                if (value > 1)
                {
                    return;
                }
            }

            Console.ReadKey();
        }
    }

обратите внимание, что в первом прогоне Length показывает результат почти в 3(!) раза лучше, чем в последующих 9. почему, интересно?

сейчас переписал тест - результаты расположились более ожидаемо

Код


Iterations count: 100000000
Direct: 201,7
Length: 307,2
Foreach: 411,5

вот код:

Код


    class Program
    {
        private static readonly Random random = new Random();
        private const int Count = 100000000;
        private const int TestCount = 10;
        private static readonly int[] array = new int[Count];
        private static readonly long[] testResults = new long[TestCount];

        public Program()
        {
            for (int i = 0; i < Count; i++)
            {
                array[i] = 0;
            }
        }

        static void Main()
        {
            InitializeArray();

            Console.WriteLine("Iterations count: {0}", Count);

            for (int i = 0; i < TestCount; i++)
            {
                Stopwatch sw = new Stopwatch();
                sw.Start();
                if (DirectTest() == Int32.MinValue)
                {
                    return;
                }
                sw.Stop();
                testResults[i] = sw.ElapsedMilliseconds;
            }
            Console.WriteLine("Direct: {0}", GetAverageResult(testResults));

            for (int i = 0; i < TestCount; i++)
            {
                Stopwatch sw = new Stopwatch();
                sw.Start();
                if (LengthTest() == Int32.MinValue)
                {
                    return;
                }
                sw.Stop();
                testResults[i] = sw.ElapsedMilliseconds;
            }
            Console.WriteLine("Length: {0}", GetAverageResult(testResults));

            for (int i = 0; i < TestCount; i++)
            {
                Stopwatch sw = new Stopwatch();
                sw.Start();
                if (ForeachTest() == Int32.MinValue)
                {
                    return;
                }
                sw.Stop();
                testResults[i] = sw.ElapsedMilliseconds;
            }
            Console.WriteLine("Foreach: {0}", GetAverageResult(testResults));

            Console.ReadKey();
        }

        private static int DirectTest()
        {
            int result = 0;
            for (int i = 0; i < Count; i++)
            {
                result |= array[i];
            }

            return result;
        }

        private static int LengthTest()
        {
            int result = 0;
            for (int i = 0; i < array.Length; i++)
            {
                result |= array[i];
            }

            return result;
        }

        private static int ForeachTest()
        {
            int result = 0;
            foreach (int i in array)
            {
                result |= array[i];
            }

            return result;
        }

        private static void InitializeArray()
        {
            for (int i = 0; i < Count; i++)
            {
                array[i] = i;
            }
        }

        private static double GetAverageResult(long[] results)
        {
            double accumulator = 0;
            foreach (long result in results)
            {
                accumulator += result;
            }

            return accumulator / results.Length;
        }
    }

и там, и там в циклах произвожу нагрузочные действия, чтобы не дать оптимизатору выкинуть бесполезный код

PashaPash

Дата 21.12.2008, 21:35 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1233
Регистрация: 3.1.2008

Репутация: 9
Всего: 49

На самом деле результат зависит от конфигурации - debug/release, от конкретного процесора, от размера кэша, от ОС, от фаз луны...
Например, вот release/a.Length на моей машине:

Код


            for (int i = 0; i < a.Length; i++) ;
00000039  xor         edx,edx 
0000003b  mov         dword ptr [ebp-8],edx 
0000003e  nop              
0000003f  jmp         00000044 
00000041  inc         dword ptr [ebp-8] 
00000044  mov         eax,dword ptr [ebp-8]    <-- эти 3 строчки - сравнение a.Length и i. геттер, кстати, заинлайнен
00000047  mov         edx,dword ptr [ebp-0Ch] 
0000004a  cmp         eax,dword ptr [edx+4] 
0000004d  jl          00000041

Вот release с константой. Кстати, массив не используется в цикле, можно сразу выбросить.

Код


            for (int i = 0; i < count; i++) ;
0000001c  xor         edx,edx 
0000001e  mov         dword ptr [ebp-8],edx 
00000021  nop              
00000022  jmp         00000027 
00000024  inc         dword ptr [ebp-8] 
00000027  cmp         dword ptr [ebp-8],64h <-- вот вся разница с a.Length
0000002b  jl          00000024

А вот foreach, видны проверки range. Но иногда работает все равно быстрее - луна помогает.

Код

0000003e  mov         eax,dword ptr [ebp-0Ch] 
00000041  mov         dword ptr [ebp-10h],eax 
00000044  xor         edx,edx 
00000046  mov         dword ptr [ebp-8],edx 
00000049  nop              
0000004a  jmp         0000005F 
0000004c  mov         eax,dword ptr [ebp-8] 
0000004f  mov         edx,dword ptr [ebp-10h] 
00000052  cmp         eax,dword ptr [edx+4] 
00000055  jb          0000005C 
00000057  call        700DAC1C 
0000005c  inc         dword ptr [ebp-8] 
0000005f  mov         eax,dword ptr [ebp-8] 
00000062  mov         edx,dword ptr [ebp-10h] 
00000065  cmp         eax,dword ptr [edx+4] 
00000068  jl          0000004C

На самом деле после IL еще столько уровней, что мерять миллисекунды на конкретной машине - бессмысленно. Скорость будет зависеть, скажем, от количества конвейеров, или от температуры в комнате.

--------------------

Bird's-eye View?

nmn

Дата 22.12.2008, 03:32 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 593
Регистрация: 26.11.2005

Репутация: нет
Всего: 1

значит можно использовать foreach не боясь много(несколько порядков) потерять в производительности?

Код


const int elCount=10000000;
            int[] a=new int[elCount];
            double value = 0;
            Stopwatch t = Stopwatch.StartNew();
            for (int j = 0; j < elCount; j++) value = Math.Sin(a[j]+value);
            t.Stop();
            Console.WriteLine("direct: {0}",t.ElapsedMilliseconds);
            if (value > 10) return;

            t = Stopwatch.StartNew();
            foreach (int j in a) value = Math.Sin(j+value);
            t.Stop();
            Console.WriteLine("foreach: {0}", t.ElapsedMilliseconds);
            if (value > 10) return;

            t = Stopwatch.StartNew();
            for (int j = 0; j < a.Length; j++) value = Math.Sin(a[j]+value);
            t.Stop();
            Console.WriteLine("length: {0}", t.ElapsedMilliseconds);
            if (value > 10) return;

Код


direct: 227
foreach: 278
length: 207

Это сообщение отредактировал(а) nmn - 22.12.2008, 04:12

jonie

Дата 22.12.2008, 08:38 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 5613
Регистрация: 21.8.2005
Где: Владимир

Репутация: 6
Всего: 118

имхо foreach не так показателен для массивов, как for.

PashaPash че эт у тя за IL такой ? смахивает больше на x86 assembler (intel).
вы под чистым .net -ом поглядите IL код.... там, глядишь, и до yeild дойдете мб (хз как там реализован foreach для массивов)....

nmn надо сравнивать скорости для разных массивов) а-то оно уже в кеше и всякая фигня другая...

foreach медленее, остальное всё фигня 8)

--------------------

Что-то не поняли? -> Напейтесь до зеленых человечков... эта сверхцивилизация Вам поможет...

PashaPash

Дата 22.12.2008, 13:48 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1233
Регистрация: 3.1.2008

Репутация: 9
Всего: 49

Цитата(jonie @ 22.12.2008, 08:38

)

PashaPash че эт у тя за IL такой ? смахивает больше на x86 assembler (intel).
вы под чистым .net -ом поглядите IL код.... там, глядишь, и до yeild дойдете мб (хз как там реализован foreach для массивов)....

А это и есть чистый x86 assembler, тот самый, в который IL скомпилировался. Странно сравнивать промежуточные результаты, если можно сравнить код, тем более что его умеет показывать сама студия. foreach для массивов все равно организован внутренними хаками, которые компилируются вот в такой забавный код. Никаких yield там нет, тупо цикл с проверкой границ.

Это сообщение отредактировал(а) PashaPash - 22.12.2008, 13:48

--------------------

Bird's-eye View?

jonie

Дата 23.12.2008, 09:13 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 5613
Регистрация: 21.8.2005
Где: Владимир

Репутация: 6
Всего: 118

Цитата

можно сравнить код, тем более что его умеет показывать сама студия

вот этого я не знал.. хм... теперь будем знать 8)

--------------------

Что-то не поняли? -> Напейтесь до зеленых человечков... эта сверхцивилизация Вам поможет...

source777

Дата 24.12.2008, 23:26 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 1878
Регистрация: 12.3.2007

Репутация: 3
Всего: 56

Цитата(knox @ 21.12.2008, 20:03

)

цикл foreach работает в разы дольше for

Вот и не лень вам писать эту чушь из раза в раз?
Причём опираясь чисто на синтетический тест, на практике всё зависит от конкретной ситуации, а написать синтетический тест, который покажет, что цикл с for работает медленнее цикла с foreach не составит труда хоть сколько-нибудь опытному .NET-программисту!

P.S. Особенно смешно смотрятся подобные метания с учётом того простого факта из практики, что пустых итераций не бывает, а в 90% случаев затраты на одну итерацию оказываются в разы больше, чем на внутренние механизмы foreach. В итоге вы в лучшем практическом(а не синтетическом) случае при 1000 итерациях выиграете от замены foreach на for приблизительно 0.1% от общего времени выполнения цикла. Безусловно это очень мощный стимул вовсе отказаться от foreach. smile

--------------------

Если бы программистам платили за то, чтобы убирать код из программы вместо того, чтобы добавлять его, программы были бы намного лучше © Николас Негропонте

mihryak

Дата 25.12.2008, 00:03 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 731
Регистрация: 28.4.2007
Где: С-Пб

Репутация: 10
Всего: 36

source777, если не ошибаюсь, в одном из подобных топиков от Вас (тебя?) было сообщение, с упоминанием возможности объяснить, почему foreach действительно хорош, но из-за общего нервного тона дискуссии, ей (возможностью) воспользоваться было неуместно
можно ли это сделать здесь? безо всякой иронии спрашиваю

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| .NET для новичков \| Следующая тема »