Boost logo

Boost :

From: Joerg Walter (jhr.walter_at_[hidden])
Date: 2002-07-01 02:13:12


----- Original Message -----
From: "Michael Stevens" <support-1_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Monday, July 01, 2002 6:07 AM
Subject: Re: [boost] uBLAS: problem with sparse_vector

[snip]

> Looking at the code for map_array it seems to be a very odd beast.
> Although it has STL map like interface its container is an array. As you
> say the semantic difference this causes is the real problem. In
> particular std::map's insert operation never invalidates any references,
> iterators or pointers. While when map_array expands its capacity it
> reallocates its array and therefore invalidates everything! My guess is
> that map_array is to provide an efficient implementation when the number
> of non_zero elements does not vary.

The main reason for map_array is that it's iterator increment is simpler
than std::map's.

> >Then I embedded the following nested proxy class in map_array:
> >
> > class proxy:
> > public container_reference<map_array> {
> >
> Looking at the proxy, with write back implementation, it fixes can fix
> the invalidation problem but at some cost.

Correct.

> In particular the proxy
> stores an index, iterator and a data_value. The later must be copied as
> least twice which may be quite costly (it may not be simple type), and
> certainly is unexpected.
>
> > ~proxy () {
> > if (it_->first != i_)
> > it_ = (*this) ().find (i_);
> > it_->second = d_;
> > }
> >
> >
> I'm very worried by the if (it->first). Correct me if I am wrong, but
> surely the iterator (pointer) will be invalidated by a reallocation that
> caused us problems in the first place?

I won't correct you, because you're right. You've spotted a bug in the
bugfix. Thanks.

> Infact I cannot see any way to
> optimise away the second call to find when the proxy is destructed.
> There is no efficient way to track if the array was reallocated since
> the proxy was created.

I believe, that this can be fixed, but I've to look into it later.

> This seems to suggest that this kind of write back proxy is a very
> costly solution. This seems especially bad as map_array seems to exist
> to be more efficient the map!
>
> Given these problem I can not see any good solution for the map_array
> problem. My suggestion would be make map_array fixed size. This bypasses
> the reallocation and invalidation problem :-) The result is an efficient
> associative container for sparse storage when the number of non_zeros is
> fixed.
>
> This would also require a nasty specialisation so the spase constructors
> can pass on non_zeros to the map_array constructor.
>
> sparse_vector (size_type size, size_type non_zeros = 0):
> size_ (size), non_zeros_ (non_zeros), data_ () {}
>
> >May be, it would have been easier to only document that bug ;-)
> >
> This may be an even better solution then either costly proxies or
> enforcing a fixed size :-) Although it may then be appropriate to use
> std::map as the default storage type!

I added the proxy stuff conditionally. We'll have to benchmark map_array
with/without proxy against std::map.

> The second issue that arose from this discussion was David's observation
> that the current element creation on operator[] access were not that
> great! It seems that a proxy, which is just a reference object, would be
> an appropriate solution to this problem. This would delay the call to
> insert() to when the proxy is assigned to.
>
> Not sure however if the work involved in wrapping map (or map_array) to
> provide such a proxy out weighs the semantic niceties. The effect can
> achieve using the existing sparse find(index) functions.

I'll have to think about it.

Regards

Joerg


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk