elizarov


Блог Романа Елизарова


Previous Entry Share Next Entry
Память, пропускная способность и многопоточность
elizarov

Оценивая производительность однопоточного кода обычно замеряют время выполнения той или иной операции. Например, как я продемонстрировал ранее, на моем ноутбуке чтение целых чисел из массива и их сложение занимает около 0.37 нс, если чисел мало и они в кэше процессора, и примерно в два раза дольше при последовательном чтении из оперативной памяти. Однако, даже на моем ноутбуке есть два физических ядра, каждое из которых может выполнять по два потока команд одновременно благодаря технологии Hyper Threading (реализации идеи одновременной многопоточности от фирмы Intel), то есть всего 4 аппаратных потока. Для полного использования его ресурсов необходимо обеспечить их все работой, а значит надо писать многопоточный код, что вносит коррективы в методику оценки производительности.

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

    private int runIteration() { 
        int sum = 0; 
        for (int i = 0, n = list.size(); i < n; i++) 
            sum += list.getInt(i); 
        return sum; 
    }

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

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

    private void test() { 
        int counter = 0; 
        while (!done) { 
            dummy += runIteration(size); 
            this.counter.lazySet(++counter); 
        } 
    }

Переменная done объявлена volatile, чтобы тестирующий поток мог принять сигнал об окончании работы. Это, конечно, создает лишнюю синхронизацию с памятью на каждую итерацию и в данном случае можно было бы исхитряться и обойтись без неё, но лучше иметь простой и понятный код. А для передачи информации о количестве выполненных итераций используется метод AtomicInteger.lazySet специально сделанный в Java 1.6 для подобного рода случаев. Он позволяет избежать накладного расхода на запись volatile переменной, который пришлось бы иметь в противном случае.

При числе потоков от 1 до 5 и размере массива от 103 до 107 целых чисел, получаются следующие результаты. Данные указаны в миллиардах (x109) операций в секунду. UPDATE: Так же показано среднеквадратическое отклонение по результатам 17-и замеров по одной секунде каждый (каждый тест идет 20 секунд, первые 3 секунды не учитываются).

Размер12345
1 0002.25 ± 0.014.35 ± 0.054.45 ± 0.014.50 ± 0.014.51 ± 0.03
10 0002.17 ± 0.014.14 ± 0.044.23 ± 0.034.27 ± 0.014.27 ± 0.02
100 0002.07 ± 0.014.01 ± 0.024.12 ± 0.014.18 ± 0.024.18 ± 0.01
1 000 0001.38 ± 0.011.71 ± 0.011.82 ± 0.001.86 ± 0.011.86 ± 0.01
10 000 0001.34 ± 0.011.72 ± 0.011.82 ± 0.011.87 ± 0.011.87 ± 0.01

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

Однако, при больши́х размерах наблюдается совершенно другая картина. Увеличение числа потоков с 1 до 2-х увеличивает пропускную способность всего на 30%, ибо память это общий ресурс. На моей машине память практически достигает потолка своей пропускной способности уже на двух потоках — она не способна их одновременно обслужить. Увеличение числа потоков до 4-х позволяет увеличить пропускную способность еще на 10%, ибо одновременная многопоточность в рамках одного ядра как раз и призвана, в первую очередь, позволить процессору не простаивать в ожидании данных из памяти, а заниматься выполнением другого потока, то есть выжать максимум из подсистемы памяти.

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

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


  • 1
А теперь ещё объясни, почему при переходе от 4 к 5 потокам throughput растёт ;)

Потому что при наличие хоть какой-либо синхронизации (а куда уж без нее?), физические потоки будут так или иначе простаивать. Использование N+1 потока позволяет их дозагрузить, что часто дает небольшой, но прирост в производительности.

Edited at 2012-02-28 09:57 am (UTC)

Ой ли? "volatile" -- это не синхронизация с точки зрения ОС и шедулера. Даже если потоки испытывают contention на volatile, с точки зрения оси это потоки, тупо жгущие циклы (на самом деле, ждущие ответа от когерентности кешей). Никакого voluntary context switch'а даже не будет -- даже если это и было бы реализовано, то это на порядки дороже, чем дождаться записи в общую память.

В связи с этим разворачию вопрос подробнее: если у меня 4 треда, они все нагрузили все ЦПУ и ждут память, не отдавая свои циклы никому, каким образом наличие пятого треда увеличивает пропускную способность?

Так а там, где все жестко на памяти, никакого прироста уже и нет :) Прирост есть на маленьких объемах, когда overhead еще сравнительно большой.

"Переменная done объявлена volatile, чтобы тестирующий поток мог принять сигнал об окончании работы."

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

Пруфлинк?

Несмотря на то, что некоторые оптимизации действительно неприемлемы над volatile-данными, это не "достаточно пугает" компилятор. Если бы ваше замечание оказалось правдой, то бОльшая часть concurrent-примитивов, опирающихся на volatile для обеспечения visibility, работала бы "очень медленно".

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

А "ваш компилятор" -- это кто?

Тем не менее, наш опыт работы над производительностью конкретно HotSpot'а показывает, что не так страшен volatile, как contended volatile. А он, в свою очередь, не намного страшнее просто contended не-volatile.

Во-первых, если убрать тут volatile, то на архитектуре с достаточным числом регисторов метод test() просто будет не остановить (он будет крутиться вечно). А во-вторых, как правильно заметил shipilev, HotSpot этот самый volatile нисколько не пугает. Он его обрабатывает ровно так, как и должен по модели памяти Java.

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

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

Simultaneous Multi-Threading (SMT) в соверменных процессорах (и HT в процессорах Intel в частности) помогает использовать простаивающие вычислительные устройства (такие как, например, целочисленные или вещественные ALU, которых обычно несколько штук), однако это не есть основной двигатель ради которого вообще делают SMT. Основная цель SMT в том, чтобы скомпенсировать задержки на ожидание доступа в память. У меня на эту тему запланирован более любопытный и очень наглядный пример.


Edited at 2012-02-28 12:25 pm (UTC)

Именно поэтому высокопроизводительное ПО (например Linux) идёт в сторону per-cpu data и RCU, о чём собственно рассказывает "The parallel programming book" ( https://www.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html ), правда, в контексте Си.

Спасибо за ссылку, но в данном случае тест был именно с per-cpu data и никакой синхронизации или работы с разделяемыми данными в самом тесте не было (только для сбора статистики). Каждый поток работал со своим массивом данных.

Ссылку на букварь ещё стоит добавить:

What every programmer should know about memory
http://www.akkadia.org/drepper/cpumemory.pdf

Спасибо. На эту тему есть масса статей и даже книг — недостатка материала для изучения не наблюдается.

  • 1
?

Log in

No account? Create an account