SIMD optimization for list_sort

From 8781b8feef917fdb826c520f60a9556c678025cc Mon Sep 17 00:00:00 2001
From: "R, Rakshit" <rakshit.r@intel.com>
Date: Thu, 1 Aug 2024 11:16:58 +0530
Subject: [PATCH v1] Add list_sort implementation based on x86-simd-sort
 library

---
 configure                                     | 228 ++++++++++++++-
 configure.ac                                  |  31 ++
 meson.build                                   |  24 ++
 meson_options.txt                             |   6 +
 src/backend/nodes/list.c                      | 219 ++++++++++++++
 src/include/nodes/pg_list.h                   |   2 +
 src/include/pg_config.h.in                    |   6 +
 src/test/modules/Makefile                     |   1 +
 src/test/modules/test_listsort/.gitignore     |   4 +
 src/test/modules/test_listsort/Makefile       |  23 ++
 src/test/modules/test_listsort/README         |  10 +
 .../test_listsort/expected/test_listsort.out  |  13 +
 .../test_listsort/sql/test_listsort.sql       |   4 +
 .../test_listsort/test_listsort--1.0.sql      |   9 +
 .../modules/test_listsort/test_listsort.c     | 210 ++++++++++++++
 .../test_listsort/test_listsort.control       |   5 +
 src/test/regress/expected/list_sort_simd.out  |  87 ++++++
 src/test/regress/parallel_schedule            |   2 +-
 src/test/regress/regress.c                    | 266 ++++++++++++++++++
 src/test/regress/sql/list_sort_simd.sql       |  32 +++
 src/tools/pgindent/typedefs.list              |   1 +
 21 files changed, 1176 insertions(+), 7 deletions(-)
 create mode 100644 src/test/modules/test_listsort/.gitignore
 create mode 100644 src/test/modules/test_listsort/Makefile
 create mode 100644 src/test/modules/test_listsort/README
 create mode 100644 src/test/modules/test_listsort/expected/test_listsort.out
 create mode 100644 src/test/modules/test_listsort/sql/test_listsort.sql
 create mode 100644 src/test/modules/test_listsort/test_listsort--1.0.sql
 create mode 100644 src/test/modules/test_listsort/test_listsort.c
 create mode 100644 src/test/modules/test_listsort/test_listsort.control
 create mode 100644 src/test/regress/expected/list_sort_simd.out
 create mode 100644 src/test/regress/sql/list_sort_simd.sql

diff --git a/configure b/configure
index ceeef9b0915..336de2f6adb 100755
--- a/configure
+++ b/configure
@@ -701,6 +701,9 @@ with_zstd
 LZ4_LIBS
 LZ4_CFLAGS
 with_lz4
+SIMDSORT_LIBS
+SIMDSORT_CFLAGS
+with_simdsort
 with_zlib
 with_system_tzdata
 with_libxslt
@@ -803,6 +806,7 @@ infodir
 docdir
 oldincludedir
 includedir
+runstatedir
 localstatedir
 sharedstatedir
 sysconfdir
@@ -868,6 +872,7 @@ with_libxml
 with_libxslt
 with_system_tzdata
 with_zlib
+with_simdsort
 with_lz4
 with_zstd
 with_ssl
@@ -897,6 +902,8 @@ ICU_LIBS
 XML2_CONFIG
 XML2_CFLAGS
 XML2_LIBS
+SIMDSORT_CFLAGS
+SIMDSORT_LIBS
 LZ4_CFLAGS
 LZ4_LIBS
 ZSTD_CFLAGS
@@ -945,6 +952,7 @@ datadir='${datarootdir}'
 sysconfdir='${prefix}/etc'
 sharedstatedir='${prefix}/com'
 localstatedir='${prefix}/var'
+runstatedir='${localstatedir}/run'
 includedir='${prefix}/include'
 oldincludedir='/usr/include'
 docdir='${datarootdir}/doc/${PACKAGE_TARNAME}'
@@ -1197,6 +1205,15 @@ do
   | -silent | --silent | --silen | --sile | --sil)
     silent=yes ;;
 
+  -runstatedir | --runstatedir | --runstatedi | --runstated \
+  | --runstate | --runstat | --runsta | --runst | --runs \
+  | --run | --ru | --r)
+    ac_prev=runstatedir ;;
+  -runstatedir=* | --runstatedir=* | --runstatedi=* | --runstated=* \
+  | --runstate=* | --runstat=* | --runsta=* | --runst=* | --runs=* \
+  | --run=* | --ru=* | --r=*)
+    runstatedir=$ac_optarg ;;
+
   -sbindir | --sbindir | --sbindi | --sbind | --sbin | --sbi | --sb)
     ac_prev=sbindir ;;
   -sbindir=* | --sbindir=* | --sbindi=* | --sbind=* | --sbin=* \
@@ -1334,7 +1351,7 @@ fi
 for ac_var in	exec_prefix prefix bindir sbindir libexecdir datarootdir \
 		datadir sysconfdir sharedstatedir localstatedir includedir \
 		oldincludedir docdir infodir htmldir dvidir pdfdir psdir \
-		libdir localedir mandir
+		libdir localedir mandir runstatedir
 do
   eval ac_val=\$$ac_var
   # Remove trailing slashes.
@@ -1487,6 +1504,7 @@ Fine tuning of the installation directories:
   --sysconfdir=DIR        read-only single-machine data [PREFIX/etc]
   --sharedstatedir=DIR    modifiable architecture-independent data [PREFIX/com]
   --localstatedir=DIR     modifiable single-machine data [PREFIX/var]
+  --runstatedir=DIR       modifiable per-process data [LOCALSTATEDIR/run]
   --libdir=DIR            object code libraries [EPREFIX/lib]
   --includedir=DIR        C header files [PREFIX/include]
   --oldincludedir=DIR     C header files for non-gcc [/usr/include]
@@ -1579,6 +1597,7 @@ Optional Packages:
   --with-system-tzdata=DIR
                           use system time zone data in DIR
   --without-zlib          do not use Zlib
+  --with-simdsort         build with SIMDSORT support
   --with-lz4              build with LZ4 support
   --with-zstd             build with ZSTD support
   --with-ssl=LIB          use LIB for SSL/TLS support (openssl)
@@ -1610,6 +1629,10 @@ Some influential environment variables:
   XML2_CONFIG path to xml2-config utility
   XML2_CFLAGS C compiler flags for XML2, overriding pkg-config
   XML2_LIBS   linker flags for XML2, overriding pkg-config
+  SIMDSORT_CFLAGS
+              C compiler flags for SIMDSORT, overriding pkg-config
+  SIMDSORT_LIBS
+              linker flags for SIMDSORT, overriding pkg-config
   LZ4_CFLAGS  C compiler flags for LZ4, overriding pkg-config
   LZ4_LIBS    linker flags for LZ4, overriding pkg-config
   ZSTD_CFLAGS C compiler flags for ZSTD, overriding pkg-config
@@ -9036,6 +9059,147 @@ fi
 
 
 
