Discussion : List vs. Set/Multiset for timecaches

[Tom Ruehr]

I suggest we switch over from using simple linked lists for the time
caches to set or multiset.
Explanation: using linked lists enforces O(N) in some operations,
which would be O(log(N)) for set and multiset + set and multiset have
amortized constant runtime for the typical operations aswell.

Complexity now, with list:
Lookup somewhere: O(N)!
Insert at end: O(1)
Insert somewhere: O(N) (rarely happens in our usecases)
Remove from start: O(1)

Complexity then, with set:
Lookup somewhere: O(log(N))
Insert at end: O(log(N)), amortized O(1)
Insert somewhere: O(log(N))
Remove from start: O(log(N), amortized O(1)

We mostly do inserts at the end and lookups at the end, as well as
remove operations at the start to obe the caching time limits.
The O(N) for a lookup in the middle somehow gets me thinking we should
change. Typically if we are looking for data at an exact timestamp,
this timestamp should in most cases be found quickly when iterating
from the end back, but there log(N) could be better in many cases
already.
While it is hard to find a benchmark that works for all use cases, I
guess we would want to make a benchmark for a typical case such as
listening to /tf on a PR2 and see how much worse that gets when using
std::set, if at all. If this is not much worse that list, i would
propose to switch to set or multiset in the standard implementation,
otherwise give the user the choice to decide whether to use lists or
sets, whichever is better for the usecase.

How do you feel about this issue?

-tom

[Bhaskara Marthi]

Adding Lorenz, who had looked into more efficient for tf in lisp.
- b

-tom

--
You received this message because you are subscribed to the Google Groups "ROS tf Special Interest Group" group.
To post to this group, send email to ros-s...@googlegroups.com.
To unsubscribe from this group, send email to ros-sig-tf+...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/ros-sig-tf?hl=en.

[Jack O'Quin]

On Wed, May 30, 2012 at 8:58 AM, Tom Ruehr <thomas...@googlemail.com> wrote:

> While it is hard to find a benchmark that works for all use cases, I
> guess we would want to make a benchmark for a typical case such as
> listening to /tf on a PR2 and see how much worse that gets when using
> std::set, if at all. If this is not much worse that list, i would
> propose to switch to set or multiset in the standard implementation,
> otherwise give the user the choice to decide whether to use lists or
> sets, whichever is better for the usecase.
>
> How do you feel about this issue?

Measurements are a good idea. It is intuitively unclear how frequent
updates are versus lookups.
--
 joq

[Tom Ruehr]

Finally did some preliminary performance profiling in a scenario where we load the whole tf recorded during a live demo and create lineset markers showing how a frame moved over time for vizualisation.

I used a 8 minutes recording of PR2's /tf from a run of my popcorn demo (http://www.youtube.com/watch?v=hlRFAM24NJg&feature=html5_3d) in a bagfile and then inserted all those into a tf::Transformer with unlimited storage time to time insertion and lookups.
The insertions were done in the order of the bagfile (mostly in order i guess), for lookup i did query for the gripper frame in map in .25 second time steps for the whole sequence.

The numbers are as follows:

tf1 with list : inserted 1624520 transforms in 1.361737s max time per insertion 0.000029s average 0.000001s
queried 1915 transforms in 13.649363s max 0.016229s avg 0.007128s
memory consumption 188M

tf1 with set: inserted 1624520 transforms in 1.381298s max 0.000029s avg 0.000001s
queried 1915 transforms in 0.013340s max 0.000028s avg 0.000007s
memory consumption 212M.

I would say the results are pretty decent, the insertion is not significantly slower, memory consumption is slighty higher but the random access lookup is a factor 1000 faster for this example.
Things should look even better with longer storage times.

The attached patch converts tf 1 from using lists to sets, not officially tested though.

[Tully Foote]

These numbers seem good enough to apply the patch. Unfortunately I tried, and the unit tests no longer passed.  

Tully

--
You received this message because you are subscribed to the Google Groups "ROS tf Special Interest Group" group.
To post to this group, send email to ros-s...@googlegroups.com.
To unsubscribe from this group, send email to ros-sig-tf+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msg/ros-sig-tf/-/YXWWOt3yOTQJ.
For more options, visit https://groups.google.com/groups/opt_out.
 
 

--
Tully Foote
tfo...@willowgarage.com
(650) 475-2827

[Tom Ruehr]

Unit Tests for the win!

Thank you for your patience - i'm just back from a 2 weeks vacation. Attached you find the patch vs. tf that i pulled today.

One error was due to a mixup of start and end of storage when deciding when to prune the 'list', which would lead to the storage not getting pruned.

The other one was more interesting, it turns out that in the test ring45, the frame b is created with two different parents at the same time, a and inverse_a.

I changed the behaviour in this case to the default which is 'overwrite existant data at same timestamp with newer data', so that at lookup b has parent a.

I do not know if this is intended to be tested in that test, it could make sense to pull this specific case into a new test to make the tests more readable.

The tests now runs through without error for me.

-tom