Duncan P. N. Exon Smith
2014-Jul-15 17:54 UTC
[LLVMdev] [cfe-dev] Bug in MapVector::erase ?
> 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... :/ > > - DavidHere'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>
Can we explicitly delete the erase method or do something else to document the fact that it is unsupported? It was added incidentally in r211350, even though it was added and removed by Doug back in r175538 / r175449. On Tue, Jul 15, 2014 at 10:54 AM, Duncan P. N. Exon Smith < dexonsmith at apple.com> wrote:> > > 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? > > > _______________________________________________ > cfe-dev mailing list > cfe-dev at cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-dev > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140715/6948608b/attachment.html>
Duncan P. N. Exon Smith
2014-Jul-15 18:28 UTC
[LLVMdev] [cfe-dev] Bug in MapVector::erase ?
> On 2014-Jul-15, at 11:07, Reid Kleckner <rnk at google.com> wrote: > > Can we explicitly delete the erase method or do something else to document the fact that it is unsupported? It was added incidentally in r211350, even though it was added and removed by Doug back in r175538 / r175449. >I'm happy with it deleted or fixed (see WIP patch that fixes it w/o tests). For now, I'll fix it, and then David (or someone else) can migrate the code to `remove_if()`. FWIW, when it's fixed, it doesn't have to be "unsupported" -- it's just *slow*. -------------- 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/00ee4949/attachment.obj>