- Boost - lists.boost.org

Patches report
by Marshall Clow 19 Mar '07

19 Mar '07

[ Unchanged from last Friday ] Patch count: 18 3 vladimir_prus 2 rogeeff 2 agurtovoy 1 turkanis 1 shammah 1 ramey 1 pdimov 1 jsiek 1 johnmaddock 1 grafik 1 dlwalker 1 az_sw_dude 1 anthonyw 1 alnsn Assignee: agurtovoy <http://sourceforge.net/users/agurtovoy/> Summary: Adjusts mpl::pair concept to be compatible with STL pairs Bug #: 1489713 <http://sourceforge.net/tracker/index.php?func=detail&aid=1489713&group_id=7…> Assignee: agurtovoy <http://sourceforge.net/users/agurtovoy/> Summary: [mpl] evc4 port Bug #: 1583396 <http://sourceforge.net/tracker/index.php?func=detail&aid=1583396&group_id=7…> Assignee: alnsn <http://sourceforge.net/users/alnsn/> Summary: lexical_cast - local variable shadow patch Bug #: 1665462 <http://sourceforge.net/tracker/index.php?func=detail&aid=1665462&group_id=7…> Assignee: anthonyw <http://sourceforge.net/users/anthonyw/> Summary: [thread] MSVS: Allow use of thread headers with /Za Bug #: 1627420 <http://sourceforge.net/tracker/index.php?func=detail&aid=1627420&group_id=7…> Assignee: az_sw_dude <http://sourceforge.net/users/az_sw_dude/> Summary: Unused variable in format date parser Bug #: 1652860 <http://sourceforge.net/tracker/index.php?func=detail&aid=1652860&group_id=7…> Assignee: dlwalker <http://sourceforge.net/users/dlwalker/> Summary: [integer] add support for integers longer than long Bug #: 1507034 <http://sourceforge.net/tracker/index.php?func=detail&aid=1507034&group_id=7…> Assignee: grafik <http://sourceforge.net/users/grafik/> Summary: bjam: always define OSPLAT Bug #: 1619769 <http://sourceforge.net/tracker/index.php?func=detail&aid=1619769&group_id=7…> Assignee: johnmaddock <http://sourceforge.net/users/johnmaddock/> Summary: [config] evc4 port Bug #: 1489359 <http://sourceforge.net/tracker/index.php?func=detail&aid=1489359&group_id=7…> Assignee: jsiek <http://sourceforge.net/users/jsiek/> Summary: [concept_check.hpp] remove unused variable warning in msvc Bug #: 1388901 <http://sourceforge.net/tracker/index.php?func=detail&aid=1388901&group_id=7…> Assignee: pdimov <http://sourceforge.net/users/pdimov/> Summary: support for weak_ptr binding Bug #: 1633503 <http://sourceforge.net/tracker/index.php?func=detail&aid=1633503&group_id=7…> Assignee: ramey <http://sourceforge.net/users/ramey/> Summary: [archive] codecvt_null.hpp won't compile on QNX Bug #: 1636855 <http://sourceforge.net/tracker/index.php?func=detail&aid=1636855&group_id=7…> Assignee: rogeeff <http://sourceforge.net/users/rogeeff/> Summary: [test] no eh exception handling functions on evc4 Bug #: 1499418 <http://sourceforge.net/tracker/index.php?func=detail&aid=1499418&group_id=7…> Assignee: rogeeff <http://sourceforge.net/users/rogeeff/> Summary: [test] evc4 issue with SEH support Bug #: 1583399 <http://sourceforge.net/tracker/index.php?func=detail&aid=1583399&group_id=7…> Assignee: shammah <http://sourceforge.net/users/shammah/> Summary: pool allocator - local variable shadow patch Bug #: 1665468 <http://sourceforge.net/tracker/index.php?func=detail&aid=1665468&group_id=7…> Assignee: turkanis <http://sourceforge.net/users/turkanis/> Summary: iostreams // file_descriptor::seek BUG on files > 4 GB Bug #: 1452698 <http://sourceforge.net/tracker/index.php?func=detail&aid=1452698&group_id=7…> Assignee: vladimir_prus <http://sourceforge.net/users/vladimir_prus/> Summary: [program_options] static const variable on evc4 Bug #: 1499420 <http://sourceforge.net/tracker/index.php?func=detail&aid=1499420&group_id=7…> Assignee: vladimir_prus <http://sourceforge.net/users/vladimir_prus/> Summary: [program_options] putenv on Solaris Bug #: 1568191 <http://sourceforge.net/tracker/index.php?func=detail&aid=1568191&group_id=7…> Assignee: vladimir_prus <http://sourceforge.net/users/vladimir_prus/> Summary: VC80-Compatible String Processing in format_paragraph() Bug #: 1580068 <http://sourceforge.net/tracker/index.php?func=detail&aid=1580068&group_id=7…> -- -- 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.

