Re: [boost] [review] [sort] Sort library review manager results

Subject: Re: [boost] [review] [sort] Sort library review manager results
From: Francisco José Tapia (fjtapia_at_[hidden])
Date: 2014-12-01 13:51:52

Hi Steven,

 My idea when developed the parallel sort methods was easy. I needed
parallel sort methods for my new version of my Counter Tree library. I
examined the GCC code and I thought, it could be possible to do without
Open MP ? And try it.

 I am not against Open MP or TBB, but if you can do without them, remove an
obstacle for to be used by any C++11 compiler. I am not an expert in sort
methods, I used quick sort, heap sort and merge sort described in a basic
book of algorithms. My main interest are in the parallel methods.

 I use a concurrent stack, done with a std::vector and spin locks done with
atomic variables. In the intro sort, the threads divide the problem and
insert the parts in the concurrent stack, and after extract the last and if
is smaller than a defined value, sort with the 1 thread sort, or split and
insert in the stack.

 The stable sort is a merge sort, and is different. You have levels, in the
upper level you do 1 merge, in the next 2 …. The algorithm have atomic
counter for the levels, and when is smaller than a predefined size, sort
with the 1 thread algorithm.

 The algorithms must be refined. The size limit for a thread is (
total_size / (nthreads *8) ). The number of 8 is arbitrary, run well, but I
need more benchmarks for to obtain the best value.

 The 1 thread algorithms must be improved, specially the merge_sort, the
first solution can be copy the algorithm used in GCC, but I would like to
examine more in deep.

 The detection about the sorted elements is easy in intro sort with a
counter of movements, when you detect zero movements form one side to
other, you can check if they are ordered. In the merge sort is more
difficult, but I will examine.

 The worst case in intro sort is extremely difficult to obtain. I checked
with a counter when the algorithm use heap sort, and with hundred of
millions elements, with different data inputs, sometimes the counter is to
1, and the number of elements sorted is small.

 About the size, intro sort don't use additional memory. Merge sort use an
array of a half of the size of the input data. This array is used, in the
parallel and in the 1 thread function, each call have the range of elements
and the related part of this array.

 I use the atomics variables for to implement the spin locks. In a non
C++11 compiler, we can use pthreads, or any other thread library, and
mutex.

 In my opinion , the most interesting part of my code are the parallel
functions. The other must be improved, and you know much more about it. I
only pretend to be useful with my code and my ideas. The goal is to provide
good sort methods to the community.

 I have done other things about sorting which perhaps can be interesting. I
am testing indirect sort. When the size of the elements grows, the data bus
is stressed moving the elements and the performance of the algorithms
drops. If you create an array with pointers to the elements, and sort this
array, you have a penalty because you must access to the elements from a
pointer, but you only move pointers.  At end with the pointers sorted, a
O(N) method sort the original elements. And with the size of the elements
grows, this method is faster than the original.

 I hope have time this weekend for to pack and send the code. I don't know
if as zip file or create a git repository for this code. If I can help you,
please say me, and I will try. And if you want to use something say me for
to write the documentation, because now I have only the code, test programs
and several benchmarks.

 Congratulations by your library.

Yours

 Francisco Tapia

2014-12-01 13:57 GMT+01:00 Paul A. Bristow <pbristow_at_[hidden]>:

>
>
> > -----Original Message-----
> > From: Boost [mailto:boost-bounces_at_[hidden]] On Behalf Of Steven
> Ross
> > Sent: 01 December 2014 11:18
> > To: boost_at_[hidden]
> > Subject: Re: [boost] [review] [sort] Sort library review manager results
> >
> > >
> > > > but maybe those problems are now completely resolved and I just have
> > > > not kept up with the discussion. Also Steven Ross will want to
> > > > integrate 'spreadsort' into the modular boost directory structure
> > > > and since this is his first contribution to Boost we need to make it
> > > > understandable to him how to do this.
> > > >
> > >
> > > Yes. One question is "who is the maintainer for the overall sort
> library?"
> > > It would be nice if someone was looking at the big picture, so that
> > > there was some consistency between individual sorts for docs, testing,
> > > etc. There might be some overall docs, too, to help users choose
> > > between algorithms without having to read about each sort algorithm
> separately.
> > >
> > > Steven, are you interested in that role?
> > >
> >
> > Yes, I'm willing to perform that role.
> >
> > The question seems to boil down to: do we have
> algorithm/sort/spreadsort, or
> just
> > sort/spreadsort?  Either way, sort should probably be its own submodule.
> There was
> > still the concern from Rene that sub-sub-modules can be difficult for
> others
> to put
> > together properly (for the purpose of building a minimal necessary
> subset).
> Has that
> > been resolved?
> >
> > My inclination is that unless the maintainer of the algorithm library
> would
> welcome a
> > new sub-submodule, and the concerns about the difficulty of building a
> minimal
> > subset aren't resolved, I'd rather have this as its own module: sort.
>
> GIT is already causing some brain pain.
>
> So I think we should be rather cautious about nesting the modules any
> deeper
> than necessary.
>
> I'd favour starting at libs/sort , despite some logical sugar in adding it
> to
> Boost.Algorithms.
>
> Paul
>
> ---
> Paul A. Bristow
> Prizet Farmhouse
> Kendal UK LA8 8AB
> [phone]
>
>
>
>
>
>
>
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>