public inbox for gcc-bugs@sourceware.org
help / color / mirror / Atom feed
* [Bug libstdc++/30203] New: std::vector::size() 10x speedup (patch)
@ 2006-12-13 17:38 charles at rebelbase dot com
2006-12-13 18:07 ` [Bug libstdc++/30203] " chris at bubblescope dot net
` (5 more replies)
0 siblings, 6 replies; 7+ messages in thread
From: charles at rebelbase dot com @ 2006-12-13 17:38 UTC (permalink / raw)
To: gcc-bugs
vector::size() in bits/stl_vector.h is currently implemented as
size_type
size() const
{ return size_type(end() - begin()); }
A faster implementation is
size_type
size() const
{ return _M_impl._M_finish - _M_impl._M_start; }
Which avoids the temporary iterators' life cycles
and operator- calls.
I tried a simple timing test on both implementations,
and the latter appears to be 10x faster:
(11:35:56)(charles xyzzy)(~): cat test.cc
#include <vector>
int main () {
std::vector<int> x (100);
unsigned long l = 0;
const unsigned long iterations = 100000000;
for (unsigned long i=0; i<iterations; ++i)
l += x.size ();
return 0;
}
(11:35:58)(charles xyzzy)(~): g++ -o test test.cc -lstdc++
(11:36:05)(charles xyzzy)(~): time ./test
real 0m3.692s
user 0m3.676s
sys 0m0.004s
(11:36:10)(charles xyzzy)(~): cat test2.cc
#include <vector>
int main () {
std::vector<int> x (100);
unsigned long l = 0;
const unsigned long iterations = 100000000;
for (unsigned long i=0; i<iterations; ++i)
l += x._M_impl._M_finish - x._M_impl._M_start;
return 0;
}
(11:36:13)(charles xyzzy)(~): g++ -o test2 test2.cc -lstdc++
(11:36:19)(charles xyzzy)(~): time ./test2
real 0m0.342s
user 0m0.336s
sys 0m0.004s
--
Summary: std::vector::size() 10x speedup (patch)
Product: gcc
Version: unknown
Status: UNCONFIRMED
Severity: enhancement
Priority: P3
Component: libstdc++
AssignedTo: unassigned at gcc dot gnu dot org
ReportedBy: charles at rebelbase dot com
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30203
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug libstdc++/30203] std::vector::size() 10x speedup (patch)
2006-12-13 17:38 [Bug libstdc++/30203] New: std::vector::size() 10x speedup (patch) charles at rebelbase dot com
@ 2006-12-13 18:07 ` chris at bubblescope dot net
2006-12-14 2:48 ` pinskia at gcc dot gnu dot org
` (4 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: chris at bubblescope dot net @ 2006-12-13 18:07 UTC (permalink / raw)
To: gcc-bugs
------- Comment #1 from chris at bubblescope dot net 2006-12-13 18:07 -------
-O1 is enough to remove all advantages of this patch.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30203
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug libstdc++/30203] std::vector::size() 10x speedup (patch)
2006-12-13 17:38 [Bug libstdc++/30203] New: std::vector::size() 10x speedup (patch) charles at rebelbase dot com
2006-12-13 18:07 ` [Bug libstdc++/30203] " chris at bubblescope dot net
@ 2006-12-14 2:48 ` pinskia at gcc dot gnu dot org
2006-12-14 10:20 ` pcarlini at suse dot de
` (3 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: pinskia at gcc dot gnu dot org @ 2006-12-14 2:48 UTC (permalink / raw)
To: gcc-bugs
------- Comment #2 from pinskia at gcc dot gnu dot org 2006-12-14 02:47 -------
Can you test with -O1 or above?
As mentioned in comment #1, this should remove all advatages gained from the
"inlined" version.
--
pinskia at gcc dot gnu dot org changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|UNCONFIRMED |WAITING
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30203
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug libstdc++/30203] std::vector::size() 10x speedup (patch)
2006-12-13 17:38 [Bug libstdc++/30203] New: std::vector::size() 10x speedup (patch) charles at rebelbase dot com
2006-12-13 18:07 ` [Bug libstdc++/30203] " chris at bubblescope dot net
2006-12-14 2:48 ` pinskia at gcc dot gnu dot org
@ 2006-12-14 10:20 ` pcarlini at suse dot de
2006-12-14 17:59 ` charles at rebelbase dot com
` (2 subsequent siblings)
5 siblings, 0 replies; 7+ messages in thread
From: pcarlini at suse dot de @ 2006-12-14 10:20 UTC (permalink / raw)
To: gcc-bugs
------- Comment #3 from pcarlini at suse dot de 2006-12-14 10:19 -------
Of course. Please, let's not go along this route: it's very well known that an
efficient and clean implementation on the library (in particular the "STL"
part) relies on very many tiny functions being inlined.
--
pcarlini at suse dot de changed:
What |Removed |Added
----------------------------------------------------------------------------
Status|WAITING |RESOLVED
Resolution| |INVALID
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30203
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug libstdc++/30203] std::vector::size() 10x speedup (patch)
2006-12-13 17:38 [Bug libstdc++/30203] New: std::vector::size() 10x speedup (patch) charles at rebelbase dot com
` (2 preceding siblings ...)
2006-12-14 10:20 ` pcarlini at suse dot de
@ 2006-12-14 17:59 ` charles at rebelbase dot com
2006-12-15 5:27 ` dberlin at dberlin dot org
2006-12-15 5:27 ` [Bug libstdc++/30203] New: " Daniel Berlin
5 siblings, 0 replies; 7+ messages in thread
From: charles at rebelbase dot com @ 2006-12-14 17:59 UTC (permalink / raw)
To: gcc-bugs
------- Comment #4 from charles at rebelbase dot com 2006-12-14 17:59 -------
(In reply to comment #2)
> Can you test with -O1 or above?
> As mentioned in comment #1, this should remove all advatages gained from the
> "inlined" version.
It does indeed. Thanks for your time.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30203
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [Bug libstdc++/30203] New: std::vector::size() 10x speedup (patch)
2006-12-13 17:38 [Bug libstdc++/30203] New: std::vector::size() 10x speedup (patch) charles at rebelbase dot com
` (4 preceding siblings ...)
2006-12-15 5:27 ` dberlin at dberlin dot org
@ 2006-12-15 5:27 ` Daniel Berlin
5 siblings, 0 replies; 7+ messages in thread
From: Daniel Berlin @ 2006-12-15 5:27 UTC (permalink / raw)
To: gcc-bugzilla; +Cc: gcc-bugs
And what are the timings with a recent version of g++ and actually
turning on optimization?
On 13 Dec 2006 17:38:06 -0000, charles at rebelbase dot com
<gcc-bugzilla@gcc.gnu.org> wrote:
> vector::size() in bits/stl_vector.h is currently implemented as
>
> size_type
> size() const
> { return size_type(end() - begin()); }
>
> A faster implementation is
>
> size_type
> size() const
> { return _M_impl._M_finish - _M_impl._M_start; }
>
> Which avoids the temporary iterators' life cycles
> and operator- calls.
>
> I tried a simple timing test on both implementations,
> and the latter appears to be 10x faster:
>
> (11:35:56)(charles xyzzy)(~): cat test.cc
> #include <vector>
> int main () {
> std::vector<int> x (100);
> unsigned long l = 0;
> const unsigned long iterations = 100000000;
> for (unsigned long i=0; i<iterations; ++i)
> l += x.size ();
> return 0;
> }
> (11:35:58)(charles xyzzy)(~): g++ -o test test.cc -lstdc++
> (11:36:05)(charles xyzzy)(~): time ./test
>
> real 0m3.692s
> user 0m3.676s
> sys 0m0.004s
> (11:36:10)(charles xyzzy)(~): cat test2.cc
> #include <vector>
> int main () {
> std::vector<int> x (100);
> unsigned long l = 0;
> const unsigned long iterations = 100000000;
> for (unsigned long i=0; i<iterations; ++i)
> l += x._M_impl._M_finish - x._M_impl._M_start;
> return 0;
> }
> (11:36:13)(charles xyzzy)(~): g++ -o test2 test2.cc -lstdc++
> (11:36:19)(charles xyzzy)(~): time ./test2
>
> real 0m0.342s
> user 0m0.336s
> sys 0m0.004s
>
>
> --
> Summary: std::vector::size() 10x speedup (patch)
> Product: gcc
> Version: unknown
> Status: UNCONFIRMED
> Severity: enhancement
> Priority: P3
> Component: libstdc++
> AssignedTo: unassigned at gcc dot gnu dot org
> ReportedBy: charles at rebelbase dot com
>
>
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30203
>
>
^ permalink raw reply [flat|nested] 7+ messages in thread
* [Bug libstdc++/30203] std::vector::size() 10x speedup (patch)
2006-12-13 17:38 [Bug libstdc++/30203] New: std::vector::size() 10x speedup (patch) charles at rebelbase dot com
` (3 preceding siblings ...)
2006-12-14 17:59 ` charles at rebelbase dot com
@ 2006-12-15 5:27 ` dberlin at dberlin dot org
2006-12-15 5:27 ` [Bug libstdc++/30203] New: " Daniel Berlin
5 siblings, 0 replies; 7+ messages in thread
From: dberlin at dberlin dot org @ 2006-12-15 5:27 UTC (permalink / raw)
To: gcc-bugs
------- Comment #5 from dberlin at gcc dot gnu dot org 2006-12-15 05:27 -------
Subject: Re: New: std::vector::size() 10x speedup (patch)
And what are the timings with a recent version of g++ and actually
turning on optimization?
On 13 Dec 2006 17:38:06 -0000, charles at rebelbase dot com
<gcc-bugzilla@gcc.gnu.org> wrote:
> vector::size() in bits/stl_vector.h is currently implemented as
>
> size_type
> size() const
> { return size_type(end() - begin()); }
>
> A faster implementation is
>
> size_type
> size() const
> { return _M_impl._M_finish - _M_impl._M_start; }
>
> Which avoids the temporary iterators' life cycles
> and operator- calls.
>
> I tried a simple timing test on both implementations,
> and the latter appears to be 10x faster:
>
> (11:35:56)(charles xyzzy)(~): cat test.cc
> #include <vector>
> int main () {
> std::vector<int> x (100);
> unsigned long l = 0;
> const unsigned long iterations = 100000000;
> for (unsigned long i=0; i<iterations; ++i)
> l += x.size ();
> return 0;
> }
> (11:35:58)(charles xyzzy)(~): g++ -o test test.cc -lstdc++
> (11:36:05)(charles xyzzy)(~): time ./test
>
> real 0m3.692s
> user 0m3.676s
> sys 0m0.004s
> (11:36:10)(charles xyzzy)(~): cat test2.cc
> #include <vector>
> int main () {
> std::vector<int> x (100);
> unsigned long l = 0;
> const unsigned long iterations = 100000000;
> for (unsigned long i=0; i<iterations; ++i)
> l += x._M_impl._M_finish - x._M_impl._M_start;
> return 0;
> }
> (11:36:13)(charles xyzzy)(~): g++ -o test2 test2.cc -lstdc++
> (11:36:19)(charles xyzzy)(~): time ./test2
>
> real 0m0.342s
> user 0m0.336s
> sys 0m0.004s
>
>
> --
> Summary: std::vector::size() 10x speedup (patch)
> Product: gcc
> Version: unknown
> Status: UNCONFIRMED
> Severity: enhancement
> Priority: P3
> Component: libstdc++
> AssignedTo: unassigned at gcc dot gnu dot org
> ReportedBy: charles at rebelbase dot com
>
>
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30203
>
>
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30203
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2006-12-15 5:27 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2006-12-13 17:38 [Bug libstdc++/30203] New: std::vector::size() 10x speedup (patch) charles at rebelbase dot com
2006-12-13 18:07 ` [Bug libstdc++/30203] " chris at bubblescope dot net
2006-12-14 2:48 ` pinskia at gcc dot gnu dot org
2006-12-14 10:20 ` pcarlini at suse dot de
2006-12-14 17:59 ` charles at rebelbase dot com
2006-12-15 5:27 ` dberlin at dberlin dot org
2006-12-15 5:27 ` [Bug libstdc++/30203] New: " Daniel Berlin
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).