The Artima Developer Community
Sponsored Link

Weblogs Forum
Vlists, Stacks and Hash-Tables

3 replies on 1 page. Most recent reply: Dec 9, 2005 6:30 PM by Rupert Kittinger-Sereinig

Welcome Guest
  Sign In

Go back to the topic listing  Back to Topic List Click to reply to this topic  Reply to this Topic Click to search messages in this forum  Search Forum Click for a threaded view of the topic  Threaded View   
Previous Topic   Next Topic
Flat View: This topic has 3 replies on 1 page
Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Vlists, Stacks and Hash-Tables (View in Weblogs)
Posted: Nov 29, 2005 4:38 PM
Reply to this message Reply
Summary
I have just released a new version of the OOTL which contains a VList based implementation of a stack data-type and a hash table data-type.
Advertisement
I have just released vlist based implementations of a stack ADT and a hash-table ADT through the OOTL (Object Oriented Template Library). I have also added some benchmark results and updated the documentation.

The current OOTL release compiles on GCC 3.4.1 and Visual C++ 7.1. It is guaranteed not to work on anything older.


Rupert Kittinger-Sereinig

Posts: 21
Nickname: rkit
Registered: Dec, 2005

Re: Vlists, Stacks and Hash-Tables Posted: Dec 9, 2005 4:13 PM
Reply to this message Reply
I have a question about the performance figures: I think this data structure should have the same performance characteristics as deque, except for faster construction (there are fewer allocations).

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. I suspect the difference is caused by runtime checks in the stlport implementation.

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-=()

Christopher Diggins

Posts: 1215
Nickname: cdiggins
Registered: Feb, 2004

Re: Vlists, Stacks and Hash-Tables Posted: Dec 9, 2005 4:43 PM
Reply to this message Reply
> 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.

Rupert Kittinger-Sereinig

Posts: 21
Nickname: rkit
Registered: Dec, 2005

Re: Vlists, Stacks and Hash-Tables Posted: Dec 9, 2005 6:30 PM
Reply to this message Reply
ok, I admit I never looked inside the source of <deque> before :-)

So that's my conclusion: the STLport implementors decided to keep more information in the iterator than strictly necessary to speed up increment/decrement. But this makes advance() more expensive. operator[] is implemented using iterators although they are optimized for a different use case.

So, deque::operator[] could probably be a little bit faster. Maybe it would be fun to write a policy-based deque that can be tuned for different usage patterns...

There is another performance point that might be worth considering: following pointers like vlist is probably much more sensible to cache pollution, which may offset the advantage of the shorter code path in some usage patterns.

before I forget: a nice piece of code.

Flat View: This topic has 3 replies on 1 page
Topic: On Java Lava Lamps and Other eXtreme Feedback Devices Previous Topic   Next Topic Topic: UML vs OO Design


Sponsored Links



Google
  Web Artima.com   

Copyright © 1996-2014 Artima, Inc. All Rights Reserved. - Privacy Policy - Terms of Use - Advertise with Us