- Boost-users - lists.preview.boost.org

Re: [Boost-users] Thread-safe smart pointers, hashtables
by Gottlob Frege 06 May '06

06 May '06

> Date: Fri, 5 May 2006 14:09:33 -0600 > From: Ray Whitmer <ray(a)personallegal.net> > Subject: Re: [Boost-users] Thread-safe smart pointers, hashtables > without locking > To: boost-users(a)lists.boost.org > Message-ID: <0D5E3BD4-9A5D-4CE2-9040-35500773C190(a)personallegal.net> > Content-Type: text/plain; charset=US-ASCII; delsp=yes; format=flowed > > > The algorithm makes sense, and if all these claims hold then it > > should work, I think. I'm still concerned about step (2), however, > > if only because of the assumption that what you write as a load/ > > store in C++ maps to a load/store in ML. Will it? Always? I ask as > > a non-rhetorical question: does the C++ standard *guarantee* it? > > Because if it doesn't then it seems like a potential problem, but > > maybe I'm being too careful. I'd also say the idea of moving a pointer out of the way, and then using the flip-gate-count-thing to wait for any 'potentially-using' readers to finish, definitely has 'potential'. You would need to show detailed code to really be sure. And not to us - to the guys on comp.programming.threads. If I could answer in the affirmative, I could prove it works and not > have to talk to anyone. I can make a bunch of lesser claims, that of > course fail to add up to the strong claim but make me feel better: > > 3. I have looked at the output of many C compilers and have never > seen a pointer assignment take multiple instructions. The exception > might be if someone used a poorly-written memcpy-like operations to > transfer the contents of a structure byte by byte. A well-written > one takes the respective alignments into account and transfers > aligned 32-bit quantities one-by-one. We are talking about code in a > controlled Hashtable class, it would have to be the "C" compiler > choosing to transfer a class consisting of a single address field > using something other than a single instruction. It doesn't sound > logical to me, but it wouldn't surprise me completely to see it > happen, but I would report it as a compiler bug and expect it to be > addressed even though it is not in the standard. As long as the address of the pointer is properly aligned, it will be atomic. The language doesn't guarantee that (the language doesn't talk about atomic or threads at all - at least not yet), but the processors + compilers tend to guarantee it. HOWEVER! *even if it is atomic*, on a multi-cpu machine each cpu might see memory differently - you need memory barriers to ensure the other cpus see your new pointer value correctly. Think of cpus and memory like harddrive controllers that reorder reads and writes to lessen seeks - the cpu does the same sort of thing with memory - and in doing so, it may reorder the write of your pointer to 'happen' before you expected (because it was near other memory it was writing) and/or read the pointer later than expected (because it optimized other reads into a 'bundle' before the read of your pointer). Anyhow, if you haven't already, take a look at memory barriers, and, as a canonical example, the broken 'double checked locking pattern'. You can't do lock free without understanding this stuff. 4. These issues have to be addressed with the multi-processor cores > becoming more prevalent because they are basic to lock-free > processing, or can C++ accept significant inferiority to Java with > respect to lock-free multiprocessing? see above. Much of it doesn't come for free. For what it is worth, if anyone else thinks the solution is worth a > generic contribution, or is of the opposite opinion that it would not > be generic enough, I would be interested in hearing. I suppose this > sort of question should go to the developers list. I think it would > be much more difficult to implement a table of shared_ptr than it is > for intrusive_ptr, because assigning a shared_ptr is much less likely > to be uninterrupted, leaving other threads with a broken visible > state. There is clearly more detail to discuss as well. > Ray Whitmer Your wording of 'much less likely' is scary, and I think similar wording made James apprehensive as well. There is no grey - it is black or white, thread safe or not. And you are correct, you can't make { reading the location of a shared_ptr + incrementing its ref-count } atomic, it least not on most processors. I'm not sure of the exact implementation of intrusive_ptr, but assuming it is like most, you can make ip1 = ip2; atomic IF ip2 is 'stable', ie guaranteed to not be changing during the assignment. ie ip1 can be read and/or written by other threads "while" the assignment is happening, and you will either get the before state of ip1, or the after state. I don't think the boost implementation of intrusive_ptr's operator=() is atomic, but it could be made to be. Tony

1 0

[BGL] adjacency_list property map selection
by Daniel Mitchell 06 May '06

