On Thu, Mar 20, 2014 at 06:39:10PM +0000, Chris Williams wrote: > On Thursday, 20 March 2014 at 18:06:18 UTC, Etienne wrote: > >Right, I was assuming it was always ordered, but modern processor > >pipelines are different I guess. > > Even without rearranging the order of your code, your bit exists in > RAM but all the logic takes place in a CPU register, meaning that > any time you operate with the bit, there's at least two copies. When > the CPU switches threads (which could be at any point), it empties > the CPU into RAM. If the thread it's switching to then tries to > interact with the bit, it's going to create a third copy. Now > whichever of the two threads is slower to write back to the original > location is going to smash the other's.
Furthermore, the CPU does not access bits directly; it processes them as (at least) bytes. To set/clear a bit in memory location X, the CPU has to first read X into a register (at least 8 bits long), update the bit, and write it back into memory. If two threads are simultaneously operating on different bits that resides in the same byte, whichever CPU runs last will smash whatever the first CPU wrote. Let's say you start with 00000000b in location X, and CPU1 wants to set the first bit and CPU2 wants to set the second bit. Both CPU's initially reads 00000000b into their registers, then the first CPU sets the first bit, so it becomes 00000001b (in register) and the second CPU sets the second bit so it becomes 00000010b (in register). Now CPU1 writes 00000001b back to memory, followed by CPU2 writing 00000010b back to memory. Now what CPU1 did has been smashed by CPU2's write. Now, the current AA implementation doesn't actually pack bits like this, so this particular problem doesn't actually happen, but other similar problems will occur if you add/remove keys from the AA -- two CPU's will try to update internal AA pointers simultaneously, and end up trashing it. T -- What doesn't kill me makes me stranger.
