asterixdb-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Xikui Wang <xik...@uci.edu>
Subject Re: Re: Adapting TimSort into AsterixDB/Hyracks
Date Sat, 28 Oct 2017 16:52:02 GMT
I think probably it's not okay to use JDK's implementation due to the
license issue [1]. (Search for BCL)

Alternatively, you could use the one that Spark used from the Android
Opensource Project, as Wail pointed out. That one is under Apache License.

[1] https://www.apache.org/legal/resolved.html

On Sat, Oct 28, 2017 at 9:44 AM, Wail Alkowaileet <wael.y.k@gmail.com>
wrote:

> P.S Spark implementation is under Apache.
>
> On Sat, Oct 28, 2017 at 9:41 AM, Wail Alkowaileet <wael.y.k@gmail.com>
> wrote:
>
> > 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
> >
>
>
>
> --
>
> *Regards,*
> Wail Alkowaileet
>

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