bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time

[Gregory Heytings]

> But the scalability you measured is approximately O(n), as expected from 
> a tool that accesses the files while searching.  IDUtils' gid basically 
> runs in O(1) time.  I've just run it on a tree with 17MB of code in 400 
> files (ID database size 54KB) and on a tree with 1.4GB of code in 40,000 
> files (DB size 13.5MB), and I get the same time for the same search: 
> 15ms.  No algorithm that actually accesses most or all of the files in 
> the tree can scale like that.

Of course a table lookup is O(1) and a search is O(n).  If and only if you 
forget the time it takes to build the table and to keep it up to date. 
According to my tests, 1 call to mkid followed by 100 calls to gid is 
still slower than 100 calls to rg; the "break-even point" is somewhere 
around 200 searches.

I agree with you on one point: it is perhaps possible to make rg even 
faster with a database cache.