Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1m9QzH-0002gA-7F for pgsql-hackers@arkaria.postgresql.org; Fri, 30 Jul 2021 11:47:35 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1m9QzF-0006Tj-NX for pgsql-hackers@arkaria.postgresql.org; Fri, 30 Jul 2021 11:47:33 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1m9QzF-0006Tb-A1 for pgsql-hackers@lists.postgresql.org; Fri, 30 Jul 2021 11:47:33 +0000 Received: from mail-pl1-x632.google.com ([2607:f8b0:4864:20::632]) by makus.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.92) (envelope-from ) id 1m9QzC-0003Vj-OI for pgsql-hackers@postgresql.org; Fri, 30 Jul 2021 11:47:32 +0000 Received: by mail-pl1-x632.google.com with SMTP id t3so8661957plg.9 for ; Fri, 30 Jul 2021 04:47:30 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=6NjPFfv/lHXD1VI/QlbBfgk3aQG+dLo58vEC/GKFGQs=; b=f++2LSnBGBlS3Vn8dzV4TfD0BphzQZhm1YbH9QiSvG07K/5StMv1yhb5S5mTjn2Kag +s7Htmnrr5tKq1f8uBHdvdaq2QxuTp5KIPNzILrqdHWsbJz3JzRZ1iDLjSMSvxNy+64U ZhwQjh9spSOMywd5eZFF+Qwm2kVJcNVIVGHmhJhkRb207jvkp1gHahb60I0uoiU/hliT pciUx5Akv/MUAuBx1R/qdxDBOnBHcuCwUqAQJLFRCFfFroJJcztNINKAJpe+1mcXl+gf iL2sx53NzXl+UoErrNS7UBkhYRnwxv9HpgL3BnTYSsIa7FHiIg8oIm/8eGtiG98psATo hJmQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=6NjPFfv/lHXD1VI/QlbBfgk3aQG+dLo58vEC/GKFGQs=; b=URUEWFWgOgvpra6i7aY8loZiJZEJ+2F+7+nlE5Wgom9Cs81ALVnVjS7k6ihz5+LrwW 7TeTMvIdMG100iy13AgKKzaqo+FCxhqK/rxTr8CMA/1YB/vtEgnKq3ush+uDCN60c0Ow irxJmMBaUM0+yIVZRCCv8loQHkWPMur0l5H8MXVTEbnTVjBJr7VYHgO5i2TfF87TD3+L I8hh2HdCtMBeHg2H/bCWJbs2h4TGOb8dh0r2bGAluW4OfwlxZl3Y2ap8ZjaNNHKGzUCs ahjMnd0EX34uUDReDTyP0+iUtFELvAPqlNJkI3FIQ3XHIHM42hWLKycRhI/O0IKbiSpq 7YOw== X-Gm-Message-State: AOAM531YzgZnnVwY94Elu2e8gEIe4SlUR+6VGvxINuQA36/iX9PFxPGD nRRk7fC9YpCzsWp3yItSIs5sMgwwORz/xb4CGrg= X-Google-Smtp-Source: ABdhPJz69Umw8amKz7DIIzHWLXOSGebfH6L2TLjlfXAx9WXmyb/uSxlVrB0Hu55lJjNXGoF1LgEhHJOMaB60y2h8enE= X-Received: by 2002:a17:90a:c57:: with SMTP id u23mr2768881pje.186.1627645649334; Fri, 30 Jul 2021 04:47:29 -0700 (PDT) MIME-Version: 1.0 References: <0F9ECBA9-1DF2-4C38-BB58-B17EEE6C7B3A@yesql.se> <20210311185847.zwb2rf3n4wzelkba@alap3.anarazel.de> In-Reply-To: From: Ranier Vilela Date: Fri, 30 Jul 2021 08:47:18 -0300 Message-ID: Subject: Re: A qsort template To: John Naylor Cc: Thomas Munro , pgsql-hackers Content-Type: multipart/alternative; boundary="000000000000bfb5d705c855c875" List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --000000000000bfb5d705c855c875 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Em qui., 29 de jul. de 2021 =C3=A0s 21:34, John Naylor < john.naylor@enterprisedb.com> escreveu: > > On Sun, Jul 4, 2021 at 12:27 AM Thomas Munro > wrote: > > > > Since you are experimenting with tuplesort and likely thinking similar > > thoughts, here's a patch I've been using to explore that area. I've > > seen it get, for example, ~1.18x speedup for simple index builds in > > favourable winds (YMMV, early hacking results only). Currently, it > > kicks in when the leading column is of type int4, int8, timestamp, > > timestamptz, date or text + friends (when abbreviatable, currently > > that means "C" and ICU collations only), while increasing the > > executable by only 8.5kB (Clang, amd64, -O2, no debug). > > > > These types are handled with just three specialisations. Their custom > > "fast" comparators all boiled down to comparisons of datum bits, > > varying only in signedness and width, so I tried throwing them away > > and using 3 new common routines. Then I extended > > tuplesort_sort_memtuples()'s pre-existing specialisation dispatch to > > recognise qualifying users of those and select 3 corresponding sort > > specialisations. > > I got around to getting a benchmark together to serve as a starting point= . > I based it off something I got from the archives, but don't remember wher= e > (I seem to remember Tomas Vondra wrote the original, but not sure). To > start I just used types that were there already -- int, text, numeric. Th= e > latter two won't be helped by this patch, but I wanted to keep something > like that so we can see what kind of noise variation there is. I'll > probably cut text out in the future and just keep numeric for that purpos= e. > > I've attached both the script and a crude spreadsheet. I'll try to figure > out something nicer for future tests, and maybe some graphs. The > "comparison" sheet has the results side by side (min of five). There are = 6 > distributions of values: > - random > - sorted > - "almost sorted" > - reversed > - organ pipe (first half ascending, second half descending) > - rotated (sorted but then put the smallest at the end) > - random 0s/1s > > I included both "select a" and "select *" to make sure we have the recent > datum sort optimization represented. The results look pretty good for int= s > -- about the same speed up master gets going from tuple sorts to datum > sorts, and those got faster in turn also. > > Next I think I'll run microbenchmarks on int64s with the test harness you > attached earlier, and experiment with the qsort parameters a bit. > > I'm also attaching your tuplesort patch so others can see what exactly I'= m > comparing. > The patch attached does not apply cleanly, please can fix it? error: patch failed: src/backend/utils/sort/tuplesort.c:4776 error: src/backend/utils/sort/tuplesort.c: patch does not apply regards, Ranier Vilela --000000000000bfb5d705c855c875 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Em qui., 29 de jul. de 2021 =C3=A0s 21:34, John Naylor <john.naylor@enterprisedb.com&g= t; escreveu:

