Page MenuHomePhabricator

Make SymbolFileDWARF::ParseLineTable use std::sort instead of insertion sort
ClosedPublic

Authored by unnar on Jan 17 2020, 2:39 AM.

Details

Summary

Motivation: When setting breakpoints in certain projects line sequences are frequently being inserted out of order.

Rather than inserting sequences one at a time into a sorted line table, store all the line sequences as we're building them up and sort and flatten afterwards.

Diff Detail

Event Timeline

unnar created this revision.Jan 17 2020, 2:39 AM
labath added a subscriber: labath.Jan 17 2020, 2:59 AM

Thanks for the patch. I've been wondering how to improve this, and this solution is pretty neat.

I have just one request. Instead of the ReplaceLineTableWithSequences thingy, could you just create a LineTable constructor, which takes an ArrayRef<LineSequence *> or similar. It looks like all it takes is to make CreateLineSequenceContainer static, so you can invoke it without a LineTable instance. (There are other possible cleanups here too, but I don't think its your job do fix all of those...)

unnar added a comment.EditedJan 17 2020, 3:23 AM

Thanks for the patch. I've been wondering how to improve this, and this solution is pretty neat.

I have just one request. Instead of the ReplaceLineTableWithSequences thingy, could you just create a LineTable constructor, which takes an ArrayRef<LineSequence *> or similar. It looks like all it takes is to make CreateLineSequenceContainer static, so you can invoke it without a LineTable instance. (There are other possible cleanups here too, but I don't think its your job do fix all of those...)

Thanks for the quick review!

It also requires AppendLineEntryToSequence to be static but I assume that should also be just fine.

teemperor added inline comments.
lldb/source/Symbol/LineTable.cpp
172

Nit pick, this would also work without the reinterpret_cast and const arguments. E.g.:

bool LineTable::Entry::LessThanBinaryPredicate::
operator()(const LineSequence *sequence_a, const LineSequence *sequence_b) const {
  auto *seq_a = static_cast<const LineSequenceImpl *>(sequence_a);
  auto *seq_b = static_cast<const LineSequenceImpl *>(sequence_b);
  return (*this)(seq_a->m_entries.front(), seq_b->m_entries.front());
}
unnar updated this revision to Diff 238759.Jan 17 2020, 5:55 AM
unnar marked an inline comment as done.

@labath

Can you take another look and see if this matches what you had in mind?

labath accepted this revision.Jan 17 2020, 6:13 AM

Yes, that's looks pretty much like it, but it seems you uploaded the diff incorrectly -- it looks like its based on the previous version of your patch and not master (you should always upload the full set of changes not just the recent additions).

Also, when I asked for an ArrayRef, I forgot that you are sorting the thing -- a vector does seem reasonable in that case (sorry).

Do you have commit access? If not, I can land this for you (as soon as I get the correct diff).

This revision is now accepted and ready to land.Jan 17 2020, 6:13 AM
unnar updated this revision to Diff 238771.Jan 17 2020, 7:15 AM

Switched back to std::vector and uploaded the full diff.

I don't have commit access so it would be appreciated if you could land this for me, thanks!

This revision was automatically updated to reflect the committed changes.
grimar added a subscriber: grimar.Jan 21 2020, 12:25 AM
grimar added inline comments.
lldb/source/Symbol/LineTable.cpp
27

I wonder if this have to be std::stable_sort?
For std::sort the order of equal elements is not guaranteed to be preserved.

nit: you could also probably use the llvm::sort (it would be a bit shorter):
llvm::sort(sequences, less_than_bp);

teemperor added inline comments.Jan 21 2020, 1:31 AM
lldb/source/Symbol/LineTable.cpp
27

I think we should change this to llvm::sort just because of the additional checks we get there (I think the shuffle/sort<->stable_sort checks are only in llvm::sort).

labath added inline comments.Jan 21 2020, 5:12 AM
lldb/source/Symbol/LineTable.cpp
27

I've changed this to llvm::stable_sort in 9a52ea5cf9c. I went for a stable sort because it's possible (though probably not very useful) for the debug info to contain two line sequences for the same address (and I've just today found a flaky test due to nondeterminism in lldb).