+#
+# SIMDSORT
+#
+{ $as_echo "$as_me:${as_lineno-$LINENO}: checking whether to build with SIMDSORT support" >&5
+$as_echo_n "checking whether to build with SIMDSORT support... " >&6; }
+
+
+
+# Check whether --with-simdsort was given.
+if test "${with_simdsort+set}" = set; then :
+  withval=$with_simdsort;
+  case $withval in
+    yes)
+
+$as_echo "#define USE_SIMDSORT 1" >>confdefs.h
+
+      ;;
+    no)
+      :
+      ;;
+    *)
+      as_fn_error $? "no argument expected for --with-simdsort option" "$LINENO" 5
+      ;;
+  esac
+
+else
+  with_simdsort=no
+
+fi
+
+
+{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $with_simdsort" >&5
+$as_echo "$with_simdsort" >&6; }
+
+
+if test "$with_simdsort" = yes; then
+
+pkg_failed=no
+{ $as_echo "$as_me:${as_lineno-$LINENO}: checking for x86simdsortcpp" >&5
+$as_echo_n "checking for x86simdsortcpp... " >&6; }
+
+if test -n "$SIMDSORT_CFLAGS"; then
+    pkg_cv_SIMDSORT_CFLAGS="$SIMDSORT_CFLAGS"
+ elif test -n "$PKG_CONFIG"; then
+    if test -n "$PKG_CONFIG" && \
+    { { $as_echo "$as_me:${as_lineno-$LINENO}: \$PKG_CONFIG --exists --print-errors \"x86simdsortcpp\""; } >&5
+  ($PKG_CONFIG --exists --print-errors "x86simdsortcpp") 2>&5
+  ac_status=$?
+  $as_echo "$as_me:${as_lineno-$LINENO}: \$? = $ac_status" >&5
+  test $ac_status = 0; }; then
+  pkg_cv_SIMDSORT_CFLAGS=`$PKG_CONFIG --cflags "x86simdsortcpp" 2>/dev/null`
+		      test "x$?" != "x0" && pkg_failed=yes
+else
+  pkg_failed=yes
+fi
+ else
+    pkg_failed=untried
+fi
+if test -n "$SIMDSORT_LIBS"; then
+    pkg_cv_SIMDSORT_LIBS="$SIMDSORT_LIBS"
+ elif test -n "$PKG_CONFIG"; then
+    if test -n "$PKG_CONFIG" && \
+    { { $as_echo "$as_me:${as_lineno-$LINENO}: \$PKG_CONFIG --exists --print-errors \"x86simdsortcpp\""; } >&5
+  ($PKG_CONFIG --exists --print-errors "x86simdsortcpp") 2>&5
+  ac_status=$?
+  $as_echo "$as_me:${as_lineno-$LINENO}: \$? = $ac_status" >&5
+  test $ac_status = 0; }; then
+  pkg_cv_SIMDSORT_LIBS=`$PKG_CONFIG --libs "x86simdsortcpp" 2>/dev/null`
+		      test "x$?" != "x0" && pkg_failed=yes
+else
+  pkg_failed=yes
+fi
+ else
+    pkg_failed=untried
+fi
+
+
+
+if test $pkg_failed = yes; then
+        { $as_echo "$as_me:${as_lineno-$LINENO}: result: no" >&5
+$as_echo "no" >&6; }
+
+if $PKG_CONFIG --atleast-pkgconfig-version 0.20; then
+        _pkg_short_errors_supported=yes
+else
+        _pkg_short_errors_supported=no
+fi
+        if test $_pkg_short_errors_supported = yes; then
+	        SIMDSORT_PKG_ERRORS=`$PKG_CONFIG --short-errors --print-errors --cflags --libs "x86simdsortcpp" 2>&1`
+        else
+	        SIMDSORT_PKG_ERRORS=`$PKG_CONFIG --print-errors --cflags --libs "x86simdsortcpp" 2>&1`
+        fi
+	# Put the nasty error message in config.log where it belongs
+	echo "$SIMDSORT_PKG_ERRORS" >&5
+
+	as_fn_error $? "Package requirements (x86simdsortcpp) were not met:
+
+$SIMDSORT_PKG_ERRORS
+
+Consider adjusting the PKG_CONFIG_PATH environment variable if you
+installed software in a non-standard prefix.
+
+Alternatively, you may set the environment variables SIMDSORT_CFLAGS
+and SIMDSORT_LIBS to avoid the need to call pkg-config.
+See the pkg-config man page for more details." "$LINENO" 5
+elif test $pkg_failed = untried; then
+        { $as_echo "$as_me:${as_lineno-$LINENO}: result: no" >&5
+$as_echo "no" >&6; }
+	{ { $as_echo "$as_me:${as_lineno-$LINENO}: error: in \`$ac_pwd':" >&5
+$as_echo "$as_me: error: in \`$ac_pwd':" >&2;}
+as_fn_error $? "The pkg-config script could not be found or is too old.  Make sure it
+is in your PATH or set the PKG_CONFIG environment variable to the full
+path to pkg-config.
+
+Alternatively, you may set the environment variables SIMDSORT_CFLAGS
+and SIMDSORT_LIBS to avoid the need to call pkg-config.
+See the pkg-config man page for more details.
+
+To get pkg-config, see <http://pkg-config.freedesktop.org/>.
+See \`config.log' for more details" "$LINENO" 5; }
+else
+	SIMDSORT_CFLAGS=$pkg_cv_SIMDSORT_CFLAGS
+	SIMDSORT_LIBS=$pkg_cv_SIMDSORT_LIBS
+        { $as_echo "$as_me:${as_lineno-$LINENO}: result: yes" >&5
+$as_echo "yes" >&6; }
+
+fi
+  # We only care about -I, -D, and -L switches;
+  # note that -lsimdsort will be added by AC_CHECK_LIB below.
+  for pgac_option in $SIMDSORT_CFLAGS; do
+    case $pgac_option in
+      -I*|-D*) CPPFLAGS="$CPPFLAGS $pgac_option";;
+    esac
+  done
+  for pgac_option in $SIMDSORT_LIBS; do
+    case $pgac_option in
+      -L*) LDFLAGS="$LDFLAGS $pgac_option";;
+    esac
+  done
+fi
+
 #
 # LZ4
 #
@@ -12753,6 +12917,56 @@ fi
 
 fi
 
+if test "$with_simdsort" = yes ; then
+  { $as_echo "$as_me:${as_lineno-$LINENO}: checking for keyvalue_qsort_float_sizet in -lx86simdsortcpp" >&5
+$as_echo_n "checking for keyvalue_qsort_float_sizet in -lx86simdsortcpp... " >&6; }
+if ${ac_cv_lib_x86simdsortcpp_keyvalue_qsort_float_sizet+:} false; then :
+  $as_echo_n "(cached) " >&6
+else
+  ac_check_lib_save_LIBS=$LIBS
+LIBS="-lx86simdsortcpp  $LIBS"
+cat confdefs.h - <<_ACEOF >conftest.$ac_ext
+/* end confdefs.h.  */
+
+/* Override any GCC internal prototype to avoid an error.
+   Use char because int might match the return type of a GCC
+   builtin and then its argument prototype would still apply.  */
+#ifdef __cplusplus
+extern "C"
+#endif
+char keyvalue_qsort_float_sizet ();
+int
+main ()
+{
+return keyvalue_qsort_float_sizet ();
+  ;
+  return 0;
+}
+_ACEOF
+if ac_fn_c_try_link "$LINENO"; then :
+  ac_cv_lib_x86simdsortcpp_keyvalue_qsort_float_sizet=yes
+else
+  ac_cv_lib_x86simdsortcpp_keyvalue_qsort_float_sizet=no
+fi
+rm -f core conftest.err conftest.$ac_objext \
+    conftest$ac_exeext conftest.$ac_ext
+LIBS=$ac_check_lib_save_LIBS
+fi
+{ $as_echo "$as_me:${as_lineno-$LINENO}: result: $ac_cv_lib_x86simdsortcpp_keyvalue_qsort_float_sizet" >&5
+$as_echo "$ac_cv_lib_x86simdsortcpp_keyvalue_qsort_float_sizet" >&6; }
+if test "x$ac_cv_lib_x86simdsortcpp_keyvalue_qsort_float_sizet" = xyes; then :
+  cat >>confdefs.h <<_ACEOF
+#define HAVE_LIBX86SIMDSORTCPP 1
+_ACEOF
+
+  LIBS="-lx86simdsortcpp $LIBS"
+
+else
+  as_fn_error $? "library 'x86simdsortcpp' is required for SIMDSORt support" "$LINENO" 5
+fi
+
+fi
+
 if test "$with_lz4" = yes ; then
   { $as_echo "$as_me:${as_lineno-$LINENO}: checking for LZ4_compress_default in -llz4" >&5
 $as_echo_n "checking for LZ4_compress_default in -llz4... " >&6; }
@@ -12854,6 +13068,8 @@ fi
 fi
 
 # Note: We can test for libldap_r only after we know PTHREAD_LIBS
+# also, on AIX, we may need to have openssl in LIBS for this step.
+
 if test "$with_ldap" = yes ; then
   _LIBS="$LIBS"
   if test "$PORTNAME" != "win32"; then
@@ -14785,7 +15001,7 @@ else
     We can't simply define LARGE_OFF_T to be 9223372036854775807,
     since some C++ compilers masquerading as C compilers
     incorrectly reject 9223372036854775807.  */
-#define LARGE_OFF_T (((off_t) 1 << 62) - 1 + ((off_t) 1 << 62))
+#define LARGE_OFF_T ((((off_t) 1 << 31) << 31) - 1 + (((off_t) 1 << 31) << 31))
   int off_t_is_large[(LARGE_OFF_T % 2147483629 == 721
 		       && LARGE_OFF_T % 2147483647 == 1)
 		      ? 1 : -1];
@@ -14831,7 +15047,7 @@ else
     We can't simply define LARGE_OFF_T to be 9223372036854775807,
     since some C++ compilers masquerading as C compilers
     incorrectly reject 9223372036854775807.  */
-#define LARGE_OFF_T (((off_t) 1 << 62) - 1 + ((off_t) 1 << 62))
+#define LARGE_OFF_T ((((off_t) 1 << 31) << 31) - 1 + (((off_t) 1 << 31) << 31))
   int off_t_is_large[(LARGE_OFF_T % 2147483629 == 721
 		       && LARGE_OFF_T % 2147483647 == 1)
 		      ? 1 : -1];
@@ -14855,7 +15071,7 @@ rm -f core conftest.err conftest.$ac_objext conftest.$ac_ext
     We can't simply define LARGE_OFF_T to be 9223372036854775807,
     since some C++ compilers masquerading as C compilers
     incorrectly reject 9223372036854775807.  */
-#define LARGE_OFF_T (((off_t) 1 << 62) - 1 + ((off_t) 1 << 62))
+#define LARGE_OFF_T ((((off_t) 1 << 31) << 31) - 1 + (((off_t) 1 << 31) << 31))
   int off_t_is_large[(LARGE_OFF_T % 2147483629 == 721
 		       && LARGE_OFF_T % 2147483647 == 1)
 		      ? 1 : -1];
@@ -14900,7 +15116,7 @@ else
     We can't simply define LARGE_OFF_T to be 9223372036854775807,
     since some C++ compilers masquerading as C compilers
     incorrectly reject 9223372036854775807.  */
-#define LARGE_OFF_T (((off_t) 1 << 62) - 1 + ((off_t) 1 << 62))
+#define LARGE_OFF_T ((((off_t) 1 << 31) << 31) - 1 + (((off_t) 1 << 31) << 31))
   int off_t_is_large[(LARGE_OFF_T % 2147483629 == 721
 		       && LARGE_OFF_T % 2147483647 == 1)
 		      ? 1 : -1];
@@ -14924,7 +15140,7 @@ rm -f core conftest.err conftest.$ac_objext conftest.$ac_ext
     We can't simply define LARGE_OFF_T to be 9223372036854775807,
     since some C++ compilers masquerading as C compilers
     incorrectly reject 9223372036854775807.  */
-#define LARGE_OFF_T (((off_t) 1 << 62) - 1 + ((off_t) 1 << 62))
+#define LARGE_OFF_T ((((off_t) 1 << 31) << 31) - 1 + (((off_t) 1 << 31) << 31))
   int off_t_is_large[(LARGE_OFF_T % 2147483629 == 721
 		       && LARGE_OFF_T % 2147483647 == 1)
 		      ? 1 : -1];
diff --git a/configure.ac b/configure.ac
index d713360f340..bdd32ea1732 100644
--- a/configure.ac
+++ b/configure.ac
@@ -1069,6 +1069,31 @@ PGAC_ARG_BOOL(with, zlib, yes,
               [do not use Zlib])
 AC_SUBST(with_zlib)
 
+#
+# SIMDSORT
+#
+AC_MSG_CHECKING([whether to build with SIMDSORT support])
+PGAC_ARG_BOOL(with, simdsort, no, [build with SIMDSORT support],
+              [AC_DEFINE([USE_SIMDSORT], 1, [Define to 1 to build with SIMDSORT support. (--with-simdsort)])])
+AC_MSG_RESULT([$with_simdsort])
+AC_SUBST(with_simdsort)
+
+if test "$with_simdsort" = yes; then
+  PKG_CHECK_MODULES(SIMDSORT, x86simdsortcpp)
+  # We only care about -I, -D, and -L switches;
+  # note that -lsimdsort will be added by AC_CHECK_LIB below.
+  for pgac_option in $SIMDSORT_CFLAGS; do
+    case $pgac_option in
+      -I*|-D*) CPPFLAGS="$CPPFLAGS $pgac_option";;
+    esac
+  done
+  for pgac_option in $SIMDSORT_LIBS; do
+    case $pgac_option in
+      -L*) LDFLAGS="$LDFLAGS $pgac_option";;
+    esac
+  done
+fi
+
 #
 # LZ4
 #
@@ -1353,6 +1378,10 @@ if test "$with_libxslt" = yes ; then
   AC_CHECK_LIB(xslt, xsltCleanupGlobals, [], [AC_MSG_ERROR([library 'xslt' is required for XSLT support])])
 fi
 
+if test "$with_simdsort" = yes ; then
+  AC_CHECK_LIB(x86simdsortcpp, keyvalue_qsort_float_sizet, [], [AC_MSG_ERROR([library 'x86simdsortcpp' is required for SIMDSORt support])])
+fi
+
 if test "$with_lz4" = yes ; then
   AC_CHECK_LIB(lz4, LZ4_compress_default, [], [AC_MSG_ERROR([library 'lz4' is required for LZ4 support])])
 fi
@@ -1362,6 +1391,8 @@ if test "$with_zstd" = yes ; then
 fi
 
 # Note: We can test for libldap_r only after we know PTHREAD_LIBS
+# also, on AIX, we may need to have openssl in LIBS for this step.
+
 if test "$with_ldap" = yes ; then
   _LIBS="$LIBS"
   if test "$PORTNAME" != "win32"; then
diff --git a/meson.build b/meson.build
index 1ceadb9a830..197e0a80b11 100644
--- a/meson.build
+++ b/meson.build
@@ -895,6 +895,28 @@ else
   libxslt = not_found_dep
 endif
 
+###############################################################
+# Library: simdsort
+###############################################################
+
+simdsortopt = get_option('simdsort')
+if not simdsortopt.disabled()
+  simdsort = dependency('x86simdsortcpp', required: false)
+  # Unfortunately the dependency is named differently with cmake
+  if not simdsort.found() # combine with above once meson 0.60.0 is required
+    simdsort = dependency('x86simdsortcpp', required: simdsortopt,
+                     method: 'cmake', modules: ['SIMDSORT::simdsort_shared'],
+                    )
+  endif
+
+  if simdsort.found()
+    cdata.set('USE_SIMDSORT', 1)
+    cdata.set('HAVE_LIBSIMDSORT', 1)
+  endif
+
+else
+  simdsort = not_found_dep
+endif
 
 
 ###############################################################
@@ -3069,6 +3091,7 @@ backend_both_deps += [
   ldap,
   libintl,
   libxml,
+  simdsort,
   lz4,
   pam,
   ssl,
@@ -3723,6 +3746,7 @@ if meson.version().version_compare('>=0.57')
       'libxml': libxml,
       'libxslt': libxslt,
       'llvm': llvm,
+      'simdsort':simdsort,
       'lz4': lz4,
       'nls': libintl,
       'openssl': ssl,
diff --git a/meson_options.txt b/meson_options.txt
index d9c7ddccbc4..e21b39e3f00 100644
--- a/meson_options.txt
+++ b/meson_options.txt
@@ -112,6 +112,9 @@ option('libxslt', type: 'feature', value: 'auto',
 option('llvm', type: 'feature', value: 'disabled',
   description: 'LLVM support')
 
+option('simdsort', type: 'feature', value: 'auto',
+  description: 'SIMDSORT support')
+
 option('lz4', type: 'feature', value: 'auto',
   description: 'LZ4 support')
 
@@ -174,6 +177,9 @@ option('FOP', type: 'string', value: 'fop',
 option('GZIP', type: 'string', value: 'gzip',
   description: 'Path to gzip binary')
 
+option('SIMDSORT', type: 'string', value: 'simdsort',
+  description: 'Path to simdsort binary')
+
 option('LZ4', type: 'string', value: 'lz4',
   description: 'Path to lz4 binary')
 
diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c
index 1597b8e8127..4fa5c7a793f 100644
--- a/src/backend/nodes/list.c
+++ b/src/backend/nodes/list.c
@@ -23,6 +23,9 @@
 #include "utils/memdebug.h"
 #include "utils/memutils.h"
 
+#ifdef USE_SIMDSORT
+void		keyvalue_qsort_float_sizet(float *, size_t *, size_t);
+#endif
 
 /*
  * The previous List implementation, since it used a separate palloc chunk
@@ -1655,6 +1658,222 @@ list_copy_deep(const List *oldlist)
 	return newlist;
 }
 
+#ifdef USE_SIMDSORT
+/*
+ * Checks whether the given index is in between the first and the last index of a sequence of the specified length..
+ * Returns true if the index is neither the first element nor the last element.
+ */
+static bool
+is_not_boundary(int index, int length)
+{
+	return index != 0 && index != length - 1;
+}
+
+/*
+ * Checks at the given index, if start of the tie interval is found in the key array.
+ * Returns true if the start of a tie interval is found at the given index, otherwise returns false.
+ */
+static bool
+is_start_found(int index, int length, float *key)
+{
+	if (is_not_boundary(index, length))
+	{
+		return (key[index] == key[index + 1]) && (key[index] != key[index - 1]);
+	}
+	else
+	{
+		return (index == 0) && (key[index] == key[index + 1]);
+	}
+}
+
+/*
+ * Checks at the given index, if end of the tie interval is found in the key array.
+ * Returns true if the end of the tie interval is found at the given index, otherwise returns false.
+ */
+static bool
+is_end_found(int index, int length, float *key)
+{
+	if (is_not_boundary(index, length))
+	{
+		return (key[index] != key[index + 1]) && (key[index] == key[index - 1]);
+	}
+	else
+	{
+		return (index == length - 1) && (key[index] == key[index - 1]);
+	}
+}
+
+static void
+free_list_sort_resources(float *key, size_t *arg, bool *done)
+{
+	pfree(key);
+	pfree(arg);
+	pfree(done);
+}
+
+/*
+ * Sort a list using the x86-simd-sort library.
+ *
+ * The list is sorted in-place.
+ *
+ * The extract function provides an implementation to extract a float value from each ListCell.
+ * The ListCells are sorted based on the float value.
+ *
+ * The comparator function is the same as the one required by list_sort.
+ *
+ * Like qsort(), this provides no guarantees about sort stability
+ * for equal keys.
+ */
+static void
+list_sort_simd_float_impl(List *list, list_sort_extractor_float extract, list_sort_comparator cmp)
+{
+	typedef int (*qsort_comparator) (const void *a, const void *b);
+	int			len;
+	ListCell   *list_cells;
+
+	float	   *key;
+	size_t	   *arg;
+	bool	   *done;
+
+	size_t		start;
+	size_t		end;
+	bool		start_found;
+
+	check_list_invariants(list);
+
+	len = list_length(list);
+	if (len <= 1)
+	{
+		return;
+	}
+
+	/*
+	 * The null check for this is taken care in check_list_invariants function
+	 */
+	list_cells = list->elements;
+	if (extract == NULL)
+	{
+		list_sort(list, cmp);
+		return;
+	}
+
+	/*
+	 * key array stores the float values based on which ListCells are sorted.
+	 * arg array stores the indexes corresponding to the sorted order after
+	 * sorting is done. done array tracks rearrangement of the values based on
+	 * the sorted indices
+	 */
+	key = (float *) palloc(len * sizeof(float));
+	arg = (size_t *) palloc(len * sizeof(size_t));
+	done = (bool *) palloc(len * sizeof(bool));
+
+	if (key == NULL || arg == NULL || done == NULL)
+	{
+		if (key != NULL)
+		{
+			pfree(key);
+		}
+		if (arg != NULL)
+		{
+			pfree(arg);
+		}
+		if (done != NULL)
+		{
+			pfree(done);
+		}
+		list_sort(list, cmp);
+		return;
+	}
+
+	for (size_t ii = 0; ii < len; ii++)
+	{
+		key[ii] = extract(&list_cells[ii]);
+		arg[ii] = ii;
+		done[ii] = false;
+	}
+
+	keyvalue_qsort_float_sizet(key, arg, len);
+
+	/*
+	 * The below loop rearranges each ListCell based on the sequence of
+	 * indexes stored in the arg array which represents index of the elements
+	 * in sorted order.
+	 */
+	for (size_t ii = 0; ii < len; ii++)
+	{
+		size_t		actual_index;
+		size_t		sorted_index;
+
+		if (done[ii])
+		{
+			continue;
+		}
+		done[ii] = true;
+
+		actual_index = ii;
+		sorted_index = arg[ii];
+
+		while (ii != sorted_index)
+		{
+			ListCell	temp = list_cells[actual_index];
+			ListCell	sorted_cell = list_cells[sorted_index];
+
+			list_cells[actual_index] = sorted_cell;
+			list_cells[sorted_index] = temp;
+
+			done[sorted_index] = true;
+			actual_index = sorted_index;
+			sorted_index = arg[sorted_index];
+		}
+	}
+
+	if (cmp == NULL)
+	{
+		free_list_sort_resources(key, arg, done);
+		return;
+	}
+
+	start = 0;
+	end = 0;
+	start_found = false;
+
+	for (size_t ii = 0; ii < len; ii++)
+	{
+		if (!start_found && is_start_found(ii, len, key))
+		{
+			start = ii;
+			start_found = true;
+		}
+		else if (is_end_found(ii, len, key))
+		{
+			ListCell   *start_ptr = &list_cells[start];
+
+			end = ii;
+
+			qsort(start_ptr, end - start + 1, sizeof(ListCell), (qsort_comparator) cmp);
+			start_found = false;
+		}
+	}
+
+	free_list_sort_resources(key, arg, done);
+}
+#endif
+
+/*
+ * Directs sorting to the SIMD-enabled version of list_sort if Postgres is built
+ * with x86-simd-sort support, else it directs it to list_sort.
+ */
+void
+list_sort_simd_float(List *list, list_sort_extractor_float extract, list_sort_comparator cmp)
+{
+#ifdef USE_SIMDSORT
+	list_sort_simd_float_impl(list, extract, cmp);
+#else
+	list_sort(list, cmp);
+#endif
+
+}
+
 /*
  * Sort a list according to the specified comparator function.
  *
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index a872fc501e0..565f9948a1b 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -683,4 +683,6 @@ extern void list_sort(List *list, list_sort_comparator cmp);
 extern int	list_int_cmp(const ListCell *p1, const ListCell *p2);
 extern int	list_oid_cmp(const ListCell *p1, const ListCell *p2);
 
+typedef float (*list_sort_extractor_float) (const ListCell *a);
+extern void list_sort_simd_float(List *list, list_sort_extractor_float extract, list_sort_comparator cmp);
 #endif							/* PG_LIST_H */
diff --git a/src/include/pg_config.h.in b/src/include/pg_config.h.in
index 07b2f798abd..b5eed4ae89d 100644
--- a/src/include/pg_config.h.in
+++ b/src/include/pg_config.h.in
@@ -253,6 +253,9 @@
 /* Define to 1 if you have the `wldap32' library (-lwldap32). */
 #undef HAVE_LIBWLDAP32
 
+/* Define to 1 if you have the `x86simdsortcpp' library (-lx86simdsortcpp). */
+#undef HAVE_LIBX86SIMDSORTCPP
+
 /* Define to 1 if you have the `xml2' library (-lxml2). */
 #undef HAVE_LIBXML2
 
@@ -688,6 +691,9 @@
 /* Define to 1 to build with PAM support. (--with-pam) */
 #undef USE_PAM
 
+/* Define to 1 to build with SIMDSORT support. (--with-simdsort) */
+#undef USE_SIMDSORT
+
 /* Define to 1 to use software CRC-32C implementation (slicing-by-8). */
 #undef USE_SLICING_BY_8_CRC32C
 
diff --git a/src/test/modules/Makefile b/src/test/modules/Makefile
index c0d3cf0e14b..74f9c8b4c6c 100644
--- a/src/test/modules/Makefile
+++ b/src/test/modules/Makefile
@@ -24,6 +24,7 @@ SUBDIRS = \
 		  test_integerset \
 		  test_json_parser \
 		  test_lfind \
+		  test_listsort \
 		  test_misc \
 		  test_oat_hooks \
 		  test_parser \
diff --git a/src/test/modules/test_listsort/.gitignore b/src/test/modules/test_listsort/.gitignore
new file mode 100644
index 00000000000..5dcb3ff9723
--- /dev/null
+++ b/src/test/modules/test_listsort/.gitignore
@@ -0,0 +1,4 @@
+# Generated subdirectories
+/log/
+/results/
+/tmp_check/
diff --git a/src/test/modules/test_listsort/Makefile b/src/test/modules/test_listsort/Makefile
new file mode 100644
index 00000000000..d7845c5e763
--- /dev/null
+++ b/src/test/modules/test_listsort/Makefile
@@ -0,0 +1,23 @@
+# src/test/modules/test_listsort/Makefile
+
+MODULE_big = test_listsort
+OBJS = \
+	$(WIN32RES) \
+	test_listsort.o
+PGFILEDESC = "test_listsort - example of a custom sort for floating point numbers"
+
+EXTENSION = test_listsort
+DATA = test_listsort--1.0.sql
+
+REGRESS = test_listsort
+
+ifdef USE_PGXS
+PG_CONFIG = pg_config
+PGXS := $(shell $(PG_CONFIG) --pgxs)
+include $(PGXS)
+else
+subdir = src/test/modules/test_listsort
+top_builddir = ../../../..
+include $(top_builddir)/src/Makefile.global
+include $(top_srcdir)/contrib/contrib-global.mk
+endif
diff --git a/src/test/modules/test_listsort/README b/src/test/modules/test_listsort/README
new file mode 100644
index 00000000000..dc1161c36aa
--- /dev/null
+++ b/src/test/modules/test_listsort/README
@@ -0,0 +1,10 @@
+test_listsort is a module for stress testing the list_sort implementation based on the x86-simd-sort library.
+It generates an array of ListCells and sorts it based on the float value held by each ListCell.
+
+One function is provided:
+
+test_listsort (arg1 integer, arg2 integer, arg3 integer, arg4 boolean) returns float[]
+
+arg1 is the size of the ListCell array to be sorted.
+arg2 and arg3 are used to generate ties. This is used while generating test data.
+arg4 is a flag to select the SIMD-enabled (using the x86-simd-sort library) or qsort version of list_sort
diff --git a/src/test/modules/test_listsort/expected/test_listsort.out b/src/test/modules/test_listsort/expected/test_listsort.out
new file mode 100644
index 00000000000..6b986cbde80
--- /dev/null
+++ b/src/test/modules/test_listsort/expected/test_listsort.out
@@ -0,0 +1,13 @@
+CREATE EXTENSION test_listsort;
+SELECT test_listsort(10000, 500, 50, false);
+                                                            test_listsort                                                            
+-------------------------------------------------------------------------------------------------------------------------------------
+ {1.8109567e-06,2.763141e-05,0.00040355558,0.000526655,0.0007317057,0.0007829778,0.0008651167,0.0008660783,0.0008709226,0.001022493}
+(1 row)
+
+SELECT test_listsort(10000, 500, 50, true);
+                                                            test_listsort                                                            
+-------------------------------------------------------------------------------------------------------------------------------------
+ {1.8109567e-06,2.763141e-05,0.00040355558,0.000526655,0.0007317057,0.0007829778,0.0008651167,0.0008660783,0.0008709226,0.001022493}
+(1 row)
+
diff --git a/src/test/modules/test_listsort/sql/test_listsort.sql b/src/test/modules/test_listsort/sql/test_listsort.sql
new file mode 100644
index 00000000000..0cfb8acc781
--- /dev/null
+++ b/src/test/modules/test_listsort/sql/test_listsort.sql
@@ -0,0 +1,4 @@
+CREATE EXTENSION test_listsort;
+
+SELECT test_listsort(10000, 500, 50, false);
+SELECT test_listsort(10000, 500, 50, true);
diff --git a/src/test/modules/test_listsort/test_listsort--1.0.sql b/src/test/modules/test_listsort/test_listsort--1.0.sql
new file mode 100644
index 00000000000..573f6c68972
--- /dev/null
+++ b/src/test/modules/test_listsort/test_listsort--1.0.sql
@@ -0,0 +1,9 @@
+/* src/test/modules/test_listsort/test_listsort--1.0.sql */
+
+-- complain if script is sourced in psql, rather than via CREATE EXTENSION
+\echo Use "CREATE EXTENSION test_listsort" to load this file. \quit
+
+CREATE FUNCTION test_listsort (arg1 integer, arg2 integer, arg3 integer, arg4 boolean)
+RETURNS float[]
+STRICT
+AS 'MODULE_PATHNAME' LANGUAGE C;
\ No newline at end of file
diff --git a/src/test/modules/test_listsort/test_listsort.c b/src/test/modules/test_listsort/test_listsort.c
new file mode 100644
index 00000000000..77bc67189cf
--- /dev/null
+++ b/src/test/modules/test_listsort/test_listsort.c
@@ -0,0 +1,210 @@
+/*-------------------------------------------------------------------------
+ *
+ * test_listsort.c
+ *	  Simple example of list_sort implementation using x86-simd-sort library
+ *
+ * Copyright (c) 2007-2025, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *	  src/test/modules/test_listsort/test_listsort.c
+ *
+ *-------------------------------------------------------------------------
+ */
+#include "postgres.h"
+
+#include <math.h>
+#include <signal.h>
+
+#include "funcapi.h"
+#include "utils/array.h"
+
+PG_MODULE_MAGIC;
+
+typedef struct SortTestData
+{
+	float		value;
+	int			tie_breaker;
+} SortTestData;
+
+static int
+tie_breaker(const ListCell *a, const ListCell *b)
+{
+	SortTestData *sort_test_data = (SortTestData *) a->ptr_value;
+	int			val1 = sort_test_data->tie_breaker;
+
+	SortTestData *sort_test_data2 = (SortTestData *) b->ptr_value;
+	int			val2 = sort_test_data2->tie_breaker;
+
+	if (val1 > val2)
+	{
+		return 1;
+	}
+	else if (val1 < val2)
+	{
+		return -1;
+	}
+	else
+	{
+		return 0;
+	}
+	return 1;
+}
+
+static int
+comparator(const ListCell *a, const ListCell *b)
+{
+	SortTestData *sort_test_data = (SortTestData *) a->ptr_value;
+	float		val1 = sort_test_data->value;
+
+	SortTestData *sort_test_data2 = (SortTestData *) b->ptr_value;
+	float		val2 = sort_test_data2->value;
+
+	if (val1 > val2)
+	{
+		return 1;
+	}
+	else if (val1 < val2)
+	{
+		return -1;
+	}
+	else
+	{
+		return tie_breaker(a, b);
+	}
+}
+
+static float
+get_value(const ListCell *a)
+{
+	SortTestData *sort_test_data = (SortTestData *) a->ptr_value;
+
+	return sort_test_data->value;
+}
+
+/*  Creates ListCells with each ListCell having a float value.
+ *  The max_random and tie_case_limit parameters are used to introduce ties.
+ */
+static ListCell **
+create_list_cell(ListCell *list_cells, int size, int max_random, int tie_case_limit)
+{
+	ListCell  **list_cell_ptrs = (ListCell **) palloc(size * sizeof(ListCell *));
+
+	if (list_cell_ptrs == NULL)
+	{
+		elog(ERROR, "error allocating memory");
+	}
+	srand(42);
+
+	for (int i = 0; i < size; i++)
+	{
+		ListCell	current_cell;
+		ListCell   *cell = (ListCell *) palloc(sizeof(ListCell));
+		SortTestData *sort_test_data;
+		float		random_float;
+		int			random_number;
+		int			bounded_random_number;
+
+		cell = (ListCell *) palloc(sizeof(ListCell));
+		if (cell == NULL)
+		{
+			elog(ERROR, "error allocating memory");
+		}
+
+		sort_test_data = (SortTestData *) palloc(sizeof(SortTestData));
+		if (sort_test_data == NULL)
+		{
+			elog(ERROR, "error allocating memory");
+		}
+
+		random_float = 0;
+		random_number = rand();
+		bounded_random_number = random_number % max_random;
+		if (bounded_random_number > 0 && bounded_random_number <= tie_case_limit)
+		{
+			random_float = bounded_random_number;
+		}
+		else
+		{
+			random_float = (float) random_number / (float) RAND_MAX;
+		}
+
+		sort_test_data->value = random_float;
+		sort_test_data->tie_breaker = i;
+		cell->ptr_value = sort_test_data;
+		current_cell = *cell;
+		list_cells[i] = current_cell;
+		list_cell_ptrs[i] = cell;
+	}
+
+	return list_cell_ptrs;
+}
+
+Datum		test_listsort(PG_FUNCTION_ARGS);
+
+PG_FUNCTION_INFO_V1(test_listsort);
+Datum
+test_listsort(PG_FUNCTION_ARGS)
+{
+	int			size = PG_GETARG_INT32(0);
+	int			random_number = PG_GETARG_INT32(1);
+	int			tie_breaker_limit = PG_GETARG_INT32(2);
+	bool		call_simd_sort = PG_GETARG_BOOL(3);
+
+	ListCell   *list_cells;
+	ListCell  **list_cell_ptrs;
+	List	   *list;
+	Datum	   *array_elements;
+	ArrayType  *result;
+
+	list_cells = (ListCell *) palloc(size * sizeof(ListCell));
+	if (list_cells == NULL)
+	{
+		elog(ERROR, "error allocating memory");
+	}
+
+	list_cell_ptrs = create_list_cell(list_cells, size, random_number, tie_breaker_limit);
+	if (list_cell_ptrs == NULL)
+	{
+		elog(ERROR, "error allocating memory");
+	}
+
+	list = (List *) palloc(sizeof(List));
+	if (list == NULL)
+	{
+		elog(ERROR, "error allocating memory");
+	}
+
+	list->elements = list_cells;
+	list->length = size;
+	list->max_length = size;
+	list->type = T_List;
+
+	if (call_simd_sort)
+	{
+		list_sort_simd_float(list, get_value, comparator);
+	}
+	else
+	{
+		list_sort(list, comparator);
+	}
+
+	array_elements = (Datum *) palloc(sizeof(Datum) * 10);
+	for (int i = 0; i < 10; i++)
+	{
+		array_elements[i] = Float4GetDatum(get_value(&list_cells[i]));
+	}
+
+	result = construct_array_builtin(array_elements, 10, FLOAT4OID);
+
+	pfree(array_elements);
+	pfree(list_cells);
+	pfree(list);
+	for (int i = 0; i < size; i++)
+	{
+		pfree(list_cell_ptrs[i]->ptr_value);
+		pfree(list_cell_ptrs[i]);
+	}
+	pfree(list_cell_ptrs);
+
+	PG_RETURN_ARRAYTYPE_P(result);
+}
diff --git a/src/test/modules/test_listsort/test_listsort.control b/src/test/modules/test_listsort/test_listsort.control
new file mode 100644
index 00000000000..8952f2aef87
--- /dev/null
+++ b/src/test/modules/test_listsort/test_listsort.control
@@ -0,0 +1,5 @@
+# test_listsort extension
+comment = 'example of a custom quick sort for sorting floating point numbers'
+default_version = '1.0'
+module_pathname = '$libdir/test_listsort'
+relocatable = true
diff --git a/src/test/regress/expected/list_sort_simd.out b/src/test/regress/expected/list_sort_simd.out
new file mode 100644
index 00000000000..8d79744cd27
--- /dev/null
+++ b/src/test/regress/expected/list_sort_simd.out
@@ -0,0 +1,87 @@
+--
+-- Tests for list sort
+--
+-- directory paths and dlsuffix are passed to us in environment variables
+\getenv libdir PG_LIBDIR
+\getenv dlsuffix PG_DLSUFFIX
+\set regresslib :libdir '/regress' :dlsuffix
+CREATE FUNCTION test_list_sort_simd_float (arg1 integer, arg2 integer)
+        RETURNS float[]
+        AS :'regresslib'
+        LANGUAGE C STRICT;
+CREATE FUNCTION test_list_sort_simd_float_random (arg1 integer, arg2 integer, arg3 integer, arg4 boolean)
+        RETURNS float[]
+        AS :'regresslib'
+        LANGUAGE C STRICT;
+SELECT test_list_sort_simd_float(100, 10);
+ test_list_sort_simd_float 
+---------------------------
+ {1,2,3,4,5,6,7,8,9,10}
+(1 row)
+
+SELECT test_list_sort_simd_float(10, 5);
+ test_list_sort_simd_float 
+---------------------------
+ {1,2,3,4,5,6,7,8,9,10}
+(1 row)
+
+SELECT test_list_sort_simd_float_random(100, 20, 2, true);
+                                         test_list_sort_simd_float_random                                         
+------------------------------------------------------------------------------------------------------------------
+ {0.024923936,0.03346995,0.08167228,0.08531265,0.10674526,0.114986524,0.11994517,0.1355998,0.13572839,0.16894749}
+(1 row)
+
+SELECT test_list_sort_simd_float_random(2, 20, 2, true);
+ test_list_sort_simd_float_random 
+----------------------------------
+ {0.03346995,0.32996422}
+(1 row)
+
+SELECT test_list_sort_simd_float_random(1000, 200, 20, true);
+                                                test_list_sort_simd_float_random                                                
+--------------------------------------------------------------------------------------------------------------------------------
+ {0.0007317057,0.004217157,0.005766493,0.0061016046,0.0061097275,0.0065996465,0.0067929444,0.0072418055,0.008422677,0.00864573}
+(1 row)
+
+SELECT test_list_sort_simd_float_random(10000, 20, 2, true);
+                                                  test_list_sort_simd_float_random                                                   
+-------------------------------------------------------------------------------------------------------------------------------------
+ {1.8109567e-06,2.763141e-05,0.00040355558,0.000526655,0.0007317057,0.0007829778,0.0008651167,0.0008660783,0.0008709226,0.001022493}
+(1 row)
+
+SELECT test_list_sort_simd_float_random(10000, 200, 50, true);
+                                                 test_list_sort_simd_float_random                                                  
+-----------------------------------------------------------------------------------------------------------------------------------
+ {1.8109567e-06,2.763141e-05,0.000526655,0.0007317057,0.0008660783,0.0008709226,0.001022493,0.0012402055,0.0024320218,0.002435991}
+(1 row)
+
+SELECT test_list_sort_simd_float_random(10000, 2000, 500, true);
+                                                  test_list_sort_simd_float_random                                                   
+-------------------------------------------------------------------------------------------------------------------------------------
+ {1.8109567e-06,2.763141e-05,0.00040355558,0.000526655,0.0007317057,0.0007829778,0.0008651167,0.0008660783,0.001022493,0.0012402055}
+(1 row)
+
+SELECT test_list_sort_simd_float_random(100000, 20000, 5000, true);
+                                                     test_list_sort_simd_float_random                                                     
+------------------------------------------------------------------------------------------------------------------------------------------
+ {3.5329722e-06,2.763141e-05,6.246893e-05,7.02166e-05,7.395493e-05,9.09497e-05,0.000111196656,0.000111584086,0.00012805313,0.00015487056}
+(1 row)
+
+SELECT test_list_sort_simd_float_random(100000, 20000, 1000, true);
+                                                     test_list_sort_simd_float_random                                                     
+------------------------------------------------------------------------------------------------------------------------------------------
+ {1.8109567e-06,3.5329722e-06,2.763141e-05,6.246893e-05,7.02166e-05,7.395493e-05,9.09497e-05,9.3645416e-05,0.000111196656,0.000111584086}
+(1 row)
+
+SELECT test_list_sort_simd_float_random(100, 20, 2, false);
+                                         test_list_sort_simd_float_random                                         
+------------------------------------------------------------------------------------------------------------------
+ {0.024923936,0.03346995,0.08167228,0.08531265,0.10674526,0.114986524,0.11994517,0.1355998,0.13572839,0.16894749}
+(1 row)
+
+SELECT test_list_sort_simd_float_random(10000, 3000, 300, false);
+                                                  test_list_sort_simd_float_random                                                   
+-------------------------------------------------------------------------------------------------------------------------------------
+ {1.8109567e-06,2.763141e-05,0.00040355558,0.000526655,0.0007317057,0.0007829778,0.0008651167,0.0008660783,0.0008709226,0.001022493}
+(1 row)
+
diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule
index 1edd9e45ebb..c94aef1522b 100644
--- a/src/test/regress/parallel_schedule
+++ b/src/test/regress/parallel_schedule
@@ -98,7 +98,7 @@ test: publication subscription
 # Another group of parallel tests
 # select_views depends on create_view
 # ----------
-test: select_views portals_p2 foreign_key cluster dependency guc bitmapops combocid tsearch tsdicts foreign_data window xmlmap functional_deps advisory_lock indirect_toast equivclass
+test: select_views portals_p2 foreign_key cluster dependency guc bitmapops combocid tsearch tsdicts foreign_data window xmlmap functional_deps advisory_lock indirect_toast list_sort_simd equivclass
 
 # ----------
 # Another group of parallel tests (JSON related)
diff --git a/src/test/regress/regress.c b/src/test/regress/regress.c
index 5c7158f72b1..db12128669c 100644
--- a/src/test/regress/regress.c
+++ b/src/test/regress/regress.c
@@ -544,6 +544,272 @@ test_canonicalize_path(PG_FUNCTION_ARGS)
 	PG_RETURN_TEXT_P(cstring_to_text(path));
 }
 
