On March 24, 2015 10:32:35 PM EDT, Steven Ross wrote:

...

TimSort -> 2M

[snip]

Timsort seems fairly impressive, but specialized and already available for free, hence not necessary to include in the library.

While "specialized" may be sufficient grounds to avoid including Timsort, its availability elsewhere for free is not a good justification for excluding it from Boost. Providing a single source of good, varied algorithms, with equivalent documentation including comparative information to help users choose among the options would seem more than ample reason to include an algorithm. I realize that the more algorithms you include, the greater your documentation and maintenance burden, so you may still choose to reject Timsort on such grounds. I just didn't want you to dismiss it too quickly. ___ Rob (Sent from my portable computation engine)

On Wed, Mar 25, 2015 at 4:43 AM, Rob Stewart wrote:

On March 24, 2015 10:32:35 PM EDT, Steven Ross wrote:

...

...

TimSort -> 2M

[snip]

...

Timsort seems fairly impressive, but specialized and already available for free, hence not necessary to include in the library.

While "specialized" may be sufficient grounds to avoid including Timsort, its availability elsewhere for free is not a good justification for excluding it from Boost.

Providing a single source of good, varied algorithms, with equivalent documentation including comparative information to help users choose among the options would seem more than ample reason to include an algorithm.

I realize that the more algorithms you include, the greater your documentation and maintenance burden, so you may still choose to reject Timsort on such grounds. I just didn't want you to dismiss it too quickly.

Sure, if a Timsort library author wishes to volunteer to include it in boost, I'll add it.

Hi Francisco, On Wed, Mar 25, 2015 at 3:57 PM Francisco José Tapia wrote:

TEST OBJECTS

