Page MenuHomePhabricator

[BreakpointList] Simplify/modernize BreakpointList (NFC)
ClosedPublic

Authored by JDevlieghere on Jan 7 2019, 6:39 PM.

Details

Summary

I was looking at the code in BreakpointList.cpp and found it deserved a quick cleanup.

  • Extract duplicate code
  • Use range-based for loop
  • Use early return in loops

Diff Detail

Repository
rLLDB LLDB

Event Timeline

JDevlieghere created this revision.Jan 7 2019, 6:39 PM

I wonder if we should use a vector instead of a list here too. For small data sets a std::vector usually outperforms a std::list. I *think* the data-locality would outweigh the cost of copying the shared pointers.

vsk added a comment.Jan 7 2019, 9:04 PM

Looks like a nice/reasonable cleanup, thanks!

Based on the coverage report (https://teemperor.de/lldb-coverage/coverage/Users/vsk/src/llvm.org-lldbsan/llvm/tools/lldb/source/Breakpoint/BreakpointList.cpp.html#L217) and benchmarks (https://teemperor.de/lldb-bench/static.html) GetBreakpointAtIndex doesn't looks that hot, so I'm not sure it's worth changing / accidentally regressing.

source/Breakpoint/BreakpointList.cpp
163–164

Just call the non-const overload and const_cast?

aprantl added inline comments.Jan 8 2019, 8:13 AM
source/Breakpoint/BreakpointList.cpp
18

perhaps:

  • factor out bp->GetTarget()?
  • pass a BerakpointSP & or Breakpoint & to avoid shared pointer traffic?
163–164

separate commit?

163–164

is the whole point of this loop to do something like m_breakpoints[i]?
why not std::next(..., i) ?

Second vote from me to switch to a std::vector since we have a function get breakpoint at index. Other than that, looks good.

clayborg added inline comments.Jan 8 2019, 8:22 AM
source/Breakpoint/BreakpointList.cpp
22

If we don't pass a "BreakpointSP& sp", then use std::move?

110–113

If m_breakpoints is a std::vector, we can keep it sorted and use std::lower_bound for faster lookups

117–118

ditto

163–164

If we use std::vector this will be O(1)

163–164

If we use std::vector this will be O(1)

  • Use std::vector
  • Code review feedback
  • Remove code duplication when returning a const by value.
JDevlieghere marked 10 inline comments as done.Jan 8 2019, 1:44 PM
JDevlieghere added inline comments.
source/Breakpoint/BreakpointList.cpp
163–164

I'm happy to split it up but since I'm touching so much already might as well merge it into a single change.

aprantl accepted this revision.Jan 8 2019, 1:54 PM
aprantl added inline comments.
source/Breakpoint/BreakpointList.cpp
49

very nice!

106

also nice!

This revision is now accepted and ready to land.Jan 8 2019, 1:54 PM
clayborg accepted this revision.Jan 8 2019, 2:03 PM

If we keep the list sorted we might be able to improve finding breakpoints by ID, but that can be done if we need to. BreakpointList::Add would need to insert it sorted, then we can get better than O(n) performance on FindBreakpointByID and Remove (anything that was using find_if when it is searching for a breakpoint by ID).

JDevlieghere marked an inline comment as done.Jan 8 2019, 2:09 PM

If we keep the list sorted we might be able to improve finding breakpoints by ID, but that can be done if we need to. BreakpointList::Add would need to insert it sorted, then we can get better than O(n) performance on FindBreakpointByID and Remove (anything that was using find_if when it is searching for a breakpoint by ID).

I'll do this as a follow-up.

This revision was automatically updated to reflect the committed changes.

If we keep the list sorted we might be able to improve finding breakpoints by ID, but that can be done if we need to. BreakpointList::Add would need to insert it sorted, then we can get better than O(n) performance on FindBreakpointByID and Remove (anything that was using find_if when it is searching for a breakpoint by ID).

I'll do this as a follow-up.

On second thought, maybe it's not such a good idea after all. Internal breakpoints are negative so if we keep the vector sorted we'd always insert them at the front of the vector. We could change strategies based on whether the list is internal or not, but that seems overkill, especially given the code is not that hot as Vedant pointed out.

If we keep the list sorted we might be able to improve finding breakpoints by ID, but that can be done if we need to. BreakpointList::Add would need to insert it sorted, then we can get better than O(n) performance on FindBreakpointByID and Remove (anything that was using find_if when it is searching for a breakpoint by ID).

I'll do this as a follow-up.

On second thought, maybe it's not such a good idea after all. Internal breakpoints are negative so if we keep the vector sorted we'd always insert them at the front of the vector. We could change strategies based on whether the list is internal or not, but that seems overkill, especially given the code is not that hot as Vedant pointed out.

No worries. This is why I mentioned "if we need to". Fine to wait until we need to do this for some reason that proves to be an efficiency issue