public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/16611] Terrible code generated for vector<bool>
[not found] <bug-16611-2744@http.gcc.gnu.org/bugzilla/>
@ 2005-12-23 20:12 ` pcarlini at suse dot de
2005-12-23 21:13 ` pcarlini at suse dot de
` (3 subsequent siblings)
4 siblings, 0 replies; 10+ messages in thread
From: pcarlini at suse dot de @ 2005-12-23 20:12 UTC (permalink / raw)
To: gcc-bugs
------- Comment #9 from pcarlini at suse dot de 2005-12-23 20:12 -------
FWIW, on x86-linux at least, we are making progress on the compiler side.
With 4.0.2 I get (-O2):
00000000 <_Z1fRKSt6vectorIbSaIbEEj>:
0: 55 push %ebp
1: 89 e5 mov %esp,%ebp
3: 53 push %ebx
4: 8b 5d 08 mov 0x8(%ebp),%ebx
7: 8b 55 0c mov 0xc(%ebp),%edx
a: 8b 43 04 mov 0x4(%ebx),%eax
d: 01 d0 add %edx,%eax
f: 89 c1 mov %eax,%ecx
11: c1 f9 1f sar $0x1f,%ecx
14: c1 e9 1b shr $0x1b,%ecx
17: 8d 04 01 lea (%ecx,%eax,1),%eax
1a: 89 c2 mov %eax,%edx
1c: 83 e0 1f and $0x1f,%eax
1f: c1 fa 05 sar $0x5,%edx
22: c1 e2 02 shl $0x2,%edx
25: 03 13 add (%ebx),%edx
27: 29 c8 sub %ecx,%eax
29: 89 c1 mov %eax,%ecx
2b: 78 13 js 40 <_Z1fRKSt6vectorIbSaIbEEj+0x40>
2d: b8 01 00 00 00 mov $0x1,%eax
32: d3 e0 shl %cl,%eax
34: 85 02 test %eax,(%edx)
36: 5b pop %ebx
37: 5d pop %ebp
38: 0f 95 c0 setne %al
3b: 83 e0 01 and $0x1,%eax
3e: c3 ret
3f: 90 nop
40: 83 c1 20 add $0x20,%ecx
43: b8 01 00 00 00 mov $0x1,%eax
48: d3 e0 shl %cl,%eax
4a: 83 ea 04 sub $0x4,%edx
4d: 85 02 test %eax,(%edx)
4f: 5b pop %ebx
50: 5d pop %ebp
51: 0f 95 c0 setne %al
54: 83 e0 01 and $0x1,%eax
57: c3 ret
With current 4_1-branch:
00000000 <_Z1fRKSt6vectorIbSaIbEEj>:
0: 55 push %ebp
1: 89 e5 mov %esp,%ebp
3: 53 push %ebx
4: 8b 5d 08 mov 0x8(%ebp),%ebx
7: 8b 45 0c mov 0xc(%ebp),%eax
a: 8b 53 04 mov 0x4(%ebx),%edx
d: 01 d0 add %edx,%eax
f: 89 c1 mov %eax,%ecx
11: c1 f9 1f sar $0x1f,%ecx
14: c1 e9 1b shr $0x1b,%ecx
17: 8d 04 01 lea (%ecx,%eax,1),%eax
1a: 89 c2 mov %eax,%edx
1c: 83 e0 1f and $0x1f,%eax
1f: c1 fa 05 sar $0x5,%edx
22: c1 e2 02 shl $0x2,%edx
25: 03 13 add (%ebx),%edx
27: 29 c8 sub %ecx,%eax
29: 89 c1 mov %eax,%ecx
2b: 78 13 js 40 <_Z1fRKSt6vectorIbSaIbEEj+0x40>
2d: b8 01 00 00 00 mov $0x1,%eax
32: d3 e0 shl %cl,%eax
34: 85 02 test %eax,(%edx)
36: 5b pop %ebx
37: 5d pop %ebp
38: 0f 95 c0 setne %al
3b: 83 e0 01 and $0x1,%eax
3e: c3 ret
3f: 90 nop
40: 83 c1 20 add $0x20,%ecx
43: 83 ea 04 sub $0x4,%edx
46: eb e5 jmp 2d <_Z1fRKSt6vectorIbSaIbEEj+0x2d>
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=16611
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/16611] Terrible code generated for vector<bool>
[not found] <bug-16611-2744@http.gcc.gnu.org/bugzilla/>
2005-12-23 20:12 ` [Bug libstdc++/16611] Terrible code generated for vector<bool> pcarlini at suse dot de
@ 2005-12-23 21:13 ` pcarlini at suse dot de
2006-08-05 20:54 ` pcarlini at suse dot de
` (2 subsequent siblings)
4 siblings, 0 replies; 10+ messages in thread
From: pcarlini at suse dot de @ 2005-12-23 21:13 UTC (permalink / raw)
To: gcc-bugs
------- Comment #10 from pcarlini at suse dot de 2005-12-23 21:13 -------
Well, I'm not sure that, besides code size, 4_1 is doing better than 4.0.2, but
both are certainly better than 3.4.x.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=16611
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/16611] Terrible code generated for vector<bool>
[not found] <bug-16611-2744@http.gcc.gnu.org/bugzilla/>
2005-12-23 20:12 ` [Bug libstdc++/16611] Terrible code generated for vector<bool> pcarlini at suse dot de
2005-12-23 21:13 ` pcarlini at suse dot de
@ 2006-08-05 20:54 ` pcarlini at suse dot de
2006-08-06 14:46 ` paolo at gcc dot gnu dot org
2006-08-06 14:48 ` pcarlini at suse dot de
4 siblings, 0 replies; 10+ messages in thread
From: pcarlini at suse dot de @ 2006-08-05 20:54 UTC (permalink / raw)
To: gcc-bugs
--
pcarlini at suse dot de changed:
What |Removed |Added
----------------------------------------------------------------------------
AssignedTo|unassigned at gcc dot gnu |pcarlini at suse dot de
|dot org |
Status|NEW |ASSIGNED
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=16611
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/16611] Terrible code generated for vector<bool>
[not found] <bug-16611-2744@http.gcc.gnu.org/bugzilla/>
` (2 preceding siblings ...)
2006-08-05 20:54 ` pcarlini at suse dot de
@ 2006-08-06 14:46 ` paolo at gcc dot gnu dot org
2006-08-06 14:48 ` pcarlini at suse dot de
4 siblings, 0 replies; 10+ messages in thread
From: paolo at gcc dot gnu dot org @ 2006-08-06 14:46 UTC (permalink / raw)
To: gcc-bugs
------- Comment #11 from paolo at gcc dot gnu dot org 2006-08-06 14:45 -------
Subject: Bug 16611
Author: paolo
Date: Sun Aug 6 14:45:04 2006
New Revision: 115972
URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=115972
Log:
2006-08-06 Paolo Carlini <pcarlini@suse.de>
PR libstdc++/16611
* include/bits/stl_bvector.h (vector<bool>::operator[],
vector<bool>::operator[] const): Do not use iterator::operator+,
hand code.
Modified:
trunk/libstdc++-v3/ChangeLog
trunk/libstdc++-v3/include/bits/stl_bvector.h
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=16611
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/16611] Terrible code generated for vector<bool>
[not found] <bug-16611-2744@http.gcc.gnu.org/bugzilla/>
` (3 preceding siblings ...)
2006-08-06 14:46 ` paolo at gcc dot gnu dot org
@ 2006-08-06 14:48 ` pcarlini at suse dot de
4 siblings, 0 replies; 10+ messages in thread
From: pcarlini at suse dot de @ 2006-08-06 14:48 UTC (permalink / raw)
To: gcc-bugs
------- Comment #12 from pcarlini at suse dot de 2006-08-06 14:47 -------
Now I get:
00000000 <_Z1fRKSt6vectorIbSaIbEEj>:
0: 55 push %ebp
1: 89 e5 mov %esp,%ebp
3: 8b 45 08 mov 0x8(%ebp),%eax
6: 8b 4d 0c mov 0xc(%ebp),%ecx
9: 53 push %ebx
a: 8b 10 mov (%eax),%edx
c: b8 01 00 00 00 mov $0x1,%eax
11: 89 cb mov %ecx,%ebx
13: 83 e1 1f and $0x1f,%ecx
16: c1 eb 05 shr $0x5,%ebx
19: d3 e0 shl %cl,%eax
1b: 85 04 9a test %eax,(%edx,%ebx,4)
1e: 5b pop %ebx
1f: 5d pop %ebp
20: 0f 95 c0 setne %al
23: 0f b6 c0 movzbl %al,%eax
26: c3 ret
I guess we can close the library issue.
--
pcarlini at suse dot de changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|ASSIGNED |RESOLVED
Resolution| |FIXED
Target Milestone|--- |4.2.0
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=16611
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/16611] New: Terrible code generated for vector<bool>
@ 2004-07-17 21:57 falk at debian dot org
2005-04-12 8:07 ` [Bug libstdc++/16611] " falk at debian dot org
` (4 more replies)
0 siblings, 5 replies; 10+ messages in thread
From: falk at debian dot org @ 2004-07-17 21:57 UTC (permalink / raw)
To: gcc-bugs
If I look at the assembly of this function:
bool f(const std::vector<bool>& v, std::size_t x) {
return v[x];
}
I get:
0000000000000020 <f(std::vector<bool, std::allocator<bool> > const&, unsigned
long)>:
20: 08 00 50 a0 ldl t1,8(a0)
24: 00 00 70 a4 ldq t2,0(a0)
28: 90 ff de 23 lda sp,-112(sp)
2c: 21 f6 41 48 zapnot t1,0xf,t0
30: 68 00 5e b0 stl t1,104(sp)
34: 48 00 5e b0 stl t1,72(sp)
38: 11 04 21 42 addq a1,t0,a1
3c: 08 00 5e b0 stl t1,8(sp)
40: 38 00 5e b0 stl t1,56(sp)
44: 81 f7 27 4a sra a1,0x3f,t0
48: 60 00 7e b4 stq t2,96(sp)
4c: 40 00 7e b4 stq t2,64(sp)
50: 81 56 27 48 srl t0,0x3a,t0
54: 00 00 7e b4 stq t2,0(sp)
58: 30 00 7e b4 stq t2,48(sp)
5c: 01 04 21 42 addq a1,t0,t0
60: 81 d7 20 48 sra t0,0x6,t0
64: 22 d7 20 48 sll t0,0x6,t1
68: 41 06 23 40 s8addq t0,t2,t0
6c: 31 05 22 42 subq a1,t1,a1
70: f8 ff 61 20 lda t2,-8(t0)
74: 40 00 51 20 lda t1,64(a1)
78: 0d 00 20 ea blt a1,b0 <f(std::vector<bool, std::allocator<bool>
> const&, unsigned long)+0x90>
7c: 60 00 3e b4 stq t0,96(sp)
80: 68 00 3e b2 stl a1,104(sp)
84: 68 00 3e a0 ldl t0,104(sp)
88: 60 00 5e a4 ldq t1,96(sp)
8c: 01 00 1f 20 lda v0,1
90: 20 07 01 48 sll v0,t0,v0
94: 00 00 22 a4 ldq t0,0(t1)
98: 00 00 01 44 and v0,t0,v0
9c: a0 03 e0 43 cmpult zero,v0,v0
a0: 70 00 de 23 lda sp,112(sp)
a4: 01 80 fa 6b ret
a8: 1f 04 ff 47 nop
ac: 00 00 fe 2f unop
b0: 68 00 5e b0 stl t1,104(sp)
b4: 60 00 7e b4 stq t2,96(sp)
b8: f2 ff ff c3 br 84 <f(std::vector<bool, std::allocator<bool> >
const&, unsigned long)+0x64>
bc: 00 00 fe 2f unop
It should really look more like the code I get for
struct vector_bool { unsigned long *data; };
bool f(const vector_bool& v, std::size_t i) {
return (v.data[i / 64] >> (i % 64)) & 1;
}
which is
0000000000000000 <f(vector_bool const&, unsigned long)>:
0: 00 00 50 a4 ldq t1,0(a0)
4: 81 d6 20 4a srl a1,0x6,t0
8: 11 f0 27 46 and a1,0x3f,a1
c: 41 06 22 40 s8addq t0,t1,t0
10: 00 00 01 a4 ldq v0,0(t0)
14: 80 06 11 48 srl v0,a1,v0
18: 00 30 00 44 and v0,0x1,v0
1c: 01 80 fa 6b ret
The code for .at() looks even more horrible.
--
Summary: Terrible code generated for vector<bool>
Product: gcc
Version: 3.5.0
Status: UNCONFIRMED
Keywords: missed-optimization
Severity: normal
Priority: P2
Component: libstdc++
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: falk at debian dot org
CC: gcc-bugs at gcc dot gnu dot org
GCC build triplet: alphaev68-unknown-linux-gnu
GCC host triplet: alphaev68-unknown-linux-gnu
GCC target triplet: alphaev68-unknown-linux-gnu
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=16611
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/16611] Terrible code generated for vector<bool>
2004-07-17 21:57 [Bug libstdc++/16611] New: " falk at debian dot org
@ 2005-04-12 8:07 ` falk at debian dot org
2005-04-12 14:31 ` sabre at nondot dot org
` (3 subsequent siblings)
4 siblings, 0 replies; 10+ messages in thread
From: falk at debian dot org @ 2005-04-12 8:07 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From falk at debian dot org 2005-04-12 08:07 -------
(In reply to comment #3)
> This code from stl_bvector.h is the problem: [...]
Hmm, right. I don't fully understand why it is done in this complicated
manner, does vector<bool>::operator[] need to do anything more than my
example function? Anyway, I'll reassign it to libstdc++... feel free to
close it if it is unavoidable, or reassign back to tree-optimize if it is
actually an optimizer deficiency.
--
What |Removed |Added
----------------------------------------------------------------------------
Component|tree-optimization |libstdc++
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=16611
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/16611] Terrible code generated for vector<bool>
2004-07-17 21:57 [Bug libstdc++/16611] New: " falk at debian dot org
2005-04-12 8:07 ` [Bug libstdc++/16611] " falk at debian dot org
@ 2005-04-12 14:31 ` sabre at nondot dot org
2005-04-17 16:35 ` pcarlini at suse dot de
` (2 subsequent siblings)
4 siblings, 0 replies; 10+ messages in thread
From: sabre at nondot dot org @ 2005-04-12 14:31 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From sabre at nondot dot org 2005-04-12 14:31 -------
This is definately a libstdc++ issue.
-Chris
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=16611
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/16611] Terrible code generated for vector<bool>
2004-07-17 21:57 [Bug libstdc++/16611] New: " falk at debian dot org
2005-04-12 8:07 ` [Bug libstdc++/16611] " falk at debian dot org
2005-04-12 14:31 ` sabre at nondot dot org
@ 2005-04-17 16:35 ` pcarlini at suse dot de
2005-04-18 8:10 ` falk at debian dot org
2005-04-18 14:23 ` pcarlini at suse dot de
4 siblings, 0 replies; 10+ messages in thread
From: pcarlini at suse dot de @ 2005-04-17 16:35 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pcarlini at suse dot de 2005-04-17 16:34 -------
Hi. It can well be a libstdc++ problem, and indeed I can imagine ways to avoid
signed integers in the code. However, I'm not sure that someone will actually
do the work, given the soon-to-be-deprecated status of vector<bool>... All in
all, wouldn't be more useful trying to improve the optimization of the code
as-is?!?
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=16611
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/16611] Terrible code generated for vector<bool>
2004-07-17 21:57 [Bug libstdc++/16611] New: " falk at debian dot org
` (2 preceding siblings ...)
2005-04-17 16:35 ` pcarlini at suse dot de
@ 2005-04-18 8:10 ` falk at debian dot org
2005-04-18 14:23 ` pcarlini at suse dot de
4 siblings, 0 replies; 10+ messages in thread
From: falk at debian dot org @ 2005-04-18 8:10 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From falk at debian dot org 2005-04-18 08:10 -------
(In reply to comment #6)
> Hi. It can well be a libstdc++ problem, and indeed I can imagine ways to avoid
> signed integers in the code. However, I'm not sure that someone will actually
> do the work, given the soon-to-be-deprecated status of vector<bool>...
This is news to me. Does this mean that vector<bool> is not going to be special-
cased any more? That seems like a very bad idea to me, since programs will
suddenly take 8 times as much memory (or even more). What's the rationale?
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=16611
^ permalink raw reply [flat|nested] 10+ messages in thread
* [Bug libstdc++/16611] Terrible code generated for vector<bool>
2004-07-17 21:57 [Bug libstdc++/16611] New: " falk at debian dot org
` (3 preceding siblings ...)
2005-04-18 8:10 ` falk at debian dot org
@ 2005-04-18 14:23 ` pcarlini at suse dot de
4 siblings, 0 replies; 10+ messages in thread
From: pcarlini at suse dot de @ 2005-04-18 14:23 UTC (permalink / raw)
To: gcc-bugs
------- Additional Comments From pcarlini at suse dot de 2005-04-18 14:23 -------
> This is news to me. Does this mean that vector<bool> is not going to be special-
> cased any more? That seems like a very bad idea to me, since programs will
> suddenly take 8 times as much memory (or even more). What's the rationale?
Oh, well, this is a *well* known issue: roughly, the C++ standard committee
considers vector<bool> a serious mistake, because, in short, doesn't conform
to *many* of the standard requirements for containers. The current plan (as
of Lillehammer, last week) consists of two parts: 1- Deprecating vector<bool>,
2- Adding a new bit_vector container. Of course no one wants to remove the
current vector<bool> without a replacement. Please Google a bit for further
details or ask me privately.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=16611
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2006-08-06 14:48 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
[not found] <bug-16611-2744@http.gcc.gnu.org/bugzilla/>
2005-12-23 20:12 ` [Bug libstdc++/16611] Terrible code generated for vector<bool> pcarlini at suse dot de
2005-12-23 21:13 ` pcarlini at suse dot de
2006-08-05 20:54 ` pcarlini at suse dot de
2006-08-06 14:46 ` paolo at gcc dot gnu dot org
2006-08-06 14:48 ` pcarlini at suse dot de
2004-07-17 21:57 [Bug libstdc++/16611] New: " falk at debian dot org
2005-04-12 8:07 ` [Bug libstdc++/16611] " falk at debian dot org
2005-04-12 14:31 ` sabre at nondot dot org
2005-04-17 16:35 ` pcarlini at suse dot de
2005-04-18 8:10 ` falk at debian dot org
2005-04-18 14:23 ` pcarlini at suse dot de
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).