Re: [boost] uBLAS: problem with sparse_vector

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