This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Testing 2.16 release candidate with gnulib - quadratic behaviourdetected in SSE42 strstr?
- From: Carlos O'Donell <carlos_odonell at mentor dot com>
- To: libc-alpha <libc-alpha at sourceware dot org>, Bruno Haible <bruno at clisp dot org>
- Date: Thu, 28 Jun 2012 00:13:56 -0400
- Subject: Testing 2.16 release candidate with gnulib - quadratic behaviourdetected in SSE42 strstr?
Community,
http://sourceware.org/glibc/wiki/Testing/Gnulib
Running the 2.16 release candidate against the gnulib
testsuite has turned up three object files being build
by gnulib that aren't listed in the known issues:
(a) logf
(b) log10f
(c) remove
(d) strstr
I've run out of time just getting the build bits setup
and reviewing 2.15 backports. I'm hoping that some of
my European friends can look at these as the earth turns
to their part of the world...
Initial analysis:
(a) logf
(b) log10f
Why wasn't -lm added to the link?
This looks like an environment/configuration issue with gnulib.
Adding `-lm' to CC fixes this, but that can't be right.
configure:84449: checking whether log10f works according to ISO C 99 with IEC 60559
configure:84504: gcc -Wl,-rpath=/scratch/carloso/build4-lucid-cs/install//lib64:/scratch/carloso/build4-lucid-cs/install//usr/lib64 -Wl,--dynamic-linker=/scratch/carloso/build4-lucid-cs/install//lib64/ld-linux-x86-64.so.2 -std=gnu99 -o conftest -g -O2 -nostdinc -I/usr/local/tools/gcc-4.3.3/lib/gcc/x86_64-unknown-linux-gnu/4.3.2/include-fixed -I/scratch/carloso/build4-lucid-cs/install//usr/include -I/usr/local/tools/gcc-4.3.3/lib/gcc/x86_64-unknown-linux-gnu/4.3.2/include -Wall conftest.c >&5
/tmp/cceWScoH.o: In function `main':
/tmp/testdir/conftest.c:632: undefined reference to `log10f'
collect2: ld returned 1 exit status
configure:84508: $? = 1
configure: program exited with status 1
configure: failed program was:
...
configure:84537: result: no
(c) remove
This function is added automatically.
e.g.
~~~ config.log ~~~
gl_LIBOBJS=' asnprintf.o chdir-long.o dprintf.o fclose.o fcntl.o fflush.o fprintf.o fpurge.o fseek.o fseeko.o fseterr.o futimens.o glob.o ioctl.o isfinite.o isnand.o isnanf.o isnanl.o linkat.o nanosleep.o openat-proc.o printf.o printf-args.o printf-parse.o remove.o snprintf.o sprintf.o strerror_r.o strstr.o utimensat.o vasnprintf.o vdprintf.o vfprintf.o vprintf.o vsnprintf.o vsprintf.o'
gl_LTLIBOBJS=' asnprintf.lo chdir-long.lo dprintf.lo fclose.lo fcntl.lo fflush.lo fprintf.lo fpurge.lo fseek.lo fseeko.lo fseterr.lo futimens.lo glob.lo ioctl.lo isfinite.lo isnand.lo isnanf.lo isnanl.lo linkat.lo nanosleep.lo openat-proc.lo printf.lo printf-args.lo printf-parse.lo remove.lo snprintf.lo sprintf.lo strerror_r.lo strstr.lo utimensat.lo vasnprintf.lo vdprintf.lo vfprintf.lo vprintf.lo vsnprintf.lo vsprintf.lo'
~~~
There is no mention of this in the known issues list here:
http://sourceware.org/glibc/wiki/Testing/Gnulib
(d) strstr
This is the one that worries me.
configure:121073: checking whether strstr works in linear time
configure:121161: gcc -lm -Wl,-rpath=/scratch/carloso/build4-lucid-cs/install//lib64:/scratch/carloso/build4-lucid-cs/install//usr/lib64 -Wl,--dynamic-linker=/scratch/carloso/build4-lucid-cs/install//lib64/ld-linux-x86-64.so.2 -std=gnu99 -o conftest -g -O2 -nostdinc -I/usr/local/tools/gcc-4.3.3/lib/gcc/x86_64-unknown-linux-gnu/4.3.2/include-fixed -I/scratch/carloso/build4-lucid-cs/install//usr/include -I/usr/local/tools/gcc-4.3.3/lib/gcc/x86_64-unknown-linux-gnu/4.3.2/include -Wall conftest.c >&5
configure:121165: $? = 0
configure:121171: ./conftest
configure:121175: $? = 142
configure: program exited with status 142
configure: failed program was:
| /* confdefs.h. */
...
| /* end confdefs.h. */
|
| #include <signal.h> /* for signal */
| #include <string.h> /* for strstr */
| #include <stdlib.h> /* for malloc */
| #include <unistd.h> /* for alarm */
| static void quit (int sig) { exit (sig + 128); }
|
| int
| main ()
| {
|
| int result = 0;
| size_t m = 1000000;
| char *haystack = (char *) malloc (2 * m + 2);
| char *needle = (char *) malloc (m + 2);
| /* Failure to compile this test due to missing alarm is okay,
| since all such platforms (mingw) also have quadratic strstr. */
| signal (SIGALRM, quit);
| alarm (5);
| /* Check for quadratic performance. */
| if (haystack && needle)
| {
| memset (haystack, 'A', 2 * m);
| haystack[2 * m] = 'B';
| haystack[2 * m + 1] = 0;
| memset (needle, 'A', m);
| needle[m] = 'B';
| needle[m + 1] = 0;
| if (!strstr (haystack, needle))
| result |= 1;
| }
| return result;
|
| ;
| return 0;
| }
configure:121193: result: no
This looks like it might be a real bug.
Removing the alarm(5); and attaching to the long running process shows:
GNU gdb (Sourcery CodeBench 2012.09-1 - Preview) 7.2.50.20100908-cvs
Copyright (C) 2010 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law. Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-unknown-linux-gnu".
For bug reporting instructions, please see:
<https://support.codesourcery.com/GNUToolchain/>.
(gdb) attach 8102
Attaching to process 8102
Reading symbols from /tmp/testdir/conftest...done.
warning: Could not load shared library symbols for linux-vdso.so.1.
Do you need "set solib-search-path" or "set sysroot"?
Reading symbols from /scratch/carloso/build4-lucid-cs/install//lib64/libm.so.6...done.
Loaded symbols for /scratch/carloso/build4-lucid-cs/install//lib64/libm.so.6
Reading symbols from /scratch/carloso/build4-lucid-cs/install//lib64/libc.so.6...done.
Loaded symbols for /scratch/carloso/build4-lucid-cs/install//lib64/libc.so.6
Reading symbols from /scratch/carloso/build4-lucid-cs/install//lib64/ld-linux-x86-64.so.2...done.
Loaded symbols for /scratch/carloso/build4-lucid-cs/install//lib64/ld-linux-x86-64.so.2
0x00007fcc57c6c272 in __m128i_strloadu (s1=0x7fcc582c625d 'A' <repeats 200 times>..., s2=0x7fcc57a56010 'A' <repeats 200 times>...) at ../sysdeps/x86_64/multiarch/strstr.c:92
92 if (__builtin_expect ((int) ((size_t) p & 0xfff) > 0xff0, 0))
(gdb) bt
#0 0x00007fcc57c6c272 in __m128i_strloadu (s1=0x7fcc582c625d 'A' <repeats 200 times>..., s2=0x7fcc57a56010 'A' <repeats 200 times>...) at ../sysdeps/x86_64/multiarch/strstr.c:92
#1 __strstr_sse42 (s1=0x7fcc582c625d 'A' <repeats 200 times>..., s2=0x7fcc57a56010 'A' <repeats 200 times>...) at ../sysdeps/x86_64/multiarch/strstr.c:317
#2 0x0000000000400734 in main () at conftest.c:1019
(gdb) c
Continuing.
Does this mean we've picked up quadratic behaviour in the supposedly fast SSE42 optimized strstr? :-(
The test finishes in an awesome 5 minutes :-)
carloso@build4-lucid-cs:/tmp/testdir$ time ./conftest real 5m22.318s
user 4m21.060s
sys 0m0.000s
Could someone please verify this?
Cheers,
Carlos.
--
Carlos O'Donell
Mentor Graphics / CodeSourcery
carlos_odonell@mentor.com
carlos@codesourcery.com
+1 (613) 963 1026