1 0

Support requests report
by Marshall Clow 19 Mar '07

19 Mar '07

[ Down from 39 on Wednesday ] Support count: 38 9 grafik 6 vladimir_prus 4 johnmaddock 3 jsiek 3 jbandela 2 turkanis 2 rogeeff 2 az_sw_dude 1 urzuga 1 shammah 1 samuel_k 1 nobody 1 fcacciola 1 djowel 1 agurtovoy Assignee: agurtovoy <http://sourceforge.net/users/agurtovoy/> Summary: duplicat initial members -> erase_key postcond. fail Bug #: 1642614 <http://sourceforge.net/tracker/index.php?func=detail&aid=1642614&group_id=7…> Assignee: az_sw_dude <http://sourceforge.net/users/az_sw_dude/> Summary: support new 2007 DST rules for timezone db Bug #: 1471723 <http://sourceforge.net/tracker/index.php?func=detail&aid=1471723&group_id=7…> Assignee: az_sw_dude <http://sourceforge.net/users/az_sw_dude/> Summary: new timezone db file for #1471723 - 2007 DST support Bug #: 1478619 <http://sourceforge.net/tracker/index.php?func=detail&aid=1478619&group_id=7…> Assignee: djowel <http://sourceforge.net/users/djowel/> Summary: Embedded python won't compile Bug #: 1391956 <http://sourceforge.net/tracker/index.php?func=detail&aid=1391956&group_id=7…> Assignee: fcacciola <http://sourceforge.net/users/fcacciola/> Summary: boost::optional<enum> fails with /CLR Bug #: 973424 <http://sourceforge.net/tracker/index.php?func=detail&aid=973424&group_id=75…> Assignee: grafik <http://sourceforge.net/users/grafik/> Summary: Jam Fails to Build Bug #: 954048 <http://sourceforge.net/tracker/index.php?func=detail&aid=954048&group_id=75…> Assignee: grafik <http://sourceforge.net/users/grafik/> Summary: Boost on opteron AMD Bug #: 1200700 <http://sourceforge.net/tracker/index.php?func=detail&aid=1200700&group_id=7…> Assignee: grafik <http://sourceforge.net/users/grafik/> Summary: Linker Problems with VC .NET 2003 / STLPort / Boost Bug #: 1292345 <http://sourceforge.net/tracker/index.php?func=detail&aid=1292345&group_id=7…> Assignee: grafik <http://sourceforge.net/users/grafik/> Summary: Unable to build boost with Dinkumware STL version 4.02 Bug #: 1336312 <http://sourceforge.net/tracker/index.php?func=detail&aid=1336312&group_id=7…> Assignee: grafik <http://sourceforge.net/users/grafik/> Summary: Compiling only needed version Bug #: 1377001 <http://sourceforge.net/tracker/index.php?func=detail&aid=1377001&group_id=7…> Assignee: grafik <http://sourceforge.net/users/grafik/> Summary: Building universal binary on MacOSX Bug #: 1409774 <http://sourceforge.net/tracker/index.php?func=detail&aid=1409774&group_id=7…> Assignee: grafik <http://sourceforge.net/users/grafik/> Summary: Cross compiling boost for Windows CE (ARM) from VS2005 Bug #: 1457763 <http://sourceforge.net/tracker/index.php?func=detail&aid=1457763&group_id=7…> Assignee: grafik <http://sourceforge.net/users/grafik/> Summary: libraries won't build Bug #: 1524001 <http://sourceforge.net/tracker/index.php?func=detail&aid=1524001&group_id=7…> Assignee: grafik <http://sourceforge.net/users/grafik/> Summary: Having some trouble building boost Bug #: 1534701 <http://sourceforge.net/tracker/index.php?func=detail&aid=1534701&group_id=7…> Assignee: jbandela <http://sourceforge.net/users/jbandela/> Summary: Problem compiling :/ Bug #: 942349 <http://sourceforge.net/tracker/index.php?func=detail&aid=942349&group_id=75…> Assignee: jbandela <http://sourceforge.net/users/jbandela/> Summary: SLOOOWW tokenizer compilation on VC++6.0 Bug #: 969590 <http://sourceforge.net/tracker/index.php?func=detail&aid=969590&group_id=75…> Assignee: jbandela <http://sourceforge.net/users/jbandela/> Summary: Visual C++ 'Language Extensions' support Bug #: 1039338 <http://sourceforge.net/tracker/index.php?func=detail&aid=1039338&group_id=7…> Assignee: johnmaddock <http://sourceforge.net/users/johnmaddock/> Summary: Regex Bug #: 1156957 <http://sourceforge.net/tracker/index.php?func=detail&aid=1156957&group_id=7…> Assignee: johnmaddock <http://sourceforge.net/users/johnmaddock/> Summary: Problem running configure for unsupported platform Bug #: 1339778 <http://sourceforge.net/tracker/index.php?func=detail&aid=1339778&group_id=7…> Assignee: johnmaddock <http://sourceforge.net/users/johnmaddock/> Summary: regex - perl syntax affects what gets matched Bug #: 1519824 <http://sourceforge.net/tracker/index.php?func=detail&aid=1519824&group_id=7…> Assignee: johnmaddock <http://sourceforge.net/users/johnmaddock/> Summary: Crash on RH machine with gcc < 3.4 Bug #: 1635211 <http://sourceforge.net/tracker/index.php?func=detail&aid=1635211&group_id=7…> Assignee: jsiek <http://sourceforge.net/users/jsiek/> Summary: Boost with Dinkumware C++ Library !? Bug #: 531963 <http://sourceforge.net/tracker/index.php?func=detail&aid=531963&group_id=75…> Assignee: jsiek <http://sourceforge.net/users/jsiek/> Summary: creating my own properties Bug #: 619615 <http://sourceforge.net/tracker/index.php?func=detail&aid=619615&group_id=75…> Assignee: jsiek <http://sourceforge.net/users/jsiek/> Summary: Max Flow Algorithm Bug #: 1445526 <http://sourceforge.net/tracker/index.php?func=detail&aid=1445526&group_id=7…> Assignee: nobody Summary: Building Boost with Open Watcom Compiler Bug #: 1547257 <http://sourceforge.net/tracker/index.php?func=detail&aid=1547257&group_id=7…> Assignee: rogeeff <http://sourceforge.net/users/rogeeff/> Summary: failing on 6 targets in MacOS X Bug #: 1572712 <http://sourceforge.net/tracker/index.php?func=detail&aid=1572712&group_id=7…> Assignee: rogeeff <http://sourceforge.net/users/rogeeff/> Summary: [Test Library] How to init/free a singleton Bug #: 1670855 <http://sourceforge.net/tracker/index.php?func=detail&aid=1670855&group_id=7…> Assignee: samuel_k <http://sourceforge.net/users/samuel_k/> Summary: Boost.Format doesn't work on MSVC with /vd2 compiler option Bug #: 1545133 <http://sourceforge.net/tracker/index.php?func=detail&aid=1545133&group_id=7…> Assignee: shammah <http://sourceforge.net/users/shammah/> Summary: warning using pool.hpp Bug #: 1663127 <http://sourceforge.net/tracker/index.php?func=detail&aid=1663127&group_id=7…> Assignee: turkanis <http://sourceforge.net/users/turkanis/> Summary: Boost.Iostreams and newline translation Bug #: 1299123 <http://sourceforge.net/tracker/index.php?func=detail&aid=1299123&group_id=7…> Assignee: turkanis <http://sourceforge.net/users/turkanis/> Summary: boost.iostreams file_descriptor and sharing Bug #: 1445474 <http://sourceforge.net/tracker/index.php?func=detail&aid=1445474&group_id=7…> Assignee: urzuga <http://sourceforge.net/users/urzuga/> Summary: lambda vs pure virtual functions Bug #: 1231445 <http://sourceforge.net/tracker/index.php?func=detail&aid=1231445&group_id=7…> Assignee: vladimir_prus <http://sourceforge.net/users/vladimir_prus/> Summary: program_options Can one have options with optional values? Bug #: 1102652 <http://sourceforge.net/tracker/index.php?func=detail&aid=1102652&group_id=7…> Assignee: vladimir_prus <http://sourceforge.net/users/vladimir_prus/> Summary: program_options Can one have options with optional values? Bug #: 1102664 <http://sourceforge.net/tracker/index.php?func=detail&aid=1102664&group_id=7…> Assignee: vladimir_prus <http://sourceforge.net/users/vladimir_prus/> Summary: program_options bug? Bug #: 1114084 <http://sourceforge.net/tracker/index.php?func=detail&aid=1114084&group_id=7…> Assignee: vladimir_prus <http://sourceforge.net/users/vladimir_prus/> Summary: Boost.Build v2 build script help for evc4 Bug #: 1498919 <http://sourceforge.net/tracker/index.php?func=detail&aid=1498919&group_id=7…> Assignee: vladimir_prus <http://sourceforge.net/users/vladimir_prus/> Summary: Bjam build should support attachment of individual build ids Bug #: 1530168 <http://sourceforge.net/tracker/index.php?func=detail&aid=1530168&group_id=7…> Assignee: vladimir_prus <http://sourceforge.net/users/vladimir_prus/> Summary: program_options strips off escaped quotes in some situations Bug #: 1677601 <http://sourceforge.net/tracker/index.php?func=detail&aid=1677601&group_id=7…> -- -- 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.

