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

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

[charles at rebelbase dot com]

vector::operator[](size_type) in bits/stl_vector.h is currently implemented as

      reference
      operator[](size_type __n)
      { return *(begin() + __n); }

      const_reference
      operator[](size_type __n) const
      { return *(begin() + __n); }

A faster implementation would be:

      reference
      operator[](size_type __n)
      { return _M_impl._M_start[__n]; }

      const_reference
      operator[](size_type __n) const
      { return _M_impl._M_start[__n]; }

I tried a simple timing test on both implementations,
and the latter appears to be 10x faster:

(11:59:43)(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[50];
  return 0;
}
(12:00:14)(charles xyzzy)(~): g++ -o test test.cc -lstdc++
(12:00:22)(charles xyzzy)(~): time ./test

real    0m2.956s
user    0m2.948s
sys     0m0.008s
(12:00:27)(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_start[50];
  return 0;
}
(12:00:31)(charles xyzzy)(~): g++ -o test2 test2.cc -lstdc++
(12:00:39)(charles xyzzy)(~): time ./test2

real    0m0.228s
user    0m0.228s
sys     0m0.000s


-- 
           Summary: std::vector operator[] 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=30204

[Bug libstdc++/30204] std::vector operator[] 10x speedup (patch)

[chris at bubblescope dot net]

------- Comment #1 from chris at bubblescope dot net  2006-12-13 18:08 -------
-O1 is enough to remove all advantages of this patch.

Also, that isn't really a fair timing comparison, as you've removed the
function call altogether (I still expect it to be faster, but possibly not by
10x)


-- 

chris at bubblescope dot net changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |chris at bubblescope dot net


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30204

[Bug libstdc++/30204] std::vector operator[] 10x speedup (patch)

[pinskia at gcc dot gnu dot org]

------- Comment #2 from pinskia at gcc dot gnu dot org  2006-12-14 02:49 -------
Can you test with -O1 or above?
As mentioned in comment #1, this should remove all advatages gained from the
"inlined" version.

> Also, that isn't really a fair timing comparison, as you've removed the
> function call altogether (I still expect it to be faster, but possibly not by
> 10x)

For -O0, I would not doubt removing the function calls get a 10x speed up,
which is one of the reasons why -O1 makes this much faster than -O0 :).


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30204

[Bug libstdc++/30204] std::vector operator[] 10x speedup (patch)

[pcarlini at suse dot de]

------- Comment #3 from pcarlini at suse dot de  2006-12-14 10:33 -------
Likewise...


-- 

pcarlini at suse dot de changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |RESOLVED
         Resolution|                            |INVALID


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30204

[Bug libstdc++/30204] std::vector operator[] 10x speedup (patch)

[pcarlini at suse dot de]

------- Comment #4 from pcarlini at suse dot de  2006-12-14 11:18 -------
By the way, forgot that in mainline and 4.2 branch the issue simply doesn't
exist anymore: for completely different reasons, we are *already* using
directly _M_start, _M_finish, and co.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30204

[Bug libstdc++/30204] std::vector operator[] 10x speedup (patch)

[charles at rebelbase dot com]

------- Comment #5 from charles at rebelbase dot com  2006-12-14 17:58 -------
(In reply to comment #1)
> -O1 is enough to remove all advantages of this patch.
> 
> Also, that isn't really a fair timing comparison, as you've removed the
> function call altogether (I still expect it to be faster, but possibly not by
> 10x)

Yes, you're right.  Thanks for looking at this.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=30204