is +=1 thread safe

A

Alexander Schmolck

Gary Herron said:
But... It's not!

A simple test shows that. I've attached a tiny test program that shows this
extremely clearly. Please run it and watch it fail.

In [7]: run ~/tmp/t.py
final count: 2000000
should be: 2000000

(I took the liberty to correct your test to actually do what I said, namely
use a numpy.array; just replace ``count = 0`` with ``import numpy; count =
numpy.array(0)``).


'as

p.s. please don't send me copies to on-list replies, at least not without
explicitly mentioning the fact -- I've got better things to do then guessing
whether something was meant to be off-list or not.
 
M

Marc Christiansen

Alexander Schmolck said:
Gary Herron said:
But... It's not!

A simple test shows that. I've attached a tiny test program that
shows this extremely clearly. Please run it and watch it fail.

In [7]: run ~/tmp/t.py
final count: 2000000
should be: 2000000

(I took the liberty to correct your test to actually do what I said, namely
use a numpy.array; just replace ``count = 0`` with ``import numpy; count =
numpy.array(0)``).

I did the same change. Here are the results of four runs:

final count: 1999980
should be: 2000000

final count: 1999996
should be: 2000000

final count: 1999123
should be: 2000000

final count: 1999978
should be: 2000000

This is on a AMD64 X2 using Python 2.5.2 and numpy 1.0.4.

Marc
 
G

Gary Herron

Alexander said:
But... It's not!

A simple test shows that. I've attached a tiny test program that shows this
extremely clearly. Please run it and watch it fail.

In [7]: run ~/tmp/t.py
final count: 2000000
should be: 2000000

(I took the liberty to correct your test to actually do what I said, namely
use a numpy.array; just replace ``count = 0`` with ``import numpy; count =
numpy.array(0)``).

The test was meant to simulate the OP's problem, but even with your
suggestion of using numpy, it *still* fails! Just start increasing the
number of increments by a factor of 2, 4, 10 until it fails:

final count: 1999998
should be: 2000000

final count: 5999997
should be: 6000000

final count: 5995068
should be: 6000000

(Surprisingly, using numpy makes this test *much* slower, meaning the
increment executes many more instructions, which implies hitting a
thread context switch at exactly the critical point is much less
common. But it can happen if you run the test long enough.)

I am running this on a Core2 Duo CPU, but the GIL should prevent that
from affecting the result of the run.

I've reattached the file with the numpy change (and a larger loop
counter) for others to try.

Gary Herron
 
C

Carl Banks

In [7]: run ~/tmp/t.py
final count: 2000000
should be: 2000000
(I took the liberty to correct your test to actually do what I said, namely
use a numpy.array; just replace ``count = 0`` with ``import numpy; count =
numpy.array(0)``).

The test was meant to simulate the OP's problem, but even with your
suggestion of using numpy, it *still* fails!


Ok, so numpy scalars don't support += atomically. Thank you for your
skepticism in discovering this.

However, what I said was not wholly untrue: code in C extensions is
protected by the GIL and thus not interruptable, unless it either
releases the GIL, or calls back into Python code (which is apparently
what numpy scalars do).

To illustrate, a small extension module is included below. Just to
make things interesting, I added a long busy loop in between reading
and setting the counter, just to give the other thread maximum
opportunity to cut in.

If you were to compile it and run the test, you would find that it
works perfectly.


===========================
/* atomic.c */

#include <Python.h>
#include <structmember.h>

typedef struct {
PyObject_HEAD
long value;
} AtomicCounterObject;

static int init(AtomicCounterObject* self, PyObject* args,
PyObject* kwargs) {
self->value = 0;
return 0;
}

static PyObject* iadd(AtomicCounterObject* self, PyObject* inc) {
long incval = PyInt_AsLong(inc);
long store, i;
static int bigarray[100000];
if (incval == -1 && PyErr_Occurred()) return 0;

store = self->value;

/* Give the thread plenty of time to interrupt */
for (i = 0; i < 100000; i++) bigarray++;

self->value = store + incval;

return (PyObject*)self;
}

