Помогите понять оптимизацию C # - PullRequest
12 голосов
/ 09 февраля 2011

Я играл с C # и хотел ускорить программу. Я внес изменения и смог это сделать. Однако мне нужна помощь в понимании того, почему изменения сделали это быстрее.

Я попытался сократить код до чего-то более понятного в вопросе. Score1 и Report1 - более медленный путь. Score2 и Report2 - более быстрый способ. Первый метод сначала сохраняет строку и int в структуре параллельно. Затем в последовательном цикле он проходит через массив этих структур и записывает их данные в буфер. Второй метод сначала записывает данные в строковый буфер параллельно. Затем в последовательном цикле он записывает строковые данные в буфер. Вот некоторые примеры времени выполнения:

Общее время выполнения 1 = 0,492087 сек. Общее время прогона 2 = 0,273619 с

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

Даже если я уменьшу цикл в Report1, чтобы записать одну строку вывода в буфер, он все равно будет медленнее (общее время около .42 с).

Вот упрощенный код:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.Threading.Tasks;
using System.IO;

namespace OptimizationQuestion
{
    class Program
    {
        struct ValidWord
        { 
            public string word;
            public int score;
        }
        ValidWord[] valid;
        StringBuilder output;
        int total; 

        public void Score1(string[] words)
        {
            valid = new ValidWord[words.Length];

            for (int i = 0; i < words.Length; i++)
            {
                StringBuilder builder = new StringBuilder();

                foreach (char c in words[i])
                {
                    if (c != 'U')
                        builder.Append(c);
                }
                if (words[i].Length == 3)
                {
                    valid[i] = new ValidWord 
                    { word = builder.ToString(), score = words[i].Length };
                }
            }
        }
        public void Report1(StringBuilder outputBuffer)
        {
            int total = 0;
            foreach (ValidWord wordInfo in valid)
            {
                if (wordInfo.score > 0)
                {
                    outputBuffer.AppendLine(String.Format("{0} {1}", wordInfo.word.ToString(), wordInfo.score));
                    total += wordInfo.score;
                }
            }
            outputBuffer.AppendLine(string.Format("Total = {0}", total));
        }

        public void Score2(string[] words)
        {
            output = new StringBuilder();
            total = 0;           
            for (int i = 0; i < words.Length; i++)
            {
                StringBuilder builder = new StringBuilder();

                foreach (char c in words[i])
                {
                    if (c != 'U')
                        builder.Append(c);
                }
                if (words[i].Length == 3)
                {
                    output.AppendLine(String.Format("{0} {1}", builder.ToString(), words[i].Length));
                    total += words[i].Length;
                }
            }
        }
        public void Report2(StringBuilder outputBuffer)
        {
            outputBuffer.Append(output.ToString());
            outputBuffer.AppendLine(string.Format("Total = {0}", total));
        } 
        static void Main(string[] args)
        {
            Program[] program = new Program[100];
            for (int i = 0; i < program.Length; i++)
                program[i] = new Program(); 

            string[] words = File.ReadAllLines("words.txt");

            Stopwatch stopwatch = new Stopwatch();
            const int TIMING_REPETITIONS = 20;
            double averageTime1 = 0.0;
            StringBuilder output = new StringBuilder();
            for (int i = 0; i < TIMING_REPETITIONS; ++i)
            {
                stopwatch.Reset();
                stopwatch.Start();
                output.Clear();
                Parallel.ForEach<Program>(program, p =>
                    {
                        p.Score1(words);
                    });
                for (int k = 0; k < program.Length; k++)
                    program[k].Report1(output);
                stopwatch.Stop();
                averageTime1 += stopwatch.Elapsed.TotalSeconds;
                GC.Collect();
            }
            averageTime1 /= (double)TIMING_REPETITIONS;
            Console.WriteLine(string.Format("Run 1 Total Average Time = {0:0.000000} sec", averageTime1));
            double averageTime2 = 0.0;
            for (int i = 0; i < TIMING_REPETITIONS; ++i)
            {
                stopwatch.Reset();
                stopwatch.Start();
                output.Clear();
                Parallel.ForEach<Program>(program, p =>
                    {
                        p.Score2(words);
                    });
                for (int k = 0; k < program.Length; k++)
                    program[k].Report2(output);
                stopwatch.Stop();
                averageTime2 += stopwatch.Elapsed.TotalSeconds;
                GC.Collect();
            }
            averageTime2 /= (double)TIMING_REPETITIONS;
            Console.WriteLine(string.Format("Run 2 Total Average Time = {0:0.000000} sec", averageTime2));
            Console.ReadLine();
        }
    }
}

