[Bug 479] New: Some filters will break real-time

For more infomation about this bug, visit
Summary: Some filters will break real-time
Product: BFL
Version: trunk
Platform: All
OS/Version: All
Status: NEW
Severity: blocker
Priority: P1
Component: core
AssignedTo: bfl [..] ...
ReportedBy: klaas [dot] gadeyne [..] ...
CC: bfl [..] ...
Estimated Hours: 0.0

HistogramFilter::SysUpdate(SystemModel* const sysmodel, const int& u)
{
[...]
vector old_prob = ( (DiscretePdf*)_post )->ProbabilitiesGet();
vector new_prob(num_states);
[...]
}

If I'm not mistaken, this will lead to allocations on the heap and make the
historgram filter unsuited for use in real-time applications.
I noticed similar code in the MeasUpdate function of HistogramFilter and the
KalmanFilter code also seems to suffer from a similar issue:

void
KalmanFilter::CalculateSysUpdate(ColumnVector J, Matrix F, SymmetricMatrix Q)
{
[...]
Matrix temp = F * (Matrix)_post->CovarianceGet() * F.transpose() +
(Matrix)Q;
SymmetricMatrix Sigma_new(_post->DimensionGet());
[...]
}

Idem dito for the IEKF code and the SRIEKF. Particle Filter code seems to be
fine. I guess people@PMA should have noticed this when using this filters
under LXRT?