1 0

Re: [boost] SQL library with full embedded SQL-syntax
by Lyfar Dmitriy 19 Mar '07

19 Mar '07

Hello, sorry for my long responce. Rene Rivera wrote: > Sure... But we could use that same argument to propose that we write C++ > programs by writing an abstraction on top of C++ compilers in Python so > that we can remove the incompatibilities in the various C++ > implementations. Having had the displeasure of dealing with PL/SQL there > is one serious drawback to the language embedded approach, it ties ones > to the capabilities of the abstraction. May be you right, but I think that that comparison is incorrect, because of as far as I know SQL-standart doesn't include many useful features from various databases, opposite, the C++ standart, which is describes the whole language :) The main goal of the abstract layer for that library is, as Thorsten said, is to provide "portable" SQL for at least a simple queries. There is no goal to emulate features of each db for others at the first time. > Jorge Lodos wrote: > Sorry, I don't see how any of this applies -- just because the SQL is a string > doesn't mean it comes from an untrusted source. And, programmers that don't > validate input from untrusted sources deserve what they get.... I'd like to draw an intermediate conclusions: 1) The SQL library should provide a backdoor so you can still use string queries if you need to be non-portable or cutting egde etc. 2) Embedded SQL commands is type-safe, but strings are flexible and more useful in the 'real world' 3) It's hard to write one big abstract layer for all databases with single functionality and many people doesn't need in it usually. 4) ...? Phil Endecott wrote: > Well, an interface is not much use without some sort of implementation > behind it. Possible implementations for a "generic relational > interface" include an SQL database, on-disk data structures implemented > using something like stxxl, and in-memory data structures made > persistent using serialisation. A measure of a good generic relational > interface could be that it works well with all of these implementations. > > Thinking just about SQL backends, the basic question is whether we want to > > (a) hide the SQL, making the database accesses look more like C++ > function calls and data structures, or > > (b) make the SQL explicit, making the C++ code look more like SQL. > > I definitely vote for (a), and the possibility of moving an application > to something like stxxl is one of my motivations for that. If you interested in such libraries -- take a look at database template library(dtl) also. What do you think about containers overhead? Does the (a) variant means that the parsing of the result of query is something like parsing an Variant type? Is it always opportune? The people who wants to have type-safety of queries and platform independence will select the (b) variant, I hope :) ----- Best Regards, Dmitriy Lyfar

