Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #11400 > unrolled thread
| Started by | "raphfrk@gmail.com" <raphfrk@gmail.com> |
|---|---|
| First post | 2012-01-17 04:04 -0800 |
| Last post | 2012-01-17 10:24 -0800 |
| Articles | 20 on this page of 74 — 9 participants |
Back to article view | Back to comp.lang.java.programmer
Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-17 04:04 -0800
Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-17 08:17 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-17 08:50 -0800
Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-17 09:00 -0800
Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-17 08:54 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-17 11:24 -0800
Re: Volatile happens before question Patricia Shanahan <pats@acm.org> - 2012-01-17 14:49 -0800
Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-17 15:49 -0800
Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-17 17:14 -0800
Re: Volatile happens before question Patricia Shanahan <pats@acm.org> - 2012-01-17 18:17 -0800
Re: Volatile happens before question Joshua Maurice <joshuamaurice@gmail.com> - 2012-01-19 16:45 -0800
Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-17 08:18 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-17 08:33 -0800
Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-17 08:49 -0800
Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-17 09:21 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-17 10:10 -0800
Re: Volatile happens before question Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-01-17 10:28 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-17 10:41 -0800
Re: Volatile happens before question Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-01-17 11:06 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-17 12:09 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-17 12:12 -0800
Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-17 12:38 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-17 13:35 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-17 14:41 -0800
Re: Volatile happens before question Patricia Shanahan <pats@acm.org> - 2012-01-17 14:55 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-17 15:27 -0800
Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-17 17:37 -0800
Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-17 17:42 -0800
Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-17 15:46 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-17 16:14 -0800
Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-17 20:01 -0800
Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-17 20:37 -0800
Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-17 21:52 -0800
Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-17 23:47 -0800
Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-18 00:08 -0800
Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-18 09:04 -0800
Re: Volatile happens before question Steven Simpson <ss@domain.invalid> - 2012-01-18 11:22 +0000
Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-18 06:24 -0800
Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-18 07:32 -0800
Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-18 08:34 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-18 10:12 -0800
Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-18 11:15 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-18 11:59 -0800
Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-18 12:24 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-18 13:16 -0800
Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-18 15:00 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-18 16:12 -0800
Re: Volatile happens before question Patricia Shanahan <pats@acm.org> - 2012-01-18 16:34 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-18 17:17 -0800
Re: Volatile happens before question Patricia Shanahan <pats@acm.org> - 2012-01-18 19:03 -0800
Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-18 15:30 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-18 16:10 -0800
Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-19 08:18 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-19 09:40 -0800
Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-19 10:10 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-19 10:39 -0800
Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-19 12:13 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-19 13:31 -0800
Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-19 16:14 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-19 21:16 -0800
Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-20 03:23 -0800
Re: Volatile happens before question "raphfrk@gmail.com" <raphfrk@gmail.com> - 2012-01-20 06:46 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-20 08:56 -0800
Re: Volatile happens before question Lew <noone@lewscanon.com> - 2012-01-20 11:12 -0800
Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-18 17:06 -0800
Re: Volatile happens before question Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-01-19 12:46 -0800
Re: Volatile happens before question markspace <-@.> - 2012-01-19 13:38 -0800
Re: Volatile happens before question Peter Duniho <NpOeStPeAdM@NnOwSlPiAnMk.com> - 2012-01-18 07:32 -0800
Re: Volatile happens before question Lew <noone@lewscanon.com> - 2012-01-18 00:06 -0800
Re: Volatile happens before question Knute Johnson <nospam@knutejohnson.com> - 2012-01-18 09:23 -0800
Re: Volatile happens before question Joshua Maurice <joshuamaurice@gmail.com> - 2012-01-19 17:07 -0800
Re: Volatile happens before question Joshua Maurice <joshuamaurice@gmail.com> - 2012-01-19 17:12 -0800
Re: Volatile happens before question Joshua Maurice <joshuamaurice@gmail.com> - 2012-01-19 19:22 -0800
Re: Volatile happens before question Daniel Pitts <newsgroup.nospam@virtualinfinity.net> - 2012-01-17 10:24 -0800
Page 3 of 4 — ← Prev page 1 2 [3] 4 Next page →
| From | markspace <-@.> |
|---|---|
| Date | 2012-01-18 10:12 -0800 |
| Message-ID | <jf7239$k2b$1@dont-email.me> |
| In reply to | #11467 |
On 1/18/2012 8:34 AM, raphfrk@gmail.com wrote: > On Jan 18, 3:32 pm, Peter Duniho<NpOeStPe...@NnOwSlPiAnMk.com> wrote: >> On Wed, 18 Jan 2012 06:24:54 -0800 (PST), raph...@gmail.com wrote: >>> http://mailinator.blogspot.com/2007/05/readerwriter-in-java-in-nonblo... >>> [...] >> >> It looks correct to me. > > I don't understand why it is ok. Doesn't it suffer from the same > issue as my example? Yeah, it's a trick. Or at least isn't great documentation. To figure it out, you have to read the introduction to the AtomicInteger documentation, which tells you that you need to read the package documentation for "the properties of atomic variables." In the package documentation, it eventually explains that: "get has the memory effects of reading a volatile variable. "set has the memory effects of writing (assigning) a volatile variable. " So you are synchronizing here just as if you were reading and writing to a volatile. I don't think the implementation uses volatile, I think it uses native methods which have the same effect, but you can think of the internal values as using a volatile to hold the atomic values. Voila!
[toc] | [prev] | [next] | [standalone]
| From | "raphfrk@gmail.com" <raphfrk@gmail.com> |
|---|---|
| Date | 2012-01-18 11:15 -0800 |
| Message-ID | <726da9ce-57f4-4136-b50b-56a032aca196@f1g2000yqi.googlegroups.com> |
| In reply to | #11470 |
On Jan 18, 6:12 pm, markspace <-@.> wrote: > Yeah, it's a trick. You mean yeah, it has the same problem, so won't work either?
[toc] | [prev] | [next] | [standalone]
| From | markspace <-@.> |
|---|---|
| Date | 2012-01-18 11:59 -0800 |
| Message-ID | <jf78bd$s4v$1@dont-email.me> |
| In reply to | #11473 |
On 1/18/2012 11:15 AM, raphfrk@gmail.com wrote:
> On Jan 18, 6:12 pm, markspace<-@.> wrote:
>> Yeah, it's a trick.
>
> You mean yeah, it has the same problem, so won't work either?
Looking at his code a bit more carefully, I think it has problems, but
not the same one. I guess the extra variables in his code that you're
looking at are local variables. So those are safe, they don't figure
into multi-threading concerns.
The bit that confuses me is that he "protects" his map with a write counter:
writeCounter.getAndIncrement();
map.put(key, value);
writeCounter.getAndIncrement();
And then allows the reader(s) into the critical section whenever the
writeCounter is even (why not just decrement the counter after a write
access?).
while (((save = writeCounter.get()) & 1) == 1);
value = map.get(key);
So if a reader starts "first" and passes the first test
(writeCounter==0), and then starts to access the map, and then a writer
comes in and also begins to access the map... yeah you have two threads
accessing the map at the same time. This doesn't seem to work at all.
(Hint: ConcurrentHashMap
<http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/ConcurrentHashMap.html>)
[toc] | [prev] | [next] | [standalone]
| From | "raphfrk@gmail.com" <raphfrk@gmail.com> |
|---|---|
| Date | 2012-01-18 12:24 -0800 |
| Message-ID | <652cb878-fb2f-4361-8f70-61bc493cebf6@r16g2000yqi.googlegroups.com> |
| In reply to | #11474 |
On Jan 18, 7:59 pm, markspace <-@.> wrote: > Looking at his code a bit more carefully, I think it has problems, but not the same one. I would be interested in his basic locking principle. I think it has the same problem. He is assuming that if he .gets() an even number, then no write lock has happened. However, that isn't guaranteed. > The bit that confuses me is that he "protects" his map with a write counter: > > writeCounter.getAndIncrement(); > map.put(key, value); > writeCounter.getAndIncrement(); > > And then allows the reader(s) into the critical section whenever the > writeCounter is even (why not just decrement the counter after a write > access?). This is to handle the case where the reader reads the counter before and after a write. It needs to be able to tell something changed. > while (((save = writeCounter.get()) & 1) == 1); > value = map.get(key); > > So if a reader starts "first" and passes the first test > (writeCounter==0), and then starts to access the map, and then a writer > comes in and also begins to access the map... yeah you have two threads > accessing the map at the same time. This doesn't seem to work at all. True, he is assuming that a .get() on an unstable map won't do anything dangerous, like cause an infinite loop. Also, a .get() might be setup so that it makes some housekeeping changes to the map. > > (Hint: ConcurrentHashMap > > <http://docs.oracle.com/javase/7/docs/api/java/util/concurrent/Concurr...>) I was just wondering about his basic method.
[toc] | [prev] | [next] | [standalone]
| From | markspace <-@.> |
|---|---|
| Date | 2012-01-18 13:16 -0800 |
| Message-ID | <jf7crq$p30$1@dont-email.me> |
| In reply to | #11475 |
On 1/18/2012 12:24 PM, raphfrk@gmail.com wrote: > I would be interested in his basic locking principle. > > I think it has the same problem. He is assuming that if he .gets() an > even number, then no write lock has happened. Well, he assumes no write is in progress. A write would have definitely happened if writeCounter was 2, for example. > However, that isn't guaranteed. I don't see how it isn't guaranteed. get() and set() on an AtomicInteger create a happens-before relationship, just like a volatile. Both the variable itself and the map should be protected on a "good" read. I'm concerned about what happens when there's a write (a reader could be in there too) and what happens on a "bad" read. I didn't see where he creates/publishes writeCounter and lock. I assume they're safely published as final instance fields somewhere. That shouldn't be a problem. > This is to handle the case where the reader reads the counter before > and after a write. It needs to be able to tell something changed. Good point, I realized this after I posted. > True, he is assuming that a .get() on an unstable map won't do > anything dangerous, like cause an infinite loop. That's what I was thinking. With folks like Brian Goetz and Bartosz saying the system can simply invent values, it's hard to analyze the resulting code for any kind of deterministic behavior. Esp. because Java is a step away from the machine, and I don't know exactly what sort of operations are going to be executed. In particular, during the write, if a reader is also present, I wonder if the writer could "see" a bad read due to the reader present, and then "finalize" that bad read and write it to memory. Stuff like this is hard to analyze. *IF* you assume that the read operation actually returns, and doesn't throw an exception, or melt some other part of the code (like the writer), *then* I think you can say that the update will be detected by the reader, and the operation will be re-tried. This does seem to eventually guarantee an uncontended read of the map, provided writes don't happen "too frequently," which must be the case for this sort of lock-free code, or it isn't going to work. So, yes I think it works if you're prepared to make some assumptions about the behavior of the JVM. However, I don't think anyone on this list should be making those assumptions. Better safe than sorry. > I was just wondering about his basic method. ConcurrentHashMap uses a totally different technique. It "stripes" the map into several smaller maps, each of which has its own lock. Therefore the chance that two threads will "collide" and need the same lock is reduced. Striping locks is a much easier technique, easier to analyze and very effective afaik. Java Concurrency in Practice talks about this in some detail. It's worth checking out. After you're done with striping, check out ConcurrentSkipListMap, and look up some of the basic info on the skip list algorithm (Sedgewick is good). More crazy techniques.
[toc] | [prev] | [next] | [standalone]
| From | Knute Johnson <nospam@knutejohnson.com> |
|---|---|
| Date | 2012-01-18 15:00 -0800 |
| Message-ID | <jf7iti$t0k$1@dont-email.me> |
| In reply to | #11476 |
On 1/18/2012 1:16 PM, markspace wrote: > That's what I was thinking. With folks like Brian Goetz and Bartosz > saying the system can simply invent values, it's hard to analyze the > resulting code for any kind of deterministic behavior. Esp. because Java > is a step away from the machine, and I don't know exactly what sort of > operations are going to be executed. I know that the JLS says that variables can have values out of thin air but Goetz says on page 36 "When a thread reads a variable without synchronization, it may see a stale value, but at least it sees a value that was actually placed there by some thread rather then some random value. This safety guarantee is called out-of-thin-air safety." -- Knute Johnson
[toc] | [prev] | [next] | [standalone]
| From | markspace <-@.> |
|---|---|
| Date | 2012-01-18 16:12 -0800 |
| Message-ID | <jf7n57$ojv$2@dont-email.me> |
| In reply to | #11477 |
On 1/18/2012 3:00 PM, Knute Johnson wrote: > On 1/18/2012 1:16 PM, markspace wrote: >> That's what I was thinking. With folks like Brian Goetz and Bartosz >> saying the system can simply invent values, it's hard to analyze the >> resulting code for any kind of deterministic behavior. Esp. because Java >> is a step away from the machine, and I don't know exactly what sort of >> operations are going to be executed. > > I know that the JLS says that variables can have values out of thin air > but Goetz says on page 36 "When a thread reads a variable without > synchronization, it may see a stale value, but at least it sees a value > that was actually placed there by some thread rather then some random > value. This safety guarantee is called out-of-thin-air safety." That's a good find. I can't reconcile that statement with other things I'm seeing. Since real world hardware seems to be able to produce values out of thin air, I don't see how Java could prevent this. It seems that one or the other statement is incorrect.
[toc] | [prev] | [next] | [standalone]
| From | Patricia Shanahan <pats@acm.org> |
|---|---|
| Date | 2012-01-18 16:34 -0800 |
| Message-ID | <WMudnbfiHcGx-IrSnZ2dnUVZ_rqdnZ2d@earthlink.com> |
| In reply to | #11481 |
On 1/18/2012 4:12 PM, markspace wrote: > On 1/18/2012 3:00 PM, Knute Johnson wrote: >> On 1/18/2012 1:16 PM, markspace wrote: >>> That's what I was thinking. With folks like Brian Goetz and Bartosz >>> saying the system can simply invent values, it's hard to analyze the >>> resulting code for any kind of deterministic behavior. Esp. because Java >>> is a step away from the machine, and I don't know exactly what sort of >>> operations are going to be executed. >> >> I know that the JLS says that variables can have values out of thin air >> but Goetz says on page 36 "When a thread reads a variable without >> synchronization, it may see a stale value, but at least it sees a value >> that was actually placed there by some thread rather then some random >> value. This safety guarantee is called out-of-thin-air safety." > > > That's a good find. I can't reconcile that statement with other things > I'm seeing. Since real world hardware seems to be able to produce values > out of thin air, I don't see how Java could prevent this. It seems that > one or the other statement is incorrect. > > I'm curious about the "values out of thin air" statement about hardware. Could you give some information about how it happens? Patricia
[toc] | [prev] | [next] | [standalone]
| From | markspace <-@.> |
|---|---|
| Date | 2012-01-18 17:17 -0800 |
| Message-ID | <jf7qvf$abm$1@dont-email.me> |
| In reply to | #11482 |
On 1/18/2012 4:34 PM, Patricia Shanahan wrote: > > I'm curious about the "values out of thin air" statement about hardware. > Could you give some information about how it happens? <http://vimeo.com/3757991> If I understand correctly: x & y are global integers initialized to 0. r1 and r2 are temporary variables. Thread 1: int r1 = x; y = r1; Thread 2: int r2 = y; x = r2; What happens is during the read of x, it is not found in cache. So a bus cycle is started to read the value of x, but at the same time the cpu has nothing to do while waiting, so it speculates as to the value of x and continues processing. Let's say the cpu speculates that x is 42. r1 = 42; Now since r1 is 42, when y is written it also gets a speculative write of the value 42; y = 42; This doesn't actually go on the memory bus, it's held in an output queue of writes. Next, Thread 2 comes along and also tries to read y. It also can't and like thread 1 decides to speculate on the value of y while waiting for main memory. It speculates y is 42. r2 = 42; Next x is written from the value of r2. x = 42; At this point, the internal cpu bus sees a write of 42 to the memory location of x and thinks its speculation was correct, cancels the memory read, and commits the value of y to memory. That's what I understood from that talk on Vimeo. I'm starting to wonder though exactly what sort of problem Bartosz Milewski is describing there. I thought he was describing what could actually happen in the absence of synchronization; possibly he is speculating on some kind of hardware issue however.
[toc] | [prev] | [next] | [standalone]
| From | Patricia Shanahan <pats@acm.org> |
|---|---|
| Date | 2012-01-18 19:03 -0800 |
| Message-ID | <_IGdnREOZNS5FYrSnZ2dnUVZ_tudnZ2d@earthlink.com> |
| In reply to | #11485 |
On 1/18/2012 5:17 PM, markspace wrote: > On 1/18/2012 4:34 PM, Patricia Shanahan wrote: >> >> I'm curious about the "values out of thin air" statement about hardware. >> Could you give some information about how it happens? > > > <http://vimeo.com/3757991> > > If I understand correctly: > > x & y are global integers initialized to 0. r1 and r2 are temporary > variables. > > Thread 1: > > int r1 = x; > y = r1; > > Thread 2: > > int r2 = y; > x = r2; > > > What happens is during the read of x, it is not found in cache. So a bus > cycle is started to read the value of x, but at the same time the cpu > has nothing to do while waiting, so it speculates as to the value of x > and continues processing. Let's say the cpu speculates that x is 42. > > r1 = 42; > > Now since r1 is 42, when y is written it also gets a speculative write > of the value 42; > > y = 42; > > This doesn't actually go on the memory bus, it's held in an output queue > of writes. > > Next, Thread 2 comes along and also tries to read y. It also can't and > like thread 1 decides to speculate on the value of y while waiting for > main memory. It speculates y is 42. > > r2 = 42; > > Next x is written from the value of r2. > > x = 42; > > At this point, the internal cpu bus sees a write of 42 to the memory > location of x and thinks its speculation was correct, cancels the memory > read, and commits the value of y to memory. > > That's what I understood from that talk on Vimeo. I'm starting to wonder > though exactly what sort of problem Bartosz Milewski is describing > there. I thought he was describing what could actually happen in the > absence of synchronization; possibly he is speculating on some kind of > hardware issue however. > That looks to me like a straight bug in the speculative processing implementation. The books and papers I've read on the subject, going back to some of the earliest supercomputers, all emphasize bookkeeping to ensure that speculative results are known to be speculative, and not sent to the bus or used in other threads until they are committed. I'm not saying that no processor could possibly have such a bug, but I would be surprised it it existed. Patricia
[toc] | [prev] | [next] | [standalone]
| From | "raphfrk@gmail.com" <raphfrk@gmail.com> |
|---|---|
| Date | 2012-01-18 15:30 -0800 |
| Message-ID | <6280ea10-c656-40fa-ba3d-50f24d471978@j15g2000yqb.googlegroups.com> |
| In reply to | #11476 |
On Jan 18, 9:16 pm, markspace <-@.> wrote: > I don't see how it isn't guaranteed. get() and set() on an > AtomicInteger create a happens-before relationship, just like a > volatile. The issue is that the .get() doesn't have a happens before the next write. So, if the write .increments() the counter and the .get() reads the updated value, then the .get() is guaranteed to happen after the .increment(). However, if the .get() gets the old value then it isn't guaranteed to happen before the increment, i.e. there is no guarantee.
[toc] | [prev] | [next] | [standalone]
| From | markspace <-@.> |
|---|---|
| Date | 2012-01-18 16:10 -0800 |
| Message-ID | <jf7n1d$ojv$1@dont-email.me> |
| In reply to | #11479 |
On 1/18/2012 3:30 PM, raphfrk@gmail.com wrote:
> However, if the .get() gets the old value then it isn't guaranteed to
> happen before the increment, i.e. there is no guarantee.
If you get the old value, then no writes have occurred. We're talking
AtomicInteger::get() here, right? Not Map::get() or something.
Thread 1 Thread 2
Writer Reader
map.put() // write
writeCounter.increment() -----> writeCounter.get() // happens before
map.get() // read
-----> writerCounter.get() // happens before
map.get()
[toc] | [prev] | [next] | [standalone]
| From | "raphfrk@gmail.com" <raphfrk@gmail.com> |
|---|---|
| Date | 2012-01-19 08:18 -0800 |
| Message-ID | <6b44805b-ff63-41ba-8060-cbd92164f9d6@o9g2000yqa.googlegroups.com> |
| In reply to | #11480 |
On Jan 19, 12:10 am, markspace <-@.> wrote:
> On 1/18/2012 3:30 PM, raph...@gmail.com wrote:
>
> > However, if the .get() gets the old value then it isn't guaranteed to
> > happen before the increment, i.e. there is no guarantee.
>
> If you get the old value, then no writes have occurred. We're talking
> AtomicInteger::get() here, right? Not Map::get() or something.
>
> Thread 1 Thread 2
> Writer Reader
>
> map.put() // write
> writeCounter.increment() -----> writeCounter.get() // happens before
> map.get() // read
>
> -----> writerCounter.get() // happens before
> map.get()
Yes that is correct, it is also possible that it goes:
Thread 1 Thread 2
Writer Reader
W1: map.put() // write
R1: writeCounter.get() // happens
before
R2: map.get() // read
R3: writerCounter.get() // happens
before
W2: writeCounter.increment()
So, the happens before chains are:
Thread 1:
<Start> happens before W1
W1 happens before W2
Thread 2:
<Start> happens before R1
R1 happens before R2
R2 happens before R3
Inter thread
None
So, there is no guarantee that W1 happens before R2 (and similar no
guarantee that R2 happens before W1), so they could occur at the same
time.
[toc] | [prev] | [next] | [standalone]
| From | markspace <-@.> |
|---|---|
| Date | 2012-01-19 09:40 -0800 |
| Message-ID | <jf9kid$vac$1@dont-email.me> |
| In reply to | #11494 |
On 1/19/2012 8:18 AM, raphfrk@gmail.com wrote:
> Yes that is correct, it is also possible that it goes:
>
> Thread 1 Thread 2
> Writer Reader
>
> W1: map.put() // write
> R1: writeCounter.get() // happens
> before
> R2: map.get() // read
> R3: writerCounter.get() // happens
> before
> W2: writeCounter.increment()
That one I specifically don't see. If you get a reader and a writer
accessing the map at the same time, then the reader will detect a change
and retry the operation. There's two get's on the reader side, it might
be useful to distinguish between them.
public V get(Object key) {
int save = 0;
V value = null;
do {
while (((save = writeCounter.get()) & 1) == 1); // RA
value = map.get(key);
} while (save != writeCounter.get()); // RB
return value;
}
I'll do the same on the writer side just for clarity.
public V put(K key, V value) {
lock.lock();
try {
writeCounter.getAndIncrement(); // WA
map.put(key, value);
writeCounter.getAndIncrement(); // WB
} finally {
lock.unlock();
}
return value;
}
So here's how I parse a "failed" read.
Thread 1 Thread 2
Writer Reader
writerCounter.get() // RA
writeCounter.increment() // WA
map.put()
// 1: No happens-before here
map.get()
writerCounter.get() // RB
writerCounter.get() // RA
// 2: this repeats until...
writeCounter.increment() // WB
-----> writerCounter.get() // RA
map.get()
writerCounter.get() // RB
The ----> arrow indicates the happens-before (which is the same way the
JLS shows happens-before).
(I'm ignoring the happens-before for the writeCounter itself. That
there is such a relationship should be obvious.)
Now with the WB -> RA pair there's been happens before relationship
established and the second map.get() in the reader thread is ok.
The first map.get() is fubar but according to Patricia we should at
least expect to get back from the get call with only bad data, no other
problems. Likewise, the write should not be expected to create "out of
this air" values. If so, then the second read should be clean.
[toc] | [prev] | [next] | [standalone]
| From | "raphfrk@gmail.com" <raphfrk@gmail.com> |
|---|---|
| Date | 2012-01-19 10:10 -0800 |
| Message-ID | <240ac224-9713-4931-89f6-aeb7578aee09@m11g2000yqe.googlegroups.com> |
| In reply to | #11497 |
On Jan 19, 5:40 pm, markspace <-@.> wrote: > So here's how I parse a "failed" read. I did a re-ordering again. This is synchronization ordering (in theory W-write and R-read shouldn't even be included, as they are non- volatile). From a synchronization ordering it looks like a successful read, as both operations are separate. Thread 1 Thread 2 Writer Reader writerCounter.get() // RA map.get() // R-read writerCounter.get() // RB writeCounter.increment() // WA map.put(); // W-write writeCounter.increment() // WB RB will return the safe/stable value for writeCounter, so the read loop returns successfully on the first attempt. RA happens-before R-read happens-before RB WA happens-before W-write happens-before WB However, you can't say that RB happens-before WA. Therefore, there is no happens before path between W-write and R-read. They are effectively concurrent. The rule would need to be "A read from a volatile variable happens- before the write to that volatile that overwrites the value", but that rule isn't in the spec.
[toc] | [prev] | [next] | [standalone]
| From | markspace <-@.> |
|---|---|
| Date | 2012-01-19 10:39 -0800 |
| Message-ID | <jf9o0f$kmr$1@dont-email.me> |
| In reply to | #11498 |
On 1/19/2012 10:10 AM, raphfrk@gmail.com wrote: > However, you can't say that RB happens-before WA. Therefore, there is > no happens before path between W-write and R-read. They are > effectively concurrent. There doesn't need to be a happens-before here, however. It's a *read*, and doesn't create a data race. The only thing you care about is that writes happen-before reads. If the reads and writes you show *actually were* executed concurrently, it would have been caught by the RB read, like I showed in my earlier trace. > The rule would need to be "A read from a volatile variable happens- > before the write to that volatile that overwrites the value", but that > rule isn't in the spec. Doesn't need to be. Reads don't make data races. You need an unprotected write for that, followed by a read. There could be any number of reads, or no reads, before the write and it won't matter. Reads don't alter state, so there's nothing to protect.
[toc] | [prev] | [next] | [standalone]
| From | "raphfrk@gmail.com" <raphfrk@gmail.com> |
|---|---|
| Date | 2012-01-19 12:13 -0800 |
| Message-ID | <5ff9ba43-a357-4c0b-9c26-0a90242884d5@m11g2000yqe.googlegroups.com> |
| In reply to | #11499 |
On Jan 19, 6:39 pm, markspace <-@.> wrote: > On 1/19/2012 10:10 AM, raph...@gmail.com wrote: > > > However, you can't say that RB happens-before WA. Therefore, there is > > no happens before path between W-write and R-read. They are > > effectively concurrent. > > There doesn't need to be a happens-before here, however. It's a *read*, > and doesn't create a data race. The only thing you care about is that > writes happen-before reads. The point is that the read has to happen before the write, since the read is checking if a write lock happened. In reality, something like this is allowed writeCounter.increment() -> update stored in memory map.put() -> written immediately Seeing that writeCounter is still the old value doesn't mean that map.put hasn't been committed to memory yet.
[toc] | [prev] | [next] | [standalone]
| From | markspace <-@.> |
|---|---|
| Date | 2012-01-19 13:31 -0800 |
| Message-ID | <jfa23r$o3p$1@dont-email.me> |
| In reply to | #11500 |
On 1/19/2012 12:13 PM, raphfrk@gmail.com wrote: > On Jan 19, 6:39 pm, markspace<-@.> wrote: >> On 1/19/2012 10:10 AM, raph...@gmail.com wrote: >> >>> However, you can't say that RB happens-before WA. Therefore, there is >>> no happens before path between W-write and R-read. They are >>> effectively concurrent. >> >> There doesn't need to be a happens-before here, however. It's a *read*, >> and doesn't create a data race. The only thing you care about is that >> writes happen-before reads. > > The point is that the read has to happen before the write, since the > read is checking if a write lock happened. > > In reality, something like this is allowed > > writeCounter.increment() > -> update stored in memory > map.put() > -> written immediately I'm pretty sure that's the exact opposite of what is allowed. Remember that AtomicInteger::increment() is documented to have the same semantics as both reading and writing a volatile. I.e., from the perspective of a given execution order, the write from increment() is guaranteed to happen first. Writes and reads may not be reordered around it. I don't think write are allowed to be interleaved with other writes this way. > > Seeing that writeCounter is still the old value doesn't mean that > map.put hasn't been committed to memory yet. It's seeing writes from the future I'm most worried about right now. The read in the reader thread could see (perhaps) a write from the future, the map.put(). I'm looking around for something like "a read that happens before a a volatile read may not be reordered beyond a a write to that same volatile."
[toc] | [prev] | [next] | [standalone]
| From | "raphfrk@gmail.com" <raphfrk@gmail.com> |
|---|---|
| Date | 2012-01-19 16:14 -0800 |
| Message-ID | <ababef97-5d65-4295-9906-90f7f2311e61@k28g2000yqc.googlegroups.com> |
| In reply to | #11502 |
On Jan 19, 9:31 pm, markspace <-@.> wrote: > I'm pretty sure that's the exact opposite of what is allowed. Remember > that AtomicInteger::increment() is documented to have the same semantics > as both reading and writing a volatile. I.e., from the perspective of a > given execution order, the write from increment() is guaranteed to > happen first. Writes and reads may not be reordered around it. I don't > think write are allowed to be interleaved with other writes this way. However, that only applies to volatile read/writes themselves, I think. There has to be a happens-before chain from W-write to R-read, in the example. Otherwise, you can't say they happen separately.
[toc] | [prev] | [next] | [standalone]
| From | markspace <-@.> |
|---|---|
| Date | 2012-01-19 21:16 -0800 |
| Message-ID | <jfatbb$tuo$1@dont-email.me> |
| In reply to | #11507 |
On 1/19/2012 4:14 PM, raphfrk@gmail.com wrote: > On Jan 19, 9:31 pm, markspace<-@.> wrote: >> I'm pretty sure that's the exact opposite of what is allowed. Remember >> that AtomicInteger::increment() is documented to have the same semantics >> as both reading and writing a volatile. I.e., from the perspective of a >> given execution order, the write from increment() is guaranteed to >> happen first. Writes and reads may not be reordered around it. I don't >> think write are allowed to be interleaved with other writes this way. > > However, that only applies to volatile read/writes themselves, I > think. > > There has to be a happens-before chain from W-write to R-read, in the > example. Otherwise, you can't say they happen separately. No, and this is where a lot of folks mess up. For locks (monitors), volatile variables, and other syncrhonization actions, there's specifically a transitive relationship. ALL writes prior to a synchronization action happen-before all subsequent reads. So if you do this: int a = 1; int b = 2; int volatile v = 3; Then a, b, and v all synchronize "together" and code like this: x = v; y = b; z = a; Reads correctly when the read of v happens after the write of v. (Note I'm specifically ignoring the case where the read of v does NOT happen after the write of v. I think everyone agrees all bets are off in that case.) What you did was a little different. y = b; x = v; This can't synchronize, because even when the read of v does come after the write of v, b is still read before that, so it's value is really free to be anything.
[toc] | [prev] | [next] | [standalone]
Page 3 of 4 — ← Prev page 1 2 [3] 4 Next page →
Back to top | Article view | comp.lang.java.programmer
csiph-web