[LLVMdev] [cfe-dev] Bug in MapVector::erase ?

[Duncan P. N. Exon Smith]

> On 2014-Jul-15, at 10:05, David Blaikie <dblaikie at gmail.com> wrote:
> 
> On Tue, Jul 15, 2014 at 9:43 AM, Duncan P. N. Exon Smith
> <dexonsmith at apple.com> wrote:
>> 
>>> On 2014-Jul-15, at 09:38, David Blaikie <dblaikie at gmail.com> wrote:
>>> 
>>> On Tue, Jul 15, 2014 at 9:31 AM, Duncan P. N. Exon Smith
>>> <dexonsmith at apple.com> wrote:
>>>> 
>>>>> On 2014-Jul-15, at 08:29, David Blaikie <dblaikie at gmail.com> wrote:
>>>>> 
>>>>> Sounds pretty clearly buggy, and against the original design of the
>>>>> ADT (as pointed out by the documentation quotation). When was erase
>>>>> functionality added to MapVector? Can/should it be removed (and the
>>>>> use case changed to use some other container)
>>>>> 
>>>>> Making erase linear time sounds... not ideal, but possibly its
>>>>> sufficient for some/current use cases. Or we could consider other
>>>>> solutions to the use cases.
>>>> 
>>>> Heh -- it's already linear.  It erases from the middle of a vector.
>>>> 
>>>> At the least, if erasing is kept (and fixed), someone needs to update the
>>>> docs and add a unit test.
>>>> 
>>>> One way of speeding this up would be to erase a set of values in bulk.  I
>>>> think we could easily add a `remove_if()` function that deleted a set of
>>>> matching items in linear time, using a linear-size auxiliary array of
>>>> indices to keep state.
>>>> 
>>>> I'd be happy to implement this if there's a need (if you can easily design
>>>> it out, that's better).
>>> 
>>> Yeah, at a glance it doesn't seem especially painful to design out -
>>> maybe 10 lines of code.
>> 
>> Great.  The `remove_if()` would probably be about the same (excluding tests), so
>> if this is ever the "right" approach, it might still be worth it.
> 
> After attempting, this gets a bit more insidious and (perhaps
> unsurprisingly) my estimate turned out to be rather optimistic.
> 
> (for the record, it gets ugly in EmitGenDwarfAranges which currently
> computes the length ahead of time (so, it does things like take the
> length of the ranges collection - so if we leave dead entries in there
> it'd have to iterate through to count, for example - or just use a
> label difference))
> 
> If you're happy to fix/test a MapVector::remove_if, that'd be swell.
> It might be a while before I find the time to refactor this whole
> thing into something common (& /maybe/ in the process, avoid this
> particular removal quirk) between DwarfDebug and MCDwarf... :/
> 
> - David

Here's a patch with the fixes (totally untested).  I'll commit
incrementally as I write unit tests, but you can use this locally if
you want to try out changes to the MC code in the meantime.

+chandlerc: as code owner of ADT, any problem with me adding this API
to MapVector?

-------------- next part --------------
A non-text attachment was scrubbed...
Name: mapvector.patch
Type: application/octet-stream
Size: 1999 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140715/4d6029ca/attachment.obj>