From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: John A Pershing Jr Newsgroups: gmane.emacs.help Subject: Re: Performance of String Operations Date: Sun, 11 Oct 2009 16:58:26 -0400 Organization: Optimum Online Message-ID: <82r5t91wct.fsf@alum.mit.edu> References: <87ocodrg8w.fsf@galatea.local> NNTP-Posting-Host: lo.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii X-Trace: ger.gmane.org 1255297260 5797 80.91.229.12 (11 Oct 2009 21:41:00 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Sun, 11 Oct 2009 21:41:00 +0000 (UTC) To: help-gnu-emacs@gnu.org Original-X-From: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Sun Oct 11 23:40:50 2009 Return-path: Envelope-to: geh-help-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([199.232.76.165]) by lo.gmane.org with esmtp (Exim 4.50) id 1Mx69p-00046s-U5 for geh-help-gnu-emacs@m.gmane.org; Sun, 11 Oct 2009 23:40:50 +0200 Original-Received: from localhost ([127.0.0.1]:38299 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.43) id 1Mx69p-0007kg-D6 for geh-help-gnu-emacs@m.gmane.org; Sun, 11 Oct 2009 17:40:49 -0400 Original-Path: news.stanford.edu!usenet.stanford.edu!newsfeed.news2me.com!nx01.iad01.newshosting.com!newshosting.com!69.16.185.51.MISMATCH!tmp-post01.iad!news.highwinds-media.com!news.cv.net!not-for-mail Original-Newsgroups: gnu.emacs.help User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/23.1 (windows-nt) Cancel-Lock: sha1:u+cskJSv9Dlo1OTLbE0smctayw0= Original-Lines: 32 Original-NNTP-Posting-Host: 74.88.209.219 Original-X-Complaints-To: abuse@cv.net Original-Xref: news.stanford.edu gnu.emacs.help:173766 X-BeenThere: help-gnu-emacs@gnu.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Users list for the GNU Emacs text editor List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Original-Sender: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Errors-To: help-gnu-emacs-bounces+geh-help-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.help:68850 Archived-At: pjb@informatimago.com (Pascal J. Bourguignon) writes: > Notice however that emacs provides a data structure for efficient > modification, notably for big strings. It is called a buffer. One of the great ideas from the ancient origins of Emacs is the notion of a "buffer" with its "gap"; I assume that this has carried forward to today's C-based Emacs. A buffer is a large, contiguous chunk of storage containing text, where the text is broken up into two pieces -- the "front" and the "back" (if there are technical terms for this, I don't know what they are). The front of the text occupies the first characters of the buffer, and the back of the text occupies the last characters of the buffer. The result is that there is a "gap" in the middle of the buffer. E.g., |the quick brown |.....gap.....|fox jumped over the dog.| Frequently (but not always), things will be arranged so that 'point' is at the gap: this makes insertion of text easy -- nothing has to be shifted or moved; the inserted text simply gets laid down at the front of the gap, appended to the "front" piece of what's already there. If you move the point somewhere else and start inserting text, there is an internal routine that will "move" the gap so that it lines up with the new position of point (actually, text is moved from one side of the gap to the other). Of course, a bunch of low-level functions need to be aware of the gap (e.g., string searches), and there's a bunch of complex bookkeeping, but this is all worth it for the avoidance of lots of string copying. -jp