- Boost - lists.boost.org

[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

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

18 Mar '07

On March 18, Henrik Sundberg wrote >Isn't sort within sort handled by a more complex '<' operation? >I.e '<' returns the order of the inner sort, when the outer is equal. Yes, that can be done, but it is much slower because of the many operations that need to be done. In addition, since radixquicksort is to be used for strings, the compare operation will still have to use a string comparison, severly slowing it down. Also, if you use a function that creates a string, you can do an extrordanarily complex sort, like sort by name, then number, then grade, and if grade is below a B+, then sort by age. This can be done because you cn change how the id string is created. That is why quicksort is useful.

2 1

[spirit] compile error with gcc-4.1
by Juergen Hunold 18 Mar '07

18 Mar '07

Hi ! I've done a manual test run on CVS Head today and found that some spirit test are broken with: gcc.compile.c++ /build/bjam/boost_1.35.0/libs/spirit/test/ast_calc_tests.test/gcc-4.1/debug/ast_calc_tests.o /home/hunold/packages/boost/boost/spirit/tree/common.hpp:696: error: declaration of 'class T' /home/hunold/packages/boost/boost/spirit/tree/common.hpp:682: error: shadows template parm 'class T' I run: gcc version 4.1.2 (Ubuntu 4.1.2-0ubuntu4) It seems that this was caused by a commit from Hartmut Kaiser last week, r1.26, which introduce a new template parameter "T". Please find a simple patch attached. Yours, Jürgen -- * Dipl.-Math. J�rgen Hunold ! Ingenieurgesellschaft f�r * voice: ++49 511 262926 57 ! Verkehrs- und Eisenbahnwesen mbH * fax : ++49 511 262926 99 ! Lister Stra�e 15 * juergen.hunold(a)ivembh.de ! www.ivembh.de * * Gesch�ftsf�hrer: ! Sitz des Unternehmens: Hannover * Prof. Dr.-Ing. Thomas Siefer ! Amtsgericht Hannover, HRB 56965 * PD Dr.-Ing. Alfons Radtke !

2 1

GSoC mentors
by headl004＠bama.ua.edu 18 Mar '07

18 Mar '07

Does anyone know who the GSoC mentors are for Boost or how we can get in touch with them? Thanks! Justin Headley

3 4

Re: [boost] [sorting] How radixsort can be more useful than quicksort
by Sam Schetterer 18 Mar '07

18 Mar '07

Henrik Sundberg wrote >The '<' is used for branching anyway. Is this really a valid reason? >Constructing concatenated strings for all values to be sorted to be >able to use string sort, seems to be a big overhead. In both normal and radix quicksort, when that is used for branching, the compiler arranges the code so the the cpu will usually follow the right branch path, meaning that it will pipeline into the if or while or for statement. However, in cases like the example, many of the less than statements in the operator< will not be satisfied, breaking the pipeline again and again, especially when it goes all the way to the bottom of the statement. On vault, I have uploaded source code for a radixosrt that shows the problme with complex operator< (it uses normal radixsort), when compared to the operator[] for normal radixsort. also, imagine that the class that you have designed with a complex operator< is a template class that is used for many types. For radixsort, that size of operator[] is constant. With operator<, it grows to large sizes and causes coad bloat, and it is slow. In addition, even if quicksort is still faster than radixsort, radixsort hs a linear running time (complexity is O(N)), and will always run that fast for any possible order of the data. Finally, going back to the problem of pipelining, radixsort is very pipeline friendy, and almost all of the branches will be properly followed. The only time that will not happen is when each for loop is exited. On computers with long pipelines, like the Pentium Pro, which has a 20 step pipeline, along with many other computers, radixsort will have a huge advantage of quicksort for complex operator<. Then, about creating strings, it is not a very large overhead and only has to be done when the objects change, and is only done on objects containing strings. When strings are normally compared, each byte is examined each time. radix quicksort only examines each byte once, giving it another large advantage over normal quicksort and other non-radix sorts.

1 0

[Sorting] How radixsort can be more useful than quicksort
by Sam Schetterer 18 Mar '07

18 Mar '07

Henrik Sundberg wrote >Isn't sort within sort handled by a more complex '<' operation? >I.e '<' returns the order of the inner sort, when the outer is equal. Henirk, the problem is if one your approach, operator< can become extremely complex, and therefore, slow. Also, even if there is only one layer of complexity, checking the outer layer and then possibly checking the inner layer introduces multiple branches of control into the program, and most of the time, they will not be followed. Therefore, much of the time that operator< is called for your complex object, the computers pipeline in emptied, and for modern computers, that can have a big effect, as their pipelines can reach sizes of 20 steps, and that takes a long time to refill. In addition, that approach is still unstable.

2 1

[sorting] New example of why radixsort can be better than quicksort
by Sam Schetterer 18 Mar '07

18 Mar '07

I have uploaded the source code for this example to vault. It shows a more extreme case of how making a more complex operator<, like Henrik Sundberg advised, is both slow and big, while the operator[] for the samew class is fast and small.

1 0

Re: [boost] Review Schedule
by Tom Brinkman 18 Mar '07

18 Mar '07

Ok. Thanks Harmut. You've been assigned the "Globally Unique Identifier". Contact the author and let us know when you would like to schedule the review. Contact Ron or myself if you have any troubles.

1 0