Prev: Continuation of the MacOS networking thread...
Next: Continuation of the MacOS networking thread...
From: novickivan on 23 Dec 2009 23:34
On Dec 22, 4:19 pm, David Schwartz <dav...(a)webmaster.com> wrote:
> On Dec 22, 4:09 pm, "novicki...(a)gmail.com" <novicki...(a)gmail.com>

> > The subtle question here is, are reads and writes of a variable
> > atomic?  Do i have to worry that i am reading the variable while it is
> > being updated and might get total garbage such as 9 million as the
> > value when i read it.  Or is the worst case that i missed some
> > increments because the increment on 1 thread was done without taking
> > into account the updates from another thread?
>
> It depends what the documentation for the threading standard you are
> using says. If POSIX, you are not guaranteed anything at all, it could
> even crash.
>
Ok, I understand it is not guaranteed to be safe by POSIX ( yes i am
assuming posix threads).

However, I am still curious if due to the design of modern hardware in
general, it is possible to read a value for the variable that was
never actually set. The code is trying to set values between 1 and 1
million. But could you read a value of 8 million if 8 million is
never set. The reason would be because you read an incompletely
written value at some point. Or is the computer such that you can
only read complete values and never a partially written value.

The use case would be if you did not care about missing some updates
to a variable, that was not locked, but still you don't want to read a
value that was never set in the variable at all. If this could be
"guaranteed" by the bus size or something like that, you might be able
to save doing locks.

Thanks for all the info so far guys.

Cheers, and merry Christmas,
Ivan Novick
From: David Schwartz on 23 Dec 2009 23:43
On Dec 23, 8:34 pm, "novicki...(a)gmail.com" <novicki...(a)gmail.com>
wrote:

> However, I am still curious if due to the design of modern hardware in
> general, it is possible to read a value for the variable that was
> never actually set.  The code is trying to set values between 1 and 1
> million.  But could you read a value of 8 million if 8 million is
> never set.  The reason would be because you read an incompletely
> written value at some point.  Or is the computer such that you can
> only read complete values and never a partially written value.

Most likely, word tearing would be the only way. I don't know of any
POSIX platform where integers are subject to word tearing. The problem
is that you would be producing software that might break when a new
CPU, operating system, compiler, or something else comes out. On the
bright side, at least on x86, a lot of software makes the assumption
that read and writes to and from aligned integers are atomic (I think
it may even be guaranteed by Intel in the x86 specification) so you
certainly wouldn't be the only thing that would break.

> The use case would be if you did not care about missing some updates
> to a variable, that was not locked, but still you don't want to read a
> value that was never set in the variable at all.  If this could be
> "guaranteed" by the bus size or something like that, you might be able
> to save doing locks.

It's almost definitely not worth it. You would lose the other benefits
of locks, such as congestion avoidance.

DS
From: Golden California Girls on 23 Dec 2009 23:59
novickivan(a)gmail.com wrote:
> lets say I have
>
> unsigned int x = 0;
>
> And the code
>
> x++;
>
> Is run a total of 1 million times but the million times is divided
> across many threads.
>
> If i try to read the value of x am i guaranteed to get a value between
> 0 and 1 million.
>
> The subtle question here is, are reads and writes of a variable
> atomic? Do i have to worry that i am reading the variable while it is
> being updated and might get total garbage such as 9 million as the
> value when i read it. Or is the worst case that i missed some
> increments because the increment on 1 thread was done without taking
> into account the updates from another thread?
>
> I hope i have made the question clear.

There has to be an assumption made, that int is large enough to store 1 million.
That isn't stated in your code. Rather obviously if it isn't large enough and
as it is unsigned then no matter what happens your answer will be yes.



If your question was is there hardware that allows an interrupt in the middle of
a machine cycle of a read or write, I'm not aware of any, but that may not be
true of an emulator machine.
From: David Schwartz on 24 Dec 2009 01:49
On Dec 23, 8:59 pm, Golden California Girls <gldncag...(a)aol.com.mil>
wrote:

> If your question was is there hardware that allows an interrupt in the middle of
> a machine cycle of a read or write, I'm not aware of any, but that may not be
> true of an emulator machine.

Well, the more likely problems would be either that a single machine
instruction would be used to accomplish the read or the write or that
one CPU would read at the same time another is writing. An interrupt
in the middle of an instruction is just one possible way it could
fail.

In theory, on x86 you could use two machine instructions to write a 32-
bit value if you wanted to. It's hard to imagine any reason a compiler
would do that. And, on x86, 32-bit aligned values are not subject to
word tearing.

There are other ways it can go wrong, but they're also very unlikely.
For example, the compiler could 'optimize':

a++;

to:

a+=10000;
j=a;
j-=9999;
a=j;

As far as the compiler knows, this will have precisely the same
effect. However, if another thread read the value at the same time as
the 'j=a;' step, and then incremented it and wrote it back after the
'a=j;' step, you could get a totally bogus value.

Now, I know what you're thinking -- there's no way the compiler would
ever make an 'optimization' like this because it actually makes the
code worse. But the scary truth is that there are optimizations like
this that compilers do make.

One example is if the compiler is just one register short. Faced with
'i++;' on a RISC platform the most optimal implementation might be to
swap the memory location with a register, increment the register, and
swap back.

Sadly, there are similar known cases on x86. If I had the time, I'd
track down the GCC bug report.

DS
From: novickivan on 24 Dec 2009 10:54
On Dec 23, 10:49 pm, David Schwartz <dav...(a)webmaster.com> wrote:
> On Dec 23, 8:59 pm, Golden California Girls <gldncag...(a)aol.com.mil>
> wrote:
>
> > If your question was is there hardware that allows an interrupt in the middle of
> > a machine cycle of a read or write, I'm not aware of any, but that may not be
> > true of an emulator machine.
>
> Well, the more likely problems would be either that a single machine
> instruction would be used to accomplish the read or the write or that
> one CPU would read at the same time another is writing. An interrupt
> in the middle of an instruction is just one possible way it could
> fail.
>
> In theory, on x86 you could use two machine instructions to write a 32-
> bit value if you wanted to. It's hard to imagine any reason a compiler
> would do that. And, on x86, 32-bit aligned values are not subject to
> word tearing.
>
> There are other ways it can go wrong, but they're also very unlikely.
> For example, the compiler could 'optimize':
>
> a++;
>
> to:
>
> a+=10000;
> j=a;
> j-=9999;
> a=j;
>
> As far as the compiler knows, this will have precisely the same
> effect. However, if another thread read the value at the same time as
> the 'j=a;' step, and then incremented it and wrote it back after the
> 'a=j;' step, you could get a totally bogus value.
>
> Now, I know what you're thinking -- there's no way the compiler would
> ever make an 'optimization' like this because it actually makes the
> code worse. But the scary truth is that there are optimizations like
> this that compilers do make.
>
> One example is if the compiler is just one register short. Faced with
> 'i++;' on a RISC platform the most optimal implementation might be to
> swap the memory location with a register, increment the register, and
> swap back.
>
> Sadly, there are similar known cases on x86. If I had the time, I'd
> track down the GCC bug report.
>
> DS

Ok, I feel convinced, that it is NOT safe to read and write to a
variable from multiple threads without locks even if you are not
concerned with missing the latest updates to the values. At the risk
of starting a whole new thread, I guess the best performance would be
to use atomic memory access functions like these:
http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html or
the equivalent.

Cheers,
Ivan Novick
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5 6 7 8
Prev: Continuation of the MacOS networking thread...
Next: Continuation of the MacOS networking thread...