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 1oRSbR-0007UN-3w for pgsql-hackers@arkaria.postgresql.org; Fri, 26 Aug 2022 06:14:01 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1oRSbP-0007zb-3h for pgsql-hackers@arkaria.postgresql.org; Fri, 26 Aug 2022 06:13:59 +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 1oRSbO-0007xz-Fl for pgsql-hackers@lists.postgresql.org; Fri, 26 Aug 2022 06:13:58 +0000 Received: from mail-pg1-x52e.google.com ([2607:f8b0:4864:20::52e]) by makus.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.92) (envelope-from ) id 1oRSbH-0002z5-7Z for pgsql-hackers@postgresql.org; Fri, 26 Aug 2022 06:13:57 +0000 Received: by mail-pg1-x52e.google.com with SMTP id v4so527764pgi.10 for ; Thu, 25 Aug 2022 23:13:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:from:to:cc; bh=Vs+9G0SHpWSmDuGqBMaPKLoM41kb0MFWOWqVgS1AUeY=; b=MrjJfC9uaX0AeZoLJwfbWdACphfWCszMnkd2MEilfSudzdwjPMw/95lsiu/SD7rxpC kMp9aecLsQJxTdHSKyHEx7sYJet0OMBBwPGeUsjjPTmY0aQ2ZF9OT22Lwf7adxD6Qk4B OSkkqlQMwa+fGESD4S5BynsLg28zutWr7/6sctNqC8ukLfVY334RFXWLnTr8xpe6f1/y 4mDM2JlmiKFq0aYz73YGjfwrDqUxN9i1ISsQSWSRmb2DK5vklcAR4hjgAtDKkSLAvmmk CKsJoGSjQv/+gz5Q6zni9nssxmwA2/PEovrUmS4I/l1zvx/bKhG4FufnJ7ED4U6970Bb BoFw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=in-reply-to:content-disposition:mime-version:references:message-id :subject:cc:to:from:date:x-gm-message-state:from:to:cc; bh=Vs+9G0SHpWSmDuGqBMaPKLoM41kb0MFWOWqVgS1AUeY=; b=Hy/Q+hIYNRjTPKHvWaO5fGGX828Poq5Gk1KiA26cJmsRYerPAZaxCvuNRlWgm2z6sf +vCXCxGrYinZYvmSLD30b5hmVVNLtZpsPKY2CxwCOxKJZTb7Ht2sYwYqh7RKeLKf+k2E tyteVWVBXQlMVaNeOeXxdxe3SF+lvUs6RM4gAULaC8C+noCYM22evW1M2BisxMe6T2AN FjC+TpU4VdT8OkUY8nG+iUmGMs3c+CzegKPVUQK2caG0y1kT4svcbD/AaHf4imPhQ7Py VMDrr5uhiwrVog30IQk0kjW4saduUcfAqa39XO5mxQLEgGDIAUuq6FFHMYFol+iFivlW Hatw== X-Gm-Message-State: ACgBeo2yeYCXkNBY+Xvg78dDHMg07f0e3ORF39/cq43nMQLhmdbPTJMI 5GKBrpgQFvvWLoDQQLf1Www= X-Google-Smtp-Source: AA6agR4bBIGOGiI7s4ZGbz3JseeMR/EZuBFKg/F4GoXbXdwbFEMVDYaNeGzDs1YjjwRKqUhqLdqtaw== X-Received: by 2002:aa7:990c:0:b0:536:8d21:8b9b with SMTP id z12-20020aa7990c000000b005368d218b9bmr2331865pff.49.1661494430146; Thu, 25 Aug 2022 23:13:50 -0700 (PDT) Received: from nathanxps13 ([50.47.162.83]) by smtp.gmail.com with ESMTPSA id b10-20020a170903228a00b001728eb339e2sm626954plh.286.2022.08.25.23.13.48 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Thu, 25 Aug 2022 23:13:49 -0700 (PDT) Date: Thu, 25 Aug 2022 23:13:47 -0700 From: Nathan Bossart To: John Naylor Cc: Andres Freund , pgsql-hackers Subject: Re: use ARM intrinsics in pg_lfind32() where available Message-ID: <20220826061347.GA1777731@nathanxps13> References: <20220819212602.brjkd6ppgbohvo6g@awork3.anarazel.de> <20220819222814.GA401294@nathanxps13> <20220822211547.GA1126462@nathanxps13> <20220824180111.GB1302810@nathanxps13> <20220825045729.GA1458024@nathanxps13> <20220826045115.GA1638993@nathanxps13> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="Nq2Wo0NMKNjxTN9z" Content-Disposition: inline In-Reply-To: <20220826045115.GA1638993@nathanxps13> List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --Nq2Wo0NMKNjxTN9z Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Here is a new patch set that applies on top of v9-0001 in the json_lex_string patch set [0] and v3 of the is_valid_ascii patch [1]. [0] https://postgr.es/m/CAFBsxsFV4v802idV0-Bo%3DV7wLMHRbOZ4er0hgposhyGCikmVGA%40mail.gmail.com [1] https://postgr.es/m/CAFBsxsFFAZ6acUfyUALiem4DpCW%3DApXbF02zrc0G0oT9CPof0Q%40mail.gmail.com -- Nathan Bossart Amazon Web Services: https://aws.amazon.com --Nq2Wo0NMKNjxTN9z Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v3-0001-abstract-architecture-specific-implementation-det.patch" From 5f973a39d67a744d514ee80e05a1c7f40bc0ebc6 Mon Sep 17 00:00:00 2001 From: Nathan Bossart Date: Thu, 25 Aug 2022 22:18:30 -0700 Subject: [PATCH v3 1/2] abstract architecture-specific implementation details from pg_lfind32() --- src/include/port/pg_lfind.h | 55 ++++++++++++++++++---------------- src/include/port/simd.h | 60 +++++++++++++++++++++++++++++++++++++ 2 files changed, 90 insertions(+), 25 deletions(-) diff --git a/src/include/port/pg_lfind.h b/src/include/port/pg_lfind.h index a4e13dffec..7a851ea42c 100644 --- a/src/include/port/pg_lfind.h +++ b/src/include/port/pg_lfind.h @@ -91,16 +91,19 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem) { uint32 i = 0; -#ifdef USE_SSE2 +#ifndef USE_NO_SIMD /* - * A 16-byte register only has four 4-byte lanes. For better - * instruction-level parallelism, each loop iteration operates on a block - * of four registers. Testing has showed this is ~40% faster than using a - * block of two registers. + * For better instruction-level parallelism, each loop iteration operates + * on a block of four registers. Testing for SSE2 has showed this is ~40% + * faster than using a block of two registers. */ - const __m128i keys = _mm_set1_epi32(key); /* load 4 copies of key */ - uint32 iterations = nelem & ~0xF; /* round down to multiple of 16 */ + const Vector32 keys = vector32_broadcast(key); /* load copies of key */ + uint32 nelem_per_vector = sizeof(Vector32) / sizeof(uint32); + uint32 nelem_per_iteration = 4 * nelem_per_vector; + + /* round down to multiple of elements per iteration */ + uint32 tail_idx = nelem & ~(nelem_per_iteration - 1); #if defined(USE_ASSERT_CHECKING) bool assert_result = false; @@ -116,31 +119,33 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem) } #endif - for (i = 0; i < iterations; i += 16) + for (i = 0; i < tail_idx; i += nelem_per_iteration) { - /* load the next block into 4 registers holding 4 values each */ - const __m128i vals1 = _mm_loadu_si128((__m128i *) & base[i]); - const __m128i vals2 = _mm_loadu_si128((__m128i *) & base[i + 4]); - const __m128i vals3 = _mm_loadu_si128((__m128i *) & base[i + 8]); - const __m128i vals4 = _mm_loadu_si128((__m128i *) & base[i + 12]); + Vector32 vals1, vals2, vals3, vals4, + result1, result2, result3, result4, + tmp1, tmp2, result; + + /* load the next block into 4 registers */ + vector32_load(&vals1, &base[i]); + vector32_load(&vals2, &base[i + nelem_per_vector]); + vector32_load(&vals3, &base[i + nelem_per_vector * 2]); + vector32_load(&vals4, &base[i + nelem_per_vector * 3]); /* compare each value to the key */ - const __m128i result1 = _mm_cmpeq_epi32(keys, vals1); - const __m128i result2 = _mm_cmpeq_epi32(keys, vals2); - const __m128i result3 = _mm_cmpeq_epi32(keys, vals3); - const __m128i result4 = _mm_cmpeq_epi32(keys, vals4); + result1 = vector32_eq(keys, vals1); + result2 = vector32_eq(keys, vals2); + result3 = vector32_eq(keys, vals3); + result4 = vector32_eq(keys, vals4); /* combine the results into a single variable */ - const __m128i tmp1 = _mm_or_si128(result1, result2); - const __m128i tmp2 = _mm_or_si128(result3, result4); - const __m128i result = _mm_or_si128(tmp1, tmp2); + tmp1 = vector32_or(result1, result2); + tmp2 = vector32_or(result3, result4); + result = vector32_or(tmp1, tmp2); /* see if there was a match */ - if (_mm_movemask_epi8(result) != 0) + if (vector32_any_lane_set(result)) { -#if defined(USE_ASSERT_CHECKING) Assert(assert_result == true); -#endif return true; } } @@ -151,14 +156,14 @@ pg_lfind32(uint32 key, uint32 *base, uint32 nelem) { if (key == base[i]) { -#if defined(USE_SSE2) && defined(USE_ASSERT_CHECKING) +#ifndef USE_NO_SIMD Assert(assert_result == true); #endif return true; } } -#if defined(USE_SSE2) && defined(USE_ASSERT_CHECKING) +#ifndef USE_NO_SIMD Assert(assert_result == false); #endif return false; diff --git a/src/include/port/simd.h b/src/include/port/simd.h index 8f85153110..bd4f1a3f39 100644 --- a/src/include/port/simd.h +++ b/src/include/port/simd.h @@ -32,6 +32,7 @@ #include #define USE_SSE2 typedef __m128i Vector8; +typedef __m128i Vector32; #else /* @@ -40,18 +41,24 @@ typedef __m128i Vector8; */ #define USE_NO_SIMD typedef uint64 Vector8; +typedef uint64 Vector32; #endif static inline void vector8_load(Vector8 *v, const uint8 *s); +static inline void vector32_load(Vector32 *v, const uint32 *s); static inline Vector8 vector8_broadcast(const uint8 c); +static inline Vector32 vector32_broadcast(const uint32 c); static inline bool vector8_has_zero(const Vector8 v); static inline bool vector8_has(const Vector8 v, const uint8 c); static inline bool vector8_has_le(const Vector8 v, const uint8 c); static inline bool vector8_is_highbit_set(const Vector8 v); static inline Vector8 vector8_or(const Vector8 v1, const Vector8 v2); +static inline Vector32 vector32_or(const Vector32 v1, const Vector32 v2); #ifndef USE_NO_SIMD static inline Vector8 vector8_eq(const Vector8 v1, const Vector8 v2); +static inline Vector32 vector32_eq(const Vector32 v1, const Vector32 v2); +static inline bool vector32_any_lane_set(const Vector32 v); #endif /* @@ -68,6 +75,16 @@ vector8_load(Vector8 *v, const uint8 *s) #endif } +static inline void +vector32_load(Vector32 *v, const uint32 *s) +{ +#ifdef USE_SSE2 + *v = _mm_loadu_si128((const __m128i *) s); +#else + memcpy(v, s, sizeof(Vector32)); +#endif +} + /* * Functions for creating a vector with all elements set to the same value. @@ -83,6 +100,16 @@ vector8_broadcast(const uint8 c) #endif } +static inline Vector32 +vector32_broadcast(const uint32 c) +{ +#ifdef USE_SSE2 + return _mm_set1_epi32(c); +#else + return ~UINT64CONST(0) / 0xFFFFFFFF * c; +#endif +} + /* * Functions for comparing vector elements to a given value. @@ -196,6 +223,21 @@ vector8_is_highbit_set(const Vector8 v) #endif } +/* + * vector32_any_lane_set() assumes that each lane in the given vector is set to + * either all ones or all zeroes. If this is not true, its behavior is + * undefined. + */ +#ifndef USE_NO_SIMD +static inline bool +vector32_any_lane_set(const Vector32 v) +{ +#ifdef USE_SSE2 + return _mm_movemask_epi8(v) != 0; +#endif +} +#endif + /* comparisons between vectors */ #ifndef USE_NO_SIMD @@ -206,6 +248,14 @@ vector8_eq(const Vector8 v1, const Vector8 v2) return _mm_cmpeq_epi8(v1, v2); #endif } + +static inline Vector32 +vector32_eq(const Vector32 v1, const Vector32 v2) +{ +#ifdef USE_SSE2 + return _mm_cmpeq_epi32(v1, v2); +#endif +} #endif /* bitwise operations */ @@ -220,4 +270,14 @@ vector8_or(const Vector8 v1, const Vector8 v2) #endif } +static inline Vector32 +vector32_or(const Vector32 v1, const Vector32 v2) +{ +#ifdef USE_SSE2 + return _mm_or_si128(v1, v2); +#else + return v1 | v2; +#endif +} + #endif /* SIMD_H */ -- 2.25.1 --Nq2Wo0NMKNjxTN9z Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v3-0002-use-ARM-Advanced-SIMD-intrinsic-functions-where-a.patch" From be7a5be891050330556f950731889d5c352ce58c Mon Sep 17 00:00:00 2001 From: Nathan Bossart Date: Thu, 25 Aug 2022 22:59:12 -0700 Subject: [PATCH v3 2/2] use ARM Advanced SIMD intrinsic functions where available --- src/include/port/simd.h | 46 +++++++++++++++++++++++++++++++++++++++-- 1 file changed, 44 insertions(+), 2 deletions(-) diff --git a/src/include/port/simd.h b/src/include/port/simd.h index bd4f1a3f39..839c0f25db 100644 --- a/src/include/port/simd.h +++ b/src/include/port/simd.h @@ -34,6 +34,19 @@ typedef __m128i Vector8; typedef __m128i Vector32; +/* + * Include arm_neon.h if the compiler is targeting an architecture that + * supports ARM Advanced SIMD (Neon) intrinsics. While Neon support is + * technically optional for aarch64, we assume it's unlikely that anyone will + * run PostgreSQL on specialized hardware lacking this feature, and we assume + * that compilers targeting this architecture understand Neon intrinsics. + */ +#elif defined(__aarch64__) +#include +#define USE_NEON +typedef uint8x16_t Vector8; +typedef uint32x4_t Vector32; + #else /* * If no SIMD instructions are available, we can in some cases emulate vector @@ -70,6 +83,8 @@ vector8_load(Vector8 *v, const uint8 *s) { #ifdef USE_SSE2 *v = _mm_loadu_si128((const __m128i *) s); +#elif USE_NEON + *v = vld1q_u8(s); #else memcpy(v, s, sizeof(Vector8)); #endif @@ -80,6 +95,8 @@ vector32_load(Vector32 *v, const uint32 *s) { #ifdef USE_SSE2 *v = _mm_loadu_si128((const __m128i *) s); +#elif USE_NEON + *v = vld1q_u32(s); #else memcpy(v, s, sizeof(Vector32)); #endif @@ -95,6 +112,8 @@ vector8_broadcast(const uint8 c) { #ifdef USE_SSE2 return _mm_set1_epi8(c); +#elif USE_NEON + return vdupq_n_u8(c); #else return ~UINT64CONST(0) / 0xFF * c; #endif @@ -105,6 +124,8 @@ vector32_broadcast(const uint32 c) { #ifdef USE_SSE2 return _mm_set1_epi32(c); +#elif USE_NEON + return vdupq_n_u32(c); #else return ~UINT64CONST(0) / 0xFFFFFFFF * c; #endif @@ -120,6 +141,8 @@ vector8_has_zero(const Vector8 v) { #ifdef USE_SSE2 return _mm_movemask_epi8(_mm_cmpeq_epi8(v, _mm_setzero_si128())); +#elif USE_NEON + return vmaxvq_u8(vceqzq_u8(v)) != 0; #else return vector8_has_le(v, 0); #endif @@ -146,6 +169,8 @@ vector8_has(const Vector8 v, const uint8 c) #ifdef USE_SSE2 result = _mm_movemask_epi8(_mm_cmpeq_epi8(v, vector8_broadcast(c))); +#elif USE_NEON + result = vmaxvq_u8(vceqq_u8(v, vector8_broadcast(c))) != 0; #else /* any bytes in v equal to c will evaluate to zero via XOR */ result = vector8_has_zero(v ^ vector8_broadcast(c)); @@ -159,8 +184,8 @@ static inline bool vector8_has_le(const Vector8 v, const uint8 c) { bool result = false; -#ifdef USE_SSE2 - __m128i sub; +#ifndef USE_NO_SIMD + Vector8 sub; #endif /* pre-compute the result for assert checking */ @@ -185,6 +210,11 @@ vector8_has_le(const Vector8 v, const uint8 c) */ sub = _mm_subs_epu8(v, vector8_broadcast(c)); result = vector8_has_zero(sub); +#elif USE_NEON + + /* use the same approach as the USE_SSE2 block above */ + sub = vqsubq_u8(v, vector8_broadcast(c)); + result = vector8_has_zero(sub); #else /* @@ -218,6 +248,8 @@ vector8_is_highbit_set(const Vector8 v) { #ifdef USE_SSE2 return _mm_movemask_epi8(v) != 0; +#elif USE_NEON + return vmaxvq_u8(vandq_u8(v, vector8_broadcast(0x80))) != 0; #else return v & vector8_broadcast(0x80); #endif @@ -234,6 +266,8 @@ vector32_any_lane_set(const Vector32 v) { #ifdef USE_SSE2 return _mm_movemask_epi8(v) != 0; +#elif USE_NEON + return vmaxvq_u32(v) != 0; #endif } #endif @@ -246,6 +280,8 @@ vector8_eq(const Vector8 v1, const Vector8 v2) { #ifdef USE_SSE2 return _mm_cmpeq_epi8(v1, v2); +#elif USE_NEON + return vceqq_u8(v1, v2); #endif } @@ -254,6 +290,8 @@ vector32_eq(const Vector32 v1, const Vector32 v2) { #ifdef USE_SSE2 return _mm_cmpeq_epi32(v1, v2); +#elif USE_NEON + return vceqq_u32(v1, v2); #endif } #endif @@ -265,6 +303,8 @@ vector8_or(const Vector8 v1, const Vector8 v2) { #ifdef USE_SSE2 return _mm_or_si128(v1, v2); +#elif USE_NEON + return vorrq_u8(v1, v2); #else return v1 | v2; #endif @@ -275,6 +315,8 @@ vector32_or(const Vector32 v1, const Vector32 v2) { #ifdef USE_SSE2 return _mm_or_si128(v1, v2); +#elif USE_NEON + return vorrq_u32(v1, v2); #else return v1 | v2; #endif -- 2.25.1 --Nq2Wo0NMKNjxTN9z--