static PyObject* toint(AtomicCounterObject* self) {
return PyInt_FromLong(self->value);
}

static PyNumberMethods ac_as_number = {
0, /*nb_add*/
0, /*nb_subtract*/
0, /*nb_multiply*/
0, /*nb_divide*/
0, /*nb_remainder*/
0, /*nb_divmod*/
0, /*nb_power*/
0, /*nb_negative*/
0, /*nb_positive*/
0, /*nb_absolute*/
0, /*nb_nonzero*/
0, /*nb_invert*/
0, /*nb_lshift*/
0, /*nb_rshift*/
0, /*nb_and*/
0, /*nb_xor*/
0, /*nb_or*/
0, /*nb_coerce*/
(unaryfunc)toint, /*nb_int*/
0, /*nb_long*/
0, /*nb_float*/
0, /*nb_oct*/
0, /*nb_hex*/
(binaryfunc)iadd, /*nb_inplace_add*/
0, /*nb_inplace_subtract*/
0, /*nb_inplace_multiply*/
0, /*nb_inplace_divide*/
0, /*nb_inplace_remainder*/
0, /*nb_inplace_power*/
0, /*nb_inplace_lshift*/
0, /*nb_inplace_rshift*/
0, /*nb_inplace_and*/
0, /*nb_inplace_xor*/
0, /*nb_inplace_or*/
0, /* nb_floor_divide */
0, /* nb_true_divide */
0, /* nb_inplace_floor_divide */
0, /* nb_inplace_true_divide */
0, /* nb_index */
};

static PyTypeObject AtomicCounterType = {
PyObject_HEAD_INIT(NULL)
0, /*ob_size*/
"AtomicCounter", /*tp_name*/
sizeof(AtomicCounterObject), /*tp_basicsize*/
0, /*tp_itemsize*/
0, /*tp_dealloc*/
0, /*tp_print*/
0, /*tp_getattr*/
0, /*tp_setattr*/
0, /*tp_compare*/
0, /*tp_repr*/
&ac_as_number, /*tp_as_number*/
0, /*tp_as_sequence*/
0, /*tp_as_mapping*/
0, /*tp_hash */
0, /*tp_call*/
0, /*tp_str*/
0, /*tp_getattro*/
0, /*tp_setattro*/
0, /*tp_as_buffer*/
Py_TPFLAGS_DEFAULT, /*tp_flags*/
0, /*tp_doc */
0, /*tp_traverse*/
0, /*tp_clear*/
0, /*tp_richcompare*/
0, /*tp_weaklistoffset*/
0, /*tp_iter*/
0, /*tp_iternext*/
0, /*tp_methods*/
0, /*tp_members*/
0, /*tp_getset*/
0, /*tp_base*/
0, /*tp_dict*/
0, /*tp_descr_get*/
0, /*tp_descr_set*/
0, /*tp_dictoffset*/
(initproc)init, /*tp_init*/
0,
PyType_GenericNew,
};


static PyMethodDef methods[] = {
{0} /* sentinel */
};


PyMODINIT_FUNC initatomic(void) {
PyObject* m;
if (PyType_Ready(&AtomicCounterType) < 0)
return;
m = Py_InitModule("atomic", methods);
if (m == NULL)
return;
Py_INCREF(&AtomicCounterType);
PyModule_AddObject(m, "AtomicCounter", (PyObject
*)&AtomicCounterType);
}

========================
# actest.py

import threading

N = 200000
import atomic; count = atomic.AtomicCounter()

class timer(threading.Thread):
def run(self):
global count
for i in xrange(N):
count += 1

def test():
thread1=timer()
thread2=timer()
thread1.start()
thread2.start()
thread1.join()
thread2.join()
print 'final count:', count
print ' should be:', 2*N

if __name__=='__main__':
test()
========================


Carl Banks
 
C

Carl Banks

However, what I said was not wholly untrue: code in C extensions is
protected by the GIL and thus not interruptable, unless it either
releases the GIL, or calls back into Python code (which is apparently
what numpy scalars do).

