Uploaded image for project: 'Qt'
  1. Qt
  2. QTBUG-101447

Optimize the use of Boyer-Moore searching

    XMLWordPrintable

Details

    • Task
    • Resolution: Unresolved
    • P2: Important
    • None
    • None
    • None

    Description

      Searching and comparison operators should always be noexcept, which is a problem with our boyer-moore algorithms, because they may allocate. std::boyer_moore_searcher is also not noexcept.

      So we need to write new private BM matchers, which should separate the table generation from the table use, so as to decouple the charset used for building BM tables from the one used to match against. std::boyer_moore_searcher is nice API that way, since it it completely customisable by passing user-defined hashers.

      As regards QTBUG-100239, we need to cap the stored case-folded needle, so it can be stored in a statically-sized buffer. Maybe something like 256 chars or bytes. The result of matching using BM are then only candidates which, if the needle is longer than 256, need to be confirmed by a sliced().startsWith(needle.sliced(256)).

      Attachments

        No reviews matched the request. Check your Options in the drop-down menu of this sections header.

        Activity

          People

            cnn Qt Core & Network
            mmutz Marc Mutz
            Vladimir Minenko Vladimir Minenko
            Alex Blasche Alex Blasche
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

            Dates

              Created:
              Updated:

              Gerrit Reviews

                There are no open Gerrit changes