Ответы [ 7 ]

1 голос
/ 28 февраля 2011

Какова цель программы?Score1 и Score2 ничего не говорят нам о том, что пытаются сделать алгоритмы.Похоже, что он пытается найти любое слово, состоящее из трех букв со всеми удаленными заглавными буквами U, является допустимым словом и добавляется в список?

Какой смысл вызывать Parallel.Foreach в группе программслучаи, когда каждой вещи передается один и тот же ввод?И всегда создавать StringBuilder для каждого слова не очень хороший подход.Вы хотите свести к минимуму все новые вызовы в критических областях производительности, чтобы уменьшить количество срабатываний GC.

Я запустил вашу программу в текстовом файле: http://introcs.cs.princeton.edu/data/words.txt

  • Общее время выполнения 1 = 0,160149 с
  • Общее время выполнения 2 = 0,056846 с

Запуск его под профилировщиком выборки VS 2010 показывает, что Report1 примерно в 78 раз медленнее, чемReport2 и составляет большую часть разницы.Главным образом из-за всех вызовов string.Format и Append.

Score1 и Score2 примерно одинаковы по скорости, а Score1 идет немного медленнее из-за дополнительного времени в StringBuilder.ctor и clr.dll.

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

1 голос
/ 28 февраля 2011

Прежде всего, вы распараллеливаете повторные прогоны. Это улучшит ваше время тестирования, но может не сильно помочь вашему реальному рабочему времени. Чтобы точно измерить, сколько времени потребуется, чтобы на самом деле пройти через один список слов, вам нужно иметь ровно один список слов, идущий за раз. В противном случае отдельные потоки, обрабатывающие все списки, в некоторой степени конкурируют друг с другом за системные ресурсы, и время для каждого списка страдает, даже если время для выполнения всех списков в целом быстрее.

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

В вашем случае это становится немного сложнее, потому что построитель строк, необходимый для вашего конечного продукта, не описан как поточно-ориентированный. Это не так уж и плохо. Вот пример вызова параллельного foreach для списка из одного слова:

var locker = new Object(); //I'd actually make this static, but it should end up as a closure and so still work
var OutputBuffer = new StringBuilder(); // you can improve things futher if you can make a good estimate for the final size and force it allocate all the memory it will need up front
int score = 0;
Parallel.ForEach(words, w => 
{
   // We want to push as much of the work to the individual threads as possible.
   // If run in 1 thread, a stringbuilder per word would be bad.
   // Run in parallel, it allows us to do a little more of the work outside of locked code.
   var buf = new StringBuilder(w.Length + 5);
   string word = buf.Append(w.Where(c=>c!='U').Concat(' ').ToArray()).Append(w.Length).ToString();

   lock(locker)
   {
       OutputBuffer.Append(word);
       score += w.Length;
   }
});
OutputBuffer.Append("Total = ").Append(score);

Просто вызовите это 20 раз в обычном последовательно обработанном цикле for. Опять же, он может закончить тесты немного медленнее, но я думаю, что он будет работать в реальном мире немного быстрее из-за недостатка вашего теста. Также обратите внимание, что я набрал это прямо в окне ответа & mdash; Я никогда не пытался скомпилировать событие, и поэтому оно вряд ли будет идеальным прямо из ворот.

После исправления эталонного теста, чтобы более точно отразить, как параллельный код повлияет на ваше реальное время обработки, следующим шагом будет выполнить некоторое профилирование , чтобы увидеть, где на самом деле находится ваша программа. тратить время Вот как вы узнаете, на какие области нужно обратить внимание.

