asterixdb-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Wail Alkowaileet <wael....@gmail.com>
Subject Re: Re: Adapting TimSort into AsterixDB/Hyracks
Date Sat, 28 Oct 2017 16:41:25 GMT
Android has an implementation:
https://github.com/retrostreams/android-retrostreams/blob/master/src/main/java/java9/util/TimSort.java

Spark has ported it
https://github.com/apache/spark/blob/master/core/src/main/java/org/apache/spark/util/collection/TimSort.java

We can customize it for AsterixDB comparators.

On Sat, Oct 28, 2017 at 9:28 AM, Chen Luo <cluo8@uci.edu> wrote:

> I don't know whether there is an easy way for us to directly reuse TimSort
> in JDK since it's design for sorting objects in an Array, while in Hyracks
> we don't have explicit object creation and sort everything in main memory.
> So what I did is that I copied it's source code, and replaced all object
> assignments/swaps/comparisons using Hyracks in-memory operations.
>
> Best regards,
> Chen Luo
>
> On Sat, Oct 28, 2017 at 12:07 AM, 李文海 <00008749@whu.edu.cn> wrote:
>
> > I believe reusing jdk afap could be better. btw, timsort is better than
> > others by 1x when records are locally ordered .
> > best
> >
> > 在 2017-10-28 14:38:21,"abdullah alamoudi" <bamousaa@gmail.com> 写道:
> >
> > >While I have no answer to the question of legality, this sounds great.
> > >
> > >~Abdullah.
> > >
> > >> On Oct 27, 2017, at 9:20 PM, Chen Luo <cluo8@uci.edu> wrote:
> > >>
> > >> Hi devs,
> > >>
> > >> I have adapted the TimSort algorithm used in JDK (java.util.TimSort)
> > into
> > >> Hyracks, which gives 10-20% performance improvements on random data.
> It
> > >> will be more useful if the input data is partially sorted, e.g.,
> primary
> > >> keys fetched from secondary index scan, which I haven't got time to
> > >> experiment with.
> > >>
> > >> *Before going any further, is it legal to adapt some algorithm
> > >> implementation from JDK into our codebase? *I saw the JDK
> implementation
> > >> itself is adopted from
> > >> http://svn.python.org/projects/python/trunk/Objects/listsort.txt as
> > well.
> > >>
> > >> Best regards,
> > >> Chen Luo
> > >
> >
> >
>



-- 

*Regards,*
Wail Alkowaileet

Mime
  • Unnamed multipart/alternative (inline, None, 0 bytes)
View raw message