- Boost - lists.boost.org

Re: [boost] [1.35.0] Intel compiler - does anyone care?
by Chad Walters 04 Jan '08

04 Jan '08

Beman Dawes wrote: > If there are folks who do care, perhaps they could suggest a plan to > eliminate the failures, or at least shed light on why so many tests are > failing. I imagine that Intel should care. ;) One of my team members used to work on the Intel compiler - I'll ask him to ping his former colleagues to see if we can get some attention from them on this issue. Chad

1 0

Question regarding boost.unordered
by Lipik Contact 03 Jan '08

03 Jan '08

Hello list, I have downloaded unordered library from the vault and plan to start using it. However, looking at the documentation, there might be issues that prevent it being useful for me. Could someone please comment on the following: If the user holds a reference (or pointer) to some element in the container (e.g. T const *p = &*it), is that reference guaranteed to remain valid after the insertion/erase of some other elements? I ask because doc says that erasing through an iterator can be O(size) - which seems to suggest that erase can lead to a rehash, invalidating iterators. This appears to contradict the iterator lifetime guarantee posited by the standard (after all, tree based containers don't rebalance after erase, do they?) Another question: any thoughts on whether it is better to use boost::hash for pointers and wstrings, or would a modification of the FNV hash included with unordered give better results? Also, I'm assuming that I can plug this library into boost-1.33.1. Many thanks Amit

3 2

Trac open bugs - by assignee
by Marshall Clow 03 Jan '08

03 Jan '08

[ 190 open bugs today, 190 yesterday ] If you are maintaining a library, and have not logged into the trac system at <http://svn.boost.org/trac/boost/>, please do so ASAP. Until you do that, no tickets can be assigned to you, and will remain under "None". Instructions on working with tickets can be found at: <http://svn.boost.org/trac/boost/wiki/TicketWorkflow> and a mapping of user names to "real names" can be found at: <http://svn.boost.org/trac/boost/report/16> Bug summary 18 az_sw_dude 17 dgregor 15 djowel 12 doug_gregor 11 grafik 11 dave 11 None 10 agurtovoy 8 vladimir_prus 8 jsiek 7 johnmaddock 7 anthonyw 5 witt 4 bemandawes 3 rogeeff 3 pdimov 3 jmaurer 3 igaztanaga 3 ebf 3 danielw 2 urzuga 2 turkanis 2 pavol_droba 2 niels_dekker 2 nesotto 2 nasonov 2 matias 2 <Blank> 1 t_schwinger 1 speedsnail 1 shammah 1 samuel_krempp 1 ramey 1 marshall 1 kaalus 1 hljin 1 hkaiser 1 dlwalker 1 burbelgruff 1 aaron_windsor <Blank> 1307 [lambda] invalid boostbook <Blank> 1434 Boost.Preprocessor_ small fix for the documentation None 1068 Mersenne twister disables streaming for Visual C++ None 1094 Finding the correct library to link (feature request for pkg-config support)h None 1222 lambda::ret<T> should declare result_type. None 1247 Typos in "boost/random/additive_combine.hpp"_ lines 68-69 None 1270 uniform_smallint doesn't compile with lagged_fibonacci random number generators None 1407 Boost is doesn't install on MacPorts using Leopard None 1493 SVN files making it through to install None 1515 [lambda] C4512 warnings from VC8.0 None 1544 uniform_01 w/ref template param causes ref to ref error None 1546 Method boost::random::uniform_int::operator()(engine_ value) is missing None 1548 [variant][docs]typo: formal arg_ operand_ should be v in times_two arglist aaron_windsor 778 top-level configure is broken agurtovoy 1001 gcc 4.1.2 segfaults on mpl/test/apply.cpp agurtovoy 1051 MPL header ordering triggers bug agurtovoy 1099 unable to iterate through a "non-explicitly-declared" mpl::set agurtovoy 1215 Boost 1.34.1_ mpl: Wrong workaround detection using MinGW32 (or.hpp_ line #33) agurtovoy 1317 has_xxx randomly broken in msvc agurtovoy 1469 [mpl] nested typedef of set has two different meanings agurtovoy 1476 always<> is not nullary. agurtovoy 1528 g++ 4.3.0 reports error because of redeclaration of next agurtovoy 588 mpl::remove compile error with gcc 4.1.0 agurtovoy 640 documentation mistake anthonyw 1154 tss destruction segfaults in conjunction with dlopen/dlclose anthonyw 1168 [thread] tss crashes randomly anthonyw 1268 xtime_cmp changes to deal with overflow were reverted anthonyw 1470 Boost.Thread: Compilation errors with non-__cdecl calling convention anthonyw 1547 [thread] error C2065: 'NULL' : undeclared identifier in thread_primitives.hpp anthonyw 876 xtime documentation incomplete anthonyw 881 errors when build with Apache stdcxx az_sw_dude 1028 typo in boost header: date_time/time_defs.hpp az_sw_dude 1078 from_iso_string cannot read the output from to_iso_string az_sw_dude 1098 Urgent libboost-date-time1.33.1 : bugs on ia64 ? az_sw_dude 1147 date_time library contains global #define ERROR az_sw_dude 1160 warning: month_format shadows a member of this az_sw_dude 1162 warning: ticks shadows a member of this az_sw_dude 1289 posix_time::time_facet forgets to pass a_ref argument to base class az_sw_dude 1299 change in typedef stringstream_type in format_date_parser.hpp causing compilation error az_sw_dude 1306 invalid docbook in date_period.xml az_sw_dude 1384 Linking problem with date_time library on Visual C++ 2008 Express az_sw_dude 1386 date_time documentation Jamfile breaks building of boost docs az_sw_dude 1524 format_date_parser.hpp(221) : cannot convert parameter 1 az_sw_dude 287 wrong usage of ios_base::narrow az_sw_dude 316 date_time type conversion warning az_sw_dude 604 from_ftime incorrectly processes FILETIME filled with zeros az_sw_dude 642 operator<< for gregorian::date_duration not found az_sw_dude 889 Insane Dependencies az_sw_dude 890 date_time library supports only the current dst rule bemandawes 1378 filesystem path invalid name for hidden files (LINUX) bemandawes 1389 filesystem::ostream << boost::format generates operator ambigious error (in MSVC++) bemandawes 1458 Darwin Tiger throws std::runtime_error: locale::facet::_S_create_c_locale name not valid bemandawes 752 directory_iterator doesn't work with catch burbelgruff 1503 typeof bug (big integral constant) danielw 1044 Argument pack inaccessable in a functions return type danielw 1054 Parameter takes an "infinite" amount of time to compile with the Intel compiler. danielw 1097 keyword.hpp generates many warnings C4180: qualifier applied to function type has no meaning; ignored dave 1010 linking boost.python on freebsd dave 1019 iterator_facade::pointer should be the return type of operator-> (DR 445) dave 1085 Python rules for compiling in Mac OS X dave 1179 [boost.python] can not export a union in VC2005sp1 dave 1181 [boost.python] can modify enum value dave 1387 Review / update docs to reflect changes dave 1460 Python classes with multiple bases are convertible only to the first class in the lists dave 1482 boost::python::throw_error_already_set should be marked noreturn dave 1516 [python] Failing VC9 regression tests dave 865 Use of C++0x keyword as identifier dave 910 gcc strict-aliasing problems with python dgregor 1003 [iostreams] copy-paste error in typedefs for wchar multichar_filters dgregor 1139 [iostreams] Regex filter segfaults when zero matches found dgregor 1140 boost::iostreams linked_streambuf bug dgregor 1149 Minor doc error in basic_null_device dgregor 1164 Floyd Warshall broken with unsigned edge weights dgregor 1185 iostreams::direct_streambuf<T_Tr>::is_open always returns false if output iterator is not null dgregor 1192 [boostbook] problem when two files have the same name dgregor 1199 configure doesn't work with path containing whitespaces (MacOS X) dgregor 1232 mapped_file_source::is_open() is broken under windows dgregor 1310 [result_of] const-qualified function pointer doesn't work dgregor 1326 Unable to check graph isomorphism using LEDA adapter dgregor 1391 dominator_tree_test on Borland/CodeGear outputs overly long line dgregor 1394 Translate libs/graph/build/python/Jamfile to BBv2 dgregor 1395 Write Tests for Python Bindings dgregor 556 Bundled graph properties dgregor 732 Johnson All-Pairs needs better "no path" information dgregor 736 Const correctness violation djowel 1170 Emit Warnings instead of # symbols in the syntax highlighter djowel 1171 Quickbook title output djowel 1172 non-utf djowel 1176 Space after inline code djowel 1206 Escaping from within code? djowel 1273 CR+LF newlines in position_iterator djowel 1276 spirit problem with _GLIBCXX_DEBUG djowel 1277 Closing section like [pre with } causes Quickbok to crash djowel 1280 sections in imported source files get put inside <para> elements in docbook output djowel 1281 Quickbook produces invalid BoostBook/DocBook XML djowel 1324 tuple should have a swap() that operates element-by-element djowel 1396 wrong result_of invocation around transform_view djowel 1436 [quickbook] inline code inside headings djowel 1484 Quickbook produces illegal docbook for some docinfo fields. djowel 1500 [Spirit/Phoenix] C4512 Compiler warnings from VC8 dlwalker 613 boost/crc.hpp uses non-standard conforming syntax doug_gregor 1021 [Graph][reverse_graph] Problem using reverse_graph adapter with an adapted user defined graph doug_gregor 1076 compile error: disconnecting struct with operator()() doesn't work in VS2005 SP1 doug_gregor 375 LEDA graph adaptors do not handle hidden nodes properly doug_gregor 402 random_vertex/random_edge are unnecessarily inefficient doug_gregor 403 Document copy_component doug_gregor 447 reverse_graph and constness of property maps doug_gregor 708 Dijkstra no_init version should not require VertexListGraph doug_gregor 733 Numbered headers don't work with "preferred" syntax doug_gregor 735 Fruchterman-Reingold grid performance can be improved doug_gregor 738 Memory leaks with signal::connect? doug_gregor 829 Implicit graph not implement doug_gregor 852 Problem with Boost and GCC 4.1 ebf 1507 [variant] C4512 warnings from VC8.0 ebf 965 [doc] boost::variant tutorial - final example uses v1_v2 should be seq1_seq2 ebf 993 Variant should use least common multiple of alignments_ rather than maximum grafik 1041 Cygwin requires PATH setting. grafik 1062 Cygwin install stage fails with combination of patches grafik 1322 trac rejects patch attachment as spam grafik 1417 Regresson tests hang in Darwin (Tiger) grafik 1430 Regression fails under Cygwin grafik 1433 Trac's spam detection rejects too many valid messages grafik 1512 Broken link to vacpp in bjam docs. grafik 1513 Broken link to bcpp in bjam docs. grafik 616 Boost Jam_ and non english directorys grafik 959 linking fails when Boost is compiled with STLport 5.1.* on Linux (names mismatch) grafik 986 Problem building Python modules on boost 1.34.0 hkaiser 1079 boost-1.34.0 fails to compile. concept checks not satisfied. hljin 1522 bit_range friend decl in bit_aligned_pixel_reference.hpp needs to be fully qualified for gcc 4.3 mainline igaztanaga 1080 boost::interprocess win32 global file mapping issue igaztanaga 1210 interprocess::barrier hangs during second use under linux (boost 1.33.1) igaztanaga 1390 Interpocess: managed shared memory failing completely under OS X jmaurer 351 Diff in state of mersenne_twister gen between GCC3.41 & CW9 jmaurer 599 uniform_01 copies engine instead of using a reference jmaurer 819 uniform_int<> with type's maximum availaible range error johnmaddock 1081 Empty string rejected as perl-style regex johnmaddock 1314 Using SSE-intrinsics in VC8 causes static assert in type_with_alignment.hpp johnmaddock 1411 Fix BOOST_PARTIAL_SPECIALIZATION_EXPLICT_ARGS johnmaddock 1440 libs/config/test/link/Jamfile.v2 confuses process_jam_log johnmaddock 1446 POSIX API doesn't use C locale johnmaddock 1451 error: use of C99 long long integer constant johnmaddock 1511 Non latin symbols in regexp jsiek 1531 segfault in dynamic_bitset::reference assign operator jsiek 1540 Poisson distribution very slow for large mean (and may also overflow). jsiek 416 Spelling of Edmonds-Karp-Algorithm jsiek 575 Calling subgraph::global_to_local on a root graph jsiek 636 strange compiling problem for transitive_closure jsiek 815 remove_edge core dumps on self-circle jsiek 875 No iterator based constructor for adjacency_matrix jsiek 900 graphml reader namespace handling is broken kaalus 1184 property_tree assignment (operator) bug marshall 1252 [pool] severe overhead with unaligned sizes. matias 1406 Understanding the Tables outdated matias 1539 Missing semi-colon in random library quitck start example nasonov 1220 lexical_cast requires RTTI nasonov 754 boost::any - typeid comparison across shared boundaries nesotto 1284 [range] sub_range assignment issue nesotto 1464 boost_range_array unused in several array_size() functions niels_dekker 1459 value_initialized leaves data uninitialized_ when using Borland niels_dekker 1491 value_initialized leaves data uninitialized_ when using GCC pavol_droba 1152 rle_example fails pavol_droba 1385 begin must be boost-qualified pdimov 1106 shared_ptr<T> should not convert to shared_ptr<U> when T* doesn't convert to U* pdimov 1444 scoped_ptr::operator== should be equivalent to a.get()==b.get()_ but is currently !!a==!!b pdimov 779 gcc-4.2 atomicity.h location ramey 1121 xml_archive_exception is missing seperate header file_ and documentation mismatch rogeeff 1383 signal.h features not found on Mac OS rogeeff 1489 BOOST_CHECK_CLOSE fails to compile with templated value type rogeeff 1542 [test] compiler errors when building with stdcxx library samuel_krempp 859 boost::format ignores a user defined locale shammah 386 boost::pool_allocator breaks with vector of vectors speedsnail 1138 Problems with TSS and static thread library t_schwinger 1100 Building boost.function_types fails cvs rev-1.1_ no chdir command in bash turkanis 1523 [iostreams] VC8/VC9 compiler warnings turkanis 1545 [boost/rational.hpp] 'noskipws' is not a member of 'std' urzuga 574 [boost::lambda] Compile error with libstdc++ debug mode urzuga 781 Lambda: (_1 + "y")(string("x")) Doesn't Compile vladimir_prus 1165 more quoting problems vladimir_prus 1274 Useless error message vladimir_prus 1321 invalid docbook in tool documentation vladimir_prus 1527 [program_options] Second (and subsequent) lines in tabbed text not aligned correctly vladimir_prus 1530 Program options documentation - Overview - Syntactic Information example typo vladimir_prus 1537 no value given in 'mysql_password =' vladimir_prus 469 multitoken broken vladimir_prus 689 [program_options] Endless loop with long default arguments witt 1046 Boost.Python quickstart instructions mention nonexistent target witt 583 Fixes for build on IBM pSeries for AIX and Linux witt 834 Homepage regression links witt 957 The "Getting Started" page does not mention the stdlib option witt 973 zip_iterator has value_type == reference -- -- Marshall Marshall Clow Qualcomm, Inc. <mailto:mclow@qualcomm.com> The famous British scientist, Lord Kelvin, said: "When you measure what you are speaking about and express it in numbers, you know something about it, but when you cannot (or do not) measure it, when you cannot (or do not) express it in numbers, then your knowledge is of a meagre and unsatisfactory kind."

1 0

Re: [boost] [Boost-users] upcoming Switch library review Jan 5th - Jan 9th
by Stjepan Rajko 03 Jan '08

03 Jan '08

On Jan 2, 2008 2:36 PM, dan marsden <danmarsden(a)yahoo.co.uk> wrote: > Stjepan Rajko wrote: > > If you are interested, please consider submitting a review of this > > library. I will send more detailed instructions on what to include in > > the review on the 5th. > > Can I jump the gun with with a few questions please? Of course - thanks for opening up the discussion! I'm just not sure whether Steven will be able to respond until the review officially starts. > > Why is the fall through behaviour to throw an exception? This is > not consistent with standard switch, possibly a motivation section is > needed in the docs to explain this type of decision? > > I'm not too clear with the documentation what the parameter 'n' can > be? It is of type 'Int' which is described as being an Integer in the > parameters section of the documentation. What does this mean, any > built in integral type, can I switch on a std::string? What are the > limitations? I got a bit lost here in the docs here, after admittedly only > a quick read. Maybe just some clarification is required? > > The parameter section does not specify the arities of the 2 function > object parameters, I had to deduce them from the example. Why do > these have to be function objects, and not just any callable type, > including ordinary functions (using the Boost.ResultOf mechanism to > sort out the return type)? I'm not sure how useful that would be for 'f', > but for 'default_' a full blow function object seems a bit much typing, > can't I just use a function. > > Also, why is 'default_' unary, the default in a standard switch > statement does not access the switch parameter, and the example > does not exploit this feature either. Why not just a nullary function? > Again some motivation might be nice. > > And finally, as the introduction mentions the efficiency of the standard > switch statement, could the docs show some performance stats for the > library code for comparison? > > Cheers > > Dan > Stjepan

1 0

optimization of boost::end
by Neal Becker 03 Jan '08

03 Jan '08

The common idiom is: for (; i != boost::end (vector); ++i) ... The compiler had damn well better realize that boost::end is a constant function that can be lifted from the loop, or performance can be severely impacted. Does anyone have any experience with this? Is there a portable way to give hints to the compiler? Should boost provide such a facility?

3 3

[review][unordered] Review summary
by Ion Gaztañaga 03 Jan '08

03 Jan '08

Hi to all, This post tries to summarize the review of the new Boost.Unordered library. In general, there were no serious implementation change requests and most reviewers had only documentation issues. Here we go: * * * begin of summary * * * Thosten Ottosen's review: ---------------------- (http://lists.boost.org/Archives/boost/2007/12/131372.php) Thorsten questioned about the convenience of supporting throwing hash or predicates. This started a thread about the exception safety guarantees of STL containers and Daniel explained the thread-safety guarantees of Unordered. Basically, Daniel's implementation uses an smart double-buffering technique to obtain strong safety guarantees (stricter than the requirements of the standard) in some operations. There's an slight size overhead (the container must allocate space for two equality functors and hashers) but according to Daniel, speed should not suffer. Chung Ping Wang's review: ---------------------- (http://lists.boost.org/Archives/boost/2007/12/131372.php) The only complain was the packaging of the library (there was an "unordered" directory at the top). Since the library has been accepted it will be packaged as the rest of Boost libraries so the problem disappears. Mathias Gaunard's comment: ---------------------- (http://lists.boost.org/Archives/boost/2007/12/131426.php) Mathias suggested adding move semantics and in-place construction. Daniel said that these features were likely to be added in the future. He pointed that we have no standard move emulation library in Boost so we'll need to push that first. Regarding in-place construction, there is a problem with allocators, since containers are now required to call allocator::construct() to construct values. Hervé Brönnimann's review: ---------------------- (http://lists.boost.org/Archives/boost/2007/12/131435.php) Hervé praised the library and suggested adding operator==(). Daniel replied that he was trying to limit himself to obvious design decisions for extensions so he didn't want to go into this area. He also cited some problems with non-unique key unordered containers. Hervé suggested extending the prime number list and Daniel agreed. Daniel also agreed to correct some documentation issues. "Swap" semantics wrt allocators was also discussed. "Swap" and its effect on containers is an active issue in the committee, so Daniel is free to implement what he thinks best until we have a firm resolution. John Torjo's review: ---------------------- (http://lists.boost.org/Archives/boost/2007/12/131557.php) A concise and positive review with no comments. Jamie Allsop's review: ---------------------- (http://lists.boost.org/Archives/boost/2007/12/131762.php) Documentation suggestions that Daniel found interesting and a request to include a comparison with other implementations. Steven Watanabe's comments ---------------------- (http://lists.boost.org/Archives/boost/2007/12/131817.php) Several implementation comments regarding (ADL, BOOST_DEDUCED_TYPENAME, warnings...). See the post for details. Cromwell Enage's review ---------------------- (http://lists.boost.org/boost-users/2007/12/32706.php) Suggested the addition of local_cbegin() and similar, and some documentation suggestions Daniel agreed to solve. Paul A Bristow's review ---------------------- (http://lists.boost.org/Archives/boost/2007/12/131545.php) A brief and positive review with no comments. * * * end of summary * * * Regards, Ion

3 2

Old Lambda support request....
by Marshall Clow 03 Jan '08

03 Jan '08

Three years old - looks like an easy answer. <http://svn.boost.org/trac/boost/ticket/426> Anyone? Anyone? Bueller? Thanks. -- -- Marshall Marshall Clow Idio Software <mailto:marshall@idio.com> It is by caffeine alone I set my mind in motion. It is by the beans of Java that thoughts acquire speed, the hands acquire shaking, the shaking becomes a warning. It is by caffeine alone I set my mind in motion.

4 3

[Accumulators] is there an updated version?
by Jamie Allsop 03 Jan '08

03 Jan '08

I recently had a need for some simple statistical analysis of performance data and thought rather than sit down and write my own functions for mean, variance etc. I'd take the time to learn and use the Accumulators library that was accepted into boost on February the 19th of this year, <http://lists.boost.org/boost-announce/2007/02/0114.php> The only version I could find was that in the vault, <http://www.boost-consulting.com/vault/index.php?action=downloadfile&filenam…> This appears to have been updated last on 21.09.2007 03:32. The first thing I am wondering is why this library is not in TRUNK now that it is a part of boost? Secondly I thought I'd comment briefly on something that I noticed came up during review but has (as yet) not been addressed in the vault version. I too assumed that using boost::accumulators::tag::variance would return a useful value for variance, unfortunately it returned (in my case) what appeared to be an erroneous negative value. The 'immediate_' form worked ok. My comment would be that after reading the review there was some debate about providing a naive implementation. My thought after spending time reading the reviews and browsing the code to try to figure out what was happening was that, if I wanted a naive implementation, I could provide that easily myself. However I turned to the library to a) save me writing and maintaining the code, and b) to enjoy a well thought out implementation by a domain knowledgeable implementor. I therefore think that the natural choices should be accurate implementations. If I know enough about my data to realise I can get away with a naive implementation that sacrifices accuracy (perhaps for performance reasons) then I can select one purposefully. My first experience with the accumulators library was a mixed bag, but I have not used it enough to really form too many opinions on it. I suppose when I initially looked at it I thought I would have access to statistical algorithms that I could apply to my data, but in fact it works differently than that (and I am sure there was a good reason for that approach). I'll have to revisit the doc to see if I can find understand the motivation better. It works well as it is mind you. Beyond that the library appears useful and I look forward to making more use of it. I'd be very interested in seeing a newer version of the library that addresses the many points highlighted during the review or at least know that the library is currently being tidied up and will make into a boost release soon :) Thanks, Jamie

