GNU bug report logs -
#50733
28.0.1; project-find-regexp can block Emacs for a long time
Previous Next
Full log
View this message in rfc822 format
>
> 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.
This bug report was last modified 3 years and 319 days ago.
Previous Next
GNU bug tracking system
Copyright (C) 1999 Darren O. Benham,
1997,2003 nCipher Corporation Ltd,
1994-97 Ian Jackson.