Indeed. The sensible thing is to use caching and avoid doing long-running operations in real-time. When the user presses a key the browser searches through a small cache of recent urls, if there is a delay before pressing the next key (say a second or so) then that triggers a more thorough search through the entire history.
It is incredibly annoying for the suggestion list to change after its first appearance. You may have been about to select a particular URL when it changes unexpectedly, and you end up navigating somewhere you hadn't intended.
Wait until there's a significant pause in typing before updating.
If the user interact with the list (keys or mouse) then the browser should not modify it, until the user type again.
Then why store all history?
Presumably so you can elect to search history and be prepared to wait for results - unlike omnibar where you want instant typing.