|
|
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-11 16:21:19
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: ublas-bounces_at_[hidden] [mailto:ublas-
> bounces_at_[hidden]] 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: 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]