06 May '06

Are there any plans to replace the property map selection code with a mechanism based on partial specialization? I'm implementing interior property maps for my own graph classes and must decide which approach to use. Partial specialization is elegant, but there's also value in consistency with BGL. D.

1 0

Re: [Boost-users] [multi-array] [C++ ] multi array dimensions
by Sohail Somani 05 May '06

05 May '06

> -----Original Message----- > From: boost-users-bounces(a)lists.boost.org > [mailto:boost-users-bounces@lists.boost.org] On Behalf Of > Bruno Martínez > Sent: Friday, May 05, 2006 4:52 PM > To: boost-users(a)lists.boost.org > Subject: Re: [Boost-users] [multi-array] [C++ ] multi array dimensions > > On Tue, 02 May 2006 16:04:04 -0300, Karim Bakir > <rimbak(a)yahoo.fr> wrote: > > > Ok so , And is it possible to retrieve the size of the dimension? > > Yes. That's the shape() member function. I've been thinking, it would be nice if shape() returned a const boost::array & whose indexing has nice asserts at debug time :) Anyone else feels the same?

1 0

[multi-array] [C++ ] multi array dimensions
by Karim Bakir 05 May '06

05 May '06

Hi , I want to known if exists method which give us the dimension of a multi array ...I see the documentation and i 'will say no , if no, does it exist a method to determine the dimension of a multi array ? Thanks.

2 5

Possible bug in program_options when disabling _SECURE_SCL on VS8
by Roger Dahl 05 May '06

05 May '06

I think I've found a bug in program_options. #define _SECURE_SCL 0 on Visual Studio 2005 causes program_options to crash in store(). I used boost from CVS. Below is an example. Thanks for an awesome library! Roger -- #define _SECURE_SCL 0 #include <boost/program_options.hpp> namespace po = boost::program_options; int main(int argc, char* argv[]) { po::options_description desc("Allowed Options"); desc.add_options() ("help", "produce help message") ; po::variables_map vm; po::store(po::parse_command_line(argc, argv, desc), vm); po::notify(vm); return 0; }

1 0

Re: [Boost-users] Thread-safe smart pointers, hashtables without locking
by Ray Whitmer 05 May '06

05 May '06

> The algorithm makes sense, and if all these claims hold then it > should work, I think. I'm still concerned about step (2), however, > if only because of the assumption that what you write as a load/ > store in C++ maps to a load/store in ML. Will it? Always? I ask as > a non-rhetorical question: does the C++ standard *guarantee* it? > Because if it doesn't then it seems like a potential problem, but > maybe I'm being too careful. If I could answer in the affirmative, I could prove it works and not have to talk to anyone. I can make a bunch of lesser claims, that of course fail to add up to the strong claim but make me feel better: 1. For years, people have written and relied on C/C++ characteristics that apparently were not in the standard until later if at all. If the popular platforms support it, it takes a strong reason to justify a violation of it. 2. Java, on any platform, would seem to strongly depend upon a reference assignment being accomplished all-or-nothing as a machine assignment. The alternative would be threads that see partial references being assigned in different threads and all the safety of references is out the window. This is such a common operation, it would be difficult to believe that there is thread synchronization going on around every pointer/reference assignment. 3. I have looked at the output of many C compilers and have never seen a pointer assignment take multiple instructions. The exception might be if someone used a poorly-written memcpy-like operations to transfer the contents of a structure byte by byte. A well-written one takes the respective alignments into account and transfers aligned 32-bit quantities one-by-one. We are talking about code in a controlled Hashtable class, it would have to be the "C" compiler choosing to transfer a class consisting of a single address field using something other than a single instruction. It doesn't sound logical to me, but it wouldn't surprise me completely to see it happen, but I would report it as a compiler bug and expect it to be addressed even though it is not in the standard. 4. These issues have to be addressed with the multi-processor cores becoming more prevalent because they are basic to lock-free processing, or can C++ accept significant inferiority to Java with respect to lock-free multiprocessing? Sorry that my arguments in this case frequently refer to Java. > > Have you read any of the literature on lock-free data structures, > btw? There was articles in the October and December '04 C/C++ User > Journal about them. I have read a number of articles on the subject, several specifically on the topic of lock-free hashtables, several with implementations they claim to be proven to be correct. My own first attempt is far from a proven-correct implementation. Many seem to arrive at similar conclusions, although each has its own slightly-different take on the subject and quite different mechanisms. They are also very often theoretical and build their proofs of completeness on features not apparently explicitly present in "C" standards. I certainly have yet to find an implementation I can just plug in and use. They often resort to garbage collection to solve the hard problems (even if they are working in C) or if they solve the deallocation problem, they only do so for the main array, not for the entries in the hashtable itself. > I realize that I haven't answered your original question about > atomic_count, btw, and I'm sorry: the reason is simply that I don't > know! Thanks for the comments anyway, which were thought-provoking. For what it is worth, if anyone else thinks the solution is worth a generic contribution, or is of the opposite opinion that it would not be generic enough, I would be interested in hearing. I suppose this sort of question should go to the developers list. I think it would be much more difficult to implement a table of shared_ptr than it is for intrusive_ptr, because assigning a shared_ptr is much less likely to be uninterrupted, leaving other threads with a broken visible state. There is clearly more detail to discuss as well. Ray Whitmer

