boost::shared_ptr<> uses mutex rather than CAS methods
Shared_ptr<> down deep uses a light-weight mutex to protect the increment and decrement of its reference count. A mutex isn't needed here. A mutex may yield the context of execution. This seems silly to protect a single instruction. To support threads, all modern processors offer some form of interlocked operation or atomic compare-and-swap instruction. On SPARC cpus, it is the CAS instruction, which acts much like a spin-lock. Windows offers InterlockedIncrement() and InterlocledDecrement() functions, which in the newer Microsoft compilers may be compiled as an intrinsic. I'm a bit allergic to context yielding synchronization objects thrown randomly into my server code. Does anyone know of any reasons to not use CAS-style programming here before I propose using it for smart_ptr<>? Glen
On Thu, 09 Dec 2004 09:32:05 -0800, Dayton <mvglen04-cnews@yahoo.com> wrote:
Shared_ptr<> down deep uses a light-weight mutex to protect the increment and decrement of its reference count. A mutex isn't needed here. A mutex may yield the context of execution. This seems silly to protect a single instruction.
To support threads, all modern processors offer some form of interlocked operation or atomic compare-and-swap instruction. On SPARC cpus, it is the CAS instruction, which acts much like a spin-lock. Windows offers InterlockedIncrement() and InterlocledDecrement() functions, which in the newer Microsoft compilers may be compiled as an intrinsic.
I'm a bit allergic to context yielding synchronization objects thrown randomly into my server code. Does anyone know of any reasons to not use CAS-style programming here before I propose using it for smart_ptr<>?
Glen
This should probably be a FAQ. I'm sure there are lots of messages in archive about this. Peter Dimov, or one of the Peters, I think has such an interlocked implementation which you'll find referred to in the message archive. Though the issue, from memory, is that there are two counts, for the weak and "strong" references and a lightweight mutex is about the same cost as two interlocked or CAS style ops so there is not necessarily a big benefit in changing. Explicit, yielding is a bad thing though... However, this leave the shared_ptr as a slowish pointer in a multithreaded environment if that is important to you. Even in a multithreaded code base you often want a fast single threaded smart pointer for appropriate situations, the current shared_ptr is not appropriate here either. A policy based design should allow you to customise these decisions as Loki's smart pointer shows. I think David Held is the closest to a reification of this abstraction for boost. There are many issues with policy based designs, especially without template typedefs in the language and w.r.t. compatibility, that have been discussed in the past, which is why the current shared_ptr interface design is perhaps the best common denominator to be useful to the widest audience. We are better with it than with arguing endlessly about the best approach... Another thought is to be aware that the count can be wrong sometimes and the semantics can still work. Researchers have used this to make faster reference counting work. That is, it doesn't matter if your count is wrong and too high, all that really matters is that someone gets a zero when the references are eliminated. I can probably dig out a reference to the paper I'm thinking of, if anyone is interested... You also raise an interesting point that as well as having correctness unit tests, boost should probably have performance benchmarking unit tests for libs where appropriate as performance needs to be checked and monitored for many lib components. HTH, matt matthurd@acm.org
On Thu, Dec 09, 2004 at 09:32:05AM -0800, Dayton wrote:
Shared_ptr<> down deep uses a light-weight mutex to protect the increment and decrement of its reference count. A mutex isn't needed here. A mutex may yield the context of execution. This seems silly to protect a single instruction.
To support threads, all modern processors offer some form of interlocked operation or atomic compare-and-swap instruction. On SPARC cpus, it is the CAS instruction, which acts much like a spin-lock. Windows offers InterlockedIncrement() and InterlocledDecrement() functions, which in the newer Microsoft compilers may be compiled as an intrinsic.
I'm a bit allergic to context yielding synchronization objects thrown randomly into my server code. Does anyone know of any reasons to not use CAS-style programming here before I propose using it for smart_ptr<>?
FYI I've modified boost::shared_ptr for inclusion in GCC's standard library and have replaced the mutexes with atomic ops along those lines. (I've finished the changes but am trying to find time to write extensive tests for the libstdc++ testsuite before I add the code to GCC's CVS repository. I was warned on this list that the tests take the most work :) jon -- "It is always the best policy to tell the truth, unless, of course, you are an exceptionally good liar." - Jerome K. Jerome
<snip>
On Thu, Dec 09, 2004 at 09:32:05AM -0800, Dayton wrote: <snip>
FYI I've modified boost::shared_ptr for inclusion in GCC's standard library and have replaced the mutexes with atomic ops along those lines.
(I've finished the changes but am trying to find time to write extensive tests for the libstdc++ testsuite before I add the code to GCC's CVS repository. I was warned on this list that the tests take the most work :)
I saw another interesting note about GCC and type traits the other day. The only probably is that it is a one way door to the GPL world from boost due to the GPL licence restrictions, even looking at the GCC implementation and implementing any improvements is questionable :-( $0.02 matt.
Matt Hurd wrote:
I saw another interesting note about GCC and type traits the other day. The only probably is that it is a one way door to the GPL world from boost due to the GPL licence restrictions, even looking at the GCC implementation and implementing any improvements is questionable :-(
Keep in mind that the copyright owner has the right to contribute his work to anyone under any terms he sees fit. i.e. Jon can contribute his change to boost under boost's license if both parties are interested. Neal
Matt Hurd wrote: [...]
I saw another interesting note about GCC and type traits the other day. The only probably is that it is a one way door to the GPL world from boost due to the GPL licence restrictions, even looking at the GCC implementation and implementing any improvements is questionable :-(
Why is looking at GPL code a potential problem? I know that some software companies try to claim all sorts of trade secret and patent rights over their code, but from a pure copyright perspective, there is not and cannot be any problem with examining an existing code to figure out how it works and then reimplementing it. AFAIK it is entirely analagous to, say, reading a chemistry textbook and then trying out some of the reactions at home, or even writing your own textbook. Unless you actually plagarize parts of it, copyright law doesn't care. Granted, this case may be a bit more complicated if both codes come from a common source and are substantially identical to begin with. But copyright law wasn't designed to cover such cases anyway. It might be worth asking the FSF (as the copyright holder) what they think, my guess would be "don't care". Cheers, Ian
On Thu, 09 Dec 2004 22:09:36 +0100, Ian McCulloch <ianmcc@physik.rwth-aachen.de> wrote:
Matt Hurd wrote:
[...]
I saw another interesting note about GCC and type traits the other day. The only probably is that it is a one way door to the GPL world from boost due to the GPL licence restrictions, even looking at the GCC implementation and implementing any improvements is questionable :-(
Why is looking at GPL code a potential problem? I know that some software companies try to claim all sorts of trade secret and patent rights over their code, but from a pure copyright perspective, there is not and cannot be any problem with examining an existing code to figure out how it works and then reimplementing it. AFAIK it is entirely analagous to, say, reading a chemistry textbook and then trying out some of the reactions at home, or even writing your own textbook. Unless you actually plagarize parts of it, copyright law doesn't care.
Granted, this case may be a bit more complicated if both codes come from a common source and are substantially identical to begin with. But copyright law wasn't designed to cover such cases anyway. It might be worth asking the FSF (as the copyright holder) what they think, my guess would be "don't care".
Cheers, Ian
Perhaps you are right, I don't know, IANAL. I'm sure you're right about the "don't care" part. I'd imagine it is a risk thing. I seem to remember one of the original BIOS clone vendors, Phoenix I think, in the 80s hiring people that had never seen a BIOS before as part of "clean room" implementation team. That's one extreme... W.r.t. the original copyright holder granting rights, that's fine, but other contributions, fixes, to GCC CVS and the like are not necessarily part of that unless they are fed back. It is just a complication w.r.t. licenses. I'd be quite happy if FSF took over the world, license incompatibilities dissolved... matt.
participants (6)
-
Dayton -
Ian McCulloch -
Jonathan Wakely -
Matt Hurd -
Neal Coombes -
Peter Dimov