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:44:00 GMT
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