1 0

Re: [Boost-users] Thread-safe smart pointers, hashtables without locking
by james.jones＠firstinvestors.com 05 May '06

05 May '06

From: Ray Whitmer <ray(a)personallegal.net> >> This would be truly thread-safe but might perform better if you >> have lots of simultaneous readers/writers. I haven't tested this, >> but if you do, I'd be interested to hear the results. > > I don't think it even begins to be thread-safe, because it doesn't > begin to deal with reallocation of the array itself... That's certainly true. I guess I was thinking of a hashtable whose interface is that it is allocated with a fixed size and not reallocated (although it might be copy-constructed to a hashtable of a different size). If modern hashtables reallocate their storage, that would certainly have to be done in a thread-safe manner. > Here is my first stab at a solution: > > 2. Perform changes to the hashtable in a manner that, given atomic > loads or stores of aligned pointers, never leaving the table in a > state that simultaneous readers cannot use it. This is very easy > compared to the allocation issues, and I have been doing this in Java > for years. I would be happy to expand on this. This write operation > may include releasing objects with ref-count 1, if this is supposed > to be a weak hashtable that does not keep unused objects in the index. [rest snipped] The algorithm makes sense, and if all these claims hold then it should work, I think. I'm still concerned about step (2), however, if only because of the assumption that what you write as a load/store in C++ maps to a load/store in ML. Will it? Always? I ask as a non-rhetorical question: does the C++ standard *guarantee* it? Because if it doesn't then it seems like a potential problem, but maybe I'm being too careful. Have you read any of the literature on lock-free data structures, btw? There was articles in the October and December '04 C/C++ User Journal about them. I realize that I haven't answered your original question about atomic_count, btw, and I'm sorry: the reason is simply that I don't know! - James Jones Administrative Data Mgmt. (v)732-510-1806 375 Raritan Center Pkwy, Suite A (f)732-510-1855 Edison, NJ 08837 Visit us on the web at http://www.firstinvestors.com/

1 0

[tribool]compile error
by Thomas Matelich 05 May '06

05 May '06

