[Bug libstdc++/35968] nth_element fails to meet its complexity requirements
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968 Anders Kaseorg changed: What|Removed |Added CC||andersk at mit dot edu --- Comment #11 from Anders Kaseorg --- (In reply to Patrick J. LoPresti from comment #10) > Complexity: Linear on average. > > It is not obvious (to me) what distribution the "on average" refers to. All > permutations of input with equal probability, I suppose (?) Expected running time is typically measured over the random choices (if any) made internally by the algorithm, not over a random input distribution. For example, quickselect with random pivot selection would satisfy this, but not quickselect with deterministic pivot selection. Sometimes expected running time on average-case inputs is studied, but referring to that definitely requires more words.
[Bug libstdc++/35968] nth_element fails to meet its complexity requirements
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=35968 --- Comment #13 from Anders Kaseorg --- (In reply to Patrick J. LoPresti from comment #12) > I am familiar with the usual algorithmic complexity definitions. > > So, just to be clear... Your assertion is that the C++ standards committee > adopted a specification that rules out a deterministic implementation? I should have been clearer: I’m saying it rules out quickselect with a deterministic pivot selection rule that doesn’t inspect Θ(n) elements. Quickselect with randomized Θ(1) pivot selection would satisfy the specification, as would quickselect with deterministic Θ(n) pivot selection by median-of-medians or similar, but not quickselect with deterministic Θ(1) pivot selection by taking the first element or similar.
[Bug c++/50093] New: [4.6 Regression] STL containers of non-default-constructible classes fail under -std=c++0x
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50093
Bug #: 50093
Summary: [4.6 Regression] STL containers of
non-default-constructible classes fail under
-std=c++0x
Classification: Unclassified
Product: gcc
Version: unknown
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: c++
AssignedTo: unassig...@gcc.gnu.org
ReportedBy: ande...@mit.edu
This code builds with ‘g++-4.5’, ‘g++-4.5 -std=c++0x’, and ‘g++-4.6’, but fails
with ‘g++-4.6 -std=c++0x’:
#include
class Foo {
Foo(int) {}
};
template class std::vector;
int main() {return 0;}
$ g++-4.6 -std=c++0x foo.cc
In file included from /usr/include/c++/4.6/vector:63:0,
from foo.cc:1:
/usr/include/c++/4.6/bits/stl_construct.h: In function ‘void
std::_Construct(_T1*, _Args&& ...) [with _T1 = Foo, _Args = {}]’:
/usr/include/c++/4.6/bits/stl_uninitialized.h:481:3: instantiated from
‘static void
std::__uninitialized_default_n_1<_TrivialValueType>::__uninit_default_n(_ForwardIterator,
_Size) [with _ForwardIterator = Foo*, _Size = long unsigned int, bool
_TrivialValueType = false]’
/usr/include/c++/4.6/bits/stl_uninitialized.h:529:7: instantiated from ‘void
std::__uninitialized_default_n(_ForwardIterator, _Size) [with _ForwardIterator
= Foo*, _Size = long unsigned int]’
/usr/include/c++/4.6/bits/stl_uninitialized.h:589:7: instantiated from ‘void
std::__uninitialized_default_n_a(_ForwardIterator, _Size, std::allocator<_Tp>&)
[with _ForwardIterator = Foo*, _Size = long unsigned int, _Tp = Foo]’
/usr/include/c++/4.6/bits/stl_vector.h:1134:2: instantiated from ‘void
std::vector<_Tp, _Alloc>::_M_default_initialize(std::vector<_Tp,
_Alloc>::size_type) [with _Tp = Foo, _Alloc = std::allocator,
std::vector<_Tp, _Alloc>::size_type = long unsigned int]’
foo.cc:5:21: instantiated from here
/usr/include/c++/4.6/bits/stl_construct.h:76:7: error: no matching function for
call to ‘Foo::Foo()’
/usr/include/c++/4.6/bits/stl_construct.h:76:7: note: candidates are:
foo.cc:3:5: note: Foo::Foo(int)
foo.cc:3:5: note: candidate expects 1 argument, 0 provided
foo.cc:2:7: note: constexpr Foo::Foo(const Foo&)
foo.cc:2:7: note: candidate expects 1 argument, 0 provided
foo.cc:2:7: note: constexpr Foo::Foo(Foo&&)
foo.cc:2:7: note: candidate expects 1 argument, 0 provided
[Bug c++/50093] [4.6 Regression] STL containers of non-default-constructible classes fail under -std=c++0x
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=50093 Anders Kaseorg changed: What|Removed |Added Known to work||4.5.3 Known to fail||4.6.1 --- Comment #1 from Anders Kaseorg 2011-08-15 20:06:59 UTC --- Works with g++-4.5 (Ubuntu/Linaro 4.5.3-5ubuntu1) 4.5.3. Fails with g++-4.6 (Ubuntu/Linaro 4.6.1-6ubuntu6) 4.6.1. (Both on Ubuntu 11.10 alpha, amd64.)
[Bug c/47901] -Wall should not imply -Wformat-zero-length by default
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47901
--- Comment #4 from Anders Kaseorg 2012-04-23 20:10:22
UTC ---
Yes, I understand what -Wall is supposed to mean.
I don’t have a problem with -Wall warning about ‘if (foo = 3)’ when I probably
intended ‘if (foo == 3)’ and I could have written ‘if ((foo = 3))’ if that’s
what I really wanted.
I don’t have a problem with -Wall warning about ‘printf("hello", "world")’ when
I probably intended ‘printf("hello %s", "world")’ and I could have written
‘printf("hello")’ if that’s what I really wanted.
But ‘custom_printf_like_function(foo, "")’ is something different. What do you
think that line indicates I intended? What coding style do you think -Wall is
expecting if I really meant the empty string?
[Bug c/47901] -Wall should not imply -Wformat-zero-length by default
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47901
--- Comment #5 from Anders Kaseorg 2012-04-23 20:22:20
UTC ---
I’m not sure ("%s", "") is a suitable replacement in general. Maybe this is a
far-fetched example, but what the purpose of custom_printf is to shell-quote
all its arguments, so that custom_printf(foo, "") writes "some_command" with no
arguments but custom_printf(foo, "%s", "") writes "some_command ''" with a
single empty argument?
In any event, ("%s", "") is certainly different code with a potential runtime
cost, and it’s not fair for -Wall to complain about the more straightforward
("") unless it’s reasonably likely for that code to be hiding some class of
bugs. Is it?
(Another real-world example from a project I help maintain:
https://github.com/barnowl/barnowl/blob/barnowl-1.8.1/keys.c#L337 )
[Bug c/47901] -Wall should not imply -Wformat-zero-length by default
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=47901 --- Comment #7 from Anders Kaseorg 2012-04-23 21:31:18 UTC --- That’s a _much_ higher-level style decision than assumed by any of the other -Wall warnings (or indeed any other warning switches at all), and a questionable one at that. -Wall should not encourage me to duplicate all my custom printf-like functions just so they can be used with the empty string. I understand that I can turn this warning off, but this bug is about the defaults, and defaults are important.
[Bug c++/56137] New: std::initializer_list accepts invalid designated initializers
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=56137
Bug #: 56137
Summary: std::initializer_list accepts invalid designated
initializers
Classification: Unclassified
Product: gcc
Version: 4.7.2
Status: UNCONFIRMED
Severity: minor
Priority: P3
Component: c++
AssignedTo: unassig...@gcc.gnu.org
ReportedBy: ande...@mit.edu
The following initializers are incorrectly accepted by g++ -std=c++11
(4.7.2-19ubuntu1 and 4.8.0 20130121-0ubuntu1):
#include
std::vector v = {.ignored_name = 1, .also_ignored_name = 2};
#include
std::initializer_list l = {.ignored_name = 1, .also_ignored_name = 2};
[Bug c++/79301] New: With -Werror=pedantic outside C++17 mode, __has_cpp_attribute(fallthrough) is nonzero but [[fallthrough]] fails
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=79301
Bug ID: 79301
Summary: With -Werror=pedantic outside C++17 mode,
__has_cpp_attribute(fallthrough) is nonzero but
[[fallthrough]] fails
Product: gcc
Version: 7.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: c++
Assignee: unassigned at gcc dot gnu.org
Reporter: andersk at mit dot edu
Target Milestone: ---
One would expect code like this to silence the new -Wimplicit-fallthrough
warning that’s been added to -Wextra:
switch (x) {
case 0:
printf("zero\n");
#if __has_cpp_attribute(fallthrough)
[[fallthrough]];
#elif __has_cpp_attribute(gnu::fallthrough)
[[gnu::falthrough]];
#endif
case 1:
printf("zero or one\n");
}
However, this fails to compile with -Werror=pedantic in C++14 mode or earlier:
“error: ‘fallthrough’ is a C++17 feature; use ‘gnu::fallthrough’
[-Werror=pedantic]”.
__has_cpp_attribute(fallthrough) should evaluate to 0 if [[fallthrough]] is not
going to work.
[Bug c++/79301] With -Werror=pedantic outside C++17 mode, __has_cpp_attribute(fallthrough) is nonzero but [[fallthrough]] fails
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=79301 --- Comment #3 from Anders Kaseorg --- (In reply to Jakub Jelinek from comment #2) > I think right now you need to use > #ifdef __has_cpp_attribute > # if __has_cpp_attribute(fallthrough) >= __cplusplus > [[fallthrough]]; Surely you intended* #if __has_cpp_attribute(fallthrough) && __cplusplus >= __has_cpp_attribute(fallthrough)? But neither version helps in current g++-7, where __cplusplus is 201402 (C++14) or 201500 (C++17), while __has_cpp_attribute(fallthrough) is greater than both: 201603. (* Yes, this is confusing, and I would suggest that this confusion is already a good argument for __has_cpp_attribute doing the language standard comparison itself rather than foisting it off on the programmer. That is, __has_cpp_attribute(fallthrough) should return 201500 (C++17 and higher) or 0 (C++14 and lower))
[Bug c++/79301] With -Werror=pedantic outside C++17 mode, __has_cpp_attribute(fallthrough) is nonzero but [[fallthrough]] fails
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=79301 --- Comment #5 from Anders Kaseorg --- (In reply to Jakub Jelinek from comment #4) > (In reply to Anders Kaseorg from comment #3) > > (In reply to Jakub Jelinek from comment #2) > > > I think right now you need to use > > > #ifdef __has_cpp_attribute > > > # if __has_cpp_attribute(fallthrough) >= __cplusplus > > > [[fallthrough]]; > > > > Surely you intended* #if __has_cpp_attribute(fallthrough) && __cplusplus >= > > __has_cpp_attribute(fallthrough)? > > No, I meant what I wrote. __has_cpp_attribute(fallthrough) gives you the > year + month when the feature has been introduced, and you then use it only > if it has been introduced before or at the same time as the C++ version > (__cplusplus gives you again year + month) you are compilining for. For the nonzero case, “before or at the same time” translates to <=, not >=.
[Bug c/65307] Incorrect optimization breaks basic arithmetic
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=65307 Anders Kaseorg changed: What|Removed |Added CC||andersk at mit dot edu --- Comment #2 from Anders Kaseorg --- Confirmed, except that changing two() * 2 to two() + two() or two() << 1 does not make a difference for me. This looks more related to inlining: -O1: works -O2: fails -O1 -finline-small-functions: fails -O2 -fno-inline-small-functions: works And if I mark two() and six() as inline, then it fails even at -O1. (GCC 4.9.2-10ubuntu7 on Ubuntu vivid amd64)
[Bug tree-optimization/61964] New: [4.8 regression] krb5 database propagation enters infinite loop; reduced test case
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964
Bug ID: 61964
Summary: [4.8 regression] krb5 database propagation enters
infinite loop; reduced test case
Product: gcc
Version: 4.8.3
Status: UNCONFIRMED
Severity: major
Priority: P3
Component: tree-optimization
Assignee: unassigned at gcc dot gnu.org
Reporter: andersk at mit dot edu
Kerberos is miscompiled by gcc-4.8. The impact is detailed at
https://bugs.launchpad.net/bugs/1347147, but here is a reduced test case. The
expected return is 0, but when compiled with gcc-4.8 -O2, it returns 1.
$ cat bug.c
struct node { struct node *next, *prev; } node;
struct head { struct node *first; } heads[5];
int k = 2;
struct head *head = &heads[2];
int main()
{
node.prev = (void *)head;
head->first = &node;
struct node *n = head->first;
struct head *h = &heads[k];
if (n->prev == (void *)h)
h->first = n->next;
else
n->prev->next = n->next;
n->next = h->first;
return n->next == &node;
}
$ gcc-4.7 -Wall -O2 bug.c -o bug; ./bug; echo $?
0
$ gcc-4.8 -Wall -O2 bug.c -o bug; ./bug; echo $?
1
$ gcc-4.9 -Wall -O2 bug.c -o bug; ./bug; echo $?
0
$ dpkg -l gcc-4.7 gcc-4.8 gcc-4.9
[…]
ii gcc-4.7 4.7.4-2ubuntu1 amd64 GNU C compiler
ii gcc-4.8 4.8.3-6ubuntu1 amd64 GNU C compiler
ii gcc-4.9 4.9.1-3ubuntu2 amd64 GNU C compiler
I bisected the point where the problem disappeared between 4.8 and 4.9 at
r202525. However, I don’t understand why. I’m scared by the fact that r202525
was intended to fix a “missed-optimization” bug (bug 58404).
[Bug tree-optimization/61964] [4.8 regression] krb5 database propagation enters infinite loop; reduced test case
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964 --- Comment #3 from Anders Kaseorg --- (In reply to Richard Biener from comment #1) > The testcase is violating strict-aliasing rules as you access a struct head > as struct node here: Agree with ghudson here: n->prev points to &heads[2], not &heads[0]. Although assigning a casted struct head * to a struct node * is arguably sloppy, the standard does not prohibit it, as long as it is never dereferenced in that form.
[Bug tree-optimization/61964] [4.8 regression] krb5 database propagation enters infinite loop; reduced test case
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964 --- Comment #4 from Anders Kaseorg --- Another bisect between 4.7 and 4.8 shows that the bug appeared with r189321 (bug 52009). My test case has triggers the bug in more versions than Kerberos does: as far as I can tell, Kerberos was unaffected until r192604.
[Bug tree-optimization/61964] [4.8/4.9 regression] krb5 database propagation enters infinite loop; reduced test case
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61964 --- Comment #17 from Anders Kaseorg --- Thanks. I verified that GCC 4.8 r213405 fixes my test case and the original Kerberos problem.
