On Mon, Aug 4, 2008 at 3:43 PM, Roy Stogner <roy@...> wrote:
> On Mon, 4 Aug 2008, John Peterson wrote:
>> I believe the complexity requirements for std::distance on a model
>> of forward iterator is O(N).
> That's right; you only get O(1) if you've got a RandomAccessIterator.
>> I don't think we are using forward iterators here (we've just used
>> that word as a template argument in this function) but something to
>> keep in mind nonetheless.
> I'm not sure what that template argument gets instantiated with, but
> it's moot:
> The potentially offending distance() call operates on
> vector<>::const_iterator (which are definitely RandomAccess) objects.
> Benchmarking with pointer arithmetic instead made no difference.
> So I finally stuck in some even-more-finegrained PerfLogs. The
> offending line is this one:
> std::vector<Hilbert::HilbertIndices>::const_iterator pos =
> std::lower_bound (my_bin.begin(), my_bin.end(), hi);
> Not sure what to say about that. With vector iterators we ought to be
> using O(log_2(N)) operations on lower_bound, which shouldn't be taking
> two and a half milliseconds each of the many times it's called. But
> it looks like this is a gcc problem since it doesn't trigger with
> METHOD=devel. I'll try it without those GLIBCXX_DEBUG flags next...
> but removing those isn't a good long-term solution, is it? Half the
> reason I use debug mode is to get vector bounds checking and such.
I checked out the implementation of lower_bound. I noticed this:
__glibcxx_requires_partitioned(__first, __last, __val);
In debug mode, this may be checking to see if the range is partitioned
(sorted?) at each call to lower_bound, which could be an O(N)
operation. I couldn't find the exact definition of this, but in
debug/debug.h I found it #defined to