This is only happening when I'm instrumenting code with Insure++ from Parasoft. They use an EDG based parser (not sure of the version, but I know they have it set to be very strict) and it is failing like so: /usr/local/eddynet/debug_eddynet/opt/include/boost/logic/tribool.hpp: In function `boost::logic::tribool boost::logic::operator&&(boost::logic::tribool, boost::logic::tribool)': /usr/local/eddynet/debug_eddynet/opt/include/boost/logic/tribool.hpp:78: ` struct boost::logic::tribool::dummy' is private /usr/local/eddynet/debug_eddynet/opt/include/boost/logic/tribool.hpp:203: within this context /usr/local/eddynet/debug_eddynet/opt/include/boost/logic/tribool.hpp:78: ` struct boost::logic::tribool::dummy' is private /usr/local/eddynet/debug_eddynet/opt/include/boost/logic/tribool.hpp:203: within this context /usr/local/eddynet/debug_eddynet/opt/include/boost/logic/tribool.hpp:78: ` struct boost::logic::tribool::dummy' is private /usr/local/eddynet/debug_eddynet/opt/include/boost/logic/tribool.hpp:205: within this context /usr/local/eddynet/debug_eddynet/opt/include/boost/logic/tribool.hpp:78: ` struct boost::logic::tribool::dummy' is private /usr/local/eddynet/debug_eddynet/opt/include/boost/logic/tribool.hpp:205: within this context /usr/local/eddynet/debug_eddynet/opt/include/boost/logic/tribool.hpp: In function `boost::logic::tribool boost::logic::operator||(boost::logic::tribool, boost::logic::tribool)': /usr/local/eddynet/debug_eddynet/opt/include/boost/logic/tribool.hpp:78: ` struct boost::logic::tribool::dummy' is private /usr/local/eddynet/debug_eddynet/opt/include/boost/logic/tribool.hpp:270: within this context /usr/local/eddynet/debug_eddynet/opt/include/boost/logic/tribool.hpp:78: ` struct boost::logic::tribool::dummy' is private /usr/local/eddynet/debug_eddynet/opt/include/boost/logic/tribool.hpp:270: within this context /usr/local/eddynet/debug_eddynet/opt/include/boost/logic/tribool.hpp:78: ` struct boost::logic::tribool::dummy' is private /usr/local/eddynet/debug_eddynet/opt/include/boost/logic/tribool.hpp:272: within this context /usr/local/eddynet/debug_eddynet/opt/include/boost/logic/tribool.hpp:78: ` struct boost::logic::tribool::dummy' is private /usr/local/eddynet/debug_eddynet/opt/include/boost/logic/tribool.hpp:272: within this context Locally I've worked around this with changing the first part of the tribool class from: class tribool { private: to class tribool { #ifdef __INSURE__ //Symbol defined by parser when used in this context public: #endif (no #else since private is implied) Anyway, I don't mind maintaining my own mods, just thought I'd report this. If you don't mind enlightening me, I am a little curious why using safe_bool works if its private on any compiler. Seems like private typedefs usually are private. Thanks, Tom

1 0

Re: [Boost-users] [Unit-Test] How to test private functions
by james.jones＠firstinvestors.com 05 May '06

05 May '06

From: Carlo Wood <carlo(a)alinoe.com> >Also, the above is slightly dangerous, as the 'public' would >'leak' beyond the #ifdef when TESTING is defined. You'd have to make >sure that the test block at the end of the class. This is a very good point. A method defined as public in test might fail to compile as private in production. >Personally, I like the #define private public best, because it doesn't >polute the real code. But this contradicts your prior good point. This is even more dangerous than the conditional public: which you objected to, because now *every* method is public! At least with the other method, you can do it safely if you're careful. - James Jones Administrative Data Mgmt. (v)732-510-1806 375 Raritan Center Pkwy, Suite A (f)732-510-1855 Edison, NJ 08837 Visit us on the web at http://www.firstinvestors.com/

2 1

Re: [Boost-users] Thread-safe smart pointers, hashtables without locking
by Ray Whitmer 05 May '06

05 May '06