2 1

Re: [boost] Anyone downloaded the sorting library from vault?
by Sam Schetterer 19 Mar '07

19 Mar '07

On March 17, Lewis Hyatt wrote > > Are you sure about the quicksort speed difference? That seems like a huge > > difference. Did you have inlining enabled? Also, the current versions are > > not the final forms. I am implementing random-access iterators and > > user-provided functions. > > Yes, this was on cygwin compiled with g++ -O3. One thing to keep in mind is that > your routines are competing with the standard library, which can be highly > optimized for whatever target platform the compiler was written for. Unless you > have a dramatically improved algorithm, it is unlikely that your sorting > routines will beat std::sort in general, even if they do on some platforms. > > As an example, suppose your goal was to write an equivalent of std::bitset which > beat the standard implementation. It is unlikely that you could exceed the > performance of std::bitset::count(), for instance, because most implementations > use native assembly instructions to do this whenever possible. ( e.g., gcc uses > its built-in popcount function on platforms where it is available.) On the other > hand, if you hand-coded a version with the best algorithm you could find, it > might beat a few poor implementations, but in general it would be inferior. The > only way to make it better in general would be to implement all these > optimizations yourself for each target platform, but at that point, it's just > not worth the time. > > I don't think it's true that std::sort, std::stable_sort, and std::partial_sort > are the end of the story, but I think any work in a sorting library should focus > on needs which are not already met. So far, only radix sort appears to fall in > that category, but you would also need to demonstrate a case in which radix sort > is preferable to std::sort. > > > -lewis Well, one place where radix sort is preferable to std::sort is where you need to "sort within a sort", where you sort by one criteria, then by another. You do this by arranging the criteria so that the most influencial is at the top of a byte sequence, and the least influential is at the bottom of a byte sequence. Then you sort using radixsort and it comes out sorted by criteria #1 and the by criteria #2. You can do the same with radix quicksort but in that case all of the criteria is in a string. That, and radixsort is stable, and faster than std::stable_sort. Finally, radixsort runs in linear time, regardless of the input, so you can sort any data without worrying about whether it is sorted or not, yet nearly as fast or as fast as std::sort.

