Micro‐ and macro‐optimizations of SaaT search. (20th February 2019)

• Record Type: Journal Article
• Authors: Trotman, Andrew; Crane, Matt
• Is Part Of: Software, practice & experience. Volume 49:Number 5(2019)
• Page Start: 942
• Page End: 950
• Publication Date: 2019-02-20
• Subjects: efficiency -- inverted files -- Score‐at‐a‐Time -- search; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.2683
• Languages: English
• ISSNs: 0038-0644

Abstract

Summary: We introduce and test several micro‐ and macro‐optimizations to the Score‐at‐a‐Time approach to processing impact‐ordered postings lists in a search engine. Our micro‐optimizations are at the single‐assembly instruction level, but our macro‐optimizations are algorithmic. Overall, we see an improvement of 37% on our baseline (22% on state of the art). We experiment with parallel search and present evidence that we have hit the memory wall.