Mailing-List: contact dev-help@asterixdb.apache.org; run by ezmlm
Precedence: bulk
Reply-To: dev@asterixdb.apache.org
MIME-Version: 1.0
In-Reply-To: <CALgBV_c6-2oN-awOqdR4vxeMG1jMexim8y04mAw+sHnNKVTtKw@mail.gmail.com>
References: <CAEGOuq0k2TCNtQLiQUf+Dz_KZeoqSOAJ2BkuLjCsikkp=T5pgw@mail.gmail.com>
 <0DB6BB3D-170F-417B-9C3D-99905228C069@gmail.com> <3dd76412.a45d.15f61ce2cc6.Coremail.00008749@whu.edu.cn>
 <CAEGOuq2gCWWZ5TbSwsG=zazxjNUHM9frU=MwD9-Exq-ZxL6hVg@mail.gmail.com> <CALgBV_c6-2oN-awOqdR4vxeMG1jMexim8y04mAw+sHnNKVTtKw@mail.gmail.com>
From: Wail Alkowaileet <wael.y.k@gmail.com>
Date: Sat, 28 Oct 2017 09:44:00 -0700
Message-ID: <CALgBV_eQPkasLqg8Qw5HnrmUbKgtxt8fs-vCcBg+AJa2KayDVQ@mail.gmail.com>
Subject: Re: Re: Adapting TimSort into AsterixDB/Hyracks
To: dev@asterixdb.apache.org
Content-Type: multipart/alternative; boundary="001a113ac576cb2c9c055c9e1ca1"
archived-at: Sat, 28 Oct 2017 16:44:07 -0000

--001a113ac576cb2c9c055c9e1ca1
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

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 TimSo=
rt
>> in JDK since it's design for sorting objects in an Array, while in Hyrac=
ks
>> we don't have explicit object creation and sort everything in main memor=
y.
>> 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, =E6=9D=8E=E6=96=87=E6=B5=B7 <00008749@=
whu.edu.cn> wrote:
>>
>> > I believe reusing jdk afap could be better. btw, timsort is better tha=
n
>> > others by 1x when records are locally ordered .
>> > best
>> >
>> > =E5=9C=A8 2017-10-28 14:38:21=EF=BC=8C"abdullah alamoudi" <bamousaa@gm=
ail.com> =E5=86=99=E9=81=93=EF=BC=9A
>> >
>> > >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
>


--=20

*Regards,*
Wail Alkowaileet

--001a113ac576cb2c9c055c9e1ca1--