On Sun, Jul 4, 2021 at 12:27 AM Thomas Munro <thomas.munro@gmail.com= > wrote:
>
> Since you are experimenting with tuplesort = and likely thinking similar
> thoughts, here's a patch I've b= een using to explore that area.=C2=A0 I've
> seen it get, for exa= mple, ~1.18x speedup for simple index builds in
> favourable winds (Y= MMV, early hacking results only).=C2=A0 Currently, it
> kicks in when= the leading column is of type int4, int8, timestamp,
> timestamptz, = date or text + friends (when abbreviatable, currently
> that means &q= uot;C" and ICU collations only), while increasing the
> executab= le by only 8.5kB (Clang, amd64, -O2, no debug).
>
> These types= are handled with just three specialisations.=C2=A0 Their custom
> &q= uot;fast" comparators all boiled down to comparisons of datum bits,> varying only in signedness and width, so I tried throwing them away> and using 3 new common routines.=C2=A0 Then I extended
> tuple= sort_sort_memtuples()'s pre-existing specialisation dispatch to
>= recognise qualifying users of those and select 3 corresponding sort
>= ; specialisations.

I got around to getting a benchmark together to s= erve as a starting point. I based it off something I got from the archives,= but don't remember where (I seem to remember Tomas Vondra wrote the=C2= =A0original, but not sure). To start I just used types that were there alre= ady -- int, text, numeric. The latter two won't be helped by this patch= , but I wanted to keep something like that so we can see what kind of noise= variation there is. I'll probably cut text out in the future and just = keep numeric for that purpose.

I've attached both th= e script and a crude spreadsheet. I'll try to figure out something nice= r for future tests, and maybe some graphs. The "comparison" sheet= has the results side by side (min of five). There are 6 distributions of v= alues:
- random
- sorted
- "almost sorte= d"
- reversed
- organ pipe (first half ascending, = second half descending)
- rotated (sorted but then put the smalle= st at the end)
- random 0s/1s

I included= both "select a" and "select *" to make sure we have th= e recent datum sort optimization represented. The results look pretty good = for ints -- about the same speed up master gets going from tuple sorts to d= atum sorts, and those got faster in turn also.

Nex= t I think I'll run microbenchmarks on int64s with the test harness you = attached earlier, and experiment with the qsort parameters a bit.

I&= #39;m also attaching your tuplesort patch so others can see what exactly I&= #39;m comparing.
The patch attached does n= ot apply cleanly,
please can fix it?

err= or: patch failed: src/backend/utils/sort/tuplesort.c:4776
error: src/bac= kend/utils/sort/tuplesort.c: patch does not apply

= regards,
Ranier Vilela
--000000000000bfb5d705c855c875--