- Boost - lists.boost.org

Re: [boost] Taking away quicksort and mergesort
by Sam Schetterer 17 Mar '07

17 Mar '07

On March 17, Herve Bronimamm wrote >Sam: the Stl already implements sorting (stable and not), inplace and partial sorting (uses heapsort), nth_element >(generalized median), functors and iterators (generic interface). As far as I can tell, your library has no added value, >except you claim performance. I think you might badly underestimate the effort that goes into implementing the >C++ std library. The only reason someone would consider using your library over the standard library would be if >you could convincingly and reproducingly show that you are faster (and by more than a small percentage). I haven't >seen numbers. >I looked at your code and I see that you're using unguarded recursion in quicksort (check Valois's introspective sort >revisited, published in software practice and experience, 2000), swap in insertion sort, int instead of ptrdiff_t (you're >going to have a bad surprise sorting 2 billion integers on a 64bit platform), etc. My experiences showed that radix >sort was not faster than quicksort, due to the random access pattern (for large arrays) and overhead of counters (for >small arrays). And I have some doubts about the endianness (did you test on both big and small endian >platforms?). That's a lot of comments. I'll leave it at that. Cheers, Herve Well, Herve, you ask why my radixsort is better than std::sort and std::stable_sort. It is stable, it is faster std::stable_sort, and it's running time is O(kN), where k is the number of bytes in the object. That is linear running time, unlike std::sort, which is O(N log N), and radixsort is independent of the input, unlike std::sort. Finally, you can do something called a "sort within sort" using radix quicksort, which is where you sort by one value, than another. These "sort within sorts" are accomplished by appending all of the bytes of your data onto a string, and these bytes come from other strings, integers, and doubles. You then sort it with radix_quicksort, which is incredibly high speed for strings(much faster than std::sort and std::stable_sort). Also, I have uploaded code for radix_sort where you can spcify starting and ending bytes, which is something that I know that the stl does not implement.

1 0

Re: [boost] SQL library with full embedded SQL-syntax
by Phil Endecott 17 Mar '07

17 Mar '07

>> So if someone is looking for something to do, how about starting with >> containers, iterators and allocators for huge on-disk data structures. Sohail Somani wrote: > Do you mean this: http://stxxl.sourceforge.net/ ? Yes! Thanks for the link. Sebastian Redl wrote: > Aren't you designing a database here instead of a generic relational > interface? 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. Phil.

1 0

Copy editing documentation - SOC project
by Nava Whiteford 17 Mar '07

17 Mar '07

Matthias Schabel <boost(a)schabel-family.org> wrote: > > FYI, QuickBook already has the reverse-lit feature. It lets you > > "import" code snippets from actual code. Rene and I are using it > > right now to great effect. > > I have to say, as a non-CS person, I'm finding it hard to even keep > track of the differences between DocBook, BoostBook, and QuickBook, > much less figure out how to accomplish anything with them... Just as > a side note, given that documentation is already generally regarded as > one of the most painful parts of library development, I think it > would be > a good idea for Boost to standardize on one system or another and > then provide a good tutorial on how to use it... For example, after > browsing all the QuickBook documentation I could find, I still have > no idea how to implement the code snippet import feature you > described; After working with Gennadiy to copy edit some documentation I'd have to agree. Everyone has there own preference, Word, Docbook, Latex etc. but you need some common standard if your going to working collaboratively on documentation, ideally it should be a format the preserves markup in some explicit way. I know it might be an unpopular suggestion, but have you thought of moving the Boost documentation to a wiki based system? Even if only certain members are provided access I think it would be better than what you currently have, most people are happy enough learning to edit text in a wiki. Googling even gives some information on a wiki to DocBook converter... http://www.tldp.org/wt2db/ > furthermore, as far as I can tell, there is no .qbk source > in Boost (from recent CVS-HEAD) that I could use to try to emulate > your Spirit documentation (assuming that is the documentation that > uses this reverse-lit import, which I can't know a priori). Finally, > while > there appears to be some way to have DocBook output LaTeX, it > isn't clear to me that there is any way to have it parse and process > LaTeX source in, for example, the way that Doxygen does so that > you can get images of typeset equations in the HTML output. Maybe > it's possible, but it is certainly far from obvious, and the amount of > time I would have to invest learning a completely new system hardly > seems to justify the potential benefit. Anyway, sorry for the rant - it > just doesn't seem like this should be this painful... > > Matthias

