From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Eli Zaretskii Newsgroups: gmane.emacs.devel Subject: Re: [RFC] position caches Date: Tue, 12 Mar 2013 19:08:32 +0200 Message-ID: <83k3pck0kv.fsf@gnu.org> References: <513EDFAA.8030803@yandex.ru> Reply-To: Eli Zaretskii NNTP-Posting-Host: plane.gmane.org X-Trace: ger.gmane.org 1363108505 30132 80.91.229.3 (12 Mar 2013 17:15:05 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 12 Mar 2013 17:15:05 +0000 (UTC) Cc: emacs-devel@gnu.org To: Dmitry Antipov Original-X-From: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Tue Mar 12 18:15:29 2013 Return-path: Envelope-to: ged-emacs-devel@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1UFSnQ-0005Sf-KJ for ged-emacs-devel@m.gmane.org; Tue, 12 Mar 2013 18:15:28 +0100 Original-Received: from localhost ([::1]:59636 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UFSn4-0001ph-4S for ged-emacs-devel@m.gmane.org; Tue, 12 Mar 2013 13:15:06 -0400 Original-Received: from eggs.gnu.org ([208.118.235.92]:52859) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UFSjf-0005hf-5a for emacs-devel@gnu.org; Tue, 12 Mar 2013 13:15:03 -0400 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1UFSgn-0005vN-Tk for emacs-devel@gnu.org; Tue, 12 Mar 2013 13:11:35 -0400 Original-Received: from mtaout21.012.net.il ([80.179.55.169]:42994) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1UFSgn-0005vC-L6 for emacs-devel@gnu.org; Tue, 12 Mar 2013 13:08:37 -0400 Original-Received: from conversion-daemon.a-mtaout21.012.net.il by a-mtaout21.012.net.il (HyperSendmail v2007.08) id <0MJK00L004VZVV00@a-mtaout21.012.net.il> for emacs-devel@gnu.org; Tue, 12 Mar 2013 19:08:36 +0200 (IST) Original-Received: from HOME-C4E4A596F7 ([87.69.4.28]) by a-mtaout21.012.net.il (HyperSendmail v2007.08) with ESMTPA id <0MJK00LRN4YBRG70@a-mtaout21.012.net.il>; Tue, 12 Mar 2013 19:08:36 +0200 (IST) In-reply-to: <513EDFAA.8030803@yandex.ru> X-012-Sender: halo1@inter.net.il X-detected-operating-system: by eggs.gnu.org: Solaris 10 X-Received-From: 80.179.55.169 X-BeenThere: emacs-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: "Emacs development discussions." List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Original-Sender: emacs-devel-bounces+ged-emacs-devel=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.devel:157788 Archived-At: > Date: Tue, 12 Mar 2013 11:56:26 +0400 > From: Dmitry Antipov > CC: Eli Zaretskii > > This was designed in attempt to avoid long buffer scans in bidi_find_paragraph_start. > The same stuff may be used to implement simple per-buffer charpos <-> bytepos cache. > Caching the result of bidi_find_paragraph_start may improve the speed of backward > scrolling/movement (I've seen ~6x speedup for 60M buffer with average string of 5K > characters). Comments are highly appreciated. Thank you for doing this. > +BUFFER_INLINE bool > +valid_pos_cache (struct buffer *b, struct pos_cache *pc) > +{ > + return BUF_MODIFF (b) == pc->modiff; > +} I think there's a fundamental design problem here, when this cache is used for holding the paragraph start. bidi_paragraph_cache is intended to be used by bidi.c, which is invoked as part of iterating through all the visible parts of a buffer in order to display them. (Sometimes, it iterates across characters immediately before and after the window, and very rarely it does that for positions that are very far from the displayed portion of text.) The visible portion of a buffer can include more than one paragraph (each empty line starts a new paragraph), and each one of these paragraphs can have a different base direction, depending on the first strong directional character of each paragraph. Therefore, bidi.c needs to determine the paragraph start each time it enters a new paragraph. It needs to do that even if the buffer didn't change a bit, because a new paragraph can have a different base direction. The bidi_it->new_paragraph flag is set when the iteration goes out of a paragraph or when the iterator is re-seated far away of its current position. In those cases, xdisp.c calls bidi_paragraph_init, which in turn calls bidi_find_paragraph_start. You cannot return the beginning of previously found paragraph just because the buffer didn't change. So I think the cache needs to track both the beginning and the end position of a paragraph, and invalidate the cache whenever the iterator position (bidi_it->charpos etc.) is outside of these limits. OTOH, I think you can avoid the need to invalidate the cache on every buffer change, if you use markers for storing the paragraph beginning and end. Then you only need to invalidate if the change is at the marker position itself, or if the paragraph was emptied. This might hold the cache valid for quite some time. Thanks.