Boost logo

Ublas :

Subject: Re: [ublas] broken coordinate_matrix::sort with gcc 4.7 (was: patches for #7297, #7296, #6514, #6511 on trunk - please verify)
From: Ungermann, Jörn (j.ungermann_at_[hidden])
Date: 2012-09-06 15:02:35


Argh,

sorry. I seemingly have copied an intermediate buggy version that my emacs
destroyed by accident. The ";" is not the only mistake.

The following version works for matrix (not the different calls to
distance!):
// std::inplace_merge (ita.begin (), iunsorted, ita.end ());
                if (ita.begin() != iunsorted && iunsorted != ita.end ()) {
                    std::__merge_without_buffer(ita.begin (), iunsorted,
ita.end (),
                                                std::distance(ita.begin (),
iunsorted),
                                                std::distance(iunsorted,
ita.end ()));
                }
This is the change for vector_sparse.hpp
// std::inplace_merge (ipa.begin (), iunsorted, ipa.end ());
                if (ipa.begin() != iunsorted && iunsorted != ipa.end ()) {
                    std::__merge_without_buffer(ipa.begin (), iunsorted,
ipa.end (),
                                                std::distance(ipa.begin (),
iunsorted),
                                                std::distance(iunsorted,
ipa.end ()));
                }

A potentially performance-impacting alternative would be simply:
// std::sort (iunsorted, ipa.end ());
// std::inplace_merge (ipa.begin (), iunsorted, ipa.end ());
                std::sort (ipa.begin(), ipa.end ());
I did not test this for gcc, but according to the standard, the worst-case
performance goes to n^2 instead of n log n.

Sorry for the bug. I really got used to the buildbot with automated tests we
run on every commit.

Cheers,
Jörn

> -----Original Message-----
> From: ublas-bounces_at_[hidden] [mailto:ublas-
> bounces_at_[hidden]] On Behalf Of sguazt
> Sent: Donnerstag, 6. September 2012 11:16
> To: ublas mailing list
> Subject: Re: [ublas] broken coordinate_matrix::sort with gcc 4.7 (was:
> patches for #7297, #7296, #6514, #6511 on trunk - please verify)
>
> On Wed, Sep 5, 2012 at 10:06 AM, "Ungermann, Jörn"
> <j.ungermann_at_[hidden]> wrote:
> > Hello,
> >
> > I do not think that this qualifies as a valid fix, but for gcc 4.4
> and
> > gcc
> > 4.7 the following hack worked for us. Perhaps one could do a gcc
> > version specific #ifdef. Might be preferable to not working at all.
> >
> > This change in matrix_sparse.hpp
> > // std::inplace_merge (ita.begin (), iunsorted,
> ita.end ());
> > if (ita.begin() != iunsorted && iunsorted != ita.end
> ()) {
> > std::__merge_without_buffer(ita.begin (),
> > iunsorted, ita.end (),
> >
> > std::distance(iunsorted, ita.end ()));
> >
> > std::distance(iunsorted, ita.end ()));
> > }
> > and a corresponding one in vector_sparse.hpp seems to work quite well
> > for the time being. Not really future-proof, though.
> >
>
> Hello,
>
> I've tried to put this hack in matrix_sparse and compiled with GCC 4.7.
> It works. Just for info, above there are too much ";" ;) The right
> version is:
> if (ita.begin() != iunsorted && iunsorted != ita.end
> ()) {
> std::__merge_without_buffer(ita.begin (),
> iunsorted, ita.end (), std::distance(iunsorted, ita.end ()),
> std::distance(iunsorted, ita.end ()));
> }
>
> For what concerns the use of an #ifdef for GCC, I agree with you that
> it is better to have something that works than to have not. I'm just
> curious if this is a problem only concerning GCC.
> I usually compile with "--Wall --ansi --pendantic" flags in order to
> make sure that the written code is as much standard as possible. So if
> the problem is only related to GCC, does this mean that GCC is not
> fully compliant with standard C++ (actually with C++98)?
>
> > Just replacing the functionality of merge_without_buffer with a
> > dedicated function operating on the coordinate_matrix arrays would
> > also be not too difficult.
> > I guess the algorithm used by the STL is not protected? I could
> > explain the algorithm to my collegue and he can implement it.
> >
>
> Unfortunately I don't know this part of uBLAS so I can't help you. :(
>
> After this problem has been fixed, the other remaining failing test is
> test_assignment.
> Anyone, any idea?
>
> Best,
>
> -- Marco
> _______________________________________________
> ublas mailing list
> ublas_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/ublas
> Sent to: j.ungermann_at_[hidden]