Damned, I should have noticed this long ago :-(

[Bug 479] Some filters will break real-time

For more infomation about this bug, visit

--- Comment #7 from Tinne De Laet <tinne [dot] delaet [..] ...> 2008-01-10 14:10:15 ---
Created an attachment (id=188)
--> (https://www.fmtc.be/bugzilla/orocos/attachment.cgi?id=188)
Patch to solve allocation issues for extendedKalmanFilter

same remark as with kalmanfilter-patch

[Bug 479] Some filters will break real-time

For more infomation about this bug, visit

--- Comment #6 from Tinne De Laet <tinne [dot] delaet [..] ...> 2008-01-10 14:04:33 ---
Created an attachment (id=187)
--> (https://www.fmtc.be/bugzilla/orocos/attachment.cgi?id=187)
Patch to solve allocation issues for kalmanfilter

...
notice the work-around-solution for initializing some of the variables needed
in measupdate.

Tinne

[Bug 479] Some filters will break real-time

For more infomation about this bug, visit

Tinne De Laet <tinne [dot] delaet [..] ...> changed:

What |Removed |Added
--------------------------------------------------------------------------
Attachment #183 is|0 |1
obsolete| |

--- Comment #5 from Tinne De Laet <tinne [dot] delaet [..] ...> 2008-01-10 11:04:04 ---
Created an attachment (id=184)
--> (https://www.fmtc.be/bugzilla/orocos/attachment.cgi?id=184)
Patch to solve allocation issues for EKparticlefilter - bis

> Source code wise, I think this solves some issues, but not all of them.
> Since this is a particle filter involving a KF step, I think you should
> also _preallocate_ the matrices, and not only the lists, e.g. in the
> constructor instead of just
> doing
>
> _sampleCov.resize(prior->NumSamplesGet());
>
> you should add something like (note: this is only pseudo code)
>
> _cov_it = _sampleCov.begin();
> while (_cov_it != _sampleCov.end())
> {
> (*_cov_it).resize(this->StateSizeGet());
> }
>
Ack, I think the new patch also preallocates the matrices,... but using the
assign function in stead of iterating over the list.

Tinne

[Bug 479] Some filters will break real-time

For more infomation about this bug, visit

--- Comment #4 from Klaas Gadeyne <klaas [dot] gadeyne [..] ...> 2008-01-09 17:42:52 ---
(In reply to comment #3)
> Created an attachment (id=183)
--> (https://www.fmtc.be/bugzilla/orocos/attachment.cgi?id=183) [details]
> Patch to solve allocation issues for EKparticlefilter

Source code wise, I think this solves some issues, but not all of them. Since
this is a particle filter involving a KF step, I think you should also
_preallocate_ the matrices, and not only the lists, e.g. in the constructor
instead of just
doing

_sampleCov.resize(prior->NumSamplesGet());

you should add something like (note: this is only pseudo code)

_cov_it = _sampleCov.begin();
while (_cov_it != _sampleCov.end())
{
(*_cov_it).resize(this->StateSizeGet());
}

For the rest, this seems fine. However, when running make check, I get a nasty
error

*** glibc detected ***
/home/kgad/SVN/bfl-trunk/build-boost/tests/test_complete_filter: corrupted
double-linked list: 0x080c5bb8 ***
======= Backtrace: =========
/lib/i686/cmov/libc.so.6[0x40340df9]
/lib/i686/cmov/libc.so.6[0x4034253e]
/lib/i686/cmov/libc.so.6(cfree+0x90)[0x403461a0]
/usr/lib/libstdc++.so.6(_ZdlPv+0x21)[0x40271e41]
/home/kgad/SVN/bfl-trunk/build-boost/tests/test_complete_filter(_ZN9__gnu_cxx13new_allocatorIN3BFL14WeightedSampleIN13MatrixWrapper12ColumnVectorEEEE10deallocateEPS5_j+0x11)[0x8062927]
/home/kgad/SVN/bfl-trunk/build-boost/tests/test_complete_filter(_ZNSt12_Vector_baseIN3BFL14WeightedSampleIN13MatrixWrapper12ColumnVectorEEESaIS4_EE13_M_deallocateEPS4_j+0x27)[0x8062951]
/home/kgad/SVN/bfl-trunk/build-boost/tests/test_complete_filter(_ZNSt12_Vector_baseIN3BFL14WeightedSampleIN13MatrixWrapper12ColumnVectorEEESaIS4_EED2Ev+0x36)[0x806298a]
/home/kgad/SVN/bfl-trunk/build-boost/tests/test_complete_filter(_ZNSt6vectorIN3BFL14WeightedSampleIN13MatrixWrapper12ColumnVectorEEESaIS4_EED1Ev+0x5b)[0x8062d9d]
/home/kgad/SVN/bfl-trunk/build-boost/src/liborocos-bfl.so(_ZN3BFL16EKParticleFilterD0Ev+0x117)[0x4012551b]
/home/kgad/SVN/bfl-trunk/build-boost/tests/test_complete_filter(_ZN19Complete_FilterTest29testComplete_FilterValue_ContEv+0x21d2)[0x805fcba]
/home/kgad/SVN/bfl-trunk/build-boost/tests/test_complete_filter(_ZN7CppUnit10TestCallerI19Complete_FilterTestE7runTestEv+0x55)[0x806192d]
/usr/lib/libcppunit-1.12.so.0(_ZNK7CppUnit21TestCaseMethodFunctorclEv+0x29)[0x40195e49]
/usr/lib/libcppunit-1.12.so.0(_ZN7CppUnit16DefaultProtector7protectERKNS_7FunctorERKNS_16ProtectorContextE+0x2e)[0x4018742e]
/usr/lib/libcppunit-1.12.so.0(_ZNK7CppUnit14ProtectorChain14ProtectFunctorclEv+0x23)[0x40191a43]
/usr/lib/libcppunit-1.12.so.0(_ZN7CppUnit14ProtectorChain7protectERKNS_7FunctorERKNS_16ProtectorContextE+0x1d4)[0x40191764]
/usr/lib/libcppunit-1.12.so.0(_ZN7CppUnit10TestResult7protectERKNS_7FunctorEPNS_4TestERKSs+0x51)[0x4019e2b1]
/usr/lib/libcppunit-1.12.so.0(_ZN7CppUnit8TestCase3runEPNS_10TestResultE+0x10d)[0x40195b4d]
/usr/lib/libcppunit-1.12.so.0(_ZN7CppUnit13TestComposite15doRunChildTestsEPNS_10TestResultE+0x3d)[0x401964bd]
/usr/lib/libcppunit-1.12.so.0(_ZN7CppUnit13TestComposite3runEPNS_10TestResultE+0x2a)[0x401963ea]
/usr/lib/libcppunit-1.12.so.0(_ZN7CppUnit13TestComposite15doRunChildTestsEPNS_10TestResultE+0x3d)[0x401964bd]
/usr/lib/libcppunit-1.12.so.0(_ZN7CppUnit13TestComposite3runEPNS_10TestResultE+0x2a)[0x401963ea]
/usr/lib/libcppunit-1.12.so.0(_ZN7CppUnit10TestRunner13WrappingSuite3runEPNS_10TestResultE+0x40)[0x401a0960]
/usr/lib/libcppunit-1.12.so.0(_ZN7CppUnit10TestResult7runTestEPNS_4TestE+0x2a)[0x4019e04a]
/usr/lib/libcppunit-1.12.so.0(_ZN7CppUnit10TestRunner3runERNS_10TestResultERKSs+0x50)[0x401a07a0]
/usr/lib/libcppunit-1.12.so.0(_ZN7CppUnit14TextTestRunner3runERNS_10TestResultERKSs+0x2b)[0x401a3f7b]
/usr/lib/libcppunit-1.12.so.0(_ZN7CppUnit14TextTestRunner3runESsbbb+0x62)[0x401a3ff2]
/home/kgad/SVN/bfl-trunk/build-boost/tests/test_complete_filter(main+0x1f2)[0x805c442]
/lib/i686/cmov/libc.so.6(__libc_start_main+0xe0)[0x402ed450]
/home/kgad/SVN/bfl-trunk/build-boost/tests/test_complete_filter(_ZNK7CppUnit4Test12findTestPathEPKS0_RN

[Bug 479] Some filters will break real-time

For more infomation about this bug, visit

--- Comment #3 from Tinne De Laet <tinne [dot] delaet [..] ...> 2008-01-09 17:20:36 ---
Created an attachment (id=183)
--> (https://www.fmtc.be/bugzilla/orocos/attachment.cgi?id=183)
Patch to solve allocation issues for EKparticlefilter

[Bug 479] Some filters will break real-time

For more infomation about this bug, visit

Tinne De Laet <tinne [dot] delaet [..] ...> changed:

What |Removed |Added
--------------------------------------------------------------------------
Status|NEW |ASSIGNED
Target Milestone|--- |0.6.2

--- Comment #2 from Tinne De Laet <tinne [dot] delaet [..] ...> 2008-01-09 17:14:33 ---
I accept this bug, but any help is welcome of course.
I will propose patches for all filters/pdf seperately to prevent an unreadable
patch-file.

Tinne

[Bug 479] Some filters will break real-time

For more infomation about this bug, visit

--- Comment #1 from Klaas Gadeyne <klaas [dot] gadeyne [..] ...> 2008-01-08 19:36:31 ---
(In reply to comment #0)
> HistogramFilter::SysUpdate(SystemModel* const sysmodel, const int& u)
> {
> [...]
> vector old_prob = ( (DiscretePdf*)_post )->ProbabilitiesGet();
> vector new_prob(num_states);
> [...]
> }
>
> If I'm not mistaken, this will lead to allocations on the heap and make the
> historgram filter unsuited for use in real-time applications.

It appears I am not mistaken. Consider the following example

[kgad@ampere /tmp]$
cat main.cpp
#include

#define NUM_TRIES 10
#define SIZE 1000

int main()
{
for (int i=0; i< NUM_TRIES; i++)
{
std::vector a(SIZE,1.0);
std::vector b = a;
}
return 0;
}

[kgad@ampere /tmp]$
cat main_efficient.cpp
#include

#define NUM_TRIES 10
#define SIZE 1000

int main()
{
std::vector a(SIZE,1.0);
std::vector b(SIZE);

for (int i=0; i< NUM_TRIES; i++)
{
b[1]=2.0;
b=a;
}

return 0;
}

When performing some heap profiling action using valgrind's massif
tool on these executables, e.g.

valgrind --tool=massif --time-unit=B ./a.out

and then print some result using ms_print, we get the following chart
for the "naive" implementation

KB
15.64^ # : : : : @ : : : :
| # : : : : @ : : : :
| # : : : : @ : : : :
| # : : : : @ : : : :
| # : : : : @ : : : :
| # : : : : @ : : : :
| # : : : : @ : : : :
| # : : : : @ : : : :
| # : : : : @ : : : :
| # : : : : @ : : : :
| : # : :: : : :: : : : : : : : @ : :: : : :: : : : : : :
| : # : :: : : :: : : : : : : : @ : :: : : :: : : : : : :
| : # : :: : : :: : : : : : : : @ : :: : : :: : : : : : :
| : # : :: : : :: : : : : : : : @ : :: : : :: : : : : : :
| : # : :: : : :: : : : : : : : @ : :: : : :: : : : : : :
| : # : :: : : :: : : : : : : : @ : :: : : :: : : : : : :
| : # : :: : : :: : : : : : : : @ : :: : : :: : : : : : :
| : # : :: : : :: : : : : : : : @ : :: : : :: : : : : : :
| : # : :: : : :: : : : : : : : @ : :: : : :: : : : : : :
| : # : :: : : :: : : : : : : : @ : :: : : :: : : : : : :
0
+----------------------------------------------------------------------->KB
0 312.8

You can consider the x-axis to be some kind of "time", and the y-axis the heap
size. You can see very nicely that the allocation happens every time in the
for loop (10 times).

the following plot is produced for the "efficient" main

KB
15.64^ #
| #
| #
| #
| #
| #
| #
| #
| #
| #
| : # :
| : # :
| : # :
| : # :
| : # :
| : # :
| : # :
| : # :
| : # :
| : # :
0
+----------------------------------------------------------------------->KB
0 31.28

[I hope bugzilla doesn't mangle this ascii art...]

Increasing the defines in both programs also shows the performancy decrease.

regards,

Klaas

Ps. Unfortunately, AFAIK valgrind does not yet work for xenomai or
lxrt :-(