Page MenuHomePhabricator

unnar (Unnar Freyr Erlendsson)
User

Projects

User does not belong to any projects.

User Details

User Since
Jan 13 2020, 7:34 AM (40 w, 1 d)

Recent Activity

Mar 2 2020

unnar added a comment to D74759: Treat RangeDataVector as an augmented BST.

Yes please. :)

Mar 2 2020, 8:04 AM · Restricted Project
unnar added a comment to D74759: Treat RangeDataVector as an augmented BST.

Thanks for the feedback! I addressed all of your comments in the latest patch.

Mar 2 2020, 5:02 AM · Restricted Project
unnar updated the diff for D74759: Treat RangeDataVector as an augmented BST.
Mar 2 2020, 5:02 AM · Restricted Project

Feb 28 2020

unnar updated the diff for D74759: Treat RangeDataVector as an augmented BST.

As discussed with @labath I made a separate struct called AugmentedEntry that is used internally but we only ever expose the Entry part to the user.

Feb 28 2020, 3:52 AM · Restricted Project

Feb 27 2020

unnar added a comment to D74759: Treat RangeDataVector as an augmented BST.

That should work...although I'm not sure how that is any different to the range or data being public. If a user modifies anything then it has essentially invalidated the whole structure anyway.

That is a fair point. I suppose the reason why I see this as different is because this field is an implementation detail of the RangeDataVector class, and so the user should not even see it -- whereas the user has a legitimate reason to at least access the other fields (and most of the methods only provide read-only access to these fields).

I'm sorry, I haven't gotten around to looking at this patch today, but I thought I'd at least say that...

Feb 27 2020, 10:22 AM · Restricted Project

Feb 26 2020

unnar added a comment to D75180: Add unit tests for RangeDataVector::FindEntryIndexesThatContain.

No, I can't. If you could submit this for me it would be great.

Feb 26 2020, 7:35 AM · Restricted Project
unnar updated the diff for D75180: Add unit tests for RangeDataVector::FindEntryIndexesThatContain.
Feb 26 2020, 7:35 AM · Restricted Project
unnar added a comment to D74759: Treat RangeDataVector as an augmented BST.

Have you done a proper complexity analysis here? I doubt the O(log n) claim is true in general. It would have to be at least O(m + log n) (m - number of elements found), but it's not clear to me whether even this is true in general. (However, I believe this can achieve ~~log(n) for non-degenerate cases.)

I should have been more specific, searching for any interval that contains a point can be done in O(log n) but in our case where we are searching for all intervals that contain the point and as Jarin said we believe it takes O(m log n) (I admit I have not done a thorough analysis of the time complexity myself). The theoretical best you can do is indeed O(m + log n).

Yep, I can easily convince myself is m*log(n). I can believe it can be O(m+log(n)) too, but proving that would require some pretty careful accounting. In either case, I am sure this is better than what we have now.

For testing you should add some c++ unit tests for the relevant interfaces.

Done. Do you think we should also unit test ComputeUpperBounds or just the interface?

Testing the interface should be enough. In fact, the main thing that is bothering me about this patch at this stage is that the new "upper_bound" member is public and accessible to the user. I haven't decided yet what to do about it. Have you looked at what it would take to make that private somehow? Maybe by storing std::pair<Entry, bound> in the private vector, and only handing out pointers to the Entry component ?

Feb 26 2020, 7:35 AM · Restricted Project
unnar created D75180: Add unit tests for RangeDataVector::FindEntryIndexesThatContain.
Feb 26 2020, 7:24 AM · Restricted Project
unnar added a comment to D74759: Treat RangeDataVector as an augmented BST.

Sure, removed tests from this patch. They are now at D75180

Feb 26 2020, 7:24 AM · Restricted Project
unnar updated the diff for D74759: Treat RangeDataVector as an augmented BST.
Feb 26 2020, 7:24 AM · Restricted Project
unnar updated the diff for D74759: Treat RangeDataVector as an augmented BST.

Added reference to Wikipedia article.

Feb 26 2020, 5:22 AM · Restricted Project
unnar added inline comments to D74759: Treat RangeDataVector as an augmented BST.
Feb 26 2020, 5:06 AM · Restricted Project
unnar updated the diff for D74759: Treat RangeDataVector as an augmented BST.

Have you done a proper complexity analysis here? I doubt the O(log n) claim is true in general. It would have to be at least O(m + log n) (m - number of elements found), but it's not clear to me whether even this is true in general. (However, I believe this can achieve ~~log(n) for non-degenerate cases.)

Feb 26 2020, 5:06 AM · Restricted Project

Feb 18 2020

unnar created D74759: Treat RangeDataVector as an augmented BST.
Feb 18 2020, 3:53 AM · Restricted Project

Jan 17 2020

unnar updated the diff for D72909: Make SymbolFileDWARF::ParseLineTable use std::sort instead of insertion sort.

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

Jan 17 2020, 7:18 AM · Restricted Project
unnar updated the diff for D72909: Make SymbolFileDWARF::ParseLineTable use std::sort instead of insertion sort.

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

Jan 17 2020, 6:01 AM · Restricted Project
unnar added a comment to D72909: Make SymbolFileDWARF::ParseLineTable use std::sort instead of insertion sort.

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...)

Jan 17 2020, 3:23 AM · Restricted Project
unnar created D72909: Make SymbolFileDWARF::ParseLineTable use std::sort instead of insertion sort.
Jan 17 2020, 2:43 AM · Restricted Project