Is incrementing iterators actually this slow?

[James Aguilar]

Hey all,

I have a bit of code that implements a suffix array, which is essentially an
array of iterators or indexes into a string. The array starts out like this

String: ABAB
Array: 0123

But then gets sorted

Array: 2031
2 AB
0 ABAB
3 B
1 BAB

All of this is well and good, but I have a little problem. Currently, I am
using the STL's sort algorithm and providing a custom comparison function,
which ends up sorting this vector<string:: iterator> alphabetically. Here is
the comparison and other associated functions:

bool itLess(string:: const_iterator it1, string::const_i terator it2, int
skip)
{
advanceIterator s(it1, it2, skip);
return (*it1 < *it2 || *it1 == '\0');
}

int advanceIterator s(string::const _iterator &it1, string::const_i terator
&it2,
int skip)
{
string::const_i terator ref(it1);
advanceNoCheck( it1, it2, skip);

while (*it1 == *it2 && !(*it1 == '\0')) {
++it1;
++it2;
}

return it1 - ref;
}

void advanceNoCheck( string::const_i terator &it1, string::const_i terator
&it2,
int skip)
{
if (skip) {
it1 += skip;
it2 += skip;
}
}

The way the sorting works is that one method goes through the text string
and makes an iterator for each position, putting it into the array.
Afterwards, I call 'sort(m_array.b egin(), m_array.end(), &itLess).' It
takes entirely too long.

I have profiled my code with gprof (I know, it's platform specific, but you
should be able to read the output). The code was compiled with all
optimizations turned on, and run on a text of 10 million characters that did
not have a high incidence of repetition. Here is the output of the
profiler:

% cumulative self self total
time seconds seconds calls Ks/call Ks/call name
int advanceIterator s(string::const _iterator &, string::const_i terator &):
98.92 1196.55 1196.55 302747982 0.00 0.00
bool itLess(string:: const_iterator, string::const_i terator):
0.42 1201.59 5.04 282747983 0.00 0.00
std::__unguarde d_partition([template junk]):
0.21 1204.10 2.51 1074094 0.00 0.00
void advanceNoCheck( string::const_i terator &, string::const_i terator &):
0.09 1205.20 1.10 302747982 0.00 0.00

Clearly, my advanceIterator s (and hence, all of my iterator comparison) is
far too slow. If I run my code without optimizations (that is, if I do not
inline iterator::opera tor ++ and iterator::opera tor *), you would see that
most of the time spent in advanceIterator s is actually spent in those two
methods. Does anyone know a faster way to sort string::const_i terators
lexicographical ly?

- JFA1

[Andrew Koenig]

"James Aguilar" <jf**@cec.wustl .edu> wrote in message
news:d2******** **@newsreader.w ustl.edu...

bool itLess(string:: const_iterator it1, string::const_i terator it2, int
skip)
{
advanceIterator s(it1, it2, skip);
return (*it1 < *it2 || *it1 == '\0');
}
I suspect that this code doesn't do what you think it does.

I am guessing that you are using the comparison *it1 == '\0' as a way of
checking whether it1 has run off the end of the string.

It doesn't do that. It is your responsibility to know where the end of the
string is, and to dereference only iterators that you know refer to elements
of the string.

int advanceIterator s(string::const _iterator &it1, string::const_i terator
&it2,
int skip)
{
string::const_i terator ref(it1);
advanceNoCheck( it1, it2, skip);

while (*it1 == *it2 && !(*it1 == '\0')) {
++it1;
++it2;
}

return it1 - ref;
}

Same problem here: It looks like you are assuming that once you run off the
end of the string, *it1 will be 0. It won't, in general. You'll get what
you get.

[James Aguilar]

"Andrew Koenig" <ar*@acm.org> wrote in message
news:ii******** ***********@bgt nsc04-news.ops.worldn et.att.net...

Same problem here: It looks like you are assuming that once you run off
the end of the string, *it1 will be 0. It won't, in general. You'll get
what you get.

It seems to work on small problems (sorting them correctly. Also, a little
test code shows that, at least with g++ 3.3.3, it works:

#include <string>
#include <iostream>

using namespace std;

int main()
{
string a;

cout << (*(a.begin() + a.length()) == '\0') << '\n';

a += "asad";
cout << (*(a.begin() + a.length()) == '\0') << '\n';

a = "OMGZ?";
cout << (*(a.begin() + a.length()) == '\0') << '\n';

return 0;
}

prints 1, 1, 1 on my system. Even if this is non-standard, I'm almost
positive that it is not the problem.

- JFA1

[Andrew Koenig]

"James Aguilar" <jf**@cec.wustl .edu> wrote in message
news:d2******** **@newsreader.w ustl.edu...

It seems to work on small problems (sorting them correctly. Also, a
little test code shows that, at least with g++ 3.3.3, it works:
No, it happens to do something that appears to work in this particular case.
prints 1, 1, 1 on my system. Even if this is non-standard, I'm almost
positive that it is not the problem.

It doesn't matter. As written, the program's behavior is undefined.
There's no point in investigating further until this problem is corrected.