bool Associative Array Synchronized

[H. S. Teoh]

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.