Boost logo

Boost :

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


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