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