Thread-safe way to add a key to a dict only if it isn't already there?

[Steven D'Aprano]

I have a dict with string keys:

D = {'a': None, 'b': None}

(the values don't matter for this question) and I want to add a key but
only if it isn't already there. If I do the obvious:

if not 'c' in D:
D['c'] = None

there's a Time Of Check to Time Of Use bug where some other thread could
conceivably insert 'c' into the dict between the check and the insertion.

How do I do a thread-safe insertion if, and only if, the key isn't
already there?



Thanks in advance,



--
Steven D'Aprano
"Ever since I learned about confirmation bias, I've been seeing
it everywhere." -- Jon Ronson

[INADA Naoki]

D.setdefault('c', None)

> --
> https://mail.python.org/mailman/listinfo/python-list



--
INADA Naoki <songof...@gmail.com>

[Steven D'Aprano]

On Sat, 07 Jul 2018 02:51:41 +0900, INADA Naoki wrote:

> D.setdefault('c', None)

Oh that's clever!

Thanks!

[Marko Rauhamaa]

Steven D'Aprano <steve+comp....@pearwood.info>:

> On Sat, 07 Jul 2018 02:51:41 +0900, INADA Naoki wrote:
>> D.setdefault('c', None)
>
> Oh that's clever!

Is that guaranteed to be thread-safe? The documentation (<URL: http
s://docs.python.org/3/library/stdtypes.html#dict.setdefault>) makes no
such promise.

At least __collectios_abc.py
contains this method definition for MutableMapping:

def setdefault(self, key, default=None):
'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D'
try:
return self[key]
except KeyError:
self[key] = default
return default

There are more such non-thread-safe definitions.


Marko

[Stefan Behnel]

Marko Rauhamaa schrieb am 07.07.2018 um 15:41:
> Steven D'Aprano <steve+comp....@pearwood.info>:
>> On Sat, 07 Jul 2018 02:51:41 +0900, INADA Naoki wrote:
>>> D.setdefault('c', None)
>>
>> Oh that's clever!
>
> Is that guaranteed to be thread-safe? The documentation (<URL: http
> s://docs.python.org/3/library/stdtypes.html#dict.setdefault>) makes no
> such promise.

It's implemented in C and it's at least designed to avoid multiple lookups
and hash value calculations, which suggests that it's also thread-safe by
design (or by a side-effect of the design). Whether that's guaranteed, I
cannot say, but a change that makes it non-thread-safe would probably be
very controversial.

> At least __collectios_abc.py
> contains this method definition for MutableMapping:
>
> def setdefault(self, key, default=None):
> 'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D'
> try:
> return self[key]
> except KeyError:
> self[key] = default
> return default
>
> There are more such non-thread-safe definitions.

That's a different beast, because Python code can always be interrupted by
thread switches (between each byte code execution). C code cannot, unless
it starts executing byte code (e.g. for calculating a key's hash value) or
explicitly allows a thread switch at a given point.

Stefan

[Ian Kelly]

On Sat, Jul 7, 2018 at 8:03 AM Stefan Behnel <stef...@behnel.de> wrote:
>
> Marko Rauhamaa schrieb am 07.07.2018 um 15:41:

> > Steven D'Aprano <steve+comp....@pearwood.info>:
> >> On Sat, 07 Jul 2018 02:51:41 +0900, INADA Naoki wrote:
> >>> D.setdefault('c', None)
> >>
> >> Oh that's clever!
> >
> > Is that guaranteed to be thread-safe? The documentation (<URL: http
> > s://docs.python.org/3/library/stdtypes.html#dict.setdefault>) makes no
> > such promise.
>

> It's implemented in C and it's at least designed to avoid multiple lookups
> and hash value calculations, which suggests that it's also thread-safe by
> design (or by a side-effect of the design). Whether that's guaranteed, I
> cannot say, but a change that makes it non-thread-safe would probably be
> very controversial.

It's only implemented in C if you're using CPython (and if it's the
builtin dict type and not a subclass). If there's any chance that your
code might run under any other interpreter than CPython, then you
can't rely on the GIL for thread-safety. I would also point out
https://bugs.python.org/issue25343. While some operations are known to
be atomic (and therefore thread-safe), the leaning of the devs seems
to be to refrain from documenting it and instead document that *no*
operations are guaranteed atomic.

> > At least __collectios_abc.py
> > contains this method definition for MutableMapping:
> >
> > def setdefault(self, key, default=None):
> > 'D.setdefault(k[,d]) -> D.get(k,d), also set D[k]=d if k not in D'
> > try:
> > return self[key]
> > except KeyError:
> > self[key] = default
> > return default
> >
> > There are more such non-thread-safe definitions.
>

> That's a different beast, because Python code can always be interrupted by
> thread switches (between each byte code execution). C code cannot, unless
> it starts executing byte code (e.g. for calculating a key's hash value) or
> explicitly allows a thread switch at a given point.

dict.setdefault does potentially call __hash__ and __eq__ on the key.
Since this is part of the lookup I don't know whether it affects
thread-safety as long as the key is properly hashable, but it does
make it more difficult to reason about. I don't *think* that
setdefault calls Py_DECREF, but if it did then that is another
potential point of thread interruption.

By contrast, using a mutex to guard accesses is definitely safe, and
it's also self-documenting of the fact that thread-safety is a
concern.

[Devin Jeanpierre]

On Sat, Jul 7, 2018 at 6:49 AM Marko Rauhamaa <ma...@pacujo.net> wrote:
> Is that guaranteed to be thread-safe? The documentation (<URL: http
> s://docs.python.org/3/library/stdtypes.html#dict.setdefault>) makes no
> such promise.

It's guaranteed to be thread-safe because all of Python's core
containers are thread safe (in as far as they document
behaviors/invariants, which implicitly also hold in multithreaded code
-- Python does not take the approach other languages do of
"thread-compatible" containers that have undefined behavior if mutated
from multiple threads simultaneously). It isn't guaranteed to be
_atomic_ by the documentation, but I bet no Python implementation
would make dict.setdefault non-atomic.

There's no good description of the threading rules for Python data
structures anywhere. ISTR there was a proposal to give Python some
defined rules around thread-safety a couple of years ago (to help with
things like GIL-less python projects), but I guess nothing ever came
of it.

-- Devin

[Ian Kelly]

On Fri, Jul 6, 2018 at 11:56 AM INADA Naoki <songof...@gmail.com> wrote:
>
> D.setdefault('c', None)

Not guaranteed to be atomic.

I think the only safe way to do it is with a Lock.

[Ethan Furman]

On 07/06/2018 10:51 AM, INADA Naoki wrote:

> On Sat, Jul 7, 2018 at 2:49 AM Steven D'Aprano wrote:

>> I have a dict with string keys:
>>

>> --> D = {'a': None, 'b': None}

>> How do I do a thread-safe insertion if, and only if, the key isn't
>> already there?
>

> D.setdefault('c', None)

This is how Enum avoids race conditions when setting up the re.RegexType enumeration.

--
~Ethan~

[Marko Rauhamaa]

Ian Kelly <ian.g...@gmail.com>:

> the leaning of the devs seems to be to refrain from documenting it and
> instead document that *no* operations are guaranteed atomic.

I believe that to be wise. Otherwise, Python would limit its future
implementation options.

The only thing Python should guarantee is that the data structures stay
"coherent" under race conditions. In other words, there cannot be a
segmentation fault. For example, if two threads executed this code in
parallel:

global i
i = 1
i += 1

a legal end result could be that i contains the string "impossible".


Marko

[Rick Johnson]

On Friday, July 6, 2018 at 12:48:04 PM UTC-5, Steven D'Aprano wrote:
> I have a dict with string keys:
>
> D = {'a': None, 'b': None}
>
> (the values don't matter for this question) and I want to add a key but
> only if it isn't already there. If I do the obvious:
>
> if not 'c' in D:
> D['c'] = None

That's been an anti-pattern for _years_! Why did you not offer the setdefault example? Are you actually writing code like this?

[Steven D'Aprano]

On Sun, 08 Jul 2018 00:00:26 +0300, Marko Rauhamaa wrote:

> Ian Kelly <ian.g...@gmail.com>:
>> the leaning of the devs seems to be to refrain from documenting it and
>> instead document that *no* operations are guaranteed atomic.
>
> I believe that to be wise. Otherwise, Python would limit its future
> implementation options.

o_O

By that logic, one should say we shouldn't document the semantics of
operations, so we don't limit the implementation.

"What does list.sort do?"

"It currently sorts the list using a stable comparison sort, but you
can't rely on that it, because we didn't want to limit the
implementation."

Sorting is guaranteed to be stable. Does that limit the implementation
options? Yes, of course it does. So does the fact that it *sorts* --
we're limited to implementations which *sort*, and specifically
comparison sorts (not, for example, radix sorts).

Changing the implementation to a radix sort that only works on ints would
break things. So would changing the implementation to something which
empties the list of all elements. ("The empty list is always sorted.")

Stable semantics are more important than freedom to change implementation.

Whether or not an operation is thread-safe, or atomic, is part of the
semantics of the operation. It's not merely a performance issue, and we
ought to treat it will a bit more respect.

I'm not saying that everything needs to be documented as thread-safe or
not (for at least one release, Python's sorting actually was stable
before it was documented as such) but the gung-ho attitude that safety is
just an implementation detail should be resisted.

Changing implementations from one which is thread safe to one which is
not can break people's code, and shouldn't be done on a whim. Especially
since such breakage could be subtle, hard to notice, harder to track
down, and even harder still to fix.

> The only thing Python should guarantee is that the data structures stay
> "coherent" under race conditions. In other words, there cannot be a
> segmentation fault. For example, if two threads executed this code in
> parallel:
>
> global i
> i = 1
> i += 1
>
> a legal end result could be that i contains the string "impossible".

That wouldn't be coherent. The only coherent results are that i could
equal either 2 or 3:

Possibility 1:

i = 1 # thread 1
i += 1 # thread 1
i = 1 # thread 2
i += 1 # thread 2
assert i == 2

Possibility 2:

i = 1 # thread 1
i = 1 # thread 2
i += 1 # thread 1
i += 1 # thread 2
assert i == 3


Executing statements out of order is impossible, even in threaded code.
Redefining the meaning of the integer literal 1 is impossible (ignoring
unsupported shenanigans with ctypes). Monkey-patching the int __iadd__
method is impossible. So there is no coherent way to get a result of
"impossible" from just adding 1 to 1 in any coherent implementation of
Python.

[Chris Angelico]

On Sun, Jul 8, 2018 at 11:04 AM, Steven D'Aprano
<steve+comp....@pearwood.info> wrote:
>> The only thing Python should guarantee is that the data structures stay
>> "coherent" under race conditions. In other words, there cannot be a
>> segmentation fault. For example, if two threads executed this code in
>> parallel:
>>
>> global i
>> i = 1
>> i += 1
>>
>> a legal end result could be that i contains the string "impossible".
>

> That wouldn't be coherent. The only coherent results are that i could
> equal either 2 or 3:
>
> Possibility 1:
>
> i = 1 # thread 1
> i += 1 # thread 1
> i = 1 # thread 2
> i += 1 # thread 2
> assert i == 2
>
> Possibility 2:
>
> i = 1 # thread 1
> i = 1 # thread 2
> i += 1 # thread 1
> i += 1 # thread 2
> assert i == 3
>
>
> Executing statements out of order is impossible, even in threaded code.
> Redefining the meaning of the integer literal 1 is impossible (ignoring
> unsupported shenanigans with ctypes). Monkey-patching the int __iadd__
> method is impossible. So there is no coherent way to get a result of
> "impossible" from just adding 1 to 1 in any coherent implementation of
> Python.

Python threads don't switch only between lines of code, so the actual
interaction is a bit more complicated than you say. In CPython, the
increment operation is:

3 0 LOAD_GLOBAL 0 (i)
2 LOAD_CONST 1 (1)
4 INPLACE_ADD
6 STORE_GLOBAL 0 (i)

A context switch could happen between any pair of statements. In this
particular example, the end result doesn't change - coherent results
are 2 and 3, nothing else - but in other situations, there may be
times when the separate steps might be significant. For instance, if
you replace "i += 1" with "i += i", to double the value, you'll get
this:

3 0 LOAD_GLOBAL 0 (i)
2 LOAD_GLOBAL 0 (i)
4 INPLACE_ADD
6 STORE_GLOBAL 0 (i)

and that could potentially have both of them load the initial value,
then one of them runs to completion, and then the other loads the
result - so it'll add 1 and 2 and have a result of 3, rather than 2 or
4.

But you're absolutely right that there are only a small handful of
plausible results, even with threading involved.

ChrisA

[Steven D'Aprano]

On Sun, 08 Jul 2018 11:15:17 +1000, Chris Angelico wrote:

[...]

> Python threads don't switch only between lines of code,

As I understand it, there could be a switch between any two byte codes,
or maybe only between certain bytes codes. But certain more fine grained
than just between lines of code.

> so the actual
> interaction is a bit more complicated than you say. In CPython, the
> increment operation is:
>
> 3 0 LOAD_GLOBAL 0 (i)
> 2 LOAD_CONST 1 (1)
> 4 INPLACE_ADD
> 6 STORE_GLOBAL 0 (i)
>
> A context switch could happen between any pair of statements.

If you actually mean *statements* as opposed to byte codes, then the only
place there could be a switch would be either before the LOAD_GLOBAL or
after the STORE_GLOBAL (given that i is a built-in int and cannot have a
custom __iadd__ method).

Is that what you mean?

> In this
> particular example, the end result doesn't change - coherent results are
> 2 and 3, nothing else - but in other situations, there may be times when
> the separate steps might be significant.

Fortunately I wasn't talking about other code snippets, only the one
shown :-)

> For instance, if you replace "i
> += 1" with "i += i", to double the value, you'll get this:
>
> 3 0 LOAD_GLOBAL 0 (i)
> 2 LOAD_GLOBAL 0 (i)
> 4 INPLACE_ADD
> 6 STORE_GLOBAL 0 (i)
>
> and that could potentially have both of them load the initial value,
> then one of them runs to completion, and then the other loads the result
> - so it'll add 1 and 2 and have a result of 3, rather than 2 or 4.

Some people, when confronted with a problem, say, "I know, I'll use
threads". Nothhtwo probw ey ave lems.

> But you're absolutely right that there are only a small handful of
> plausible results, even with threading involved.

Indeed. Even though threading is non-deterministic, it isn't *entirely*
unconstrained.

[Chris Angelico]

On Sun, Jul 8, 2018 at 12:12 PM, Steven D'Aprano
<steve+comp....@pearwood.info> wrote:
> On Sun, 08 Jul 2018 11:15:17 +1000, Chris Angelico wrote:
>
> [...]
>> Python threads don't switch only between lines of code,
>
> As I understand it, there could be a switch between any two byte codes,
> or maybe only between certain bytes codes. But certain more fine grained
> than just between lines of code.
>
>
>> so the actual
>> interaction is a bit more complicated than you say. In CPython, the
>> increment operation is:
>>
>> 3 0 LOAD_GLOBAL 0 (i)
>> 2 LOAD_CONST 1 (1)
>> 4 INPLACE_ADD
>> 6 STORE_GLOBAL 0 (i)
>>
>> A context switch could happen between any pair of statements.
>
> If you actually mean *statements* as opposed to byte codes, then the only
> place there could be a switch would be either before the LOAD_GLOBAL or
> after the STORE_GLOBAL (given that i is a built-in int and cannot have a
> custom __iadd__ method).
>
> Is that what you mean?

I may be wrong, but I always assume that a context switch could happen
between any two bytecode operations - or, if you're reading the
disassembly, between any two lines *of disassembly*. So there could be
a switch before LOAD_GLOBAL, a switch between that and LOAD_CONST,
another switch before the ADD, another before the STORE, and another
right at the end. Well, there won't be *all* of those, but there could
be any of them.

This might not be entirely correct - there might be pairs that are
functionally atomic - but it's the safe assumption.

>> For instance, if you replace "i
>> += 1" with "i += i", to double the value, you'll get this:
>>
>> 3 0 LOAD_GLOBAL 0 (i)
>> 2 LOAD_GLOBAL 0 (i)
>> 4 INPLACE_ADD
>> 6 STORE_GLOBAL 0 (i)
>>
>> and that could potentially have both of them load the initial value,
>> then one of them runs to completion, and then the other loads the result
>> - so it'll add 1 and 2 and have a result of 3, rather than 2 or 4.
>
> Some people, when confronted with a problem, say, "I know, I'll use
> threads". Nothhtwo probw ey ave lems.

Right. Now they have to deal with interleaving, but that's all. And
honestly, MOST CODE wouldn't notice interleaving; it's only when you
change (either by rebinding or by mutating) something that can be seen
by multiple threads. Which basically means "mutable globals are a
risk, pretty much everything else is safe".

>> But you're absolutely right that there are only a small handful of
>> plausible results, even with threading involved.
>
> Indeed. Even though threading is non-deterministic, it isn't *entirely*
> unconstrained.
>

Yeah. Quite far from it, in fact. Python threading is well-defined and
fairly easy to work with. Only in a handful of operations do you need
to worry about atomicity - like the one that started this thread.

ChrisA

[Steven D'Aprano]

On Sun, 08 Jul 2018 12:23:41 +1000, Chris Angelico wrote:

>> Some people, when confronted with a problem, say, "I know, I'll use
>> threads". Nothhtwo probw ey ave lems.
>
> Right. Now they have to deal with interleaving, but that's all. And
> honestly, MOST CODE wouldn't notice interleaving; it's only when you
> change (either by rebinding or by mutating) something that can be seen
> by multiple threads. Which basically means "mutable globals are a risk,
> pretty much everything else is safe".

Its not just globals though. Any mutable object shared between two
threads is potentially a risk. Globals are just the most obvious example.

[Chris Angelico]

On Sun, Jul 8, 2018 at 1:58 PM, Steven D'Aprano
<steve+comp....@pearwood.info> wrote:
> On Sun, 08 Jul 2018 12:23:41 +1000, Chris Angelico wrote:
>
>>> Some people, when confronted with a problem, say, "I know, I'll use
>>> threads". Nothhtwo probw ey ave lems.
>>
>> Right. Now they have to deal with interleaving, but that's all. And
>> honestly, MOST CODE wouldn't notice interleaving; it's only when you
>> change (either by rebinding or by mutating) something that can be seen
>> by multiple threads. Which basically means "mutable globals are a risk,
>> pretty much everything else is safe".
>
> Its not just globals though. Any mutable object shared between two
> threads is potentially a risk. Globals are just the most obvious example.
>

Right; by "basically" I mean "yes there are others but this is what
matters". The technically-accurate part is in the previous sentence:

"can be seen by multiple threads".

ChrisA

[Marko Rauhamaa]

Chris Angelico <ros...@gmail.com>:

> On Sun, Jul 8, 2018 at 11:04 AM, Steven D'Aprano
> <steve+comp....@pearwood.info> wrote:
>>> The only thing Python should guarantee is that the data structures stay
>>> "coherent" under race conditions. In other words, there cannot be a
>>> segmentation fault. For example, if two threads executed this code in
>>> parallel:
>>>
>>> global i
>>> i = 1
>>> i += 1
>>>
>>> a legal end result could be that i contains the string "impossible".
>>
>> That wouldn't be coherent. The only coherent results are that i could
>> equal either 2 or 3:
>

> Python threads don't switch only between lines of code, so the actual

> interaction is a bit more complicated than you say. [...]

>
> But you're absolutely right that there are only a small handful of
> plausible results, even with threading involved.

You are on the right track, Chris, but you are still deducing behavior
from a particular implementation. For example Java's definition is
approximately the one I give above:

Without correct synchronization, very strange, confusing and
counterintuitive behaviors are possible.

<URL: https://docs.oracle.com/javase/specs/jls/se7/html/jls-17.htm
l#jls-17.4.5>

And we know that Python has been implemented using Java...


Marko

[Steven D'Aprano]

On Sun, 08 Jul 2018 10:52:15 +0300, Marko Rauhamaa wrote:

> You are on the right track, Chris, but you are still deducing behavior
> from a particular implementation. For example Java's definition is
> approximately the one I give above:
>
> Without correct synchronization, very strange, confusing and
> counterintuitive behaviors are possible.

Indeed, and that applies to all languages with threading, including
Python. But notice that it doesn't say:

Without correct synchronization, impossible things are possible.


> <URL: https://docs.oracle.com/javase/specs/jls/se7/html/jls-17.htm
> l#jls-17.4.5>

You seem to have read this as "Java threading can do impossible things",
but I think the correct reading of the article is "Here are the possible
things that Java threading can do to mess with your mind". That's a much
smaller subset of things which can go wrong.

(But still pretty big.)

See, for example Example 17.4-1, which explicitly shows that the Java
execution model is permitted to reorder statements:

r1 = A; B = 1;

may be reordered to

B = 1; r1 = A;

That's harmless in single-threaded code, but risky in multi-threaded
code. The result is that in the example given, r1 could end up being set
to 1 instead of the expected values -- but it cannot possibly be set to
the string "impossible", since that goes against the Java type system.

In Python, there's no possible order of operations of assigning 1 and
adding 1 that could result in a string. No Python compiler or interpreter
is permitted to evaluate `1 + 1` or `2 + 1` as the string "impossible",
even if threads are involved.

(That's not to say that threads might not assign a string to the variable
we expected to contain 2, but it would have to do so by assignment, not
by mucking about with the execution order of integer addition.)


In the case of Example 17.4-1, starting with A = B = 0, two threads
execute:

Thread 1: r2 = A; B = 1;
Thread 2: r1 = B; A = 2;

Java compilers are permitted to inspect each thread *in isolation*,
decide that the order of lines is invisible to the caller, and so re-
order them. The result of that is that those four lines can be executed
in any permutation, giving a total of 24 separate possibilities.

py> from itertools import permutations
py> instructions = ["r2 = A;", "B = 1;", "r1 = B;", "A = 2;"]
py> len(list(permutations(instructions)))
24


But Python (at least for now) cannot do this. It has a more deterministic
execution order which guarantees top-to-bottom execution of Python
statements. That implies that there are only *six* possible execution
orders of those two threads (which is still enough to add non-determinism
to your code!) not twenty-four:

r2 = A; B = 1; r1 = B; A = 2;
r2 = A; r1 = B; B = 1; A = 2;
r2 = A; r1 = B; A = 2; B = 1;
r1 = B; A = 2; r2 = A; B = 1;
r1 = B; r2 = A; A = 2; B = 1;
r1 = B; r2 = A; A = 2; B = 1;

and that remains true even if the underlying implementation is written in
Java, or Malbolge for that matter.

> And we know that Python has been implemented using Java...

That's irrelevant. A legal Python does not inherit the quirks of the
underlying implementation -- it must still follow the rules of the
language, or it isn't Python. Java is statically typed, with machine
ints, Python is dynamically typed, with no machine ints.

Relevant:

http://doc.pypy.org/en/latest/cpython_differences.html

http://docs.micropython.org/en/latest/unix/genrst/index.html

[Marko Rauhamaa]

Steven D'Aprano <steve+comp....@pearwood.info>:

> Changing implementations from one which is thread safe to one which is
> not can break people's code, and shouldn't be done on a whim.
> Especially since such breakage could be subtle, hard to notice, harder
> to track down, and even harder still to fix.

Java's HotSpot does it all the time, and it did result in code
breakage -- although the code was broken to begin with.

> So there is no coherent way to get a result of "impossible" from just
> adding 1 to 1 in any coherent implementation of Python.

Back to Java, there was a real case of 64-bit integer operations not
being atomic on 32-bit machines. Mixing up upper and lower halves
between threads could result in really weird evaluations.

More importantly, this loop may never finish:

# Initially
quit = False

# Thread 1
global quit
while not quit:
time.sleep(1)

# Thread 2
global quit
quit = True

That's the reality in Java and C. I see no reason why that wouldn't be
the reality in Python as well -- unless the language specification said
otherwise.


Marko

PS My example with "impossible" being the result of a racy integer
operation is of course unlikely but could be the outcome if the Python
runtime reorganized its object cache on the fly (in a hypothetical
implementation).

[Steven D'Aprano]

On Sun, 08 Jul 2018 14:11:58 +0300, Marko Rauhamaa wrote:

> Steven D'Aprano <steve+comp....@pearwood.info>:
>> Changing implementations from one which is thread safe to one which is
>> not can break people's code, and shouldn't be done on a whim.
>> Especially since such breakage could be subtle, hard to notice, harder
>> to track down, and even harder still to fix.
>
> Java's HotSpot does it all the time, and it did result in code breakage
> -- although the code was broken to begin with.

I said "shouldn't be done", rather than claiming that was the situation
right now with all compilers.

But I'm willing to give a little bit of slack to aggressively optimizing
compilers, provided they come with a warning.

>> So there is no coherent way to get a result of "impossible" from just
>> adding 1 to 1 in any coherent implementation of Python.
>
> Back to Java, there was a real case of 64-bit integer operations not
> being atomic on 32-bit machines. Mixing up upper and lower halves
> between threads could result in really weird evaluations.

Oh don't get me wrong, I agree with you that threading can result in
strange, unpredictable errors.

That's why I try not to use threading. I have no illusions about my
ability to debug those sorts of problems.

> More importantly, this loop may never finish:
>
> # Initially
> quit = False
>
> # Thread 1
> global quit
> while not quit:
> time.sleep(1)
>
> # Thread 2
> global quit
> quit = True

Assuming that thread 2 actually runs *at some point*, I don't see how
that can't terminate. Neither thread sets quit to False, so provided
thread 2 runs at all, it has to terminate.


I suppose if the threading implementation *could* fall back to sequential
code (thread 2 doesn't run until thread 1 finishes, which it never
does...) that outcome is possible. But it would have to be a pretty poor
implementation.

Now if you said there were fifty threads (aside from the main thread,
which is guaranteed to run) all reading quit, and only thread 50 ever
assigns to it, I'd believe that perhaps thread 50 never gets a chance to
run. But with just two threads? Explain please.

> That's the reality in Java and C. I see no reason why that wouldn't be
> the reality in Python as well -- unless the language specification said
> otherwise.

Because the Python core developers care more about correctness than speed.

> Marko
>
> PS My example with "impossible" being the result of a racy integer
> operation is of course unlikely but could be the outcome if the Python
> runtime reorganized its object cache on the fly (in a hypothetical
> implementation).

That would be a cache bug :-)

Not every interpreter bug should be considered the caller's fault :-)

[MRAB]

On 2018-07-08 14:38, Steven D'Aprano wrote:
> On Sun, 08 Jul 2018 14:11:58 +0300, Marko Rauhamaa wrote:
>

[snip]

>> More importantly, this loop may never finish:
>>
>> # Initially
>> quit = False
>>
>> # Thread 1
>> global quit
>> while not quit:
>> time.sleep(1)
>>
>> # Thread 2
>> global quit
>> quit = True
>

> Assuming that thread 2 actually runs *at some point*, I don't see how
> that can't terminate. Neither thread sets quit to False, so provided
> thread 2 runs at all, it has to terminate.
>

[snip]

The compiler could look at the code for thread 1 and see that 'quit' is
never assigned to, meaning that it could be "optimised" to:

global quit
if not quit:
while True:
time.sleep(1)

In C you'd declare 'quit' as 'volatile' to tell the compiler that it
could change unexpectedly, so don't make that assumption.

[Marko Rauhamaa]

MRAB <pyt...@mrabarnett.plus.com>:

C is an even tougher case. Even if the compiler kept on checking a
volatile value, the CPU might never propagate the cache content to the
other core. You'd need a memory barrier. In Java, "volatile" effectively
creates a memory barrier, but in C (and C++) it does not. In C you need
something like a mutex to see the effects of other threads running.

(BTW, I think that's a terrible thing for the C standards committee to
specify.)


Marko

[Marko Rauhamaa]

Steven D'Aprano <steve+comp....@pearwood.info>:

Whether it's a bug or not depends on the language specification. Java
has a very clear definition for correct synchronization. It's not so
clear on what could happen in the event of a data race; it's not
entirely unspecified, but the language spec admonishes the application
to brace itself for surprising effects.

If the Python Language Specification hasn't specified the effects of
incorrect synchronization so we can rightly suppose that the results are
unspecified.


Marko

[Chris Angelico]

None of this has any impact on Python whatsoever.

ChrisA

[Steven D'Aprano]

On Sun, 08 Jul 2018 19:35:55 +0300, Marko Rauhamaa wrote:

> Steven D'Aprano <steve+comp....@pearwood.info>:
>> On Sun, 08 Jul 2018 14:11:58 +0300, Marko Rauhamaa wrote:
>>> PS My example with "impossible" being the result of a racy integer
>>> operation is of course unlikely but could be the outcome if the Python
>>> runtime reorganized its object cache on the fly (in a hypothetical
>>> implementation).
>>
>> That would be a cache bug :-)
>>
>> Not every interpreter bug should be considered the caller's fault :-)
>
> Whether it's a bug or not depends on the language specification.

"It is true that if you turn the indicator on at the same time that you
turn the windshield wipers on, the car will explode in an enormous
fireball releasing sufficient poisonous gases to kill everyone in a
fifteen block radius. But we never said that it was safe to turn the
indicator and windshield wipers on at the same time, so it's not a bug,
its operator error."

Compiler writers and language designers need to stop hiding behind
specifications. No other industry so routinely tries (and too often
succeeds) in playing the "but we never said our product wouldn't set you
on fire" card with so little justification.

> Java
> has a very clear definition for correct synchronization. It's not so
> clear on what could happen in the event of a data race; it's not
> entirely unspecified, but the language spec admonishes the application
> to brace itself for surprising effects.

Incorrect synchronisation is irrelevant in this example. If the object
cache is *ever* in an invalid state, such that (as per your example) the
literal 1 (an int) could be evaluated as "impossible" (a string), that is
a bug in the object management. Threads or no threads.

The only excuse would be if the caller directly messed with the cache in
an unsupported fashion (say, with ctypes).


Software needs "fit for purpose" laws and end-user warranties with teeth.
If that means that the software industry spends the next thirty years
fixing bugs instead of adding features, that's a good thing.

[Steven D'Aprano]

On Sun, 08 Jul 2018 16:37:11 +0100, MRAB wrote:

> On 2018-07-08 14:38, Steven D'Aprano wrote:

>> On Sun, 08 Jul 2018 14:11:58 +0300, Marko Rauhamaa wrote:
>>

> [snip]

>>> More importantly, this loop may never finish:
>>>
>>> # Initially
>>> quit = False
>>>
>>> # Thread 1
>>> global quit
>>> while not quit:
>>> time.sleep(1)
>>>
>>> # Thread 2
>>> global quit
>>> quit = True
>>

>> Assuming that thread 2 actually runs *at some point*, I don't see how
>> that can't terminate. Neither thread sets quit to False, so provided
>> thread 2 runs at all, it has to terminate.
>>
> [snip]
>
> The compiler could look at the code for thread 1 and see that 'quit' is
> never assigned to, meaning that it could be "optimised" to:
>
> global quit
> if not quit:
> while True:
> time.sleep(1)

I'm glad you put "optimized" in scare quotes there, because any optimizer
that did that to code that runs in a thread is buggy. The re-write has
changed the semantics of the code.

Of course a compiler "could" do anything. If it re-wrote the code to
instead perform:

while True:
print(math.sin(random.random()+1)

instead, we'd have no trouble recognising that the compiler has changed
the semantics of our code to something we didn't write, and in just about
every language apart from C, we would rightly call it a compiler bug.

If I write "Do X", and the compiler instead executes "Do Y", that's a
compiler bug. The compiler has one job: to take my source code and
convert it to something which can be executed, and if it cannot do that
faithfully, it is buggy.

C is the special case: C programmers routinely blame *themselves* when
the compiler changes "Do X" to "Do Y", because the standard says it is
permitted to do anything it likes in the event of undefined behaviour.
Talk about victims coming to rationalise their own abuse and identify
with their abuser.

W.A. Wulf might have been talking about C compilers when he wrote:

"More computing sins are committed in the name of efficiency
(without necessarily achieving it) than for any other single
reason — including blind stupidity."

> In C you'd declare 'quit' as 'volatile' to tell the compiler that it
> could change unexpectedly, so don't make that assumption.

You shouldn't need to tell the compiler to assume that the variable could
change. In multi-threaded code, there's no justification for assuming the
variable can't change unless you've done a whole-program analysis and can
prove that *no* thread ever writes to that variable.

Even in single-threaded code, I think that optimizations which change
execution order are dubious. There's far too much opportunity for "it's
not a bug, because the specification says we can deny it is a bug"
faults. It's simply *bad engineering practice*.

When engineers design a bridge or a road or a building, the builders have
to faithfully follow the engineer's design, unless the design itself
explicitly allows them to make substitutions.

"The blueprints say these supporting pillars have to be filled with steel-
reinforced concrete. How about we just fill them with empty cans instead,
what could possibly go wrong?"

http://shanghaiist.com/2016/02/08/taiwan_earthquake_building_collapse/


(Disclaimer: there seems to be some controversy over whether the cans
were actually in supporting columns or not. But the point still stands.)

[Marko Rauhamaa]

Chris Angelico <ros...@gmail.com>:

> On Mon, Jul 9, 2018 at 2:11 AM, Marko Rauhamaa <ma...@pacujo.net> wrote:
>> MRAB <pyt...@mrabarnett.plus.com>:

>>> In C you'd declare 'quit' as 'volatile' to tell the compiler that it
>>> could change unexpectedly, so don't make that assumption.
>>
>> C is an even tougher case. Even if the compiler kept on checking a
>> volatile value, the CPU might never propagate the cache content to
>> the other core. You'd need a memory barrier. In Java, "volatile"
>> effectively creates a memory barrier, but in C (and C++) it does not.
>> In C you need something like a mutex to see the effects of other
>> threads running.
>>
>> (BTW, I think that's a terrible thing for the C standards committee to
>> specify.)
>
> None of this has any impact on Python whatsoever.

[citation needed]


Marko

[Rick Johnson]

Steven D'Aprano wrote:

> "The blueprints say these supporting pillars have to be
> filled with steel- reinforced concrete. How about we just
> fill them with empty cans instead, what could possibly go
> wrong?"

That was more a matter of cost savings than feline curiosity.

> (Disclaimer: there seems to be some controversy over
> whether the cans were actually in supporting columns or
> not. But the point still stands.)

On long island, they use dead bodies instead of cans.

[Chris Angelico]

Why? You might as well say "in Blurple, all integers greater than 5
compare equal to each other, and it's possible to implement a Python
interpreter in Blurple, therefore we can't trust integer comparisons
in Python". It's ridiculous to consider. The languages are completely
independent.

Are you assuming that Python's semantics are defined by the semantics
of one possible implementation language?

ChrisA

[Marko Rauhamaa]

Chris Angelico <ros...@gmail.com>:

> Are you assuming that Python's semantics are defined by the semantics
> of one possible implementation language?

What are Python's semantics defined by? I've been using these:

<URL: https://docs.python.org/3/reference/>

<URL: https://docs.python.org/3/library/>

Unfortunately, neither spec says anything about the atomicity of
dict.setdefault().

Therefore, the application programmer must assume it is not atomic. In
fact, as brought up in this discussion, the consultation of
object.__hash__() and object.__eq__() almost guarantee the
*non*-atomicity of dict.setdefault().


Marko

[Chris Angelico]

If by "atomic" you mean that absolutely no context switch can occur
during setdefault, then it probably isn't. But the point of an atomic
query/update operation is that there are exactly two possibilities:

1) The key did not exist in the dictionary. It now does, with the
provided default, which was returned.
2) The key did exist in the dictionary. The provided default is
ignored, and the previous value is returned.

Neither object.__hash__ nor object.__eq__ gives any way for this to be
violated (unless you mess with the concept of "the key did exist in
the dictionary" by breaking the definition of equality, but that's
nothing to do with atomicity). Here's the definition of setdefault:

setdefault(key, default=None, /) method of builtins.dict instance
Insert key with a value of default if key is not in the dictionary.

Return the value for key if key is in the dictionary, else default.


Simple semantics. Straight-forward. Now, maybe there's a bug in some
implementation whereby threads can violate this; but that would be a
bug to be fixed, and nothing more. You should be able to assume that
it will behave as stated.

ChrisA

[Marko Rauhamaa]

Chris Angelico <ros...@gmail.com>:

> On Mon, Jul 9, 2018 at 5:18 AM, Marko Rauhamaa <ma...@pacujo.net> wrote:
>> Chris Angelico <ros...@gmail.com>:
>>> Are you assuming that Python's semantics are defined by the semantics
>>> of one possible implementation language?
>>
>> What are Python's semantics defined by? I've been using these:
>>
>> <URL: https://docs.python.org/3/reference/>
>>
>> <URL: https://docs.python.org/3/library/>
>>
>> Unfortunately, neither spec says anything about the atomicity of
>> dict.setdefault().
>>
>> Therefore, the application programmer must assume it is not atomic. In
>> fact, as brought up in this discussion, the consultation of
>> object.__hash__() and object.__eq__() almost guarantee the
>> *non*-atomicity of dict.setdefault().
>
> If by "atomic" you mean that absolutely no context switch can occur
> during setdefault, then it probably isn't. But the point of an atomic
> query/update operation is that there are exactly two possibilities:
>
> 1) The key did not exist in the dictionary. It now does, with the
> provided default, which was returned.
> 2) The key did exist in the dictionary. The provided default is
> ignored, and the previous value is returned.

This is a classic test-and-set race condition:

# Initially
assert "A" not in d

# Thread 1
d.setdefault("A", 1)

# Thread 2
d["A"] = 2

If dict.setdefault() is atomic, the end result in all timings must be:

d["A"] == 2

However, if dict.setdefault() is not atomic, the end result may also be:

d["A"] == 1

> Neither object.__hash__ nor object.__eq__ gives any way for this to be
> violated (unless you mess with the concept of "the key did exist in
> the dictionary" by breaking the definition of equality, but that's
> nothing to do with atomicity). Here's the definition of setdefault:
>
> setdefault(key, default=None, /) method of builtins.dict instance
> Insert key with a value of default if key is not in the dictionary.
>
> Return the value for key if key is in the dictionary, else default.
>
> Simple semantics. Straight-forward. Now, maybe there's a bug in some
> implementation whereby threads can violate this; but that would be a
> bug to be fixed, and nothing more. You should be able to assume that
> it will behave as stated.

Since atomicity is not guaranteed by the definition of the method, the
application programmer must be prepared for the end result to be 1 (or
even something completely different because the Language Specification
doesn't say anything about the outcome of data races).


Marko