strstr() on ubuntu18.04 8 times slower than on ubuntu16

Regarding:

$ gcc -o strstr strstr.c

Do you compile for i386 or amd64?

I'm running on amd64, i7 cpu :

$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 8
On-line CPU(s) list: 0-7
Thread(s) per core: 2
Core(s) per socket: 4
Socket(s): 1
NUMA node(s): 1
Vendor ID: GenuineIntel
CPU family: 6
Model: 60
Model name: Intel(R) Core(TM) i7-4710HQ CPU @ 2.50GHz
Stepping: 3
CPU MHz: 1660.927
CPU max MHz: 3500.0000
CPU min MHz: 800.0000
BogoMIPS: 4988.64
Virtualization: VT-x
L1d cache: 32K
L1i cache: 32K
L2 cache: 256K
L3 cache: 6144K
NUMA node0 CPU(s): 0-7
Flags: fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts rep_good nopl xtopology nonstop_tsc cpuid aperfmperf pni pclmulqdq dtes64 monitor ds_cpl vmx est tm2 ssse3 sdbg fma cx16 xtpr pdcm pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand lahf_lm abm cpuid_fault epb invpcid_single pti ssbd ibrs ibpb stibp tpr_shadow vnmi flexpriority ept vpid fsgsbase tsc_adjust bmi1 avx2 smep bmi2 erms invpcid xsaveopt dtherm ida arat pln pts flush_l1d

Yes, but to be absolutely certain, the `strstr` binary you created is a 64-bit binary?

$ file strstr
strstr: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=f09b9ae65046d6650a9b7007a9aa5d6d472a2d06, not stripped

I can't reproduce this here. I'll note that I'm testing on a Broadwell and you're on a Haswell, but I'd hope that doesn't make a huge difference, unless H.J. Lu's latest round of CPU detection stuff has gone amok.

model name : Intel(R) Core(TM) i7-5600U CPU @ 2.60GHz

(xenial-amd64)adconrad@nosferatu:~/Downloads$ /lib/x86_64-linux-gnu/libc.so.6 | head -n1
GNU C Library (Ubuntu GLIBC 2.23-0ubuntu10) stable release version 2.23, by Roland McGrath et al.
(xenial-amd64)adconrad@nosferatu:~/Downloads$ time ./strstr aa
matches = 3000000

real 0m0.559s
user 0m0.556s
sys 0m0.001s

(bionic-amd64)adconrad@nosferatu:~/Downloads$ /lib/x86_64-linux-gnu/libc.so.6 | head -n1
GNU C Library (Ubuntu GLIBC 2.27-3ubuntu1) stable release version 2.27.
(bionic-amd64)adconrad@nosferatu:~/Downloads$ time ./strstr aa
matches = 3000000

real 0m0.527s
user 0m0.522s
sys 0m0.001s

(base)adconrad@nosferatu:~/Downloads$ /lib/x86_64-linux-gnu/libc.so.6 | head -n1
GNU C Library (Ubuntu GLIBC 2.28-0ubuntu1) stable release version 2.28.
(base)adconrad@nosferatu:~/Downloads$ time ./strstr aa
matches = 3000000

real 0m0.528s
user 0m0.525s
sys 0m0.002s

I notice that your cpu flags list avx2; this suggests the possibility that the code path being used is one that's specific to avx2, not just sse2. I have attempted to reproduce this on CPUs both with and without avx2 and I cannot. I get no statistically-significant difference in runtime, on either the avx2 system or the non-avx2 system, with glibc from Ubuntu 16.04 vs. glibc from Ubuntu 18.04.

This could be a CPU bug or a bug in vagrant rather than in glibc; there's currently not enough information to tell. I think we would need a trace that shows which implementation is being selected in glibc in this environment first and foremost, to confirm whether it's the correct one.

On my system, I can clearly see it selecting the sse2 implementation (there is no AVX implementation of strstr)

$ gdb ./strstr
(gdb) break strstr
Breakpoint 1 at 0x1040
(gdb) run aa
Starting program: /home/adconrad/Downloads/strstr aa

Breakpoint 1, __strstr_sse2_unaligned () at ../sysdeps/x86_64/multiarch/strstr-sse2-unaligned.S

