D28843: [AndPostingIterator] Replace recursive next() implementation

Stefan BrĂ¼ns noreply at phabricator.kde.org
Tue Apr 14 22:01:41 BST 2020


bruns created this revision.
bruns added reviewers: Baloo, ngraham.
Herald added projects: Frameworks, Baloo.
Herald added a subscriber: kde-frameworks-devel.
bruns requested review of this revision.

REVISION SUMMARY
  The next() call will recurse once for each document in the first set
  until all iterators align, which is especially bad when the first term
  is common. It will only advance the first iterator just by one, although
  it could skip to the largest id in the set.
  
  Use skipTo on each iterator until none of the iterators moves forward,
  and in case the iterator has moved use the new position as new lower
  bound. If one of of the iterators only contains a small set, the
  iterators on average will be moved much further in each round.
  
  As skipTo(...) and next() are mostly identical with this approach next()
  can be trivially implemented with skipTo.
  
  Depends on D28839 <https://phabricator.kde.org/D28839>

REPOSITORY
  R293 Baloo

BRANCH
  submit

REVISION DETAIL
  https://phabricator.kde.org/D28843

AFFECTED FILES
  src/engine/andpostingiterator.cpp
  src/engine/andpostingiterator.h

To: bruns, #baloo, ngraham
Cc: kde-frameworks-devel, hurikhan77, lots0logs, LeGast00n, cblack, fbampaloukas, domson, ashaposhnikov, michaelh, astippich, spoorun, ngraham, bruns, abrahams
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.kde.org/pipermail/kde-frameworks-devel/attachments/20200414/191a9333/attachment.html>


More information about the Kde-frameworks-devel mailing list