[Bug libstdc++/30203] New: std::vector::size() 10x speedup (patch)

[Bug libstdc++/30203] New: std::vector::size() 10x speedup (patch)

[charles at rebelbase dot com]

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

[Bug libstdc++/30203] std::vector::size() 10x speedup (patch)

[chris at bubblescope dot net]

------- 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

[Bug libstdc++/30203] std::vector::size() 10x speedup (patch)

[pinskia at gcc dot gnu dot org]

------- 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

[Bug libstdc++/30203] std::vector::size() 10x speedup (patch)

[pcarlini at suse dot de]

------- 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

[Bug libstdc++/30203] std::vector::size() 10x speedup (patch)

[charles at rebelbase dot com]

------- 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

Re: [Bug libstdc++/30203] New: std::vector::size() 10x speedup (patch)

[Daniel Berlin]

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
>
>

[Bug libstdc++/30203] std::vector::size() 10x speedup (patch)

[dberlin at dberlin dot org]

------- 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