2 1

Re: [boost] [Boost-users] SQL library with full embedded SQL-syntax
by Jeff Garland 19 Mar '07

19 Mar '07

Dmitri Lyfar wrote: > Hi > I would like to participate in Google Summer of Code in this year. Great, welcome! Note, this discussion would probably be better hosted in the development list, so I've cross-posted it there. > I reviewed boost projects for last years and found an interesting project, I > think. If you go to the link below you will see a short description for that > library: > http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl?Google_Summe… > > The goal of this post is to define the main library features, which will be > useful for users. > Is that library useful for C++ community? > If you are using(or have ever used) similar C++ libraries for work with SQL: > which of features do you want to have? Also I want to notice one of the > biggest beauty of that approach: you can get the compiler to type-check the > SQL-expression, what do you think about that? Well, I'll be brutally honest -- I don't think I would go that direction. We didn't pick a database project last year because a majority of the mentors agreed that the 'dsl-based' approach was more of a toy than reality. The main reason for this is that in 'real-world' applications queries are often dynamic and must be built at run-time. So, before we get ahead of ourselves and think about 'sql embedded in C++' we need the basics of getting database access. At the point the leading candidate for boostification of basic db access is SOCI: http://soci.sourceforge.net/ As I understand the state of affairs, the main barrier to Boost submission is getting the code into the usual boost structure, writing additional tests and such. I"ve cc'ed a couple of principles on SOCI, so they may want to comment on my perception. However, if I'm correct, a great SOC submission may in fact be to Boostify SOCI. It's not as 'sexy' as the embedded SQL, but I, for one would be a big supporter. Jeff

