Re: [boost] uBLAS: problem with sparse_vector

From: Michael Stevens (support-1_at_[hidden])
Date: 2002-06-30 23:07:02

>
>
>From: jhr.walter_at_[hidden] (Joerg Walter)
>
>  
>
>>> There is a bug in uBLAS that is illustrated with the following code:
>>>
>>>     v(1) = v(0) = 42
>>
>
>I've just tried to fix this problem following Dave Abraham's hint (thanks,
>Dave!). First of all I extended your sample to check std::map, map_array, ,
>sparse_vector<..., std::map>, sparse_vector<..., map_array> and realized
>this way, that the real problem was the semantic difference of std::map and
>map_array.
>  
>
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.

>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. 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? 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.
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!

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.

All the best,
    Michael