The bug has been opened on glibc and being (or already) fixed :
https://sourceware.org/bugzilla/show_bug.cgi?id=23709

Thanks
-Paul

Fixed in glibc 2.29 and later, included in Ubuntu 19.04 and later.

Hello Paul, or anyone else affected,

Accepted glibc into bionic-proposed. The package will build now and be available at https://launchpad.net/ubuntu/+source/glibc/2.27-3ubuntu1.3 in a few hours, and then in the -proposed repository.

Please help us by testing this new package. See https://wiki.ubuntu.com/Testing/EnableProposed for documentation on how to enable and use -proposed. Your feedback will aid us getting this update out to other Ubuntu users.

If this package fixes the bug for you, please add a comment to this bug, mentioning the version of the package you tested, what testing has been performed on the package and change the tag from verification-needed-bionic to verification-done-bionic. If it does not fix the bug for you, please add a comment stating that, and change the tag to verification-failed-bionic. In either case, without details of your testing we will not be able to proceed.

Further information regarding the verification process can be found at https://wiki.ubuntu.com/QATeam/PerformingSRUVerification . Thank you in advance for helping!

N.B. The updated package will be released to -updates after the bug(s) fixed by this package have been verified and the package has been in -proposed for a minimum of 7 days.

All autopkgtests for the newly accepted glibc (2.27-3ubuntu1.3) for bionic have finished running.
The following regressions have been reported in tests triggered by the package:

