November 13, 2013

Python, processor affinity или как существенно ускорить некоторые программы, ничего не делая

Всем, кто увидел первую версию поста - цифры были кривые из-за turbo boost

Возьмем простой пример tcp клиента и сервера на python. Сервер создает пул из N потоков и ждет соединений с клиентом. Получив соединение передает его на обработку в пул. На каждом соединении сервер ждет от клиента строку данных и имитирует некую обработку. При получении 'bye\n' сервер завершает обработку клиента.

Клиент открывает N соединений с сервером и генерирует на них нагрузку. Общий объем нагрузки за один запуск клиента фиксирован.

Без подсветки синтаксиса
data = ' ' * 100 + '\x0A'
def client(th_count):
    sockets = []
    for i in range(th_count):
        sock = socket.socket()

        for cnt in range(3):
            try:
                sock.connect(host_port)
                break
            except socket.error:
                if cnt == 2:
                    raise
                time.sleep(0.1)

        sockets.append(sock)

    for i in range(NUM_PACKETS):
        sock = random.choice(sockets)
        sock.send(data)

    for sock in sockets:
        sock.send('bye\x0A')
Без подсветки синтаксиса
def server(th_count):
    def process_client(sock):
        num = 0
        while True:
            msg = ""
            while not msg.endswith('\n'):
              msg += sock.recv(1)

            if msg == 'bye\n':
                break

            for i in range(serv_tout):
                pass

            num += 1

    s = socket.socket()
    s.bind(host_port)
    s.listen(5)
    with ThreadPoolExecutor(max_workers=th_count) as pool:
        fts = []

        for i in range(th_count):
            sock,_ = s.accept()
            fts.append(pool.submit(process_client, sock))

        for ft in fts:
            ft.result()

Замеряем сколько времени нужно для одного прогона этой системы с N=4

Без подсветки синтаксиса
$ python mt_test.py client 4 & time python mt_test.py server 4

real    0m8.342s
user    0m7.789s
sys     0m6.587s

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

Без подсветки синтаксиса
$ python mt_test.py client 4 & time taskset 0x00000001 python mt_test.py server 4

real    0m4.663s
user    0m3.186s
sys     0m0.762s

Уличная магия в действии - многопоточная программа исполнилась в 2 раза быстрее, когда мы разрешили использовать только одно ядро процессора.

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

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

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

  • Излишние переключения между потоками
  • Постоянная война за кеш с другими потоками в системе и друг с другом

Итак что происходит: пусть у нас есть два потока, один из которых(первый) сейчас обрабатывает принятые данные, а второй ожидает данных от сокета. Наконец второй поток получает данные и ОС готова продолжить его исполнение. Она смотрит на доступные ядра, видит что первое ядро занято первым потоком и запускает второй поток на исполнение на втором ядре. Второй поток запускается и первым делом пытается захватить GIL. Неудача - GIL захвачен первым потоком. Второй поток снова засыпает, ожидая освобождения GIL.

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

Вторая проблема состоит в том, что второй поток переброшен на исполнение на второе ядро процессора. Когда первый поток освободит GIL, то второй поток продолжит исполнение на втором ядре, потому что ОС знает, что кеши первого и второго уровня у каждого ядра свои и старается без причин не гонять потоки между ядрами. В итоге все имеющиеся потоки "размазываются" по доступным ядрам. Съедая в сумме 100% одного ядра, они превращают это в 12.5% на каждом из 8ми ядер. При этом в промежутках пока питоновские потоки ждут GIL на эти ядра вклиниваются другие потоки из системы, постоянно вытесняя наши данные из кеша.

В итоге питоновские потоки постоянно "бегают" по ядрам. Данные копируются в кеш и из кеша, а каждый кеш-промах стоит до тысяч тактов на обращение к RAM. Даже по меркам питона - серьезные нагрузки.

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

Итоги тестирования.

  • SUM - общее затраченное время
  • SYS - время, затраченное операционной системой
  • USR - время, затраченное в пользовательском режиме
  • XXX_AF - XXX в случае, если выставлена привязка к одному ядру
  • DIFF - отличие в процентах между XXX и XXX_AF

Все измерения сделаны на Core i7-2630QM@800MHz, python 2.7.5, x64, ubuntu 13.10 с усреднением по 7ми выборкам. Долгая война с turbo boost окончилась принудительным переводом процессора в режим минимальных частот.

    -------------------------------------------------------------------------
    | Потоки | SUM   SUM_AF %DIFF | SYS   SYS_AF %DIFF | USR   USR_AF %DIFF |    
    -------------------------------------------------------------------------
    | 1      | 3.35   3.55   -5   | 0.54   0.52   4    | 2.78   3.03    -8  |
    | 2      | 7.26   4.63   36   | 4.91   0.67  86    | 5.10   2.95    42  |
    -------------------------------------------------------------------------
    | 4      | 8.28   4.90   41   | 6.58   0.76  88    | 7.37   3.14    57  |
    | 8      | 7.96   5.00   37   | 6.49   0.84  87    | 7.32   3.15    57  |
    -------------------------------------------------------------------------
    | 16     | 9.77   5.88   40   | 6.53   0.73  89    | 7.01   3.15    55  |
    | 32     | 9.73   6.84   30   | 6.54   0.81  88    | 7.06   3.04    57  |
    -------------------------------------------------------------------------

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

Будет ли что-то подобное в других случаях? Хотя данная программа и обрабатывает данные, приходящие из сокета, но данные приходят быстрее, чем она может их обработать. Таким образом она является CPU bounded. Если программа будет в основном занята ожиданием данных, то выставления привязки к ядру даст меньше ускорения - ОС будет меньше перебрасывать потоки между ядрами. Чем выше нагрузка на процессор, тем больше будет выигрыш.

Когда мы можем получить замедление:

  • если в программе есть места, которые действительно параллельны, например часть работы делается С/С++ библиотекой, которая отпускает GIL
  • Или вы используете jython или ironpython
  • Если вы используете multiprocessing/ProcessPoolExecutor, которые запускают отдельные процессы и не имеют проблем с GIL. Привязка в линуксе наследуется потоками/процессами. Так что для дочерних процессов ее нужно или отменить, или выделить по своему ядру на каждый процесс.
  • В некоторых однопоточных системах, например при использовании gevent

P.S. В 3.3 поведение все то-же.

P.S.S. Нашел уже готовую статью про тоже самое.

Ссылки:
          habrahabr.ru/post/84629
          habrahabr.ru/post/141181
          vimeo.com/49718712
          stackoverflow.com/questions/868568/cpu-bound-and-i-o-bound
          ru.wikipedia.org/wiki/Hyper-threading

Исходники этого и других постов со скриптами лежат тут - github.com/koder-ua. При использовании их, пожалуйста, ссылайтесь на koder-ua.blogspot.com.

2 comments:

Кирилл Маерле said...

Костя, я зачитался, хотя плохо представляю о чем идет речь в деталях. Не хочешь через годик ещё в Москве силы попробовать?

Hope Vignesh said...

It's very great explanation , great work and easily understood ... i like this kind of blog information really very nice..

Python Training Centres in Chennai
Python Training in Chennai