And, because I know that someone will be nitpicky: yes, technically it
is interruptable at that point, but other Python threads trying to
execute the same piece of code are not allowed to run.

print 'final count:', count

This should be "int(count)".


Carl Banks
 
G

Gary Herron

Carl said:
Alexander said:
But... It's not!

A simple test shows that. I've attached a tiny test program that shows this
extremely clearly. Please run it and watch it fail.

In [7]: run ~/tmp/t.py
final count: 2000000
should be: 2000000

(I took the liberty to correct your test to actually do what I said, namely
use a numpy.array; just replace ``count = 0`` with ``import numpy; count =
numpy.array(0)``).
The test was meant to simulate the OP's problem, but even with your
suggestion of using numpy, it *still* fails!


Ok, so numpy scalars don't support += atomically. Thank you for your
skepticism in discovering this.

You're welcome.
However, what I said was not wholly untrue: code in C extensions is
protected by the GIL and thus not interruptable, unless it either
releases the GIL, or calls back into Python code (which is apparently
what numpy scalars do).

Yikes. Thanks for that.

However, the upshot of all of this is that one must maintain extreme
skepticism. Unless you know both your Python code and any extension
modules you call, and you know them at a level necessary to find such
details, you must conclude that any operation, no matter how atomic it
my look, may in fact not be atomic.

Gary Herron

To illustrate, a small extension module is included below. Just to
make things interesting, I added a long busy loop in between reading
and setting the counter, just to give the other thread maximum
opportunity to cut in.

If you were to compile it and run the test, you would find that it
works perfectly.


===========================
/* atomic.c */

#include <Python.h>
#include <structmember.h>

typedef struct {
PyObject_HEAD
long value;
} AtomicCounterObject;

static int init(AtomicCounterObject* self, PyObject* args,
PyObject* kwargs) {
self->value = 0;
return 0;
}

static PyObject* iadd(AtomicCounterObject* self, PyObject* inc) {
long incval = PyInt_AsLong(inc);
long store, i;
static int bigarray[100000];
if (incval == -1 && PyErr_Occurred()) return 0;

store = self->value;

/* Give the thread plenty of time to interrupt */
for (i = 0; i < 100000; i++) bigarray++;

self->value = store + incval;

return (PyObject*)self;
}

static PyObject* toint(AtomicCounterObject* self) {
return PyInt_FromLong(self->value);
}

static PyNumberMethods ac_as_number = {
0, /*nb_add*/
0, /*nb_subtract*/
0, /*nb_multiply*/
0, /*nb_divide*/
0, /*nb_remainder*/
0, /*nb_divmod*/
0, /*nb_power*/
0, /*nb_negative*/
0, /*nb_positive*/
0, /*nb_absolute*/
0, /*nb_nonzero*/
0, /*nb_invert*/
0, /*nb_lshift*/
0, /*nb_rshift*/
0, /*nb_and*/
0, /*nb_xor*/
0, /*nb_or*/
0, /*nb_coerce*/
(unaryfunc)toint, /*nb_int*/
0, /*nb_long*/
0, /*nb_float*/
0, /*nb_oct*/
0, /*nb_hex*/
(binaryfunc)iadd, /*nb_inplace_add*/
0, /*nb_inplace_subtract*/
0, /*nb_inplace_multiply*/
0, /*nb_inplace_divide*/
0, /*nb_inplace_remainder*/
0, /*nb_inplace_power*/
0, /*nb_inplace_lshift*/
0, /*nb_inplace_rshift*/
0, /*nb_inplace_and*/
0, /*nb_inplace_xor*/
0, /*nb_inplace_or*/
0, /* nb_floor_divide */
0, /* nb_true_divide */
0, /* nb_inplace_floor_divide */
0, /* nb_inplace_true_divide */
0, /* nb_index */
};

