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

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

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

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