8 18

Interest in std::type_info wrapper and / or multidispatching infrastructure?
by Tom Bachmann 19 Mar '07

19 Mar '07

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hi, I hope it is not considered bad style to propose new functionality in the very first message. I have been using boost for more than a year and I have found it incredibly helpful, and now I'm considering to "give back something". I have to admit, however, that I have experianced boost purely from a user perspective. [Please note that all code examples are more or less pseudo code, solely meant to illustrate my points.] The first thing I'd like to propose is a wrapper around std::type_info. I think it is well known (e.g. alexandrescu calls it TypeInfo), so I wonder if it's just my stupidity not to find it, although there's already something in boost. If not, here's the idea: Sometimes (e.g. when implementing multidispatching), you want to take std::type_info as key in a std::map. However, std::type_info does not implement op<, therefor this is not directly possible. std::type_info::before, on the other hand, does implement ordering. The (one?) basic solution is to use a wrapper around std::type_info that handles the subtleties, it'd look somewhat like: struct type_wrapper { const std::type_info& t; type_wrapper (const std::type_info& t_) : t (t_) { } bool operator< (const type_wrapper& o) const { return t.before (o.t); } // ... } This is a very small and (I think) straightforward construct and should be absolutely portable. It's scope of use might be somewhat limited, because the rtti is usually tried to be avoided, but despite that, I think, type_wrapper would fit pretty nicely into the rest of boost. My other proposal is a bit larger: I wonder if a generic multidispatching infrastructure would be wanted. Due to alexandrescu's book multidispatching was one of the first advanced topics I worked with. Two years ago or so I wrote a static multidispatcher (that is, multidispatching using template-generated if-else chains that use dynamic_cast). Currently I came across the need for multidispatching again, and I wrote a simple dynamic dispatcher. The infrastructure has greatly improved since I wrote the static multidispatcher (or I was not aware of it when I wrote the static one), I think a fairly general dispatching infrastructure can be implemented now. Now to get a bit more specific: The building block of the infrastructure I'm thinking of is a dynamic general dispatcher. That is, a function object that calls other function objects depending on certain properties of it's arguments, e.g. like this: ... dispatcher; dispatcher.add (1, foo); dispatcher.add (3, bar); dispatcher (1, "hello", 3); // foo (1, "hello", 3) dispatcher (2, "hello", 3); // exception Internally, the dispatcher manages a std::map to find the right function object to call. It has to be paremeterized to extract the properties that determine the function object to call: template < ... class Accessor, ... > class dispatcher { private: typedef ... fn_t; typedef typename Accessor::key_t key_t; typedef std::map<key_t, fn_t> map_t; map_t m; public: ... run (<arguments>) { map_t::iterator it = m.find (Accessor::extract_key (<arguments>)); if (it == m.end ()) ... return it -> second (<arguments>); } }; For the example above, Accessor could look like this: struct example_accessor { typedef int key_t; static int extract_key (int k, const std::string&, int) { return k; } }; One problem is passing parameters to dispatcher::run. I think the most sensible way is to make run take a single tuple as argument, and to generate wrappers around it using Boost.Preprocessor. Typical multidispatching (based on argument types) can now be implemented easily, using an accessor like this: struct type_accessor { typedef boost::tuple<type_wrapper, type_wrapper, type_wrapper> key_t; template<class T1, class T2, class T3> static key_t extract_key (const T1& t1, const T2& t2, const T3& t3, int, bool, std::string, ...) { return key_t (typeid (t1), typeid (t2), typeid (t3)); } }; Also, one could imagine some convenience wrappers for typical multidispatching, looking e.g. like: make (spec, obj1, obj2, obj3, obj4).run (a, b, c); // multi_obj is a class generated by the user with // some sort of assistance from the library multi_obj m (obj1, obj2); m.foo (3, a); m.bar ('a', 0, 3); Such a construction would be portable and reusable, and quite useful under some circumstances. I'm not sure if it's in the scope of boost, though. - -- - -ness- -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) iD8DBQFF/AeNvD/ijq9JWhsRAuf0AJ97rcMUvHFL7+6qmhVUfy5R39KxNgCbBBIK ls7cmxTXgulXmzccS60eY8g= =Y+CH -----END PGP SIGNATURE-----

3 3

[sorting] Taking away quicksort and mergesort
by Sam Schetterer 19 Mar '07

19 Mar '07

Would users care if I took quicksort and merge sort out of the library? They are already implemented by the stl.

6 10

[signals] thread_safe_signals release
by Frank Mori Hess 18 Mar '07

18 Mar '07

I've uploaded a tarball with my thread-safe signals implementation to the boost vault, so it is easier for people to try out: http://www.boost-consulting.com/vault/index.php?action=downloadfile&filenam… The tarball also has a modified version of the signals html docs, that should be sufficient for people to figure out what changes have been made to the api. -- Frank

5 8

Re: [boost] [sorting]
by Sam Schetterer 18 Mar '07

18 Mar '07

Herve Bronnimann wrote >Sam: again I'm curious (read: highly skeptical). When you say "much slower" do you base yourself on actual data? >I.e. Have you tried it? The reason I ask is that I don't believe it. Let's talk for concreteness of three levels (name, >number, grade). Any algorithm that does three passes on the data when one will do will be slower (doesn't matter how >complicated your comparison is, if all the name data is distinct the outer sort comparison will conclude quickly). >Radix sort insists on doing all three passes even if all names are distinct. I'm sure data will back me up, if not please >show me the numbers. --Herve Here are some numbers for normal quicksort and radix quicksort on sorting strings - these are from Algorithms in C++ third edition, by Robert Sedgewick. N is the number of words, and these words are from Moby Dick. N standard quicksort three way partitioning quicksort radix quicksort 12500 7 6 6 25000 14 12 11 50000 34 26 25 100000 83 61 54 Now, these results are from single words. here is the general equation for quicksort and radix quicksort on strings Radix quicksort - k + (2N log N), where k is the average number of bytes in each string. Normal quicksort k(2N log N), where k is the average number of bytes in each string. Imagine the speed difference in the sorting algorithms if the strings were first and last names, which commonly reach lengths of 15 or more characters, unlike the words in Moby Dick. Think of how much faster radix quicksort would be. >From the point of view of a user appending bytes onto the end of a string from a native arithmetic type, even if you lose time on the integer bytes, you gain a very large amount of time when you sort the name part of the string.