> Personally, I read this and said, "eeek!" (Well, not literally. My > office mates would wonder what was up.) I think any design like > this is going to be (at best) very non-portable, and (more likely) > subject to breaking at the worst possible moment (i.e. when > demonstrating to a customer). Is "relatively" thread-safe really > good enough here? Let me make it clear. I do not want relatively thread-safe. I want completely thread safe. It seems to me that boost already relies on an atomic counter for shared_ptr. I do not think the solution would be less portable than this. I certainly want it to run on Windows and Mac, 32 and 64 bit as well as major Unix and Linux including certain 32-bit-or-more embedded situations. There may be hopefully-rare C++ threading situations that may be difficult to recover from, and I will simply have to gather more information on these and see if they can be dealt with. > As a constructive suggestion, if you want to reduce lock conflicts > in hash tables, have you considered some form of finer-grained > locking? You could, for example, have one lock per "slot" in your > hash table. Computing the hash and finding the slot is thread-safe > (since it doesn't depend on the state of the hash table), so you > could then lock only the slot itself while performing list > maintenance or whatever you need to do to read/write the data. For the more-common reader of the hash table, it is not my intent to reduce lock conflicts, but, rather, to generally eliminate them, and replace them with something lighter-weight, such as the atomic counter used by shared_ptr, that in best cases may only take a few instructions to execute. I may have thousands of threads reading info from the hashtable at once and there may never be a natural time when there are no readers so I can update the table. The purpose of the threads is many operations that rely heavily on the hashtables -- every other instruction they are looking up something. For what it is worth, finding the slot is not thread-safe, because the table size and pointer can change. List maintenance involves multiple slots and I do not think it is worthwhile doing finer- grained locks because of the complexity, deadlock potential, and likely worse performance it would introduce. > This would be truly thread-safe but might perform better if you > have lots of simultaneous readers/writers. I haven't tested this, > but if you do, I'd be interested to hear the results. I don't think it even begins to be thread-safe, because it doesn't begin to deal with reallocation of the array itself, and if it did, your fine-grained locks appear to become worthless because you need a high-level lock protecting that allocation assuming you are going to use locks for readers, which seems like a bad idea from the start for me. There is a reason shared_ptr does not use locks (at least on the best-supported platforms), but uses an atomic count. > PS - I'd be even more worried in Java, btw, since Java opcodes > should map to CPU operations less well than a compiled binary. Not > to mention that in Java, the portability assumption becomes really > critical. Java classes are *supposed* to be portable. I do not want to get into Java wars here, but Java has to solve the deallocation problem in a thread-safe manner. When the garbage collector actually reclaims an allocation, the possibility cannot exist that someone else still happens to be using it or the language is badly broken. This is the hard thing to be solved in C++ to make a thread-safe hashtable that you do not have to deal with in Java. The deallocation problem is, from everything I have analyzed, the big problem in C++. When you attempt to deallocate something, for all you know there could be another thread that just barely loaded its pointer into shared memory and as soon as it unstalls will want to increment its reference count, but it has not yet been incremented, so even a smart pointer using an atomic reference count fails because the object is sharable in a multithreaded environment, but not the reference itself. Here is my first stab at a solution: Extra data (for each Hashtable): 1. Array of two atomic counts, one active and one inactive. 2. Index that flops between 0 and 1, so there is an active and inactive count. 3. A mutex that can be used for exclusive writers Each reader behaves as follows: 1. Fetch index. 2. Increment corresponding atomic count. 3. If fetched index is not current index, decrement atomic count and loop to step 1. This is rare and safely eliminates rare bad cases 4. Now the reader has free access to the entire hashtable structure, and is guaranteed by cooperation of the writer that the pointers it sees are not stale. It must only guarantee that any pointer referenced in step 4 is either destroyed or it's ref count is incremented before step 5 -- this includes the pointer to the allocated resizable array itself. 5. Decrement the same atomic count (of fetched index) incremented in step 3. Note that in Java, none of this is necessary for readers because the language safety assumes any reference is not deallocated. Each writer behaves as follows: 1. Obtain an exclusive lock on the hashtable. This lock only excludes other writers, not other readers. 2. Perform changes to the hashtable in a manner that, given atomic loads or stores of aligned pointers, never leaving the table in a state that simultaneous readers cannot use it. This is very easy compared to the allocation issues, and I have been doing this in Java for years. I would be happy to expand on this. This write operation may include releasing objects with ref-count 1, if this is supposed to be a weak hashtable that does not keep unused objects in the index. 3. This is really part of 2: any step in (2) which destroys a reference a reference keeps a private local copy to make sure it is not deallocated before all reading threads are finished with it. If the references are ref-counted, a ref-counted private reference is kept. 4. If there are no private local pointers/references being kept, go to step 9 5. Wait for inactive (1-index) atomic count to go to 0. This is rare and safely eliminates rare bad cases. 6. Change index (index = 1 - index). 7. Wait for inactive (1-index) atomic count to go to 0. This means that all readers who might have a copy of a stale pointer are finished. 8. Release all private local references with a reference count of 1. Non-ref-counted references always get released, due to single owner. If this is a weak hashtable, reinsert any references that have a reference count greater than one since these were found and incremented while we were waiting for readers to exit. 9. Release lock. Done. More notes: Although we don't want to go out of our way to make the writer inefficient, there is a single writer at any one time with an exclusive lock. But we do not have to wait for all readers to exit to perform the update, we only need to wait for current readers to exit, during which time new readers may enter, which we do not care about because we have already removed the candidates from public places in the list. This includes the pointer to the array itself, which is generally treated like any other allocated pointer, but does not require a reference count. There are many details I left out that did not directly pertain to the allocation problem, but only with atomically updating the rest of the table so that the reader view is always consistent. Ray Whitmer

1 0