8 14

[serialization] performance comparison
by bwood 17 Mar '07

17 Mar '07

Shalom I've been comparing results from Boost Serialization (B.Ser) and Ebenezer Enterprises(EE) on Windows XP lately. I've compared saving a 1. set<int>, 2. list<int>, and 3. list<int> and deque<int>. I'm using MSVC8.0, Boost 1.33.1, and software from www.webEbenezer.net to build the tests. I use clock() statements to measure the amount of time used. I've read on this list that there is an issue with using clock() on Windows, but I use it the same way in all the tests so doubt it is an issue here. I use a buffer of 4096 bytes in the EE versions and from what I can tell the Boost versions also use the same size of buffer. (I'm not doing anything to set the buffer size with Boost. It seems to default to 4096.) Each of the containers is filled with 1,000,000 ints. Build times/Exe sizes In each of the tests the B.Ser versions take longer to build and the executables are more than two times bigger in bytes than the EE versions. Run times I ran the B.Ser and EE versions 3 times in a row and threw out the fastest and slowest times and kept the remaining middle time. The following results are from optimized (O2) versions of the tests. set<int> B.Ser ----- 1630 EE --------- 451 B.Ser version takes 3.6 times longer than the EE version. list<int> B.Ser ----- 1440 EE --------- 271 B.Ser takes 5.3 times longer here. list<int> and deque<int> B.Ser ----- 2894 EE --------- 521 B.Ser takes 5.5 times longer here. I've only done a few tests without optimization. The results from those tests have had higher ratios than those listed above. For example, the non-optimized B.Ser version of the list<int> test is about 8 times slower than the non-optimized EE version. One thing that sticks out in my mind is that the optimized B.Ser version of the list<int> test is 3 times slower than the non-optimized EE version. These results are similar to what we observed on Linux previously. http://lists.boost.org/Archives/boost/2005/11/96497.php I didn't test exactly the same thing in the Windows tests and the Linux tests. Feedback from the Linux tests indicated some objection to our commenting out a generated call to flush the buffer we use. I didn't comment out any of the generated code in these Windows tests like I did with Linux. And so the Windows tests fill the buffer and flush it numerous times. Regards, Brian Wood Ebenezer Enterprises www.webEbenezer.net

1 0

[sorting] Complicated sorts
by Sam Schetterer 17 Mar '07

17 Mar '07

What are some of the most complicated sorting problems that you have ever been in? I would like to know so that I can try to implement a way to solve them in the sorting library.

1 0

Review Schedule
by Tom Brinkman 17 Mar '07

17 Mar '07

Review Schedule http://www.boost.org/more/formal_review_schedule.html . If you have any changes, post them as a reply to this thread. We need experienced review managers for many of the libraries in the review queue. A few of them have been waiting for a volunteer for a few months now, such as boost::exception, boost::GloballyUniqueIdentifier and boost::scope_exit. If your interested, let us know. Preferably, you will have a background in the problem domain, but no association with the library and are a regular contributer on the boost mailing list. You can read the "review manager" requirements at the following link: http://www.boost.org/more/formal_review_process.htm Most of the libraries are located at the Boost Sandbox Vault, located here: http://boost-consulting.com/vault/ Here is a summary of the libraries that are in the queue waiting for a "review manager" volunteer. ------------------------------------- Library: Exception Author: Emil Dotchevski Location: http://www.revergestudios.com/boost-exception/boost-exception.zip Review Manager: Needed Date: Needed Summary: The purpose of Boost Exception is to free designers of exception classes from having to consider what data needs to be stored in exception objects in order for the catch site to be able to make sense of what went wrong. When Boost Exception is used, arbitrary values can be stored in any exception. This can be done directly in the throw-expression, or at a later time as the exception object propagates up the call stack. The ability to add data to any exception object after it has been thrown is important, because often some of the information needed to handle an exception is unavailable at the time of the throw. ----------------------------------------- Library: Globally Unique Identifier Author: Andy Tompkins Location: Boost Sandbox Vault Review Manager: Needed Date: Needed Summary: A guid, or globally unique identifier, is an identifier standard used in many disciplines including computer networks, distributed computing, and databases. They can be used to tag objects with very short lifetimes, to reliably identify very persistent objects across a network. An attractive feature of guids is their relative small size, of 128-bits, compared to alternatives. Also the creation of guids does not require a centralized authority. ----------------------------------------- Library: Scope Exit Author: Alexander Nasonov Location: Boost Sandbox Vault Review Manager: Needed Date: Needed Summary: The scope-exit-arg-pp-seq is Boot.Preprocessor sequence of identifiers that can be used inside scope-exit-body. The direct-declarator is declarator-id followed by optional argument of type boost::scope_exit_group (inside brackets or after the equal sign). This construct executes scope-exit-body at the close of the current scope. ----------------------------------- Library: Floating Point Utilities Author: Johan Råde Location: Boost Sandbox Vault Review Manager: Needed Date: Needed Summary: Proposed Additions to the Boost Math Library <boost/math/fpclassify.hpp> Functions for floating point number classification: fpclassify, isfinite, isinf, isnan, isnormal. Follows TR1. <boost/math/signbit.hpp> Functions for floating point number sign bit access and modification: signbit, copysign, changesign. Follows TR1. <boost/math/nonfinite_num_facets.hpp> Facets that parse and format infinity and NaN according to the C99 standard. Used for portable handling of infinity and NaN in text streams. ----------------------------------- Library: Switch Author: Steven Watanabe Location: Boost Sandbox Vault Review Manager: Needed Date: Needed Summary: Needed

2 1

[build] bjam problems on OSX
by Matthias Schabel 17 Mar '07

17 Mar '07

I'm having a hard time getting bjam --v2 to function properly on my system; it's probably just something stupid, but here's the problem : download latest CVS-HEAD snapshot and install ./configure --with-libraries=regex,serialization,mpi copy bjam to /usr/local/bin cd $BOOST_ROOT/libs/date_time/test bjam --v2 resulting in a slew of errors like the following sample : "g++" -o "../../../bin.v2/libs/date_time/test/ testgreg_day.test/gcc-4.0.1/debug/testgreg_day" -Wl,--start-group "../../../bin.v2/libs/date_time/test/testgreg_day.test/gcc-4.0.1/ debug/testgreg_day.o" "../../../bin.v2/libs/date_time/build/gcc-4.0.1/ debug/link-static/libboost_date_time-gcc40-d-1_35.a" -Wl,--end- group -g ...failed gcc.link ../../../bin.v2/libs/date_time/test/ testgreg_day.test/gcc-4.0.1/debug/testgreg_day... ...skipped <p../../../bin.v2/libs/date_time/test/testgreg_day.test/ gcc-4.0.1/debug>testgreg_day.run for lack of <p../../../bin.v2/libs/ date_time/test/testgreg_day.test/gcc-4.0.1/debug>testgreg_day... gcc.link ../../../bin.v2/libs/date_time/test/testgreg_month.test/ gcc-4.0.1/debug/testgreg_month /usr/bin/ld: unknown flag: --start-group collect2: ld returned 1 exit status "g++" -o "../../../bin.v2/libs/date_time/test/ testgreg_month.test/gcc-4.0.1/debug/testgreg_month" -Wl,--start-group "../../../bin.v2/libs/date_time/test/testgreg_month.test/gcc-4.0.1/ debug/testgreg_month.o" "../../../bin.v2/libs/date_time/build/ gcc-4.0.1/debug/link-static/libboost_date_time-gcc40-d-1_35.a" - Wl,--end-group -g ...failed gcc.link ../../../bin.v2/libs/date_time/test/ testgreg_month.test/gcc-4.0.1/debug/testgreg_month... ...skipped <p../../../bin.v2/libs/date_time/test/testgreg_month.test/ gcc-4.0.1/debug>testgreg_month.run for lack of <p../../../bin.v2/libs/ date_time/test/testgreg_month.test/gcc-4.0.1/debug>testgreg_month... gcc.link ../../../bin.v2/libs/date_time/test/testgreg_year.test/ gcc-4.0.1/debug/testgreg_year /usr/bin/ld: unknown flag: --start-group collect2: ld returned 1 exit status "g++" -o "../../../bin.v2/libs/date_time/test/ testgreg_year.test/gcc-4.0.1/debug/testgreg_year" -Wl,--start-group "../../../bin.v2/libs/date_time/test/testgreg_year.test/gcc-4.0.1/ debug/testgreg_year.o" "../../../bin.v2/libs/date_time/build/ gcc-4.0.1/debug/link-static/libboost_date_time-gcc40-d-1_35.a" - Wl,--end-group -g ...failed gcc.link ../../../bin.v2/libs/date_time/test/ testgreg_year.test/gcc-4.0.1/debug/testgreg_year... ...skipped <p../../../bin.v2/libs/date_time/test/testgreg_year.test/ gcc-4.0.1/debug>testgreg_year.run for lack of <p../../../bin.v2/libs/ date_time/test/testgreg_year.test/gcc-4.0.1/debug>testgreg_year... ...skipped <p../../../bin.v2/libs/date_time/test/testdate_dll.test/ gcc-4.0.1/debug>testdate_dll for lack of <p../../../bin.v2/libs/ date_time/build/gcc-4.0.1/debug>libboost_date_time-gcc40-d-1_35.dylib... ...skipped <p../../../bin.v2/libs/date_time/test/testdate_dll.test/ gcc-4.0.1/debug>testdate_dll.run for lack of <p../../../bin.v2/libs/ date_time/test/testdate_dll.test/gcc-4.0.1/debug>testdate_dll... ...skipped <p../../../bin.v2/libs/date_time/test/ testdate_duration_dll.test/gcc-4.0.1/debug>testdate_duration_dll for lack of <p../../../bin.v2/libs/date_time/build/gcc-4.0.1/ debug>libboost_date_time-gcc40-d-1_35.dylib... ...skipped <p../../../bin.v2/libs/date_time/test/ testdate_duration_dll.test/gcc-4.0.1/debug>testdate_duration_dll.run for lack of <p../../../bin.v2/libs/date_time/test/ testdate_duration_dll.test/gcc-4.0.1/debug>testdate_duration_dll... ...failed updating 53 targets... ...skipped 173 targets... The use of date_time is not the problem - I get similar errors for other Boost libraries... I'm running on a G5 Mac OSX system 10.4.8 using stock gcc provided with Xcode (gcc 4.0.1) : gcc --version : powerpc-apple-darwin8-gcc-4.0.1 (GCC) 4.0.1 (Apple Computer, Inc. build 5363) BTW, simply doing make after configuring works fine... Any ideas? Matthias

3 6

Re: [boost] SQL library with full embedded SQL-syntax
by Phil Endecott 16 Mar '07

16 Mar '07

> What I would find way more useful would be > an abstraction that removes the SQL language itself, i.e. a relational > database library. That would have some advantages: > > * Better coherence with C++ data types. > * Possibility to support non-SQL relational databases. > * Make it easier to construct object/relational translation abstractions. Yes, absolutely. I would love to see a non-SQL C++-interfaced relational database library. With my query-is-a-functor class the SQL query string can be hidden away, and at the point of use you can fantasize that it's not doing SQL.... But in order to be useful, such a library would need to offer all of the important features of current databases, i.e. good performance with huge on-disk data sets, transactions, client/server operation, concurrency, and so on. To some extent these requirements can be usefully addressed as individual problems. So if someone is looking for something to do, how about starting with containers, iterators and allocators for huge on-disk data structures. This could be based on the existing shared memory containers, but using mmap()ed windows into files. Then we'd probably want some sort of dynamic algorithm selection ("query planning") mechanism. Regards, Phil.

3 2

[sorting] Has anyone downloaded the sorting library from vault?
by Sam Schetterer 16 Mar '07

16 Mar '07

Has anyone downloaded the sorting lbirary from vault? If you have, could you post any changes that you would like to be made or any errors in the library?

3 2

[Sorting] Updated vault files
by Sam Schetterer 16 Mar '07

16 Mar '07

I have finally uploaded all of the correct source files and documentation files into sorting.zip, in the Sorting directory and the Algorithm directory. I also have all of the documentation uploaded into Sorting-doc and Algorithms-sorting-doc.

1 0