From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-ej1-x62f.google.com (mail-ej1-x62f.google.com [IPv6:2a00:1450:4864:20::62f]) by sourceware.org (Postfix) with ESMTPS id 211CE3857BAA for ; Sat, 3 Sep 2022 03:31:50 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 211CE3857BAA Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com Received: by mail-ej1-x62f.google.com with SMTP id qh18so7204645ejb.7 for ; Fri, 02 Sep 2022 20:31:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:from:to:cc:subject:date; bh=0u3wwhMHjq6a7Af8/MQeo5U81wYaqhvqmCaXL1SHhLI=; b=H9moK3RlMl3Jw1HzwzXf7MVxxRVopn1cUWymJ+9WIdlOaZSJVkE07xc9hs2F+6KMGH hMD1iGEoKsTk2lU/gWYVeCjVwRNZVsYqG7zfwMF6+x8ilPtDpG5VyJD+4lWRjWivclvM GRQM0TLQEABMzdqVvqjJQ61iXT1sW6jVXvW4IeCurfYTrWlFGAhGtUUtG7t6xvM6uPKY HPFqeAR54ZDf+vm0JGblPFdygnVljkTKBpC0mIIEk4mmQ1UsGvL5W5DNzxrg8ixcjSy8 liATu6t0uDk0yUC3Ndm3TRuYlmmgg4tnwjIaCruA0kcVKkSBM7QWRHUalmU/BLl2Y8lh yrFQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date; bh=0u3wwhMHjq6a7Af8/MQeo5U81wYaqhvqmCaXL1SHhLI=; b=fJfhvl6/OmUvPiyqSBpR2AlRUffksDzftdgtVNDgTVpoG4+2+fcD1i1DwCZtsW7LN0 TFhhr9Zd48b14ZShmJZctStebybvswTY7WC7N6ioqeyXPTdNj0bteiBJuh8a2zaUSZMe 9EDYUDARdAntGpV9KGcWRJxrfx63z64tHFq4fe3OvopSARr7zWY2PZN87ufgCuZxTVKk GrXofvoAAHnCz5vSNzSC04Xd4Gehynzu2gjAznCt9JU1CPRJRWcgIh4tvLPlwVA4y95A k4Gh1HI7J/6jBWxwmD72S9ZhvzRAQBu/xV+FgTaQpXjMU9+p3hEibVsNSq0Nw+8L9zg9 Z3VA== X-Gm-Message-State: ACgBeo1vwyWCuuWKlWivTIxW4cwTlug+9wh2gfzjAjHAPmteLUqNWN4K O9DD/+O0iNEG04yu4BhZIpcrFklFsuG3KBcgxMAkuAqN X-Google-Smtp-Source: AA6agR6izrPGgbxZXKQO+0K8k1joppwQaOEo6B2esPT84HWpdSZbtQXVNVQD6NXeNIxkAgKWs1EjhsX+kdDvPnOh+MM= X-Received: by 2002:a17:906:eeca:b0:730:6880:c397 with SMTP id wu10-20020a170906eeca00b007306880c397mr28763364ejb.593.1662175908709; Fri, 02 Sep 2022 20:31:48 -0700 (PDT) MIME-Version: 1.0 References: <20220902203940.2385967-1-adhemerval.zanella@linaro.org> <20220902203940.2385967-10-adhemerval.zanella@linaro.org> In-Reply-To: <20220902203940.2385967-10-adhemerval.zanella@linaro.org> From: Noah Goldstein Date: Fri, 2 Sep 2022 20:31:37 -0700 Message-ID: Subject: Re: [PATCH 09/17] string: Improve generic strcmp To: Adhemerval Zanella Cc: GNU C Library , Richard Henderson , Joseph Myers , caiyinyu Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-9.8 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,KAM_SHORT,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: On Fri, Sep 2, 2022 at 1:41 PM Adhemerval Zanella via Libc-alpha wrote: > > New generic implementation tries to use word operations along with > the new string-fz{b,i} functions even for inputs with different > alignments (with still uses aligned access plus merge operation > to get a correct word by word comparison). > > Checked on x86_64-linux-gnu, i686-linux-gnu, powerpc64-linux-gnu, > and powerpc-linux-gnu by removing the arch-specific assembly > implementation and disabling multi-arch (it covers both LE and BE > for 64 and 32 bits). > > Co-authored-by: Richard Henderson > --- > string/strcmp.c | 117 +++++++++++++++++++++++++++++++++++++++++------- > 1 file changed, 101 insertions(+), 16 deletions(-) > > diff --git a/string/strcmp.c b/string/strcmp.c > index d4962be4ec..c8acc5c0b5 100644 > --- a/string/strcmp.c > +++ b/string/strcmp.c > @@ -15,33 +15,118 @@ > License along with the GNU C Library; if not, see > . */ > > +#include > +#include > +#include > +#include > #include > +#include > > -#undef strcmp > - > -#ifndef STRCMP > -# define STRCMP strcmp > +#ifdef STRCMP > +# define strcmp STRCMP > #endif > > +static inline int > +final_cmp (const op_t w1, const op_t w2) > +{ > + unsigned char c1, c2; > + for (size_t i = 0; i < sizeof (op_t); i++) > + { > + c1 = extractbyte (w1, i); > + c2 = extractbyte (w2, i); Is using extractbyte here better than just reloading indicices from memory? As well, maybe (for 64 bit atleast) maybe worth cutting in half with a 32-bit xor on the lower half then maybe skipping forward 4-bytes. > + if (c1 == '\0' || c1 != c2) > + return c1 - c2; > + } > + return c1 - c2; > +} > + > +/* Aligned loop: if a difference is found, exit to compare the bytes. Else > + if a zero is found we have equal strings. */ > +static inline int > +strcmp_aligned_loop (const op_t *x1, const op_t *x2, op_t w1) > +{ > + op_t w2 = *x2++; > + > + while (w1 == w2) > + { > + if (has_zero (w1)) > + return 0; > + w1 = *x1++; > + w2 = *x2++; > + } > + > + return final_cmp (w1, w2); > +} > + > +/* Unaligned loop: align the first partial of P2, with 0xff for the rest of > + the bytes so that we can also apply the has_zero test to see if we have > + already reached EOS. If we have, then we can simply fall through to the > + final comparison. */ > +static inline int > +strcmp_unaligned_loop (const op_t *x1, const op_t *x2, op_t w1, uintptr_t ofs) > +{ > + op_t w2a = *x2++; > + uintptr_t sh_1 = ofs * CHAR_BIT; > + uintptr_t sh_2 = sizeof(op_t) * CHAR_BIT - sh_1; > + > + op_t w2 = MERGE (w2a, sh_1, (op_t)-1, sh_2); > + if (!has_zero (w2)) > + { > + op_t w2b; > + > + /* Unaligned loop. The invariant is that W2B, which is "ahead" of W1, > + does not contain end-of-string. Therefore it is safe (and necessary) > + to read another word from each while we do not have a difference. */ > + while (1) > + { > + w2b = *x2++; > + w2 = MERGE (w2a, sh_1, w2b, sh_2); > + if (w1 != w2) > + return final_cmp (w1, w2); > + if (has_zero (w2b)) > + break; > + w1 = *x1++; > + w2a = w2b; > + } > + > + /* Zero found in the second partial of P2. If we had EOS in the aligned > + word, we have equality. */ > + if (has_zero (w1)) > + return 0; > + > + /* Load the final word of P1 and align the final partial of P2. */ > + w1 = *x1++; > + w2 = MERGE (w2b, sh_1, 0, sh_2); > + } > + > + return final_cmp (w1, w2); > +} > + > /* Compare S1 and S2, returning less than, equal to or > greater than zero if S1 is lexicographically less than, > equal to or greater than S2. */ > int > -STRCMP (const char *p1, const char *p2) > +strcmp (const char *p1, const char *p2) > { > - const unsigned char *s1 = (const unsigned char *) p1; > - const unsigned char *s2 = (const unsigned char *) p2; > - unsigned char c1, c2; > - > - do > + /* Handle the unaligned bytes of p1 first. */ > + uintptr_t n = -(uintptr_t)p1 % sizeof(op_t); > + for (int i = 0; i < n; ++i) > { > - c1 = (unsigned char) *s1++; > - c2 = (unsigned char) *s2++; > - if (c1 == '\0') > - return c1 - c2; > + unsigned char c1 = *p1++; > + unsigned char c2 = *p2++; > + int diff = c1 - c2; > + if (c1 == '\0' || diff != 0) > + return diff; > } > - while (c1 == c2); > > - return c1 - c2; > + /* P1 is now aligned to unsigned long. P2 may or may not be. */ > + const op_t *x1 = (const op_t *) p1; > + op_t w1 = *x1++; > + uintptr_t ofs = (uintptr_t) p2 % sizeof(op_t); > + return ofs == 0 > + ? strcmp_aligned_loop (x1, (const op_t *)p2, w1) > + : strcmp_unaligned_loop (x1, (const op_t *)(p2 - ofs), w1, ofs); > } > +#ifndef STRCMP > libc_hidden_builtin_def (strcmp) > +#endif > -- > 2.34.1 >