2 4

Trac support request #597
by Marshall Clow 03 Jan '08

03 Jan '08

<http://svn.boost.org/trac/boost/ticket/597> Non-basic-source-character-set characters conflict with MSVC There exist high-ascii characters in the Boost sources that cannot be converted to the local region for a given computer because the context of the originating region of the source is not known. Thus, these high-ascii characters may not have a proper mapping, and a warning will be emitted by MSVC 2003 and 2005. This should be considered a failure case because, though low, it is still emitting an alert. Thus, without the correct region set on your system, the Boost sources fail to build. I believe all the characters referenced are in comments. Is this worth fixing? Does anyone care? It appears that 90% of problem is the copyright symbol. A quick grep of the boost header files shows about 34 instances of '©', changing them to '(c)' would be easy. The rest of the problem are in author's names, for example see Jaako's name in <boost/utility/enable_if.hpp". My recommendation is to close this as "wont fix". -- -- Marshall Marshall Clow Idio Software <mailto:marshall@idio.com> It is by caffeine alone I set my mind in motion. It is by the beans of Java that thoughts acquire speed, the hands acquire shaking, the shaking becomes a warning. It is by caffeine alone I set my mind in motion.

3 2

Performance of various mutex implementations on Linux
by Phil Endecott 02 Jan '08

