Влияние записи массива значительно выше ожидаемого

Question

Я наткнулся на этот эффект при отладке приложения - см. Код репро ниже.

Это дает мне следующие результаты:

Data init, count: 100,000 x 10,000, 4.6133365 secs Perf test 0 (False): 5.8289565 secs Perf test 0 (True): 5.8485172 secs Perf test 1 (False): 32.3222312 secs Perf test 1 (True): 217.0089923 secs

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

Добавлен дополнительный тест UPD;Perf 0 показывает ожидаемые результаты, Perf 1 - показывает аномалию производительности.

class Program
{
    static void Main(string[] args)
    {
        var data = InitData();

        TestPerf0(data, false);
        TestPerf0(data, true);

        TestPerf1(data, false);
        TestPerf1(data, true);

        if (Debugger.IsAttached)
            Console.ReadKey();
    }

    private static string[] InitData()
    {
        var watch = Stopwatch.StartNew();

        var data = new string[100_000];
        var maxString = 10_000;

        for (int i = 0; i < data.Length; i++)
        {
            data[i] = new string('-', maxString);
        }

        watch.Stop();
        Console.WriteLine($"Data init, count: {data.Length:n0} x {maxString:n0}, {watch.Elapsed.TotalSeconds} secs");

        return data;
    }

    private static void TestPerf1(string[] vals, bool testStore)
    {
        var watch = Stopwatch.StartNew();

        var counters = new int[char.MaxValue];
        int tmp = 0;

        for (var j = 0; ; j++)
        {
            var allEmpty = true;

            for (var i = 0; i < vals.Length; i++)
            {
                var val = vals[i];

                if (j < val.Length)
                {
                    allEmpty = false;

                    var ch = val[j];
                    var count = counters[ch];
                    tmp ^= count;

                    if (testStore)
                        counters[ch] = count + 1;
                }
            }

            if (allEmpty)
                break;
        }

        // prevent the compiler from optimizing away our computations
        tmp.GetHashCode();

        watch.Stop();
        Console.WriteLine($"Perf test 1 ({testStore}): {watch.Elapsed.TotalSeconds} secs");
    }

    private static void TestPerf0(string[] vals, bool testStore)
    {
        var watch = Stopwatch.StartNew();

        var counters = new int[65536];
        int tmp = 0;

        for (var i = 0; i < 1_000_000_000; i++)
        {
            var j = i % counters.Length;
            var count = counters[j];
            tmp ^= count;

            if (testStore)
                counters[j] = count + 1;
        }

        // prevent the compiler from optimizing away our computations
        tmp.GetHashCode();

        watch.Stop();
        Console.WriteLine($"Perf test 0 ({testStore}): {watch.Elapsed.TotalSeconds} secs");
    }
}

Answer 1

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

if (testStore)
    counters[ch] = count + 1;

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

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

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

1. Инвертируйте петли i и j. Это полностью удалит переменную allEmpty.
2. Приведите ch к int с var ch = (int) val[j]; - потому что вы ВСЕГДА используете его в качестве индекса.
3. Подумайте, почему это вообще может быть проблемой. Вы вводите новую инструкцию, а любая инструкция платная. Если это действительно «горячая точка» вашего кода, вы можете начать думать о лучших решениях (помните: «преждевременная оптимизация - корень всего зла»).
4. Так как это «тестовая настройка», как следует из названия, это вообще важно? Просто удали его.

---

РЕДАКТИРОВАТЬ: Почему я предложил инвертировать в циклы? С этой маленькой перестановкой кода:

foreach (var val in vals)
{
    foreach (int ch in val)
    {
        var count = counters[ch];
        tmp ^= count;
        if (testStore)
        {
            counters[ch] = count + 1;
        }
    }
}

Я пришел из среды выполнения, подобной этой:

к таким временам выполнения:

Вы все еще думаете, что это не стоит пробовать? Я сохранил здесь несколько порядков и почти исключил эффект if (чтобы быть понятным - все оптимизации отключены в настройках). Если есть особые причины не делать этого, вы должны рассказать нам больше о контексте, в котором будет использоваться этот код.

---

EDIT2 : для подробного ответа. Мое лучшее объяснение, почему возникает эта проблема, заключается в том, что вы перекрестно ссылаетесь на строки кэша. В строках:

for (var i = 0; i < vals.Length; i++)
{
    var val = vals[i];

вы загружаете действительно массивный набор данных. Это намного больше, чем сама строка кэша. Так что, скорее всего, его нужно будет загружать каждую итерацию свежим из памяти в новую строку кэша (смещая старый контент). Это также известно как «очистка кэша», если я правильно помню. Спасибо @mjwills за то, что указал на это в своем комментарии.

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

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