On 2014-03-20 2:47 PM, H. S. Teoh wrote:
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
Hmm my misunderstanding comes from not taking into account everything I
knew about CPU caches. As a side note, I think I heard somewhere that
abstractions don't flatten out the learning curve at all, it's like a
bigger gun but you still need to know all the basics to avoid shooting
yourself with it. So true. Well, thanks for the explanation there :)