+typedef struct SortTestData
+{
+	float		value;
+	int			tiebreaker;
+} SortTestData;
+
+static int
+tie_breaker(const ListCell *a, const ListCell *b)
+{
+	SortTestData *sorttestdata1 = (SortTestData *) a->ptr_value;
+	int			val1 = sorttestdata1->tiebreaker;
+
+	SortTestData *sorttestdata2 = (SortTestData *) b->ptr_value;
+	int			val2 = sorttestdata2->tiebreaker;
+
+	if (val1 > val2)
+	{
+		return 1;
+	}
+	else if (val1 < val2)
+	{
+		return -1;
+	}
+	else
+	{
+		return 0;
+	}
+}
+
+static float
+get_value(const ListCell *a)
+{
+	SortTestData *sorttestdata = (SortTestData *) a->ptr_value;
+
+	return sorttestdata->value;
+}
+
+static int
+get_tie_breaker_value(const ListCell *a)
+{
+	SortTestData *sorttestdata = (SortTestData *) a->ptr_value;
+
+	return sorttestdata->tiebreaker;
+}
+
+static int
+custom_comparator(const ListCell *a, const ListCell *b)
+{
+	float		val1 = get_value(a);
+	float		val2 = get_value(b);
+
+	if (val1 > val2)
+	{
+		return 1;
+	}
+	else if (val1 < val2)
+	{
+		return -1;
+	}
+	else
+	{
+		return tie_breaker(a, b);;
+	}
+}
+
+/* Test for list_sort_simd_float starting from a list in descending order. The list is sorted in ascending order.
+  */
+Datum		test_list_sort_simd_float(PG_FUNCTION_ARGS);
+
+PG_FUNCTION_INFO_V1(test_list_sort_simd_float);
+Datum
+test_list_sort_simd_float(PG_FUNCTION_ARGS)
+{
+	int			size = PG_GETARG_INT32(0);
+
+	float		currentsize = (float) size;
+	ListCell   *listcells;
+	ListCell  **listcellptrs;
+	List	   *list;
+	Datum	   *array_elements;
+	ArrayType  *result;
+
+	listcells = (ListCell *) palloc(size * sizeof(ListCell));
+	Assert(listcells != NULL);
+
+	listcellptrs = (ListCell **) palloc(size * sizeof(ListCell *));
+	Assert(listcellptrs != NULL);
+
+	for (int i = 0; i < size; i++)
+	{
+		ListCell	currentcell;
+		ListCell   *cell;
+		SortTestData *sorttestdata;
+
+		cell = (ListCell *) palloc(sizeof(ListCell));
+		Assert(cell != NULL);
+
+		sorttestdata = (SortTestData *) palloc(sizeof(SortTestData));
+		Assert(sorttestdata != NULL);
+
+		sorttestdata->value = currentsize;
+		currentsize = currentsize - 1;
+		sorttestdata->tiebreaker = i;
+		cell->ptr_value = sorttestdata;
+		currentcell = *cell;
+		listcells[i] = currentcell;
+		listcellptrs[i] = cell;
+	}
+
+	list = (List *) palloc(sizeof(List));
+	list->elements = listcells;
+	list->length = size;
+	list->max_length = size;
+	list->type = T_List;
+
+	list_sort_simd_float(list, get_value, custom_comparator);
+
+	for (int i = 0; i < size; i++)
+	{
+		Assert(get_value(&listcells[i]) == (float) (i + 1));
+	}
+
+	array_elements = (Datum *) palloc(sizeof(Datum) * 10);
+	for (int i = 0; i < 10; i++)
+	{
+		array_elements[i] = Float4GetDatum(get_value(&listcells[i]));
+	}
+
+	result = construct_array_builtin(array_elements, 10, FLOAT4OID);
+
+	pfree(array_elements);
+	pfree(listcells);
+	for (int i = 0; i < size; i++)
+	{
+		pfree(listcellptrs[i]->ptr_value);
+		pfree(listcellptrs[i]);
+	}
+	pfree(listcellptrs);
+
+	PG_RETURN_ARRAYTYPE_P(result);
+}
+
+/*  Creates ListCells with each ListCell having a float value.
+ *  The max_random and tie_case_limit parameters are used to introduce ties.
+ */
+static ListCell **
+create_list_cell(ListCell *list_cells, int size, int max_random, int tie_case_limit)
+{
+	ListCell  **list_cell_ptrs = (ListCell **) palloc(size * sizeof(ListCell *));
+
+	for (int i = 0; i < size; i++)
+	{
+		ListCell	current_cell;
+		ListCell   *cell = (ListCell *) palloc(sizeof(ListCell));
+
+		SortTestData *sort_test_data = (SortTestData *) palloc(sizeof(SortTestData));
+
+		float		random_float = 0;
+		int			random_number = rand();
+		int			bounded_random_number = random_number % max_random;
+
+		if (bounded_random_number > 0 && bounded_random_number <= tie_case_limit)
+		{
+			random_float = bounded_random_number;
+		}
+		else
+		{
+			random_float = (float) random_number / (float) RAND_MAX;
+		}
+
+		sort_test_data->value = random_float;
+		sort_test_data->tiebreaker = i;
+		cell->ptr_value = sort_test_data;
+		current_cell = *cell;
+		list_cells[i] = current_cell;
+		list_cell_ptrs[i] = cell;
+	}
+
+	return list_cell_ptrs;
+}
+
+/* Test for list_sort_simd_float starting from a list in random order. The list is sorted in ascending order.
+ */
+Datum		test_list_sort_simd_float_random(PG_FUNCTION_ARGS);
+
+PG_FUNCTION_INFO_V1(test_list_sort_simd_float_random);
+Datum
+test_list_sort_simd_float_random(PG_FUNCTION_ARGS)
+{
+	int			size = PG_GETARG_INT32(0);
+	int			max_random = PG_GETARG_INT32(1);
+	int			tie_case_limit = PG_GETARG_INT32(2);
+	bool		call_simd_sort = PG_GETARG_BOOL(3);
+
+	ListCell   *list_cells;
+	ListCell  **list_cell_ptrs;
+	List	   *list;
+	Datum	   *array_elements;
+	ArrayType  *result;
+	int			result_len;
+
+	srand(42);
+
+	list_cells = (ListCell *) palloc(size * sizeof(ListCell));
+	Assert(list_cells != NULL);
+
+	list_cell_ptrs = create_list_cell(list_cells, size, max_random, tie_case_limit);
+
+	list = (List *) palloc(sizeof(List));
+	Assert(list != NULL);
+
+	list->elements = list_cells;
+	list->length = size;
+	list->max_length = size;
+	list->type = T_List;
+
+	if (call_simd_sort)
+	{
+		list_sort_simd_float(list, get_value, custom_comparator);
+	}
+	else
+	{
+		list_sort_simd_float(list, NULL, custom_comparator);
+	}
+
+	for (int i = 0; i < size - 1; i++)
+	{
+		Assert(get_value(&list_cells[i]) <= get_value(&list_cells[i + 1]));
+	}
+
+	for (int i = 0; i < size - 1; i++)
+	{
+		if (get_value(&list_cells[i]) == get_value(&list_cells[i + 1]))
+		{
+			Assert(get_tie_breaker_value(&list_cells[i]) <= get_tie_breaker_value(&list_cells[i + 1]));
+		}
+	}
+
+	/*
+	 * we choose to return an array of size 10 for larger sort sizes ( > 10).
+	 * The reason behind this is to make sure the corresponding .out file does
+	 * not have to show all the sorted floats especially when sort size is
+	 * large. Otherwise this will make the .out file difficult to maintain.
+	 */
+	result_len = (size < 10 ? size : 10);
+	array_elements = (Datum *) palloc(sizeof(Datum) * result_len);
+	for (int i = 0; i < result_len; i++)
+	{
+		array_elements[i] = Float4GetDatum(get_value(&list_cells[i]));
+	}
+
+	result = construct_array_builtin(array_elements, result_len, FLOAT4OID);
+
+	pfree(array_elements);
+	pfree(list_cells);
+	pfree(list);
+	for (int i = 0; i < size; i++)
+	{
+		pfree(list_cell_ptrs[i]->ptr_value);
+		pfree(list_cell_ptrs[i]);
+	}
+	pfree(list_cell_ptrs);
+
+	PG_RETURN_ARRAYTYPE_P(result);
+}
+
 PG_FUNCTION_INFO_V1(make_tuple_indirect);
 Datum
 make_tuple_indirect(PG_FUNCTION_ARGS)
