Python - параллелизм

[Olej]

Очень любопытно!
Переделал (добавил + некоторые исправления) вот тот архив mthrs.tgz, который показывался и раньше...

Было бы (на удивление!) здорово, если бы модуль multiprocessing оказался работоспособным под Windows.
Напомню:
- поток берёт свой исполнимый код из функции;
- exec*() (или spawn*(), где они такие есть) берёт свой исполнимый код из исполнимого файла (.exe в случае Windows, ELF-формата в случае Linux);
- fork() берёт свой исполнимый код как копию собственного процесса;

Последней возможности (не которой много лет стояли UNIX системы) нет на дух в Windows, никогда не было ... и никогда уже не будет . Значит нужен какой-то очень искусственный способ сделать нечто подобное в Windows.

С 1-й попытки проломить Python-параллелизм в Windows не получилось... Бесконечной лентой сыпятся мало понятные сообщение вида:

Код: Выделить всё

c:\Python-test\mthrs>mthrsw.py -n10000000 -mm
...
  File "C:\Python33\lib\multiprocessing\forking.py", line 328, in get_command_line
    is not going to be frozen to produce a Windows executable.''')
RuntimeError:
            Attempt to start a new process before the current process
            has finished its bootstrapping phase.

            This probably means that you are on Windows and you have
            forgotten to use the proper idiom in the main module:

                if __name__ == '__main__':
                    freeze_support()
                    ...

            The "freeze_support()" line can be omitted if the program
            is not going to be frozen to produce a Windows executable.
...

С этим нужно отдельно поразбираться...
Потому что это достаточно принципиально:
- на сегодня для Linux видно возможность ускорить вычислительную работу Python за счёт N ядер (даже 2-е таких возможности: os.fork & multiprocessing.pool);
- а для Windows такой возможности пока не видно...

[Olej]

Он ведёт аналогично как и fork() ...

Для полноты картины - новые результаты для 2-х ядерного Atom, каждое из ядер которого с hyperthreading... - Linux хочет это понимать как 4 ядра (что не совсем точно):

Код: Выделить всё

olej@atom:~/2013-WORK/python/mthrs$ cat /proc/cpuinfo | grep 'model name'
model name      : Intel(R) Atom(TM) CPU  330   @ 1.60GHz
model name      : Intel(R) Atom(TM) CPU  330   @ 1.60GHz
model name      : Intel(R) Atom(TM) CPU  330   @ 1.60GHz
model name      : Intel(R) Atom(TM) CPU  330   @ 1.60GHz

А теперь - эквивалентные объёмы работ, но в разное число потоков/процессов:

Код: Выделить всё

olej@atom:~/2013-WORK/python/mthrs$ ./mthrs.py -n10000000 -t1
число процессоров (ядер) = 4
исполнение в Python версия 2.6.5 (r265:79063, Oct  1 2012, 22:07:21)
число ветвей выполнения 1
число циклов в ветви 10000000
============ последовательное выполнение ============
время  3.20 секунд
================ параллельные потоки ================
время  3.23 секунд
=============== параллельные процессы ===============
время  3.22 секунд
=============== модуль multiprocessing ==============
время  3.22 секунд

Код: Выделить всё

olej@atom:~/2013-WORK/python/mthrs$ ./mthrs.py -n5000000
число процессоров (ядер) = 4
исполнение в Python версия 2.6.5 (r265:79063, Oct  1 2012, 22:07:21)
число ветвей выполнения 2
число циклов в ветви 5000000
============ последовательное выполнение ============
время  3.20 секунд
================ параллельные потоки ================
время  5.04 секунд
=============== параллельные процессы ===============
время  1.74 секунд
=============== модуль multiprocessing ==============
время  1.72 секунд

Код: Выделить всё

olej@atom:~/2013-WORK/python/mthrs$ ./mthrs.py -n2500000 -t4
число процессоров (ядер) = 4
исполнение в Python версия 2.6.5 (r265:79063, Oct  1 2012, 22:07:21)
число ветвей выполнения 4
число циклов в ветви 2500000
============ последовательное выполнение ============
время  3.24 секунд
================ параллельные потоки ================
время  5.03 секунд
=============== параллельные процессы ===============
время  1.35 секунд
=============== модуль multiprocessing ==============
время  1.41 секунд

Любопытно, что при переходе от 2-х потоков к 4-м, и в этом случае наблюдается улучшение ... не в 2 раза, естественно, а ... на ~20%

[Olej]

Было бы (на удивление!) здорово, если бы модуль multiprocessing оказался работоспособным под Windows.
...
Потому что это достаточно принципиально:
- на сегодня для Linux видно возможность ускорить вычислительную работу Python за счёт N ядер (даже 2-е таких возможности: os.fork & multiprocessing.pool);
- а для Windows такой возможности пока не видно...

Модуль multiprocessing оказывается вполне работоспособным и под Windows, они (разработчики, R. Oudkerk) там пошли на некоторые хитрые ухищрения ... Я уже сделал несколько работающих примеров для проверки, но выложу их только после обстоятельной подчистки... Для интриги - только скопирую сюда 1-й примитивный выполняющийся Windows-пример (Python 3):

Код: Выделить всё

#!/usr/bin/python3 -O
# -*- coding: utf-8 -*-

from multiprocessing import Pool

def f(x):
    return x*x

if __name__ == '__main__':
    pool = Pool( processes = 4, )
    r = pool.map( f, range( 10 ) )
    print( r )

Код: Выделить всё

c:\Python-test\multip>pool1_3.py
[0, 1, 4, 9, 16, 25, 36, 49, 64, 81]

Читайте об этом подробно ... в реализации Python 2 - здесь, в реализации Python 3 - здесь.

[Olej]

Было бы (на удивление!) здорово, если бы модуль multiprocessing оказался работоспособным под Windows.
...
Потому что это достаточно принципиально:
- на сегодня для Linux видно возможность ускорить вычислительную работу Python за счёт N ядер (даже 2-е таких возможности: os.fork & multiprocessing.pool);
- а для Windows такой возможности пока не видно...

Модуль multiprocessing оказывается вполне работоспособным и под Windows, они (разработчики, R. Oudkerk) там пошли на некоторые хитрые ухищрения ...

А пока - вариант всё того же (выше) приложения mthrsw.py, которое отказывалось работать ... под Windows код приходится выписывать довольно уродливо, ... но работает:

Код: Выделить всё

c:\Python-test\mthrs>mthrsw.py -n10000000 -mstm
число процессоров (ядер) = 2
исполнение в Python версия 3.3.2 (v3.3.2:d047928ae3f6, May 16 2013, 00:03:43) [MSC v.1600 32 bit (Intel)]
число ветвей выполнения 2
число циклов в ветви 10000000
============ последовательное выполнение ============
время 2.38 секунд
================ параллельные потоки ================
время 2.33 секунд
=============== модуль multiprocessing ==============
время 1.58 секунд

[Olej]

И какой выход? Свой диспетчер потоков (в статье ведь этот путь не отвергается)? Например, для вычислительных задач на многоядерном процессоре

Похоже, что такой диспетчер уже написан. И вполне удовлетворительно написан. И это - пакет multiprocessing из стандартного набора модулей библиотеки Python (/usr/lib/python2.7 и т.п.).

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

[Olej]

Модуль multiprocessing оказывается вполне работоспособным и под Windows, они (разработчики, R. Oudkerk) там пошли на некоторые хитрые ухищрения ...

под Windows код приходится выписывать довольно уродливо, ... но работает:

В порядке промежуточных итогов можно зафиксировать следующее:

1. Реализовать разветвление потоков в интерпретируемом байт-коде, когда сам интерпретатор однопоточный - занятие не для слабонервных. Разработчики Python делают это (как видимо до сих пор) через блокировку GIT (т.е. "крутится" только один поток, захвативший эту блокировку ... а остальные пытаются её захватить).
На многопроцессорных системах это годится только для задач, имеющих существенные интервалы пассивных ожиданий: файловый ввод-вывод, ожидание условий, паузы на sleep() и т.д.
На активных вычислительных задачах это не только не даёт выигрыша на N процессорах, но и проигрывает даже последовательному вычислению на одном процессоре!

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

3. Использование fork() из модуля os - не является выходом, поскольку механизма fork() нет в системах Windows, и теряется главное преимущество Python - переносимость между платформами.

4. Но решением может быть использование пакета multiprocessing из стандартного набора модулей библиотеки Python. Он хорошо документирован (см. ссылки в предыдущих сообщениях) и (из документации):

Due to this, the multiprocessing module allows the programmer to fully leverage multiple processors on a given machine. It runs on both Unix and Windows.

5. Объяснение происходящему (под Windows, поскольку нет fork()) можно найти здесь:

The reason is lack of fork() on Windows (which is not entirely true). Because of this, on Windows the fork is simulated by creating a new process in which code, which on Linux is being run in child process, is being run. As the code is to be run in technically unrelated process, it has to be delivered there before it can be run. The way it's being delivered is first it's being pickled and then sent through the pipe from the original process to the new one. In addition this new process is being informed it has to run the code passed by pipe, by passing --multiprocessing-fork command line argument to it. If you take a look at implementation of freeze_support() function its task is to check if the process it's being run in is supposed to run code passed by pipe or not.

5. Идея (остроумная!) состоит в том, чтобы использовать под новый процесс уже откомпилированный Python байт-код ... но для избежания повторного выполнения исполнимого кода (главной программы), а только использования реализующей функции процесса (то же, что и для потока, но для процесса) - под Windows нужно оградить код от повторного исполнения главного модуля...
Т.е., если под Linux код имел вид, например:

Код: Выделить всё

def fun( name ): # функция параллельного процесса
    # ....
    return
...
p = Process( target = fun, args = ( 'параметр', ) ) )
p.start()
p.join()

То для Windows он должен быть переписан например так

Код: Выделить всё

def fun( name ): # функция параллельного процесса
    # ....
    return
...
if __name__ == '__main__':
    freeze_support()
    p = Process( target = fun, args = ( 'параметр', ) ) )
    p.start()
    p.join()

Но приятное здесь состоит в том, что так модифицированный код будет замечательно работать и под Linux (Linux-у это до фени ).

6. Ну а поскольку основной кодировкой для Python декларировано (стандартом языка) Unicode в кодировке UTF-8 (ну наконец то - хоть один умный нашёлся!), то файлы кода Python можно просто механически копировать между Linux и Windows без нарушения работоспособности ... даже при использовании русскоязычных текстовых строк.
P.S. Не забудьте только в начале Python программы вписать такую строчку:

Код: Выделить всё

# -*- coding: utf-8 -*-

[Olej]

И какой выход? Свой диспетчер потоков (в статье ведь этот путь не отвергается)? Например, для вычислительных задач на многоядерном процессоре

Похоже, что такой диспетчер уже написан. И вполне удовлетворительно написан. И это - пакет multiprocessing из стандартного набора модулей библиотеки Python (/usr/lib/python2.7 и т.п.).

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

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

- однонаправленные очереди сообщений:

Код: Выделить всё

bash-4.2$ cat ipc.py 
#!/usr/bin/python3 -O
# -*- coding: utf-8 -*-

from multiprocessing import Process, Queue, Pipe, Value, Array
import os
import queue

def fq( qp, qc ):
    while True:
        try:
            s = qp.get( block=False )
        except queue.Empty:
            break
        print( os.getpid(), ' : ', s )
    qc.put( [  None, 'привет от потомка', os.getpid(), [ i for i in range( 10 ) ] ] )

if __name__ == '__main__':
    print( '=== Queue ===' )
    qp = Queue(); 
    qc = Queue(); 
    p = Process( target=fq, args=( qp, qc ) )
    p.start()
    qp.put( 'привет №1 от родителя' )
    qp.put( 'привет №2 от родителя' )
    print( os.getpid(), ' : ', qc.get( timeout=3 ) ) 
    p.join()

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

- двунаправленные pipe :

Код: Выделить всё

def fp( conn ):
    while True:
       if not conn.poll( 0.3 ): break
       print( os.getpid(), ' : ', conn.recv() )
    conn.send( [  None, 'привет от потомка', os.getpid(), [ i for i in range( 10 ) ] ] )
    conn.close()

if __name__ == '__main__':
    print( '=== Pipe ===' )
    pp, pc = Pipe()
    p = Process( target=fp, args=( pc, ) )
    p.start()
    pp.send( 'привет №1 от родителя' )
    pp.send( 'привет №2 от родителя' )
    print( os.getpid(), ' : ', pp.recv() ) 
    p.join()

- обмен через разделяемую память (shared memory) :

Код: Выделить всё

def fs( n, a, s ):
    print( os.getpid(), ' : ', s[:], ' + ', n.value, ' + ' , a[:] )
    n.value = 3.14159
    z = -1;
    for i in range( len( a ) ):
        z *= -1
        a[ i ] = z * a[ i ] * a[ i ]
    s[:] = 'возврат из потомка'

if __name__ == '__main__':
    print( '=== shared memory ===' )
    num = Value( 'd', 123.456 )
    arr = Array( 'i', range( 10 ) )
    str = Array( 'u', 'привет от родителя' )
    p = Process( target=fs, args=( num, arr, str ) )
    p.start()
    p.join()
    print( os.getpid(), ' : ', str[:], ' + ', num.value, ' + ' , arr[:] )

Класс
Классы multiprocessing.Value и multiprocessing.Array заимствуют терминологию, обозначения, методы (например, с 1-м параметром 'd', 'i', 'u'), заимствованные из стандартного модуля Pyhon array.array, описан здесь.

Вот как это выглядит при исполнении (все 3 фрагмента в файле ipc.py выписаны последовательно друг за другом):

Код: Выделить всё

bash-4.2$ ./ipc.py
=== Queue ===
9468  :  привет №1 от родителя
9468  :  привет №2 от родителя
9467  :  [None, 'привет от потомка', 9468, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]]
=== Pipe ===
9471  :  привет №1 от родителя
9471  :  привет №2 от родителя
9467  :  [None, 'привет от потомка', 9471, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]]
=== shared memory ===
9472  :  привет от родителя  +  123.456  +  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
9467  :  возврат из потомка  +  3.14159  +  [0, -1, 4, -9, 16, -25, 36, -49, 64, -81]

[Olej]

Вот как это выглядит при исполнении (все 3 фрагмента в файле ipc.py выписаны последовательно друг за другом):

Но это ещё не всё ...

К вопросу о переносимости и о приложениях, не зависящих от операционной системы:

1. этот файл ipc.py, подготовленный в Linux, в кодировке UTF-8, с сознательно введенными русскоязычными строками вывода и комментариев...

2. ... был тупо, без какого-либо вмешательства в содержимое, скопирован (по FTP) в Windows:

Код: Выделить всё

Microsoft Windows XP [Версия 5.1.2600]
(С) Корпорация Майкрософт, 1985-2001.

c:\Python-test\mlp>dir
 Том в устройстве C не имеет метки.
 Серийный номер тома: D476-FB08

 Содержимое папки c:\Python-test\mlp

27.08.2013  17:43    <DIR>          .
27.08.2013  17:43    <DIR>          ..
25.08.2013  10:09             1 115 child.py
27.08.2013  13:25             1 986 ipc.py
27.08.2013  13:26             4 201 mlp.hist
24.08.2013  22:24             1 107 pool.py
27.08.2013  13:24               489 URL
               5 файлов          8 898 байт
               2 папок   8 734 273 536 байт свободно

3. ... и там исполняется (сравните с выводом Linux в предыдущем сообщении):

Код: Выделить всё

c:\Python-test\mlp>ipc.py
=== Queue ===
1332  :  привет №1 от родителя
1332  :  привет №2 от родителя
1108  :  [None, 'привет от потомка', 1332, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]]
=== Pipe ===
1444  :  привет №1 от родителя
1444  :  привет №2 от родителя
1108  :  [None, 'привет от потомка', 1444, [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]]
=== shared memory ===
1208  :  привет от родителя  +  123.456  +  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
1108  :  возврат из потомка  +  3.14159  +  [0, -1, 4, -9, 16, -25, 36, -49, 64, -81]

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

Важно то, что такая переносимость Python-проектов будет иметь место не только при миграции между ОС: Windows - Linux - Solaris, но и между аппаратными реализациями: x86, ARM, MIPS ... конечно, при наличии виртуальной машины Python (CPython) в используемом программном окружении на этой архитектуре, но а). всё больше архитектур и окружений (сред исполнения) интегрируют CPython, да и б). раскрутка реализации CPython в новом окружении (где есть C-компилятор, а зачастую даже GCC) не есть сильно сложное занятие (это вам не перетягивание самого компилятора GCC с его библиотеками libc.so и libc++.so ... да и многими другими - libpthread.so и т.д.)

P.S. Подобной степени переносимости, динамической, на уровне файлов готовых к выполнению в чужой ОС, можно видеть, например:
- при выполнении *.exe из Windows под Wine (не всегда удачно);
- при выполении ELF-выполнимых бинарников из Linux в Windows под CygWin или MinGW (тоже временами ... через задницу );
- при выполнении файлов *.class байт-кода Java под любой архитектурой в JVM ... хотя Java-проекты редко распростаняются в уже компилированном виде *.class, разве что WWW-аплеты;
- при переносе Python-приложений приятной особенностью является то, что переносятся с одинаковым успехом консольные (терминальные) и графические (GUI) приложения, при том, что не нарушается языковая локализация (без всяких там CP-866 или CP-1251 ... или Windows-ных Unicode UTF-16 ... кошмар в летнюю ночь!).

[Olej]

В порядке промежуточных итогов можно зафиксировать следующее:

Вот здесь можно найти справочник всех стандартных модулей/функций по состоянию на Python 3.3.2: The Python Standard Library (из оригинальной документации проекта). Здесь интересно увидеть сколько ещё вариантов (сверх опробованных выше) реализовано вокруг параллельного и сопрограммного выполнения:

17. Concurrent Execution
17.1. threading — Thread-based parallelism
17.2. multiprocessing — Process-based parallelism
17.3. The concurrent package
17.4. concurrent.futures — Launching parallel tasks
17.5. subprocess — Subprocess management
17.6. sched — Event scheduler
17.7. queue — A synchronized queue class
17.8. select — Waiting for I/O completion
17.9. dummy_threading — Drop-in replacement for the threading module
17.10. _thread — Low-level threading API
17.11. _dummy_thread — Drop-in replacement for the _thread module

[Olej]

Всё, что здесь обсуждалось, + ещё кое что сверх того (что появилось в последнее время) - упорядочено и описано единым связным текстом, и лежит вот здесь: "Параллельные вычисления".