static PyTypeObject AtomicCounterType = {
PyObject_HEAD_INIT(NULL)
0, /*ob_size*/
"AtomicCounter", /*tp_name*/
sizeof(AtomicCounterObject), /*tp_basicsize*/
0, /*tp_itemsize*/
0, /*tp_dealloc*/
0, /*tp_print*/
0, /*tp_getattr*/
0, /*tp_setattr*/
0, /*tp_compare*/
0, /*tp_repr*/
&ac_as_number, /*tp_as_number*/
0, /*tp_as_sequence*/
0, /*tp_as_mapping*/
0, /*tp_hash */
0, /*tp_call*/
0, /*tp_str*/
0, /*tp_getattro*/
0, /*tp_setattro*/
0, /*tp_as_buffer*/
Py_TPFLAGS_DEFAULT, /*tp_flags*/
0, /*tp_doc */
0, /*tp_traverse*/
0, /*tp_clear*/
0, /*tp_richcompare*/
0, /*tp_weaklistoffset*/
0, /*tp_iter*/
0, /*tp_iternext*/
0, /*tp_methods*/
0, /*tp_members*/
0, /*tp_getset*/
0, /*tp_base*/
0, /*tp_dict*/
0, /*tp_descr_get*/
0, /*tp_descr_set*/
0, /*tp_dictoffset*/
(initproc)init, /*tp_init*/
0,
PyType_GenericNew,
};


static PyMethodDef methods[] = {
{0} /* sentinel */
};


PyMODINIT_FUNC initatomic(void) {
PyObject* m;
if (PyType_Ready(&AtomicCounterType) < 0)
return;
m = Py_InitModule("atomic", methods);
if (m == NULL)
return;
Py_INCREF(&AtomicCounterType);
PyModule_AddObject(m, "AtomicCounter", (PyObject
*)&AtomicCounterType);
}

========================
# actest.py

import threading

N = 200000
import atomic; count = atomic.AtomicCounter()

class timer(threading.Thread):
def run(self):
global count
for i in xrange(N):
count += 1

def test():
thread1=timer()
thread2=timer()
thread1.start()
thread2.start()
thread1.join()
thread2.join()
print 'final count:', count
print ' should be:', 2*N

if __name__=='__main__':
test()
========================


Carl Banks
 
A

Aahz

However, the upshot of all of this is that one must maintain extreme
skepticism. Unless you know both your Python code and any extension
modules you call, and you know them at a level necessary to find such
details, you must conclude that any operation, no matter how atomic it
my look, may in fact not be atomic.

Absolutely. Note that your statement is insufficiently encompassing:
any Python library code might easily use classes that define special
methods that cause GIL release.

This is why those of us who champion correct use of threads say that the
only easy way to create working threaded programs is to pass objects
around in Queues and never never never use an object in multiple threads.
 
A

Alexander Schmolck

Gary Herron said:
The test was meant to simulate the OP's problem, but even with your suggestion
of using numpy, it *still* fails!

Well, although I haven't tested it extensively, it doesn't appear to fail for
me, with numpy 1.02 and an AMD Athlon(tm) XP 2800+ under linux 2.6, so it is
possible that numpy's implementation has changed wrt. to GIL usage (or that
the platform makes a difference, but that seems less likely):

In [26]: run ~/tmp/t.py
final count: 2000000
should be: 2000000

In [27]: run ~/tmp/t.py
final count: 2000000
should be: 2000000

In [28]: run ~/tmp/t.py
final count: 2000000
should be: 2000000

In [29]: run ~/tmp/t.py
final count: 2000000
should be: 2000000

In [30]: run ~/tmp/t.py
final count: 10000000
should be: 10000000

I don't claim to have deep knowledge of threading/GIL issues under python, but
my understanding is that you can certainly write an extension that does this
atomically if required (although the bytecode for immutable and mutable is the
same, I think the problem in the immutable case is that the rebinding that
occurs after the inplaceadd step is to a new object, and hence not a no-op).
This isn't to distract from your and Aahz point downthread: this is inherently
a very brittle way to go about things. On the other hand if you have some
already dodgy legacy code (as the OP indicated) that you want to make work
with a minimum of fuzz, it might still be a reasonable option.

'as
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,778
Messages
2,569,605
Members
45,237
Latest member
AvivMNS

Latest Threads

Top