2 1

[sorting] Advantages of radixsort
by Sam Schetterer 18 Mar '07

18 Mar '07

Many people are questioning the speed of radixsort and radix quicksort. In some cases, those people are right, and radixsorts should not be used. However, speed of the function is not the only thing that makes it attractive. If you have downloaded the radixsort.cpp file from vault, you will find a class with an integer array with 5 integers, a complex operator< function that can be used for std::sort, and an operator[] that can be used for radixsort. The size of the complex operator is pretty large and grows for each integer added to the array. However, the size of operator[] is constant. For an example of how the complex operator< can affect a program, consider the class used in the example program to be a template class, with one template parameter for type and another for size. Not only does it contain the complex operator<, but it has the same functionality as std::vector. Because the size of the class is a template paramters, every different combination of type and size results in a version of that class is created. If that class were to be used in a full sized program, the code bloat would be tremendous. Now, consider another template class, with one paramter for type and another for size. For each size, it creates three of the classes found in the program, each with a different size. Consider that class to be used just as much as std::vector. Think about how much excess code is created just from operator<, not to mention all of the other functions that would realistically be found in a class that had the same functionality as std::vector. However, if the single line operator[] is used, there would still be extra code generated for it, but nowhere near as much as a complex operator<. Even though the std::sort and operator< might be faster that radixsort and operator[], the size of the executable will be noticably smaller if radixsort and operator[] are used.

1 0