bool Associative Array Synchronized

[Etienne]

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 :)