diff --git a/src/test/regress/sql/list_sort_simd.sql b/src/test/regress/sql/list_sort_simd.sql
new file mode 100644
index 00000000000..a2eec3633c1
--- /dev/null
+++ b/src/test/regress/sql/list_sort_simd.sql
@@ -0,0 +1,32 @@
+--
+-- Tests for list sort
+--
+
+-- directory paths and dlsuffix are passed to us in environment variables
+\getenv libdir PG_LIBDIR
+\getenv dlsuffix PG_DLSUFFIX
+
+\set regresslib :libdir '/regress' :dlsuffix
+
+CREATE FUNCTION test_list_sort_simd_float (arg1 integer, arg2 integer)
+        RETURNS float[]
+        AS :'regresslib'
+        LANGUAGE C STRICT;
+
+CREATE FUNCTION test_list_sort_simd_float_random (arg1 integer, arg2 integer, arg3 integer, arg4 boolean)
+        RETURNS float[]
+        AS :'regresslib'
+        LANGUAGE C STRICT;
+
+SELECT test_list_sort_simd_float(100, 10);
+SELECT test_list_sort_simd_float(10, 5);
+SELECT test_list_sort_simd_float_random(100, 20, 2, true);
+SELECT test_list_sort_simd_float_random(2, 20, 2, true);
+SELECT test_list_sort_simd_float_random(1000, 200, 20, true);
+SELECT test_list_sort_simd_float_random(10000, 20, 2, true);
+SELECT test_list_sort_simd_float_random(10000, 200, 50, true);
+SELECT test_list_sort_simd_float_random(10000, 2000, 500, true);
+SELECT test_list_sort_simd_float_random(100000, 20000, 5000, true);
+SELECT test_list_sort_simd_float_random(100000, 20000, 1000, true);
+SELECT test_list_sort_simd_float_random(100, 20, 2, false);
+SELECT test_list_sort_simd_float_random(10000, 3000, 300, false);
\ No newline at end of file
diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list
index 9a3bee93dec..4521e56165d 100644
--- a/src/tools/pgindent/typedefs.list
+++ b/src/tools/pgindent/typedefs.list
@@ -2717,6 +2717,7 @@ SortShimExtra
 SortState
 SortSupport
 SortSupportData
+SortTestData
 SortTuple
 SortTupleComparator
 SortedPoint
-- 
2.25.1