Из любопытства я также хотел бы знать, как работает эта версия:

var agg = new {score = 0, OutputBuffer = new StringBuilder()};
agg = words.Where(w => w.Length == 3)
   .Select(w => new string(w.Where(c => c!='U').ToArray())
   .Aggregate(agg, (a, w) => {a.OutputBuffer.AppendFormat("{0} {1}\n", w, w.Length); score += w.Length;});
agg.OutputBuffer.Append("Total = ").Append(score);
1 голос
/ 21 февраля 2011

Ну, я только что просмотрел ваш код, и мои первые мысли - время действий. В вашем Score1 вы выполняете новое распределение памяти для каждого прогона

valid[i] = new ValidWord 

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

Смысл, который я пытаюсь подчеркнуть, заключается в том, что теперь вам требуется, чтобы приложение выполнило 14000 операций чтения / записи в память, и все это занимает х (микро) секунд. И если выделяется новая память, ей нужно найти разделы памяти правильного размера.

Анализ производительности кода - довольно широкая тема, и я полагаю, что только встроенные программисты действительно используют ее ежедневно. Просто помните, что каждое ваше заявление имеет операции, связанные с ним. Например, при чтении Vector<bool> и Vector<int> у bool будет меньше времени чтения, потому что ему нужно разбить память на биты, а затем вернуть значение, где int может извлечь большие куски памяти.

Ну, это мои 2 цента, надеюсь, это даст вам лучшее представление о том, что искать. У меня дома есть хорошая книга, в которой рассказывается, как анализировать строки кода и какое время процесса он будет использовать. посмотрим, смогу ли я получить его (недавно перенесенный) и обновлю имя для вас.

1 голос
/ 18 февраля 2011

Итак, на codeproject есть сообщение, которое поможет ответить на этот вопрос.

http://www.codeproject.com/KB/cs/foreach.aspx

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

1 голос
/ 17 февраля 2011

Я попытался запустить его через профилировщик, но я не доверяю полученным результатам. (Run1 занимает меньше времени, чем Run2 в нем.) Таким образом, там нет никаких конкретных ответов, но я подозреваю, что допустимый массив [] является виновником:

  1. Это потенциально большое выделение памяти, которое выполняет Run1, а Run2 - нет. Выделение больших кусков памяти может занимать много времени.

  2. Возможно, что массив заканчивается далеко от любых других рабочих данных в физической памяти. По крайней мере, он достаточно большой, чтобы оказаться в куче больших объектов, в то время как похоже, что большинство всего остального попадет в стек или кучу маленьких объектов. Это может означать, что функции Score1 приходится иметь дело с большим количеством ошибок кэша, чем функцией Score2.

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

1 голос
/ 09 февраля 2011

Размер структуры обычно должен быть меньше размера указателя (если производительность является основной проблемой. Microsoft говорит , что все, что меньше 16 байт, работает лучше как структура, если семантика ссылочного типа не существует ' Это необходимо), иначе издержки на его передачу увеличиваются (потому что они передаются по значению) и будут больше, чем это было бы для простой передачи указателя. Ваша структура содержит указатель и целое число (что делает его больше, чем указатель), поэтому вы будете испытывать накладные расходы из-за этого.

См. Когда использовать структуры в разделе этой статьи .

0 голосов
/ 16 февраля 2011

Просто идея: я не делал никаких измерений, но, например, эта строка:

foreach (char c in words[i])
  1. Я думаю, что было бы лучше создать временную переменную для текущейword.

  2. Кроме того, итератор строки может быть медленнее.

Код станет примерно таким:

var currentWord = words[i];
for (int j = 0; j < currentWord.Length; j++){
    char c = currentWord[i]; 
    // ...
}

Новое может также быть проблемой производительности, поскольку кто-то уже определил.Как я сказал в своем комментарии, добавление дополнительных данных профилирования поможет точно определить, что происходит.Или взгляните на сгенерированный код.

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...