Modern architectures really are quite complex, and it's important to keep your internal machine model up to date with what's happening. Examples: It used to be on a 486 even correctly-predicted taken branches had a two-cycle penalty. It used to be important whether you arranged your code so the most commonly taken code was on the fall through path or not. Today, correctly predicted branches are free--the processor stitches together the current path and the new path so there are no bubbles in the pipeline. Virtual function calls also used to be more expensive back in the day, because CPU's didn't try to predict the target address of the branch. Today, CPU's have a buffer that maps from a program counter to a target address, so if your virtual function call predictably hits the same target each time, the only overhead will be the extra memory accesses to indirect through the v-table.
At the same time, things that are expensive today may not be so in the near future. Haswell is supposed to make uncontended synchronization operations almost free. It'll make a lot of algorithms, particularly lock-free algorithms, much more practical than they are today. For example, C++ smart pointers are slow in multi-threaded situations because the reference count manipulation needs to be done under a lock. But the lock is almost never needed (except when it is). Cheap synchronization should make it much more practical to use reference counting more pervasively in C++ programs.
"For example, C++ smart pointers are slow in multi-threaded situations
because the reference count manipulation needs to be done under a lock."
Several architectures support atomic increment and decrement operations, so there's no need for any lock.
Libaries like OpenSceneGraph use them for their reference counting.
Also Haskell isn't magical in this regard. Their lock free
implementations will also presumably just use safe atomic operations.
Atomic increment/decrement operations still generate a locked memory transaction of some form or the other at the processor level. Haswell is Intel's new CPU that is supposed to implement some level of hardware transactional memory, leveraging the infrastructure used for cache coherency. In theory, this will make transactional operations (atomic increment/decrement is just a tiny transaction) as cheap as a regular memory operation so long as there is no contention.
Note the classic 'bus lock' is a worst case nowadays: caches in SMP machines have their own protocols for invalidating and locking individual lines, so the entirety of the machine's memory isn't necessarily serialized, though I'm not sure when this kind of locking applies.
Sort of, but it's not really a "lock". If, as is very likely in performance-sensitive-but-uncondended multithreaded code, the CPU already has the cache line in "exclusive" (in the MESI sense) mode then the atomic operation needs to be no faster or slower than a standard read/write sequence. On x86 it is serializing, however, which can have performance impacts for some workloads.
An atomic operation on a cacheline owned exclusively by the local CPU avoids any bus lock operations, but still serializes the pipeline to avoid conflicts caused by memory operations on the same CPU. This basically destroys your memory parallelism if you use it in a situation where the atomic instruction happens often (e.g. every time an object reference is loaded or stored).
Isn't that exactly what I said? Note that "destroy memory parallelism" is often not a high penalty in typical workloads where all in-flight accesses are hitting L1 cache only. It's not nearly as high as the "full round trip to DRAM" latency implied by calling it a "lock".
I'm not really disagreeing with you, but I think we're using the terminology differently. To me, "memory" is the whole memory pipeline--everything from the load/store units, through the load/store buffers, the caches, to DRAM.
When I said it was a "locked memory transaction of some sort" I was including the effect of a serializing instruction which prevents concurrent load/store operations even if they hit the cache. I wasn't trying to imply a full round trip to DRAM.
It's important to note that even at the hardware level(for intel x64, at least), atomic increments and decrements are, in fact, just the operations with locks around them.
So relying heavily on them in multithreaded cases with heavy contention can actually reduce performance over a more complex lockless scheme.
Comments
Modern architectures really are quite complex, and it's important to keep your internal machine model up to date with what's happening. Examples: It used to be on a 486 even correctly-predicted taken branches had a two-cycle penalty. It used to be important whether you arranged your code so the most commonly taken code was on the fall through path or not. Today, correctly predicted branches are free--the processor stitches together the current path and the new path so there are no bubbles in the pipeline. Virtual function calls also used to be more expensive back in the day, because CPU's didn't try to predict the target address of the branch. Today, CPU's have a buffer that maps from a program counter to a target address, so if your virtual function call predictably hits the same target each time, the only overhead will be the extra memory accesses to indirect through the v-table.
At the same time, things that are expensive today may not be so in the near future. Haswell is supposed to make uncontended synchronization operations almost free. It'll make a lot of algorithms, particularly lock-free algorithms, much more practical than they are today. For example, C++ smart pointers are slow in multi-threaded situations because the reference count manipulation needs to be done under a lock. But the lock is almost never needed (except when it is). Cheap synchronization should make it much more practical to use reference counting more pervasively in C++ programs.
"For example, C++ smart pointers are slow in multi-threaded situations because the reference count manipulation needs to be done under a lock."
Several architectures support atomic increment and decrement operations, so there's no need for any lock. Libaries like OpenSceneGraph use them for their reference counting.
Also Haskell isn't magical in this regard. Their lock free implementations will also presumably just use safe atomic operations.
Atomic increment/decrement operations still generate a locked memory transaction of some form or the other at the processor level. Haswell is Intel's new CPU that is supposed to implement some level of hardware transactional memory, leveraging the infrastructure used for cache coherency. In theory, this will make transactional operations (atomic increment/decrement is just a tiny transaction) as cheap as a regular memory operation so long as there is no contention.
Note the classic 'bus lock' is a worst case nowadays: caches in SMP machines have their own protocols for invalidating and locking individual lines, so the entirety of the machine's memory isn't necessarily serialized, though I'm not sure when this kind of locking applies.
Sort of, but it's not really a "lock". If, as is very likely in performance-sensitive-but-uncondended multithreaded code, the CPU already has the cache line in "exclusive" (in the MESI sense) mode then the atomic operation needs to be no faster or slower than a standard read/write sequence. On x86 it is serializing, however, which can have performance impacts for some workloads.
An atomic operation on a cacheline owned exclusively by the local CPU avoids any bus lock operations, but still serializes the pipeline to avoid conflicts caused by memory operations on the same CPU. This basically destroys your memory parallelism if you use it in a situation where the atomic instruction happens often (e.g. every time an object reference is loaded or stored).
Isn't that exactly what I said? Note that "destroy memory parallelism" is often not a high penalty in typical workloads where all in-flight accesses are hitting L1 cache only. It's not nearly as high as the "full round trip to DRAM" latency implied by calling it a "lock".
I'm not really disagreeing with you, but I think we're using the terminology differently. To me, "memory" is the whole memory pipeline--everything from the load/store units, through the load/store buffers, the caches, to DRAM.
When I said it was a "locked memory transaction of some sort" I was including the effect of a serializing instruction which prevents concurrent load/store operations even if they hit the cache. I wasn't trying to imply a full round trip to DRAM.
Depends. One atomic writer - multiple readers work out to be pretty darn fast if protected by only a memory fence.
Oh sorry, I have been reading your post a bit sloppy, and transactional memory was just too much of an association with Haskell.
I think s/he meant the upcoming Haswell processor architectures, not Haskell the language.
It's important to note that even at the hardware level(for intel x64, at least), atomic increments and decrements are, in fact, just the operations with locks around them.
So relying heavily on them in multithreaded cases with heavy contention can actually reduce performance over a more complex lockless scheme.