The object used in the test ( Reburcio is a word of an exercise from my first pascal book, and don't have any sense) In the construction , copy construction and operator =, copy all the elements with a loop. The only one operation which use only the first element is the comparison.

I had done a new comparison, and compare the sum of all the elements of the object. The time are similar, you must add 5% in the small objects to 15% in the big objects.

I'm not precisely sure of your meaning, but I suggested modification of the test object to use default operators where possible, to randomize the entire contents of the object (so that not all integers in the array are the same), and to use the entire contents of the object for comparison. I believe that these suggested changes make it more reflective of the conventional large-object comparison case. Most of the time, only the first integer will be compared, but in equal cases the entire array will be compared. I don't like feeding overly simplified objects into benchmarks, because compilers can make some surprising optimizations.

TIMSORT

The Tim Sort code is not mine.

Agreed. I think we can drop it from this comparison, as your algorithm is clearly much faster. I mentioned it because it is used with other languages, and responded when somebody else on the email group suggested I allow it. I'm not asking you for an implementation. Timsort uses N/2 additional memory.

DESIGN PHASE

Now , we are in the design phase. Nothing is fixed. We can comment and change anything.

The specification is simple, provide sort algorithms, stable and not stable, for to run with 1 thread or with any number of threads, without any other external library ( as Open MP , TBB, CilkPlus..). Only with the C++ standard.

If you want to discuss about this, we can do. We admit ideas, suggestions, opinions. Any help is welcome. The final decision about if the code is included or not in the boost sort library, depend of Steven, the creator of the library.

After the design phase, with the decisions taken and the interfaces fixed. We prepare the final version, redesign a test system, test in deep and create the documentation.

I suggest deciding what you want to try to include. Getting a competitive parallel unstable sort to tbb will be hard, and I'm skeptical of including a library that just replicates what tbb provides for easy use.

I tried to improve, I would like to have more time, more equipment, and better documentation on order to find the best options, but I don't have, and I do this in my free time after my work and my family.

I'm in the same situation with regards to available time. I think many boost participants are.

I designed 6 stable sort algorithms, for to select the fast (internally named smart_merge_sort, about 10% faster than the GCC version). I prepared a version of Sample Sort, only with threads and atomic variables. In the benchmarks have similar performance than the TBB version, use one half of the auxiliary memory used by TBB and is exception safe.

I like your parallel stable sorts. They look like the most promising part of your proposed library additions. Indirect sorting is also interesting. I just want reliable large-object and string comparison numbers for them before diving in further. Have you looked at integrating your testing with the approach in the Boost Sort library? The randomgen binary generates files with different types of random number distributions that can test a variety of scenarios, and the tune.pl script controls automated performance testing.

In my opinion, the parallel stable sort is reasonably good for to be included in the final version. The important case, which shows the quality of the algorithm, is when the data are unsorted. I will try to implement the detection of the sorted elements , like in TBB, but I am not sure about the results. Th internal loops of the algorithm are delicate, and a small change , can produce big changes in the performance, as happened in other algorithms

Is there a way you can do a fast initial pass, checking for already-sorted

data? That's what Spreadsort does (at each level of the sort).

On Sun, Mar 29, 2015 at 6:25 AM Francisco José Tapia wrote:

Hi Steven

Thanks by your message.

Until now , I had been focused mainly in the algorithms, and I didn't dedicate many time to others things as the test format and the integration with boost::sort.Now, the first things to do are :

- Try to detect when the data are ordered,

Just verify that each successive element is not less than the previous. If inputs are unique (or completely identical if they compare the same), then you can compare results with those of std::sort.

- Revise in deep your library and code , in order to adapt the test and benchmarks to the procedures used in your library

About the object used in the benchmarks, we can do something simple. Reburcio is a very small class in the file Benchmarks/GCC/algorithm/reburcio.hpp. Please rewrite and send me, and only need to recompile the benchmarks.

I suggest renaming the variables to be clearer, but here's the idea: template struct intarray { uint32_t M[NN]; bool operator < ( const intarray &R) const{ for (int i = 0; i < NN; ++i) { if (M[i] != R.M[i]) { return M[i] < R.M[i]; } } return false; } }; Use /libs/sort/example/randomgen.cpp (b2 libs/sort/randomgen --tune will build the binary in the libs/sort dir) to generate randomized input files, and memcpy them into arrays of intarray to fill them with the data to sort. This will emulate the large non-vector objects the indirect sorting approach you've designed is optimized for, and will fill the entire object with randomized contents, along with having a full (default) copy constructor. You can use strings in the place of intarray also for testing strings; I randomize them by just using the >> operator on strings to read them in; it will automatically break on some characters, causing the strings to have randomized length.

*About the parts to include*

With the parallel unstable sort, all the algorithms I examined have the same approach, and due this, similar performances. The range of decision is small.

The goal is provide algorithms independent of any library or Operating System, fast , robust and easy to use. The idea of to do the same than a company is the origin of many Free SW, think about Oracle and MySQL, Internet Explorer and Firefox. Even the C++ standard, is to do the same than many companies are doing since many years ago, each with its own way. The final users are grateful because simplify our work.

TBB is available in Windows, Linux and Os X. With others operating system ( by example Android and all the real time OS), you must recompile all the source code, and I have not clear about the dynamic linking of TBB in these operating systems. Many small machines don't have task scheduler, but have threads. To force to recompile TBB for to use a parallel sort is like force to rent a bus, for to transport only one person.

Who wants to do a parallel sort on Android? The OS often only gives you one core (depending on priorities), and it would burn the battery at ridiculous speed. I just don't see the use case, unless you can provide some advantage in some fairly common use case, and it would have to fully match tbb's features to within a few percent, including efficiency on already-sorted input.

Our code have similar performance, small code, independent of any Operating System, of any other code or library. If you are C++11 compliant you have parallel sort. I think, we must include sort, parallel sort, stable sort and parallel stable sort. Perhaps, too, sample sort, but it's less important

Your stable sort and parallel stable sort look promising, and sample sort is a possibility. I recommend concentrating on them for now.

It's not just CPUs. Most of the physics engines used in games for phones are CPU based. The current multi threaded CPU architecture brings gamin to a whole new level. I see some physics done with sort, map, gather, scatter, and all. PS: I proposed this as a part of boost compute this GSoC giving GPU support for iOS devices using metal shading language. Regards, Aditya Atluri.

On Apr 6, 2015, at 1:37 AM, Ben Pope wrote:

...

On Monday, April 06, 2015 11:13 AM, Steven Ross wrote: Who wants to do a parallel sort on Android? The OS often only gives you one core (depending on priorities), and it would burn the battery at ridiculous speed.

I was under the impression that it's better on battery life to use all the cores at maximum and then sleep as quickly as possible. Clock gating of the components is getting better, but for example (and I'm completely making this up now), if two CPUs share a cache, then the cache is alive anyway so you may as well use the other CPU. I've heard the term "race to sleep" to describe this.

