Tue, 29 Apr 2008
GCC Tail-call Bug
Today I spent several hours debugging one of my distributed applications. The bug appeared to be in the sorting routine, which sometimes left the data not completely sorted. The strange thing was that when I added a debugging test at the end of each quick-sort recursive call (thus making sure I catch the unsorted data as early as possible), the problem has disappeared.
So, another Heisenbergish bug, I think. The source code is here: it is a straightforward recursive quick-sort, sorting entries with 32-bit key and 32-bit value (written to work on 64-bit systems only, do not bother to report that it is broken on legacy systems).
Now try to compile it and run with gcc -O2. For me
(gcc 4.1.2 from Fedora 8) it works. However, when using -O3
(or even -O2 -finline-functions) it doesn't. Also when
you uncomment the debug printout at the end of qsort_data(),
it should work even with -O3. I think the tail-call recursion
is not enabled when the debugging code is present.
Does it work for you? Is my code broken in a way I don't see? If this is not only a problem of my system, I will try to report it as a gcc bug.
5 replies for this story:
Spes wrote:
Yeah, I confirm the problem on all my system types -- Fedora 6, 8, CentOS 5, Gentoo 2008.0 beta (all with the gcc 4.1.2). I didn't review the code.
Spes wrote:
Btw. valdgrind is complaining about invalid reads and writes.
Yenya wrote: Re: valgrind
Well, I have never used valgrind, so I am not very familiar with its output. However, (at least some of) these warnings seem to be bogus: it complains about the initialization of data[] array at lines 30 and 31. I don't see anything wrong with it.
Yenya wrote: GCC bug id
OK, reported as http://gcc.gnu.org/bugzilla/show_bug.cgi?id=36082. I hope I am not making fool of myself with some stupid bug in my code.
Yenya wrote:
OK, I have apparently made fool of myself: when I rewrite the bucket_entry_t to be union of one 64-bit part and two 32-bit parts, and use 64-bit part for swapping entries, and 32-bit parts for accessing the key and value, it works. One would think it is equivalent to pointer casting. Maybe I should read the C standard some day.