asterixdb-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Chen Luo <cl...@uci.edu>
Subject Re: Re: Adapting TimSort into AsterixDB/Hyracks
Date Sat, 28 Oct 2017 16:28:57 GMT
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
> >
>
>

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