I think it's hard to guess at; mobile CPUs now have 8 cores, and they're not even homogeneous, some are in order execution and some out of order.

Ben

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

On Mon, Apr 6, 2015 at 12:53 PM, Steven Ross wrote:

The term race-to-sleep applies to faster but higher-power processors sometimes being more power efficient because the system can go to sleep faster. That said, as modern mobile systems normally operate with all but one core asleep,

Are you sure about that?

they are optimized for the single-core use case, and very little power is wasted on the unused CPUs.

-- Olaf

Regards, Aditya Atluri.

On Apr 6, 2015, at 6:53 AM, Steven Ross wrote:

...

On Mon, Apr 6, 2015 at 1:55 AM, Aditya Atluri wrote: It's not just CPUs. Most of the physics engines used in games for phones are CPU based. The current multi threaded CPU architecture brings gamin to a whole new level. I see some physics done with sort, map, gather, scatter, and all.

PS: I proposed this as a part of boost compute this GSoC giving GPU support for iOS devices using metal shading language.

If you can find somebody whose frame rate on mobile is significantly impacted by CPU sorting speed, I'd love to chat with them

FYI, Most of the rendering applications, have asynchronous ability. Like, after issuing a draw call, the gpu takes time to render the scene. Meanwhile, the CPU does all the physics calculation. Doing physics on the GPU causes increase in frame rendering time. This is one of the reason why mobile devices are still using CPU based Physics, AI systems. The design call of using CPU or GPU depends on the developer by testing the frame rate to be reasonable. If the frame rates are high, he may chose to go for GPU based Physics or AI. Else he sticks to CPU.

...

...

...

On Apr 6, 2015, at 1:37 AM, Ben Pope wrote:

On Monday, April 06, 2015 11:13 AM, Steven Ross wrote: Who wants to do a parallel sort on Android? The OS often only gives you one core (depending on priorities), and it would burn the battery at ridiculous speed.

I was under the impression that it's better on battery life to use all the cores at maximum and then sleep as quickly as possible. Clock gating of the components is getting better, but for example (and I'm completely making this up now), if two CPUs share a cache, then the cache is alive anyway so you may as well use the other CPU. I've heard the term "race to sleep" to describe this.

I think it's hard to guess at; mobile CPUs now have 8 cores, and they're not even homogeneous, some are in order execution and some out of order.

The term race-to-sleep applies to faster but higher-power processors sometimes being more power efficient because the system can go to sleep faster. That said, as modern mobile systems normally operate with all but one core asleep, they are optimized for the single-core use case, and very little power is wasted on the unused CPUs. When you add in that parallel sorting has 75% of the CPU efficiency, it just doesn't make sense from a power perspective especially if some other task can be computed in parallel with the sort, and as there is a single-threaded option (spreadsort) that can sort 1.5-2X faster on just one core.

_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

On Mon, Apr 6, 2015 at 10:12 AM Aditya Atluri wrote:

Regards, Aditya Atluri.

...

On Apr 6, 2015, at 6:53 AM, Steven Ross wrote:

...

On Mon, Apr 6, 2015 at 1:55 AM, Aditya Atluri wrote: It's not just CPUs. Most of the physics engines used in games for phones are CPU based. The current multi threaded CPU architecture brings gamin to a whole new level. I see some physics done with sort, map, gather, scatter, and all.

PS: I proposed this as a part of boost compute this GSoC giving GPU support for iOS devices using metal shading language.

If you can find somebody whose frame rate on mobile is significantly impacted by CPU sorting speed, I'd love to chat with them

FYI, Most of the rendering applications, have asynchronous ability. Like, after issuing a draw call, the gpu takes time to render the scene. Meanwhile, the CPU does all the physics calculation. Doing physics on the GPU causes increase in frame rendering time. This is one of the reason why mobile devices are still using CPU based Physics, AI systems. The design call of using CPU or GPU depends on the developer by testing the frame rate to be reasonable. If the frame rates are high, he may chose to go for GPU based Physics or AI. Else he sticks to CPU.

I understand that they're doing physics calculations, but are those

physics calculations containing a substantial amount of purely sequential sort time, where they can't run other computations in parallel? If so, I'd be interested in talking with them to understand what they're doing.