mysql-5.7/5.7.31-0ubuntu0.18.04.1 (armhf)
libsys-utmp-perl/1.8-1 (armhf)
libscope-upper-perl/0.30-1 (armhf)
octave-miscellaneous/1.2.1-4 (armhf, arm64, s390x, amd64, i386, ppc64el)
libsocket-multicast6-perl/unknown (armhf)
octave-strings/1.2.0-3 (armhf, arm64, s390x, amd64, i386, ppc64el)
libgnatcoll/unknown (armhf)
octave-econometrics/1:1.1.1-5 (armhf, arm64, s390x, amd64, i386, ppc64el)
octave-secs2d/0.0.8-9 (armhf, arm64, s390x, amd64, i386, ppc64el)
libb-hooks-parser-perl/unknown (armhf)
octave-general/2.0.0-3 (armhf, arm64, s390x, amd64, i386, ppc64el)
libcompress-raw-bzip2-perl/2.074-1build2 (armhf)
libunicode-casefold-perl/unknown (armhf)
mod-wsgi/4.5.17-1ubuntu1 (ppc64el)
libdata-alias-perl/unknown (armhf)
libdata-clone-perl/unknown (armhf)
libsort-key-perl/unknown (armhf)
linux-raspi-5.4/5.4.0-1018.20~18.04.1 (armhf)
ann/unknown (armhf)
icecast2/unknown (i386)
python-maxminddb/1.3.0-1 (armhf)
lua-torch-sundown/unknown (armhf)
libkf5mailcommon/4:17.12.3-0ubuntu1 (arm64, i386)
apport/2.20.9-0ubuntu7.17 (amd64)
linux-hwe-5.0/5.0.0-61.65 (armhf)
ffmpeg/7:3.4.8-0ubuntu0.2 (armhf, arm64, s390x, amd64, i386, ppc64el)
glibc/2.27-3ubuntu1.3 (armhf)
nut/2.7.4-5.1ubuntu2 (amd64)
mbuffer/unknown (armhf)
linux-aws-edge/5.0.0-1019.21~18.04.1 (amd64, arm64)
octave-ocs/0.1.5-6 (armhf, arm64, s390x, amd64, i386, ppc64el)
libx11-xcb-perl/unknown (armhf)
pgbouncer/1.8.1-1build1 (amd64)
indicator-session/17.3.20+17.10.20171006-0ubuntu1 (armhf)
gcc-6/6.5.0-2ubuntu1~18.04 (armhf)
vmtouch/unknown (armhf)
libhtml-gumbo-perl/0.17-1build1 (ppc64el)
octave-sparsersb/1.0.5-3 (armhf, arm64, s390x, amd64, i386, ppc64el)
octave-mpi/1.2.0-4 (armhf, arm64, s390x, amd64, i386, ppc64el)
libalgorithm-svm-perl/0.13-2build2 (s390x)
libconvert-binary-c-perl/0.78-1build2 (amd64)
kauth/5.44.0-0ubuntu1 (i386)
libkdegames-kde4/unknown (amd64)
openssh/1:7.6p1-4ubuntu0.3 (armhf, arm64, s390x, amd64, i386, ppc64el)
keditbookmarks/17.12.3-0ubuntu1 (ppc64el)
jovie/unknown (armhf)
kdepim-runtime/4:17.12.3-0ubuntu2 (armhf)
libscalar-util-numeric-perl/0.40-1build3 (s390x)
pgpdump/unknown (armhf)
libdevice-cdio-perl/0.4.0-3 (armhf)
octave-sockets/1.2.0-3 (armhf, arm64, s390x, amd64, i386, ppc64el)
octave-gsl/2.1.0-3 (armhf, arm64, s390x, amd64, i386, ppc64el)
libdbd-odbc-perl/1.56-1build1 (armhf)
libnet-dbus-perl/1.1.0-4build2 (armhf)
linux-aws-5.3/unknown (arm64)
libalgorithm-permute-perl/0.16-1 (s390x)
xdg-desktop-portal/1.0.3-0ubuntu0.2 (i386, ppc64el)
octave-ltfat/2.2.0+dfsg-7 (s390x, amd64, i386, ppc64el)
octave-geometry/3.0.0-6 (armhf, arm64, s390x, amd64, i386, ppc64el)
octave-linear-algebra/2.2.2-4 (armhf, arm64, s390x, amd64, i386, ppc64el)
octave-nurbs/1.3.13-4 (armhf, arm64, s390x, amd64, i386, ppc64el)
devscripts/2.17.12ubuntu1.1 (armhf, arm64, s390x, amd64, i386, ppc64el)
meliae/0.4.0+bzr199-3build1 (ppc64el)
libocas/unknown (armhf)
k3d/unknown (armhf)
firefox/80.0.1+build1-0ubuntu0.18.04.1 (armhf)
libb-hooks-op-check-perl/unknown (armhf)
octave-quaternion/2.4.0-4 (armhf, arm64, s390x, amd64, i38...

Verified 2.27-3ubuntu1.3 on Bionic:

root@bb-glibc:~# gcc strstr.c
root@bb-glibc:~# time ./a.out aa
matches = 3000000

real 0m4.149s
user 0m4.146s
sys 0m0.000s
root@bb-glibc:~# sed -i s/backports/proposed/ /etc/apt/sources.list
root@bb-glibc:~# apt update
Hit:1 http://archive.ubuntu.com/ubuntu bionic InRelease
Get:2 http://archive.ubuntu.com/ubuntu bionic-updates InRelease [88.7 kB]
Get:3 http://security.ubuntu.com/ubuntu bionic-security InRelease [88.7 kB]
Get:4 http://archive.ubuntu.com/ubuntu bionic-proposed InRelease [242 kB]
Get:5 http://archive.ubuntu.com/ubuntu bionic-proposed/main amd64 Packages [123 kB]
Get:6 http://archive.ubuntu.com/ubuntu bionic-proposed/main Translation-en [30.1 kB]
Get:7 http://archive.ubuntu.com/ubuntu bionic-proposed/restricted amd64 Packages [40.9 kB]
Get:8 http://archive.ubuntu.com/ubuntu bionic-proposed/restricted Translation-en [7508 B]
Get:9 http://archive.ubuntu.com/ubuntu bionic-proposed/universe amd64 Packages [22.1 kB]
Get:10 http://archive.ubuntu.com/ubuntu bionic-proposed/universe Translation-en [11.0 kB]
Get:11 http://archive.ubuntu.com/ubuntu bionic-proposed/multiverse amd64 Packages [7244 B]
Get:12 http://archive.ubuntu.com/ubuntu bionic-proposed/multiverse Translation-en [2172 B]
Fetched 664 kB in 1s (852 kB/s)
Reading package lists... Done
Building dependency tree
Reading state information... Done
21 packages can be upgraded. Run 'apt list --upgradable' to see them.
root@bb-glibc:~# apt install libc6 libc-bin locales
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following package was automatically installed and is no longer required:
  libfreetype6
Use 'apt autoremove' to remove it.
The following additional packages will be installed:
  libc-dev-bin libc6-dev
Suggested packages:
  glibc-doc
The following packages will be upgraded:
  libc-bin libc-dev-bin libc6 libc6-dev locales
5 upgraded, 0 newly installed, 0 to remove and 16 not upgraded.
Need to get 9741 kB of archives.
After this operation, 13.3 kB of additional disk space will be used.
Do you want to continue? [Y/n]
Get:1 http://archive.ubuntu.com/ubuntu bionic-proposed/main amd64 libc6-dev amd64 2.27-3ubuntu1.3 [2586 kB]
Get:2 http://archive.ubuntu.com/ubuntu bionic-proposed/main amd64 libc-dev-bin amd64 2.27-3ubuntu1.3 [71.8 kB]
Get:3 http://archive.ubuntu.com/ubuntu bionic-proposed/main amd64 libc6 amd64 2.27-3ubuntu1.3 [2831 kB]
Get:4 http://archive.ubuntu.com/ubuntu bionic-proposed/main amd64 locales all 2.27-3ubuntu1.3 [3613 kB]
Get:5 http://archive.ubuntu.com/ubuntu bionic-proposed/main amd64 libc-bin amd64 2.27-3ubuntu1.3 [639 kB]
Fetched 9741 kB in 2s (5058 kB/s)
Preconfiguring packages ...
(Reading database ... 32938 files and directories currently installed.)
Preparing to unpack .../libc6-dev_2.27-3ubuntu1.3_amd64.deb ...
Unpacking libc6-dev:amd64 (2.27-3ubuntu1.3) over (2.27-3ubuntu1.2) ...
Preparing to unpack .../libc-dev-bin_2.27-3ubuntu1.3_amd64.deb ...
Unpacking libc-dev-bin (2.27-3ubuntu1.3) over (2.27-3ubuntu1.2) ...
Preparing to unpack .../libc6_2.27-3ubuntu1.3_amd64.deb ...
Unpacking libc6:amd64 (...

The verification of the Stable Release Update for glibc has completed successfully and the package is now being released to -updates. Subsequently, the Ubuntu Stable Release Updates Team is being unsubscribed and will not receive messages about this bug report. In the event that you encounter a regression using the package from -updates please report a new bug using ubuntu-bug and tag the bug report regression-update so we can easily find any regressions.

This bug was fixed in the package glibc - 2.27-3ubuntu1.3

---------------
glibc (2.27-3ubuntu1.3) bionic; urgency=medium

  [ Balint Reczey ]
  * debian/gbp.conf: Add initial configuration
  * debian/control.in/main: Add Vcs-* pointing to Ubuntu packaging repository
  * arm64: Enable searching shared libraries in atomics/ on LSE HW
  * Ship arm64 variant with LSE support in libc6-lse (LP: #1885012)
  * Run tests of libc6-lse on HW supporting LSE
  * debian/patches/git-updates.diff: update from upstream stable branch
    - pthread_cond_broadcast: Fix waiters-after-spinning case
    - Fix SSe2-based memmove corrupting memory (CVE-2017-18269)
    - Fix strstr() performance regression on Haswell processors
    - Support Japanese new era "令和 (Reiwa)"
    - io: Remove copy_file_range emulation
    (LP: #1851263, #1858203, #1838327, #1797335, #1756209, #1853193)
  * XFAIL stdlib/tst-getrandom (LP: #1891403)
  * debian/testsuite-xfail-debian.mk: XFAIL new tst-support_descriptors

  [ Thadeu Lima de Souza Cascardo ]
  * tests: Make preadwritev2 invalid flags tests unsupported (LP: #1770480)

  [ Andreas Hasenack ]
  * branch-pthread_rwlock_trywrlock-hang-23844.patch:
    nptl: Fix pthread_rwlock_try*lock stalls (Bug 23844) (LP: #1864864)

 -- Balint Reczey <email address hidden> Wed, 02 Sep 2020 11:18:37 +0200