|
|
Re: Vlists, Stacks and Hash-Tables
|
Posted: Dec 9, 2005 1:43 PM
|
|
> I do not see an algorithmic reason why index access should
> be an order of magnitude faster for your vlist than for
> std::deque. Both need to find the corresponding buffer and
> offset.
Finding the corresponding buffer for VList is faster because half of the items are in the first buffer. So 50% of the time it simply has to do one subscript operation. 25% of the time it has to move to the second buffer and do a subscript operation, and so on. The STLPort 4.6.2 implementation executes the following code:
template <class _Tp>
struct _Deque_iterator_base {
enum _Constants {
_blocksize = _MAX_BYTES,
__buffer_size = (sizeof(_Tp) < (size_t)_blocksize ?
( (size_t)_blocksize / sizeof(_Tp)) : size_t(1))
};
typedef random_access_iterator_tag iterator_category;
typedef _Tp value_type;
typedef size_t size_type;
typedef ptrdiff_t difference_type;
typedef value_type** _Map_pointer;
typedef _Deque_iterator_base< _Tp > _Self;
value_type* _M_cur;
value_type* _M_first;
value_type* _M_last;
_Map_pointer _M_node;
_Deque_iterator_base(value_type* __x, _Map_pointer __y)
: _M_cur(__x), _M_first(*__y),
_M_last(*__y + __buffer_size), _M_node(__y) {}
_Deque_iterator_base() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
void _M_advance(difference_type __n)
{
difference_type __offset = __n + (_M_cur - _M_first);
if (__offset >= 0 && __offset < difference_type(__buffer_size))
_M_cur += __n;
else {
difference_type __node_offset =
__offset > 0 ? __offset / __buffer_size
: -difference_type((-__offset - 1) / __buffer_size) - 1;
_M_set_node(_M_node + __node_offset);
_M_cur = _M_first +
(__offset - __node_offset * difference_type(__buffer_size));
}
}
void _M_set_node(_Map_pointer __new_node) {
_M_last = (_M_first = *(_M_node = __new_node)) + difference_type(__buffer_size);
}
};
Of course there are many different ways to implement a deque, I was only comparing to STLPort 4.6.2.
> I suspect the difference is caused by runtime
> checks in the stlport implementation.
I use NDEBUG to turn off runtime checking. I have provided the source code on my website, and you can verify the code yourself.
> I just browsed through the code, but I noticed the
> following:
> inside iterator::operator+=(), there is technically
> undefined behaviour if the pos pointer is increased beyond
> the end of the buffer. The same goes for operator-=()
That is common practice for random access iterators (behaviour similar to raw pointers), but not neccessarily a best practice.
|
|
Previous Topic
