From: Gregory Heytings <gregory@heytings.org>
To: Eli Zaretskii <eliz@gnu.org>
Cc: 50733@debbugs.gnu.org, dgutov@yandex.ru, mardani29@yahoo.es
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 [thread overview]
Message-ID: <2391d2ad6f7f0febec7c@heytings.org> (raw)
In-Reply-To: <83y27ikznt.fsf@gnu.org>
>
> 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.
next prev parent reply other threads:[~2021-09-27 12:25 UTC|newest]
Thread overview: 49+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <m1h7edq7sc.fsf.ref@yahoo.es>
2021-09-22 9:27 ` bug#50733: 28.0.1; project-find-regexp can block Emacs for a long time Daniel Martín via Bug reports for GNU Emacs, the Swiss army knife of text editors
2021-09-22 19:09 ` Dmitry Gutov
2021-09-22 21:58 ` Daniel Martín via Bug reports for GNU Emacs, the Swiss army knife of text editors
2021-09-22 23:09 ` Dmitry Gutov
2021-09-23 17:41 ` Dmitry Gutov
2021-09-23 21:17 ` Daniel Martín via Bug reports for GNU Emacs, the Swiss army knife of text editors
2021-09-23 22:40 ` Dmitry Gutov
2021-09-24 6:34 ` Eli Zaretskii
2021-09-24 7:02 ` Juri Linkov
2021-09-24 10:43 ` Eli Zaretskii
2021-09-24 15:30 ` Juri Linkov
2021-09-24 16:08 ` Eli Zaretskii
2021-09-24 9:00 ` Gregory Heytings
2021-09-24 11:00 ` Eli Zaretskii
2021-09-24 11:43 ` Dmitry Gutov
2021-09-24 13:18 ` Gregory Heytings
2021-09-24 14:20 ` Eli Zaretskii
2021-09-24 15:50 ` Dmitry Gutov
2021-09-24 16:18 ` Eli Zaretskii
2021-09-24 16:22 ` Dmitry Gutov
2021-09-24 16:24 ` Gregory Heytings
2021-09-24 17:49 ` Eli Zaretskii
2021-09-24 17:52 ` Gregory Heytings
2021-09-24 18:48 ` Eli Zaretskii
2021-09-24 21:49 ` Gregory Heytings
2021-09-25 6:26 ` Eli Zaretskii
2021-09-27 0:43 ` Gregory Heytings
2021-09-27 5:14 ` Eli Zaretskii
2021-09-27 9:23 ` Gregory Heytings
2021-09-27 11:48 ` Eli Zaretskii
2021-09-27 12:25 ` Gregory Heytings [this message]
2021-09-27 12:44 ` Eli Zaretskii
2021-09-27 19:36 ` Gregory Heytings
2021-09-28 5:17 ` Eli Zaretskii
2021-09-28 8:23 ` Gregory Heytings
2021-09-27 12:58 ` Dmitry Gutov
2021-09-27 13:05 ` Eli Zaretskii
2021-09-27 19:37 ` Gregory Heytings
2021-09-24 18:17 ` Dmitry Gutov
2021-09-24 18:51 ` Eli Zaretskii
2021-09-24 11:40 ` Dmitry Gutov
2021-09-24 12:02 ` Eli Zaretskii
2021-09-24 12:22 ` Dmitry Gutov
2021-09-24 13:06 ` Eli Zaretskii
2021-09-24 14:05 ` Dmitry Gutov
2021-09-23 6:13 ` Eli Zaretskii
2021-09-23 20:42 ` Daniel Martín via Bug reports for GNU Emacs, the Swiss army knife of text editors
2021-09-23 22:18 ` Dmitry Gutov
2021-09-24 6:03 ` Eli Zaretskii
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=2391d2ad6f7f0febec7c@heytings.org \
--to=gregory@heytings.org \
--cc=50733@debbugs.gnu.org \
--cc=dgutov@yandex.ru \
--cc=eliz@gnu.org \
--cc=mardani29@yahoo.es \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this external index
https://git.savannah.gnu.org/cgit/emacs.git
https://git.savannah.gnu.org/cgit/emacs/org-mode.git
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.