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

[David Blaikie]

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