Re: broken coordinate_matrix::sort with gcc 4.7 (was: patches for #7297, #7296, #6514, #6511 on trunk - please verify)

Hi all,

we created a simple version of inplace_merge, which can be added as method
to coordinate_matrix. It is not intensely tested, something we would do via
Testcases in case we proceed in this direction (I do not fully trust my
lower_bound for all border cases; it also seems to use to man LoC). However,
using this in our numerical code, all of our application testcases pass.

      array_size_type lower_bound(array_size_type beg, array_size_type end,
array_size_type target) const {
        while (end > beg + 1) {
          array_size_type i = (beg + end) / 2;
          if (((index1_data_[i] > index1_data_[target]) ||
               ((index1_data_[i] == index1_data_[target]) &&
(index2_data_[i] > index2_data_[target])))) {
            end = i;
          } else {
            beg = i;
          }
        }
        if (((index1_data_[beg] < index1_data_[target]) ||
             ((index1_data_[beg] == index1_data_[target]) &&
(index2_data_[beg] < index2_data_[target])))) {
          return end;
        } else {
          return beg;
        }
      }

      void inplace_merge(array_size_type beg, array_size_type mid,
array_size_type end) const {
        array_size_type l1 = mid - beg;
        array_size_type l2 = end - mid;

        if (l1 == 0 || l2 == 0) {
          return;
        }
        if (l1 == 1 && l2 == 1) {
          if ((index1_data_[beg] > index1_data_[mid]) ||
              ((index1_data_[beg] == index1_data_[mid]) &&
(index2_data_[beg] > index2_data_[mid])))
          {
            std::swap(index1_data_[beg], index1_data_[mid]);
            std::swap(index2_data_[beg], index2_data_[mid]);
            std::swap(value_data_[beg], value_data_[mid]);
          }
          return;
        }

        array_size_type lef_mid, rig_mid;
        if (l1 >= l2) {
          lef_mid = (beg + mid) / 2;
          rig_mid = lower_bound(mid, end, lef_mid);
        } else {
          rig_mid = (mid + end) / 2;
          lef_mid = lower_bound(beg, mid, rig_mid);
        }
        std::rotate(&index1_data_[lef_mid], &index1_data_[mid],
&index1_data_[rig_mid]);
        std::rotate(&index2_data_[lef_mid], &index2_data_[mid],
&index2_data_[rig_mid]);
        std::rotate(&value_data_[lef_mid], &value_data_[mid],
&value_data_[rig_mid]);

        array_size_type new_mid = lef_mid + (rig_mid - mid);
        inplace_merge(beg, lef_mid, new_mid);
        inplace_merge(new_mid, rig_mid, end);
      }

And the std::inplace_merge call in sort needs to be replaced by

inplace_merge(0, sorted_filled_, filled_);

Similar code would be needed for the sparse vector. If desired, I can
provide patches and associated testcases. The performance of this is
indistinguishable from the STL internal buffer-less algorithm.

Cheers,
Joern

> -----Original Message-----
> From: [email protected] [mailto:ublas-
> [email protected]] On Behalf Of "Ungermann, Jörn"
> Sent: Donnerstag, 6. September 2012 21:03
> 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)
> 
> 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: [email protected] [mailto:ublas-
> > [email protected]] 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"
> > <[email protected]> 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
> > [email protected]
> > http://lists.boost.org/mailman/listinfo.cgi/ublas
> > Sent to: [email protected]

_______________________________________________
ublas mailing list
[email protected]
http://lists.boost.org/mailman/listinfo.cgi/ublas
Sent to: [email protected]