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

From: Gregory Heytings <gregory <at> heytings.org>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 50733 <at> debbugs.gnu.org, mardani29 <at> yahoo.es, dgutov <at> yandex.ru
Subject: bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time
Date: Mon, 27 Sep 2021 12:25:04 +0000

>
> 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.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.