Между mutex+int и InterlockedXXX есть разница, ёпт!

[waqur]

Поучительная история о том, как в Питон ещё в 1996 году пытались добавить нормальную многопоточность и убрать глобальную блокировку интерпретатора:

http://dabeaz.blogspot.com/2011/08/inside-look-at-gil-removal-patch-of.html



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

Рекомендую прочитать статейку полностью, но если очень вкратце:

На Питон накладывается патч, который удаляет GIL, и замеры производительности показывают падение в 4 раза:

$ python1.4g Tools/scripts/pystone.py
Pystone(1.0) time for 100000 passes = 3.09
This machine benchmarks at 32362.5 pystones/second

$ python1.4ng Tools/scripts/pystone.py
Pystone(1.0) time for 100000 passes = 12.73
This machine benchmarks at 7855.46 pystones/second

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

#define Py_INCREF(op) (_Py_RefTotal++, (op)->ob_refcnt++)
#define Py_DECREF(op) \
        if (--_Py_RefTotal, --(op)->ob_refcnt != 0) \
                ; \
        else \
                _Py_Dealloc(op)

Используется просто повсеместно. Так вот, патч 1996 года предложил сделать эти операции потокобезопастными через объект pthread_mutex_t:

/* Python/pymutex.c */
...
PyMutex * _Py_RefMutex;
...
int _Py_SafeIncr(pint)
    int *pint;
{
    int result;

    PyMutex_Lock(_Py_RefMutex);
    result = ++*pint;
    PyMutex_Unlock(_Py_RefMutex);
    return result;
}

int _Py_SafeDecr(pint)
    int *pint;
{
    int result;

    PyMutex_Lock(_Py_RefMutex);
    result = --*pint;
    PyMutex_Unlock(_Py_RefMutex);
    return result;
}

Далее самая суть:
As a performance experiment, I decided to comment out the PyMutex_Lock and PyMutex_Unlock calls and run the interpreter in an unsafe mode. With this change, the performance of my single-threaded 'spin-loop' dropped from 12.7 seconds to about 2 seconds (only slightly worse than the 1.9 seconds recorded by the GIL version).


Ну конечно, если в однопоточном случае у нас инструкция INC/DEC, то теперь - парочка вызовов ядра, которые запросто съедят несколько сотен или тысяч инструкций.

Ну нельзя таких людей, которые не знают, чем отличается InterlockedIncrement от целочисленной переменной под мьютексом, подпускать к программированию интерпретаторов! Да, в GCC нет InterlockedIncrement/InterlockedDecrement, но зато есть __sync_fetch_and_add и __attribute__(( align(sizeof(int)) )). И даже если в 1996 году их там не было, всегда была __asm__ и инструкция XADD с префиксом LOCK.

Ну болваны. У нас ещё в 1996 году мог бы быть Питон с нормальной многопоточностью!

Конечно, в более сложных случаях (блокировка на вызове метода) нужна более сложная тактика. Например виндовая функция EnterCriticalSection пытается делать спин-блокировку (не более тысячи циклов), а если захват не удаётся сделать быстро - обращается за помощью к ядру, чтобы отправить текущий поток в сон. Спин-блокировки в пользовательском режиме - это не очень хорошая идея в общем случае, т.к. поток-владелец спин-блокировки может быть принудительно вытеснен планировщиком задач ядра, и тогда все те потоки, кто ждёт блокировку, будут давать 100%ную нагрузку на процессор до тех пор, пока поток-владелец спин-блокировки не получит свой квант времени и не отпустит её. Однако, ограниченное по числу циклов спин-ожидание в пользовательском режиме, с обращением к ядерным функциям синхронизации на семафоре в качестве "плана Б" - это вполне нормальная схема, опробованная на практике виндовыми критическими секциями, которая даёт ощутимый прирост производительности по сравнению с "просто семафорами".

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

Рассмотрим к примеру обновление в памяти большого объекта (больше чем int) или нетривиальную операцию над int при одном потоке-читателе и одном потоке-писателе. Память имеет такой вид:
MARKER1 | VALUE1 | MARKER2 | VALUE2 | MARKER3
Маркеры - это выровненные целые, значения имеют произвольный вид и длину.
Обновляющая сторона безопасно инкрементирует MARKER1, обновляет VALUE1, безопасно инкрементирует MARKER2, обновляет VALUE2, безопасно инкрементирует MARKER3. Читающая сторона копирует всё это хозяйство себе локально в стек (справа налево), при частичном совпадении маркеров у неё есть значение VALUE1 или VALUE2, при полном несовпадении маркеров уходит на спин. Прерывание операции обновления VALUE1 шедулером ядра не имеет значения, т.к. у читателя всегда есть чистое VALUE2. На архитектурах, которые могут перемешивать операции чтения и записи из/в память (не-x86) вставляются инструкции-заборы (FENCE). При программировании на C/C++ заборы нужны всегда, чтобы компилятор не перемудрил и не перемешал порядок доступа к памяти.

Comments

[cd-riper.livejournal.com]

ну да, atomic int операции это не рокет сайнс и давно уже входят в состав и boost, и Qt, и как раз для тех же задач -- подсчета ссылок.

правда, с переносимостью этого дела есть приколы. и, что интересно, когда пишешь embedded код проблема всегда решается просто, потому что на любом процессоре разрешить/запретить прерывания это тривиальная и очень быстрая процедура, а вот в больших системах начинают выдумать всякие глупости на ровном месте, потому что, понятное дело, нельзя в user space вытворять такие фокусы.

[waqur.livejournal.com]

да, помню в DOSе всё было просто: cli/sti и дело в шляпе

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

некоторые из этих нюансов остаются актуальными для обработки сигналов в UNIX'е и APC-процедур в винде