On Fri, Sep 25, 2020 at 4:15 PM Martin Liška <mli...@suse.cz> wrote:
>
> On 9/25/20 3:45 PM, Richard Biener wrote:
> > On Fri, Sep 25, 2020 at 3:32 PM Martin Liška <mli...@suse.cz> wrote:
> >>
> >> On 9/25/20 3:18 PM, Richard Biener wrote:
> >>> On Fri, Sep 25, 2020 at 11:13 AM Martin Liška <mli...@suse.cz> wrote:
> >>>>
> >>>> Hello.
> >>>>
> >>>> All right, I come up with a rapid speed up that can allow us to remove
> >>>> the introduced parameter. It contains 2 parts:
> >>>> - BIT TEST: we allow at maximum a range that is smaller GET_MODE_BITSIZE
> >>>> - JT: we spent quite some time in density calculation, we can guess it
> >>>> first
> >>>> and it leads to a fast bail out.
> >>>>
> >>>> Patch can bootstrap on x86_64-linux-gnu and survives regression tests.
> >>>>
> >>>> Ready to be installed?
> >>>
> >>> Err
> >>>
> >>> + auto_vec<int> dest_bbs;
> >>> - auto_bitmap dest_bbs;
> >>>
> >>> - bitmap_set_bit (dest_bbs, sc->m_case_bb->index);
> >>> + if (!dest_bbs.contains (sc->m_case_bb->index))
> >>> + {
> >>> + dest_bbs.safe_push (sc->m_case_bb->index);
> >>> + if (dest_bbs.length () > m_max_case_bit_tests)
> >>> + return false;
> >>> + }
> >>
> >> That's intentional as m_max_case_bit_tests is a very small number (3) and
> >> I want to track *distinct* indices in dest_bbs. So dest_bbs.contains
> >> is a constant operation.
> >
> > You're storing bb->index and formerly set bb->index bit, what's the
> > difference?
> >
> > For max 3 elements a vector is OK, of course but there should be a comment
> > that says this ;) The static const is 'int' so it can in principle
> > hold up to two billion ;)
>
> Sure, comment is needed.
>
> >
> >>>
> >>> vec::contains is linear search so no. Was this for the length check?
> >>> Just do
> >>>
> >>> if (bitmap_set_bit (...))
> >>> {
> >>> length++;
> >>> if (length > ...)
> >>
> >> I would need here bitmap_count_bits. Do you prefer it?
> >
> > bitmap_set_bit returns false if the bit was already set so you can
> > count as you add bits, see the length++ above.
>
> Ah, got it!
>
> >
> > For three elements the vec will be faster though. May I suggest
> > to use
> >
> > auto_vec<int, m_max_case_bit_tests> dest_bbs;
> >
> > then and quick_push rather than safe_push (need to guard the
> > push with the max_case_bit_test).
>
> Yes.
>
> Is the patch fine with that (and Jakub's comment)?
Yes.
Thanks,
Richard.
> Martin
>
> >
> > Richard.
> >
> >
> >
> >> Martin
> >>
> >>>
> >>>> Thanks,
> >>>> Martin
> >>
>
