This is an archive of the discontinued LLVM Phabricator instance.

[DataFormatters] Make libc++ list loop detection linear
ClosedPublic

Authored by labath on Oct 20 2015, 9:47 AM.

Details

Summary

Loop detection code is being called before every element access. Although it tries to cache some
of the data by remembering the loop-free initial segment, every time it needs to increase this
segment, it will start from scratch. For the typical usage pattern, where one accesses the
elements in order, the loop detection will need to be run after every access, resulting in
quadratic behavior. This behavior is noticable even for the default 255 element limit.

In this commit, I rewrite the algorithm to be truly incremental -- it maintains the state of its
loop-detection runners between calls, and reuses them when it needs to check another segment.
This way, each part of the list is scanned only once, resulting in linear behavior.

Also note that I have changed the operator== of ListEntry to do the comparison based on the
value() function (instead of relying on ValueObjectSP equality). In my experiments, I kept
getting different ValueObjectSPs when going through the same element twice.

Diff Detail

Repository
rL LLVM

Event Timeline

labath updated this revision to Diff 37891.Oct 20 2015, 9:47 AM
labath retitled this revision from to [DataFormatters] Make libc++ list loop detection linear.
labath updated this object.
labath added a reviewer: granata.enrico.
labath added subscribers: sivachandra, lldb-commits.
granata.enrico accepted this revision.Oct 20 2015, 10:30 AM
granata.enrico edited edge metadata.

That looks reasonable. Of course, I assume you ran the test suite on OS X, including your new evil test!

This revision is now accepted and ready to land.Oct 20 2015, 10:30 AM
This revision was automatically updated to reflect the committed changes.