02 Jan '08

Dear All, I have been benchmarking different mutex implementations on Linux. The variations that I have considered are the following: NO_LOCKING: - no mutex at all, as a baseline for comparison. SPINLOCK - uses an atomic operation and a tight loop. YIELD - uses an atomic operation like SPINLOCK, and calls sched_yield() if the lock is held by another thread. PTHREADS - uses the pthread_mutex_*() functions; this is what the current Boost mutexes do (as I understand it). The pthread_mutex functions are implemented using the futex() system call. FUTEX - this is my own implementation of the same algorithm that PTHREADS uses internally, based on the futex() system call, but it uses inlining to avoid a function call in the un-contended case. Apart from the PTHREADS method, these should all be considered unproven code; if anyone would like to review them for any subtle concurrency issues or other problems you are very welcome to do so. For background details of futexes, I suggest Ullrich Drepper's paper "Futexes Are Tricky". All of these results were obtained with g++ 4.1.2 with -O3. Data Structure Sizes -------------------- The size of the mutex object, in bytes, is as follows: NO_LOCKING: 0 SPINLOCK: 4 [*] YIELD: 4 [*] FUTEX: 4 [*] PTHREADS: 24 [*] in all of these cases I believe that a single byte, or perhaps even a single bit in the case of SPINLOCK and YIELD, would be sufficient; there may be some obscure alignment issue though. I believe that the large size of the pthreads mutex object is because it supports a number of variants such as recursive and checking mutexes, and timeouts, etc. all in the same structure. My other implementations are all very basic with none of these features. Execution Time, Non-Contended Case ---------------------------------- In many uses mutexes are rarely contended, so optimising the speed of the uncontended locking and unlocking operations is a common objective. I have measured this overhead on three machines: egypt: 1GHz VIA C3 x86 uniprocessor linux-2.6.19 ghana: 266MHz Intel XScale ARM uniprocessor linux-2.6.19 atum: 3.6GHz Intel Pentium 4 x86 2 processor linux-2.6.17 The times in nanoseconds for one lock and one unlock are: egypt ghana atum NO_LOCKING 0 0 0 SPINLOCK 17 30 5.7 YIELD 13 38 6.4 FUTEX 50 95 26 PTHREADS 115 986 39 Execution Time, Contended Case ------------------------------ See my detailed results, linked below, for numbers (the runtimes given are for 10^8 operations). The execution time in the contended case includes both the execution time of the lock and unlock functions and the time spent waiting for the lock to become available; it's not straightforward to distinguish these and I haven't tried to. The broad pattern is that SPINLOCK, naturally, is very slow, and the other methods are relatively fast. In my benchmark, YIELD does better than FUTEX, but this may well be a feature of the structure of my benchmark; I would expect FUTEX to do better with large numbers of threads. PTHREADS gets worse more quickly than other other methods as the number of mutexes and threads increases, perhaps because the larger size of its structures is less cache-friendly. Code Size --------- The code size overhead in bytes for each method is as follows. (Note that this is with -O3, not -Os. My impression with -Os is that it does even less inlining that I expected, e.g. even a static function that's only called once is not inlined. I may investigate this further.) x86 ARM NO_LOCKING 0 0 SPINLOCK 42 32 YIELD 31 56 FUTEX 66 96 PTHREADS 25 28 Observations ------------ I suggest that we seriously consider using an inline futex implementation of mutexes as the default choice on Linux, rather than calling the pthread_mutex functions. This is about twice as fast (on x86) and saves a lot of data size. On the other hand, it increases code size. The code size and speed can be improved further by using a simpler method that just calls sched_yield(). However, this method is less suitable for use as a default implementation because it will have worse complexity in applications with contention: futex() knows which thread to wake up next, while sched_yield() doesn't. ARM Observations ---------------- Most ARM processors have only one atomic instruction, swap. My implementations of SPINLOCK, YIELD and FUTEX make use of this. PTHREADS has abysmal performance on ARM; I suspect, but have not yet checked, that it somehow emulates the atomic instructions that it doesn't have by calling into the kernel. You can find all of the mutex implementation and benchmarking scripts and the full results here: https://svn.chezphil.org/mutex_perf/trunk/ I hope this is of interest. Regards, Phil.

4 4