lists.texi

lists.texi

[Luc Teirlinck]

I recommend the following changes to lists.texi and can install if
desired.  In as far as spelling issues are concerned, `vs' seems to be
the standard abbreviation of `versus' and `indices' seems to be the plural
form of `index' consistently used in the Elisp manual.

In as far as the return value of `ring-insert-at-beginning' is
concerned, it definitely is _not_ OBJECT as currently documented in
the Elips manual.  The return value is the _new_ length of the ring,
but this seems to be by accident, rather than by design.  We could
either document the actual return value, change
`ring-insert-at-beginning' to really return OBJECT (does not seem
terribly useful to me) or say that the return value is not
significant.  The patch below does the latter.

===File ~/lists.texi-diff===================================
*** lists.texi	17 Jun 2005 09:08:29 -0500	1.52
--- lists.texi	18 Jun 2005 16:58:45 -0500	
***************
*** 715,721 ****
  primitives @code{setcar} and @code{setcdr}.  We call these ``destructive''
  operations because they change existing list structure.
  
! @cindex CL note---@code{rplaca} vrs @code{setcar}
  @quotation
  @findex rplaca
  @findex rplacd
--- 715,721 ----
  primitives @code{setcar} and @code{setcdr}.  We call these ``destructive''
  operations because they change existing list structure.
  
! @cindex CL note---@code{rplaca} vs @code{setcar}
  @quotation
  @findex rplaca
  @findex rplacd
***************
*** 1691,1697 ****
  @end defun
  
  @defun ring-p object
! This returns @code{t} if @var{object} is a ring.
  @end defun
  
  @defun ring-size ring
--- 1691,1697 ----
  @end defun
  
  @defun ring-p object
! This returns @code{t} if @var{object} is a ring, @code{nil} otherwise.
  @end defun
  
  @defun ring-size ring
***************
*** 1705,1725 ****
  
  @defun ring-elements ring
  This returns a list of the objects in @var{ring}, in no particular
! order.
  @end defun
  
  @defun ring-copy ring
  This returns a new ring which is a copy of @var{ring}.
! The new ring contains the same objects as @var{ring}.
  @end defun
  
  @defun ring-empty-p ring
! This returns @code{t} if @var{ring} is empty.
  @end defun
  
!   The newest element in the ring always has index 0.  Higher indexes
! correspond to older elements.  Index @minus{}1 corresponds to the
! oldest element, @minus{}2 to the next-oldest, and so forth.
  
  @defun ring-ref ring index
  This returns the object in @var{ring} found at index @var{index}.
--- 1705,1728 ----
  
  @defun ring-elements ring
  This returns a list of the objects in @var{ring}, in no particular
! order.  The length of that list is always the ring size.  If the ring
! length is less than the ring size, the entries of the list that do not
! correspond to ring elements are @code{nil}.
  @end defun
  
  @defun ring-copy ring
  This returns a new ring which is a copy of @var{ring}.
! The new ring contains the same (@code{eq}) objects as @var{ring}.
  @end defun
  
  @defun ring-empty-p ring
! This returns @code{t} if @var{ring} is empty, @code{nil} otherwise.
  @end defun
  
!   The newest element in the ring always has index 0.  Higher indices
! correspond to older elements.  Indices are computed modulo the ring
! length.  Index @minus{}1 corresponds to the oldest element, @minus{}2
! to the next-oldest, and so forth.
  
  @defun ring-ref ring index
  This returns the object in @var{ring} found at index @var{index}.
***************
*** 1744,1750 ****
  
  @defun ring-insert-at-beginning ring object
  This inserts @var{object} into @var{ring}, treating it as the oldest
! element, and returns @var{object}.
  
  If the ring is full, this function removes the newest element to make
  room for the inserted element.
--- 1747,1753 ----
  
  @defun ring-insert-at-beginning ring object
  This inserts @var{object} into @var{ring}, treating it as the oldest
! element.  The return value is not significant.
  
  If the ring is full, this function removes the newest element to make
  room for the inserted element.
============================================================

Re: lists.texi

[Luc Teirlinck]

>From my previous message:

     @defun ring-elements ring
     This returns a list of the objects in @var{ring}, in no particular
   ! order.  The length of that list is always the ring size.  If the ring
   ! length is less than the ring size, the entries of the list that do not
   ! correspond to ring elements are @code{nil}.
     @end defun

Maybe I am trying to document a bug here.  Maybe it is better not to
add these two sentences and instead make `ring-elements' do what the
first sentence above, and its docstring, say it does.  `ring-elements'
is not used in the Emacs sources, so the change is not going to break
anything and all it does is make the function work as documented.

I can install if desired.

===File ~/ring.el-diff======================================
*** ring.el	02 Sep 2003 07:41:57 -0500	1.18
--- ring.el	18 Jun 2005 18:45:44 -0500	
***************
*** 155,162 ****
        (aref vec (ring-index index hd ln (length vec))))))
  
  (defun ring-elements (ring)
!   "Return a list of the elements of RING."
!   (mapcar #'identity (cddr ring)))
  
  ;;; provide ourself:
  
--- 155,164 ----
        (aref vec (ring-index index hd ln (length vec))))))
  
  (defun ring-elements (ring)
!   "Return a list of the elements of RING, in no particular order."
!   (let (lst)
!     (setq lst (delq nil (mapcar #'identity (cddr ring))))
!     (nconc lst (make-list (- (ring-length ring) (length lst)) nil))))
  
  ;;; provide ourself:
  
============================================================

Re: lists.texi

[Luc Teirlinck]

The following patch to ring.el is equivalent to the one I sent
earlier, but probably slightly better:

===File ~/ring.el-diff-b====================================
*** ring.el	02 Sep 2003 07:41:57 -0500	1.18
--- ring.el	18 Jun 2005 18:53:24 -0500	
***************
*** 155,162 ****
        (aref vec (ring-index index hd ln (length vec))))))
  
  (defun ring-elements (ring)
!   "Return a list of the elements of RING."
!   (mapcar #'identity (cddr ring)))
  
  ;;; provide ourself:
  
--- 155,163 ----
        (aref vec (ring-index index hd ln (length vec))))))
  
  (defun ring-elements (ring)
!   "Return a list of the elements of RING, in no particular order."
!   (let ((lst (delq nil (mapcar #'identity (cddr ring)))))
!     (nconc lst (make-list (- (ring-length ring) (length lst)) nil))))
  
  ;;; provide ourself:
  
============================================================

Re: lists.texi

[Luc Teirlinck]

Actually, if we have to do all of that to get the correct return
value, we could quite as well use the following function, which does
get the order correct:

(defun ring-elements (ring)
  "Return a list of the elements of RING in order, newest first."
  (let (lst)
    (dotimes (var (ring-length ring))
      (push (ring-ref ring var) lst))
    (nreverse lst)))

Re: lists.texi

[David Kastrup]

Luc Teirlinck <teirllm@dms.auburn.edu> writes:

> Actually, if we have to do all of that to get the correct return
> value, we could quite as well use the following function, which does
> get the order correct:
>
> (defun ring-elements (ring)
>   "Return a list of the elements of RING in order, newest first."
>   (let (lst)
>     (dotimes (var (ring-length ring))
>       (push (ring-ref ring var) lst))
>     (nreverse lst)))

Looks like O(n^2) complexity to me.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: lists.texi

[Richard Stallman]

    Maybe I am trying to document a bug here.  Maybe it is better not to
    add these two sentences and instead make `ring-elements' do what the
    first sentence above, and its docstring, say it does.

I think so.

    !     (nconc lst (make-list (- (ring-length ring) (length lst)) nil))))

What's the purpose of this?  It seems only to reintroduce the same bug
that the delq fixes.

    (defun ring-elements (ring)
      "Return a list of the elements of RING in order, newest first."
      (let (lst)
	(dotimes (var (ring-length ring))
	  (push (ring-ref ring var) lst))
	(nreverse lst)))

Isn't that quadratically slow?  And it doesn't fix the bug.

Re: lists.texi

[Luc Teirlinck]

Richard Stallman wrote:

       (defun ring-elements (ring)
	 "Return a list of the elements of RING in order, newest first."
	 (let (lst)
	   (dotimes (var (ring-length ring))
	     (push (ring-ref ring var) lst))
	   (nreverse lst)))

   Isn't that quadratically slow?  And it doesn't fix the bug.

Yes, it is quadratically slow.  Let us just forget about this one.
But it did fix the bug.

       !     (nconc lst (make-list (- (ring-length ring) (length lst)) nil))))

   What's the purpose of this?  It seems only to reintroduce the same bug
   that the delq fixes.

No.  The bug is that if the size of the ring is larger than the
length, the current version of `ring-elements' introduces fake `nil'
elements.  The delq gets rid of all nil's, fake ones and potentially
legitimate ones, because certain ring elements could _really_ be nil.
The nconc re-adds the correct number of legitimate nil's.  See the
ielm run below.

When testing the new function you have to be careful.  If you just do
C-M-x on it and then start experimenting, the bug _will_ still be
there.  Indeed, ring.el is not pre-loaded.  The experimentation loads
ring.el, overriding your C-M-x with the old definition.

The ielm run below uses the following function (the one in the second
patch I sent), which I propose to install:

(defun ring-elements (ring)
  "Return a list of the elements of RING, in no particular order."
  (let ((lst (delq nil (mapcar #'identity (cddr ring)))))
    (nconc lst (make-list (- (ring-length ring) (length lst)) nil))))

The original ring-elements would return three times
(nil nil nil nil nil nil) in the run below.  The function above
_without_ the nconc would return three times nil, which would only be
correct on the first call.

*** Welcome to IELM ***  Type (describe-mode) for help.
ELISP> (setq rr (make-ring 6))
(0 0 .
   [nil nil nil nil nil nil])

ELISP> (ring-elements rr)
nil
ELISP> (ring-insert rr nil) 
nil
ELISP> (ring-elements rr)
(nil)

ELISP> (ring-insert rr nil) 
nil
ELISP> (ring-elements rr)
(nil nil)

ELISP> 

Re: lists.texi

[Richard Stallman]

    No.  The bug is that if the size of the ring is larger than the
    length, the current version of `ring-elements' introduces fake `nil'
    elements.  The delq gets rid of all nil's, fake ones and potentially
    legitimate ones, because certain ring elements could _really_ be nil.
    The nconc re-adds the correct number of legitimate nil's.  See the
    ielm run below.

Ok.

If you want to do a little work, I am sure you could write a single
loop that produces the right elements in the right order.  Then you
could rotate it properly with a single call to setcdr followed by
nconc'ing the pieces in the opposite order.

Re: lists.texi

[Luc Teirlinck]

Richard Stallman wrote:

   If you want to do a little work, I am sure you could write a single
   loop that produces the right elements in the right order.  Then you
   could rotate it properly with a single call to setcdr followed by
   nconc'ing the pieces in the opposite order.

Unless I am completely misunderstanding things, I believe I was a
little bit too quick to admit that my original function:

(defun ring-elements (ring)
  "Return a list of the elements of RING in order, newest first."
  (let (lst)
    (dotimes (var (ring-length ring))
      (push (ring-ref ring var) lst))
    (nreverse lst)))

was quadratic.  It essentially does ring-length times an aref in
_vector_, which unlike checking the element at an average position in
a _list_, would not appear to be linear in the size of the vector.

Anyway, I now propose the following which avoids the nreverse and
esentially "inlines" the `ring-ref' call, but in a way that avoids a
lot more overhead than a simple inlining.  So I believe that it should
be an improvement by a pretty good constant factor, which would not be
of too much help if it really is quadratic, but why is it?

(defun ring-elements (ring)
  "Return a list of the elements of RING, in order, newest first."
  (let ((start (car ring))
  (size (ring-size ring))
  (vect (cddr ring))
  lst)
    (dotimes (var (cadr ring) lst)
      (push (aref vect (mod (+ start var) size)) lst))))

Re: lists.texi

[David Kastrup]

Luc Teirlinck <teirllm@dms.auburn.edu> writes:

> Richard Stallman wrote:
>
>    If you want to do a little work, I am sure you could write a single
>    loop that produces the right elements in the right order.  Then you
>    could rotate it properly with a single call to setcdr followed by
>    nconc'ing the pieces in the opposite order.
>
> Unless I am completely misunderstanding things, I believe I was a
> little bit too quick to admit that my original function:
>
> (defun ring-elements (ring)
>   "Return a list of the elements of RING in order, newest first."
>   (let (lst)
>     (dotimes (var (ring-length ring))
>       (push (ring-ref ring var) lst))
>     (nreverse lst)))
>
> was quadratic.  It essentially does ring-length times an aref in
> _vector_, which unlike checking the element at an average position
> in a _list_, would not appear to be linear in the size of the
> vector.

Well, I was one of the O(n^2) criers, and I did not know that ring-ref
works via aref.  Looking at ring-ref, however, it would appear that
the O(1) constant is pretty hefty.

> Anyway, I now propose the following which avoids the nreverse and
> esentially "inlines" the `ring-ref' call, but in a way that avoids a
> lot more overhead than a simple inlining.  So I believe that it
> should be an improvement by a pretty good constant factor, which
> would not be of too much help if it really is quadratic, but why is
> it?
>
> (defun ring-elements (ring)
>   "Return a list of the elements of RING, in order, newest first."
>   (let ((start (car ring))
>   (size (ring-size ring))
>   (vect (cddr ring))
>   lst)
>     (dotimes (var (cadr ring) lst)
>       (push (aref vect (mod (+ start var) size)) lst))))

As long as you checked that the elements come out in the right order,
this would appear like a pretty good solution.

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

Re: lists.texi

[Richard M. Stallman]

    was quadratic.  It essentially does ring-length times an aref in
    _vector_, which unlike checking the element at an average position in
    a _list_, would not appear to be linear in the size of the vector.

If it is a vector, you're right, it isn't quadratic.

Re: lists.texi

[Thien-Thi Nguyen]

Luc Teirlinck <teirllm@dms.auburn.edu> writes:

> (defun ring-elements (ring)
>   "Return a list of the elements of RING in order, newest first."
>   (let (lst)
>     (dotimes (var (ring-length ring))
>       (push (ring-ref ring var) lst))
>     (nreverse lst)))

an index of -1 returns the "oldest" element.
so you could just `(ring-ref ring -1)' until the
ring is exhausted, obviating both `nreverse' and
`var' reference, while keeping the abstraction.

thi

Re: lists.texi

[Luc Teirlinck]

Thien-Thi Nguyen wrote:

   an index of -1 returns the "oldest" element.
   so you could just `(ring-ref ring -1)' until the
   ring is exhausted, obviating both `nreverse' and
   `var' reference, while keeping the abstraction.

ring-ref does not rotate the ring, nor does it "exhaust" it.  Maybe
you mean `ring-remove', but that would force me to copy the ring first.

The abstraction involves overhead, slowing the function down by a
factor of slightly more than 2.2.  Apparently the abstraction does
more to confuse people (making them believe the algorithm is
quadratic) than to enlighten them.  The aref makes it clear that the 
algorithm is linear.

I still propose to install the function I proposed in my last message.

Here are timings for different versions, running ring-elements ten
thousand times on a ring of length 1000 on a 1.7 GHZ dual Intel Xeon:

Original "abstract" nreverse version:

(defun old-ring-elements (ring)
  "Return a list of the elements of RING in order, newest first."
  (let (lst)
    (dotimes (var (ring-length ring))
      (push (ring-ref ring var) lst))
    (nreverse lst)))

50 secomds

Avoiding nreverse, keeping "abstraction":

(defun my-ring-elements (ring)
  "Return a list of the elements of RING in order, newest first."
  (let (lst)
    (dotimes (var (ring-length ring) lst)
      (push (ring-ref ring (- -1 var)) lst))))

51 seconds.  nreverse is a primitive running a very efficient
algorithm, it makes no sense to avoid it just for efficiency reasons.

This is the function I still propose to install:

(defun ring-elements (ring)
  "Return a list of the elements of RING, in order, newest first."
  (let ((start (car ring))
	(size (ring-size ring))
	(vect (cddr ring))
	lst)
    (dotimes (var (cadr ring) lst)
      (push (aref vect (mod (+ start var) size)) lst))))

23 seconds, better by a factor of 2.2.

The following does still _slightly_ better for this test case, but at
a real price in transparency.  I believe that it performs a lot more
operations than the function I propose to install, but it runs
slightly faster, because more operations are performed inside primitives.

(defun new-ring-elements (ring)
  "Return a list of the elements of RING in order, newest first."
  (let ((lst (mapcar #'identity (cddr ring)))
	(tot (+ (car ring) (cadr ring)))
	(size (ring-size ring)))
    (if (>= size tot)
	(nreverse (nbutlast (nthcdr (car ring) lst) (- size tot)))
      (nconc (nreverse (butlast lst (- (* 2 size) tot)))
	     (nreverse (nthcdr (car ring) lst))))))

20 seconds.

If one _really_ cares about efficiency, the thing to do would be to
take the function I propose to install and write it in C, but given
the fact that `ring-elements' is not even used anywhere in the Emacs
sources, this would not seem warranted.

Sincerely,

Luc.

Re: lists.texi

[Luc Teirlinck]

After thinking a bit more, the algorithm I propose to install (took 23
seconds in the test case) seems clearly superior over the one that
took 20 seconds.  The reason is that my proposed algorithm is linear
in the _length_ of the ring, the 20 second algorithm is linear in the
_size_ of the ring.  The test case involved a ring of size and lenght
1000, but for rings of large size and small lengths, the 20 second
algorithm is completely hopeless.  Running `ring-elements' ten
thousand times on an empty ring of size one thousand, the algorithm a
propose took zero seconds (well, to be precise, an unmeasurable amount
of time), the 20 second algorithm _still_ took 20 seconds.

The original buggy algorithm and my corrections of it that did not get
the order right, were _also_ linear in the _size_ of the ring, so in
that sense the new algorithm does not only produce a more satisfactory
result, but is also more efficient. 

Sincerely,

Luc.

Re: lists.texi

[Luc Teirlinck]

Apparently these timings are not very fixed.  In a freshly started
Emacs, my proposed version took 12 seconds (instead of earlier 23) and
the abstract versions 40 seconds (instead of 51).  This gives a
mysterious gain of 11 seconds for both.  But now my proposed version
runs 3.33 times faster than the abstract ones, instead of earlier 2.2.

Sincerely,

Luc.

Re: lists.texi

[Thien-Thi Nguyen]

Luc Teirlinck <teirllm@dms.auburn.edu> writes:

> ring-ref does not rotate the ring, nor does it "exhaust" it.  Maybe
> you mean `ring-remove', but that would force me to copy the ring first.

you're right.  i was thinking destructively (been reading Il Signore
Degli Annelli, that's my excuse :-)...  sorry about the noise.

> 23 seconds, better by a factor of 2.2.

sounds like the winner (w/o going to extremes).

thi

Re: lists.texi

[Thien-Thi Nguyen]

Luc Teirlinck <teirllm@dms.auburn.edu> writes:

> Apparently these timings are not very fixed.  In a freshly started
> Emacs, my proposed version took 12 seconds (instead of earlier 23) and
> the abstract versions 40 seconds (instead of 51).  This gives a
> mysterious gain of 11 seconds for both.  But now my proposed version
> runs 3.33 times faster than the abstract ones, instead of earlier 2.2.

(curmudgeon-mode) i have a hard enough time wrapping my head around
whole numbers, like 1 and 0 -- all this stuff after the decimal point is
lost on me.  when things are slow that's just an excuse for a nap!

but fwiw, in the spirit of not discouraging the nimble mind, below is
some code that you can perhaps use/tweak to exercise rings in a less
clinical environment (to put a nice name on a messy playpen... :-).

the curious will note that ewoc.el documentation is as yet unwritten.
is anyone looking into that?  can it wait until after next release?

thi

___________________________________________________________________________
;;; WORK-IN-PROGRESS  WORK-IN-PROGRESS  WORK-IN-PROGRESS  WORK-IN-PROGRESS
;;; WORK-IN-PROGRESS  WORK-IN-PROGRESS  WORK-IN-PROGRESS  WORK-IN-PROGRESS
;;; WORK-IN-PROGRESS  WORK-IN-PROGRESS  WORK-IN-PROGRESS  WORK-IN-PROGRESS

;;; edb.el --- EDB 2.x

;; Copyright (C) 2005 Thien-Thi Nguyen

;; EDB is distributed under the terms of the GNU General Public License.

;; EDB is distributed in the hope that it will be useful, but WITHOUT
;; ANY WARRANTY.  No author or distributor accepts responsibility to anyone
;; for the consequences of using it or for whether it serves any particular
;; purpose or works at all, unless he says so in writing.  Refer to the GNU
;; General Public License for full details.

;; Everyone is granted permission to copy, modify and redistribute EDB, but
;; only under the conditions described in the GNU General Public License.  A
;; copy of this license is supposed to have been given to you along with EDB
;; so you can know your rights and responsibilities.  It should be in a file
;; named COPYING.  If not, write to the Free Software Foundation, Inc.,
;; 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA for a copy.
;; Among other things, the copyright notice and this notice must be preserved
;; on all copies.

;;; Commentary:

;; Naming convention: "edb--" means "internal"; "edb-" means "public".
;; If all goes well (everything is useful), we will relax this convention
;; (and consider everything public).

;;; Code:

(eval-when-compile (require 'cl))

\f
;;; sequential read and write

(defvar edb--*sequential-i/o*           ; alist
  `((read-line . ,(lambda (finish)
                    (let (rec recs)
                      (while (< (progn
                                  (setq rec (read (current-buffer)))
                                  (skip-syntax-forward "^()")
                                  (point))
                                finish)
                        (push rec recs))
                      recs)))))

\f
;;; connection

(defvar edb--*schema-schema*
  '((single (:valid-keys
             :name :require
             :fields :fieldtype :field-separator
             :record-separator :record-separator-function
             :read-record :write-record :record-defaults
             :post-last-record :choose-display :display :report
             :summary-format :substitutions
             :every-change-function
             :field-setter :first-change-function
             :field-priorities
             :enumerated-type :tagged-setup
             :displaytype
             :before-display
             :data)
            (:valid-options)))
  "Alist of sub-alists controlling how a schema is handled.
In the sub-alist, valid keys are:

:valid-keys -- list of acceptable keys
:valid-options -- list of acceptable options")

(defun edb--validate-schema (type options schema)
  (let* ((ent (or (cdr (assq type edb--*schema-schema*))
                  (error "Invalid schema type: %S" type)))
         (valid-keys (mapcar (lambda (k-ent)
                               (if (consp k-ent)
                                   (car k-ent)
                                 k-ent))
                             (cdr (assq :valid-keys ent))))
         (valid-options (cdr (assq :valid-options ent))))
    ;; check plist form
    (let ((ls schema))
      (while ls
        (unless (keywordp (car ls))
          (error "Not a keyword: %S" (car ls)))
        (setq ls (cddr ls))))
    ;; check key membership
    (let ((ls schema))
      (while ls
        (unless (memq (car ls) valid-keys)
          (error "Not a valid key: %S" (car ls)))
        (setq ls (cddr ls))))
    ;; check option membership
    (let ((ls options))
      (while ls
        (unless (memq (car ls) valid-options)
          (error "Not a valid option: %S" (car ls)))
        (setq ls (cdr ls)))))
  ;; todo: other checks
  schema)

(defmacro edb--with-callable-connection (name &rest body)
  `(flet ((,name (&rest args) (apply ,name args)))
     ,@body))

(defun edb--connect (control-file)
  (let ((conn (lexical-let (V F)        ; todo: use obarray
                (lambda (command &rest args)
                  (case command
                    ;; it's not worthy of emacs if it's not extensible
                    (:V! (setq V (apply 'plist-put V args)))
                    (:F! (setq F (apply 'plist-put F args)))
                    (t (let (it)
                         (if (setq it (plist-get F command))
                             (apply it args)
                           (plist-get V command)))))))))
    (edb--with-callable-connection conn
      (with-temp-buffer
        (let (emacs-lisp-mode-hook)
          (emacs-lisp-mode))
        ;; determine schema metainfo
        (let ((reality (insert-file-contents control-file))
              meta)
          (unless (and (< 4 (cadr reality))
                       (string= ":EDB " (buffer-substring-no-properties 1 6))
                       (consp (setq meta (progn (goto-char 6)
                                                (read (current-buffer))))))
            (error "Does not seem to be an EDB control file"))
          ;; maintain lameness for the present
          (unless (equal '(single) meta)
            (error "Not lame enough: %S" meta))
          (conn :V! :schema-type (car meta))
          (conn :v! :schema-options (cdr meta))
          (delete-region (point-min) (point)))
        ;; determine schema
        (let (start kw val schema)
          (while (< (point) (point-max))
            (when (keywordp (setq start (point)
                                  kw (read (current-buffer))))
              (push kw schema)
              (setq val (read (current-buffer)))
              (if (memq kw '(:display :report :data))
                  (let* ((pls (if (eq t val)
                                  (list :name t :coding t :EOTB ":EOTB")
                                val))
                         (datap (eq :data kw))
                         (tb-start (progn (forward-line 1) (point)))
                         (name (plist-get pls :name))
                         (coding (or (plist-get pls :coding) t))
                         (EOTB (or (plist-get pls :EOTB) ":EOTB"))
                         tb-finish)
                    (unless (or
                             ;; data text blocks are anonymous
                             datap
                             (eq t name) (stringp name))
                      (error "Bad %S name: %S" kw name))
                    (unless (symbolp coding)
                      (error "Bad %S coding: %S" kw coding))
                    (unless (stringp EOTB)
                      (error "Bad %S EOTB: %S" kw EOTB))
                    (setq tb-finish (if (not (re-search-forward
                                              (concat "^" EOTB "$")
                                              (point-max) 1))
                                        (point-max)
                                      (forward-line 1)
                                      (match-beginning 0)))
                    (if datap
                        (let* ((seqr (plist-get pls :seqr))
                               (f (or (cdr (assq seqr edb--*sequential-i/o*))
                                      (error "Bad :seqr func: %S" seqr))))
                          (save-excursion
                            (goto-char tb-start)
                            (plist-put pls :records (funcall f tb-finish))))
                      (plist-put pls :text (buffer-substring-no-properties
                                            tb-start tb-finish)))
                    (if datap
                        (conn :V! (pop schema) pls)
                      (push pls schema)))
                (forward-comment 1)
                (push val schema))
              (delete-region start (point))))
          ;; normalize, validate and stash
          (conn :V! :schema (edb--validate-schema (conn :schema-type)
                                                  (conn :schema-options)
                                                  (nreverse schema))))))
    conn))

\f
;;; viewing

(require 'ewoc)

(defun FUTURE/ewoc-delete-node (ewoc node)
  (ewoc--delete-node-internal ewoc node))

(defun FUTURE/ewoc-point-min (ewoc)
  (ewoc-location (ewoc--header ewoc)))

;; (defun FUTURE/ewoc-point-max (ewoc)
;;   (let ((footer (ewoc--footer ewoc)))
;;     ;; add 1 because ewoc.el inserts a gratuitous newline, sigh.
;;     (+ (ewoc-location footer) (length (ewoc-data footer)) 1)))

(defstruct (edb--OBSERVER
            (:type vector)
            (:constructor edb--alloc-observer-struct)
            (:conc-name edb--O-))
  nick                ;; string
  ewoc                ;; see ewoc.el
  cur                 ;; "current node"; (ewoc-data CUR) => record
  nodes               ;; hash: record to node
  rlens               ;; hash: record to display length
  foc                 ;; (funcall FOC beg end)
  unf                 ;; (funcall UNF beg end)
  km                  ;; key map
  followers           ;; list of observers for motion synch
  ;; etc...
  )

(defun edb--observer-focus (observer)
  (let* ((cur (edb--O-cur observer))
         (beg (ewoc-location cur))
         (end (+ beg (gethash (ewoc-data cur) (edb--O-rlens observer))))
         (foc (edb--O-foc observer)))
    (add-text-properties beg end '(face font-lock-string-face))
    (when foc (funcall foc beg end))))

(defun edb--observer-unfocus (observer &optional node)
  (let* ((bye (or node (edb--O-cur observer)))
         (beg (ewoc-location bye))
         (end (+ beg (gethash (ewoc-data bye) (edb--O-rlens observer))))
         (unf (edb--O-unf observer)))
    (when unf (funcall unf beg end))
    (remove-text-properties beg end '(face font-lock-string-face))))

(defun edb--observer-move-to-node (observer cur node &optional already)
  (unless (eq node cur)
    (edb--observer-unfocus observer)
    (setf (edb--O-cur observer) (ewoc-goto-node (edb--O-ewoc observer) node))
    (edb--observer-focus observer))
  (push observer already)
  (let ((followers (edb--O-followers observer))
        record)
    (when followers
      (setq record (ewoc-data node))
      (dolist (f followers)
        (unless (memq f already)
          (save-excursion
            (with-current-buffer (ewoc-buffer (edb--O-ewoc f))
              (edb--observer-move-to-node
               f t (gethash record (edb--O-nodes f)) already))))))))

(defsubst edb--observer-at-point (&optional noerror)
  (or (get-text-property (point) :edb--O)
      (unless noerror
        (error "No observer here"))))

(defun edb--observer-move-prev ()
  (interactive)
  (let* ((ob (edb--observer-at-point))
         (ewoc (edb--O-ewoc ob))
         (cur (edb--O-cur ob)))
    (edb--observer-move-to-node ob cur (or (ewoc-prev ewoc cur)
                                           (ewoc-nth ewoc -1)))))

(defun edb--observer-move-next ()
  (interactive)
  (let* ((ob (edb--observer-at-point))
         (ewoc (edb--O-ewoc ob))
         (cur (edb--O-cur ob)))
    (edb--observer-move-to-node ob cur (or (ewoc-next ewoc cur)
                                           (ewoc-nth ewoc 0)))))

(defun z/SYNCHRONOUS-kill (record observers)
  (let (window pos ewoc node buf)
    (dolist (ob observers)
      (setq ewoc (edb--O-ewoc ob)
            node (gethash record (edb--O-nodes ob))
            buf (ewoc-buffer ewoc))
      (with-current-buffer buf
        ;; begin hmmm
        ;; this uses the "public interface" only, but that's lame.
        ;;-  (ewoc-filter
        ;;-   ewoc (lambda (rec)
        ;;-          (let ((zonkp (eq record rec)))
        ;;-            (when (and zonkp (eq record (ewoc-data (edb--O-cur ob))))
        ;;-              (edb--observer-move-next))
        ;;-            (not zonkp))))
        ;; this is the way it SHOULD be (ewoc.el needs to change).
        (when (eq node (edb--O-cur ob))
          (unless (and (eq node (ewoc-nth ewoc 0))
                       (not (ewoc-next ewoc node)))
            (goto-char (ewoc-location node))
            (edb--observer-move-next)))
        (FUTURE/ewoc-delete-node ewoc node)
        ;; end hmmm
        (unless (marker-buffer (setq pos (ewoc-location (edb--O-cur ob))))
          (setf (edb--O-cur ob) nil
                pos (FUTURE/ewoc-point-min ewoc)))
        (goto-char pos)
        (when (setq window (get-buffer-window buf))
          (set-window-point window pos))))))

(defun edb--make-observer (ls render nick buf manyp)
  (let* ((count (length ls))
         (map (make-sparse-keymap))
         (ob (edb--alloc-observer-struct
              :nick nick
              :nodes (make-hash-table :size count :weakness t)
              :rlens (make-hash-table :size count :weakness 'key)
              :foc (unless manyp
                     (lambda (beg end)
                       (remove-text-properties beg end '(invisible t))))
              :unf (unless manyp
                     (lambda (beg end)
                       (add-text-properties beg end '(invisible t))))
              :km map)))
    (with-current-buffer buf
      (setf (edb--O-ewoc ob)
            (ewoc-create
             (lexical-let ((render render)
                           (ob ob))
               (lambda (record)
                 (let ((start (point))
                       (s (funcall render record)))
                   (insert (propertize s 'keymap (edb--O-km ob) :edb--O ob))
                   (puthash record
                            ;; 1+ because ewoc.el inserts a
                            ;; gratuitous newline, sigh.
                            (1+ (- (point) start))
                            (edb--O-rlens ob)))))
             (format "%s %s\nTOP" (make-string 20 ?-) nick)
             "BOT"))
      ;; init
      (let ((ewoc (edb--O-ewoc ob))
            (nodes (edb--O-nodes ob))
            node)
        ;; fill ewoc
        (dolist (record ls)
          (puthash record (setq node (ewoc-enter-last ewoc record)) nodes)
          (unless manyp
            (edb--observer-unfocus ob node)))
        ;; set current
        (setf (edb--O-cur ob) (ewoc-locate ewoc))
        (ewoc-goto-node ewoc (edb--O-cur ob))
        (edb--observer-focus ob))
      ;; keymap (text property)
      (define-key map "p"                   'edb--observer-move-prev)
      (define-key map [remap previous-line] 'edb--observer-move-prev)
      (define-key map "n"                   'edb--observer-move-next)
      (define-key map [remap next-line]     'edb--observer-move-next)
      ob)))

(defstruct (edb--OBSERVER-GROUP
            (:type vector)
            (:constructor edb--alloc-observer-group-struct)
            (:conc-name edb--OG-))
  i                ;; index
  ring             ;; see ring.el
  last-point       ;; (perhaps unuseful)
  last-buffer      ;; (perhaps unuseful)
  timer            ;; set when updating observations falls behind too much
  changed          ;; hash: record to ticks
  display          ;; hash: record to ticks (perhaps unuseful)
  )

(defun edb--observer-group-enter (group p)
  (let ((ob (save-excursion (goto-char p) (edb--observer-at-point t))))
    (unless ob
      (setf (point) (next-single-char-property-change p :edb--O)
            ob (edb--observer-at-point t)))
    (when ob
      (goto-char
       (setf (edb--OG-i group) (let ((ring (edb--OG-ring group)))
                                 (do ((i 0 (1+ i)))
                                     ((eq ob (ring-ref ring i)) i)))
             (edb--OG-last-buffer group) (current-buffer)
             (edb--OG-last-point group) (ewoc-location (edb--O-cur ob)))))))

(defun edb--observer-group-redisplay (group)
  (let ((changes (edb--OG-changed group))
        nodes invs ewoc node curp)
    (dolist (ob (ring-elements (edb--OG-ring group)))
      (setq nodes (edb--O-nodes ob)
            invs nil
            curp nil)
      (maphash (lambda (record u)
                 (when (setq node (gethash record nodes))
                   (push node invs)
                   (unless curp
                     (setq curp (and (eq node (edb--O-cur ob)) node)))))
               changes)
      (when invs
        (with-current-buffer (ewoc-buffer (setq ewoc (edb--O-ewoc ob)))
          (when curp (edb--observer-unfocus ob))
          (apply 'ewoc-invalidate ewoc invs)
          (mapc (lambda (node)
                  (edb--observer-unfocus ob node))
                invs)
          (when curp (edb--observer-focus ob)))))
    (clrhash changes)))

(defun edb--observer-group-note-change (group record)
  (incf (gethash record (edb--OG-changed group) -1))
  (cond ((edb--OG-timer group))
        ((input-pending-p)
         (setf (edb--OG-timer group)
               (run-with-idle-timer
                0.1 nil (lambda (group)
                          (edb--observer-group-redisplay group)
                          (setf (edb--OG-timer group) nil))
                group)))
        (t (edb--observer-group-redisplay group))))

(defun edb--observer-group-ob-with-nick (group nick)
  (let ((ring (edb--OG-ring group))
        ob)
    (do ((i 0 (1+ i)))
        ((string= nick (edb--O-nick (setq ob (ring-ref ring i)))) ob))))

(defun edb--observer-group-move-to-next-observer (group)
  (interactive)
  (let ((ob (ring-ref (edb--OG-ring group) (incf (edb--OG-i group)))))
    (ewoc-goto-node (edb--O-ewoc ob) (edb--O-cur ob))
    (setf (edb--OG-last-buffer group) (current-buffer)
          (edb--OG-last-point group) (point))))

(defvar z/OG nil)                       ; observer group

(defun z/summary-buffer (name count
                         ;;manyp ls render name
                               )
  (with-current-buffer (get-buffer-create name)
    (buffer-disable-undo)
    (setq major-mode 'EDB2-HACK
          mode-name "EDB2 HACK"
          truncate-lines t)
    (use-local-map
     (let ((map (make-sparse-keymap)))
       (suppress-keymap map)
       (define-key map "\C-i"
         (lambda () (interactive)
           (if (edb--observer-at-point t)
               (edb--observer-group-move-to-next-observer z/OG)
             (edb--observer-group-enter z/OG (point)))))
       (define-key map "u"
         (lambda () (interactive)
           (let ((ob (edb--observer-at-point t))
                 record)
             (if (not ob)
                 (message "Use TAB to move to (and select) an observer")
               (incf (aref (setq record (ewoc-data (edb--O-cur ob))) 1))
               (edb--observer-group-note-change z/OG record)))))
       (define-key map "k"
         (lambda () (interactive)
           (let* ((ob (edb--observer-at-point t))
                  ewoc cur)
             (if (not ob)
                 (message "Use TAB to move to (and select) an observer")
               (z/SYNCHRONOUS-kill
                (ewoc-data (edb--O-cur ob))
                (ring-elements (edb--OG-ring z/OG)))
               (if (setq ewoc (edb--O-ewoc ob)
                         cur (edb--O-cur ob))
                   (ewoc-goto-node ewoc (edb--O-cur ob))
                 (goto-char (FUTURE/ewoc-point-min ewoc)))))))
       map))
    (set (make-local-variable 'z/OG)
         (edb--alloc-observer-group-struct
          :i 0
          :ring (make-ring count)
          :changed (make-hash-table :size count :weakness 'key)))
    (current-buffer)))

(defun z/add-observer (group buffer manyp ls render name)
  (with-current-buffer buffer
    (goto-char (point-min))
    (ring-insert (edb--OG-ring group)
                 (edb--make-observer ls render name buffer manyp))))

\f
;;; testing

'(defun test:edb--connect (control-file)
  (interactive "fControl file: ")
  (let ((conn (edb--connect control-file)))
    (edb--with-callable-connection conn
      (switch-to-buffer "*scratch*")
      (goto-char (point-min))
      (insert (format "\n%s %S %S\n"
                      control-file
                      (conn :schema-type)
                      (conn :schema-options)))
      (pp (conn :schema) (current-buffer))
      (pp (conn :data) (current-buffer)))))

(defun test:edb--viewing ()
  (interactive)
  (let* ((ls (mapcar (lambda (raw)
                       (vector raw -1))
                     '("lsakdjf" "sssss" "d d d" "42" "foobar" "baz"
                       "a" "b" "c" "d" "e" "f" "g")))
         (line (lambda (record)
                 (let ((magic (aref record 1)))
                   (if (> 0 magic)
                       "---"
                     (format "%3d%s\t%-8s\t%s"
                             magic
                             (if (zerop (% magic 10))
                                 "  !"
                               "")
                             (aref record 0)
                             (make-string magic ?|))))))
         (pict (lexical-let ((line line))
                 (lambda (record)
                   (if (> 6 (length (aref record 0)))
                       (funcall line record)
                     (let* ((field (mapconcat
                                    (lambda (n)
                                      (let ((sp (- 33 (/ n 2))))
                                        (concat "##"
                                                (make-string sp 32)
                                                (make-string n ?#)
                                                (make-string sp 32)
                                                "##")))
                                    '(8 16 32 64 48 32 32 16 8)
                                    "\n"))
                            (len (length field))
                            (magic (aref record 1))
                            x)
                       (when (< 0 magic)
                         (dotimes (i magic)
                           (aset field
                                 (if (= 10 (aref field (setq x (random len))))
                                     (1- x)
                                   x)
                                 ?-)))
                       (concat field " (" (aref record 0) ")"))))))
         (buf (z/summary-buffer "ooo" 6)))
    (switch-to-buffer buf)
    (z/add-observer z/OG buf   t ls pict "minus ten")
    (z/add-observer z/OG buf nil ls pict "minus one")
    (z/add-observer z/OG buf nil ls line "zero")
    (z/add-observer z/OG buf   t ls line "o1")
    (z/add-observer z/OG buf nil ls line "o2")
    (z/add-observer z/OG buf   t ls line "o3"))
  (let ((o1 (edb--observer-group-ob-with-nick z/OG "o1")))
    (setf (edb--O-followers o1) (list (edb--observer-group-ob-with-nick
                                       z/OG "o3")))
    (define-key (edb--O-km o1) " "
      (lambda () (interactive)
        (let* ((o1 (edb--observer-group-ob-with-nick z/OG "o1"))
               (o2 (edb--observer-group-ob-with-nick z/OG "o2"))
               (o3 (edb--observer-group-ob-with-nick z/OG "o3"))
               (now (case (random 5)
                      (0 nil)
                      (1 (list o2))
                      (2 (list o3))
                      (3 (list o2 o3))
                      (4 (list o3 o2)))))
          (setf (edb--O-followers o1) now)
          (message "%s followers now: %s"
                   (edb--O-nick o1)
                   (if now
                       (mapconcat 'edb--O-nick now " AND ")
                     "(none)")))))))

;;; ttn-sez: local-vars-block-zonkable
;;; Local Variables:
;;; auto-save-default: nil
;;; make-backup-files: nil
;;; End:

;;; edb.el ends here

Re: lists.texi

[Juri Linkov]

> Apparently these timings are not very fixed.  In a freshly started
> Emacs, my proposed version took 12 seconds (instead of earlier 23) and
> the abstract versions 40 seconds (instead of 51).  This gives a
> mysterious gain of 11 seconds for both.  But now my proposed version
> runs 3.33 times faster than the abstract ones, instead of earlier 2.2.

I noticed too that in sufficiently long Emacs sessions Lisp evaluation
slows down.

-- 
Juri Linkov
http://www.jurta.org/emacs/

Re: lists.texi

[Luc Teirlinck]

Eli Zaretskii wrote:

   One possible situation where this could happen is if you customize
   gc-cons-threshold to a large number.

I have:

gc-cons-threshold: Hide Value 400000
   State: STANDARD.

Sincerely,

Luc.

Re: lists.texi

[Eli Zaretskii]

> From: Juri Linkov <juri@jurta.org>
> Date: Wed, 22 Jun 2005 19:28:55 +0300
> Cc: ttn@gnu.org, emacs-devel@gnu.org
> 
> > Apparently these timings are not very fixed.  In a freshly started
> > Emacs, my proposed version took 12 seconds (instead of earlier 23) and
> > the abstract versions 40 seconds (instead of 51).  This gives a
> > mysterious gain of 11 seconds for both.  But now my proposed version
> > runs 3.33 times faster than the abstract ones, instead of earlier 2.2.
> 
> I noticed too that in sufficiently long Emacs sessions Lisp evaluation
> slows down.

One possible situation where this could happen is if you customize
gc-cons-threshold to a large number.

Re: lists.texi

[Luc Teirlinck]

My test case constructed ten thousand times a list of size 1000,
triggering a lot of garbage collections.  In a freshly started Emacs,
the ring-elements function I propose to install ran the test in 11
seconds, slightly over 5 being spent in gc.  This gives between 5 and
6 for the function itself.  The "abstract" version ran 37 seconds, a
little bit over 5 in gc, giving 31 to 32 for the function itself.  In
other words, avoiding the `ring-ref' overhead makes the function run
more than five times faster, but the amount of consing stays the same.

If I run the same test in a somewhat older Emacs, the functions
themselves still take 5 to 6 and 31 to 32 seconds, but now they both
spend 17.5 seconds doing gc (instead of slightly more than 5).

I guess that in a really big Emacs, gc will take even much longer.  It
is not very surprising that the more objects gc has to check, the
longer it takes.  I believe this pretty much explains the gradual
slowdown of Emacs as it grows older (and hence bigger).

Sincerely,

Luc.

Re: lists.texi

[Richard M. Stallman]

    I guess that in a really big Emacs, gc will take even much longer.  It
    is not very surprising that the more objects gc has to check, the
    longer it takes.  I believe this pretty much explains the gradual
    slowdown of Emacs as it grows older (and hence bigger).

Thanks for demonstrating that only GC is slowing down.

GC (was: lists.texi)

[Juri Linkov]

> My test case constructed ten thousand times a list of size 1000,
> triggering a lot of garbage collections.  In a freshly started Emacs,
> the ring-elements function I propose to install ran the test in 11
> seconds, slightly over 5 being spent in gc.  This gives between 5 and
> 6 for the function itself.  The "abstract" version ran 37 seconds, a
> little bit over 5 in gc, giving 31 to 32 for the function itself.  In
> other words, avoiding the `ring-ref' overhead makes the function run
> more than five times faster, but the amount of consing stays the same.
>
> If I run the same test in a somewhat older Emacs, the functions
> themselves still take 5 to 6 and 31 to 32 seconds, but now they both
> spend 17.5 seconds doing gc (instead of slightly more than 5).
>
> I guess that in a really big Emacs, gc will take even much longer.  It
> is not very surprising that the more objects gc has to check, the
> longer it takes.  I believe this pretty much explains the gradual
> slowdown of Emacs as it grows older (and hence bigger).

Yes, indeed GC is what causes the slowdown.  With the option
`garbage-collection-messages' set to t, it is clearly visible that in
a big Emacs session GC takes too much time.  For example, I can see
that each GC takes about 1 sec.  The formula (/ gc-elapsed gcs-done)
with real values (/ 1788.2 1597) gives 1.12 sec.  This is substantial
time for every GC to contribute to the overall slowdown.

-- 
Juri Linkov
http://www.jurta.org/emacs/

GC (was: lists.texi)

[Juri Linkov]

>> I noticed too that in sufficiently long Emacs sessions Lisp
>> evaluation slows down.
>
> One possible situation where this could happen is if you customize
> gc-cons-threshold to a large number.

Do you actually mean gc-cons-threshold customized to a *small* number?
(or not customized at all since the default is quite a small number)

In Emacs sessions with lots of Lisp objects every GC takes too much time.
With the default value of `gc-cons-threshold' (or a smaller number) such
slow GC running too often causes the slowdown of many normal operations
(some of which even run GC several times during one Emacs command).
It helps to increase the value of gc-cons-threshold at least tenfolds
to run slow GC less often.

(Maybe the value of `gc-cons-threshold' should grow gradually with the
size of allocated Lisp data?  The reason is that users allowing Emacs
to grow to a large size can accept a large value of gc-cons-threshold.)

Anyway, it would be good to mention this problem in the elisp manual.
Currently it suggests increasing `gc-cons-threshold' for a program
that creates lots of Lisp data.  There are too many such Emacs
packages, so this advice is not very useful.  In addition to this
problem, the manual could also mention the problem of GC duration
increasing with the size of allocated Lisp objects.  The advice
for this problem could be the same: to set `gc-cons-threshold' to
a larger value.

-- 
Juri Linkov
http://www.jurta.org/emacs/

Re: GC (was: lists.texi)

[Eli Zaretskii]

> From: Juri Linkov <juri@jurta.org>
> Cc: teirllm@dms.auburn.edu, ttn@gnu.org, emacs-devel@gnu.org
> Date: Fri, 24 Jun 2005 22:02:52 +0300
> 
> >> I noticed too that in sufficiently long Emacs sessions Lisp
> >> evaluation slows down.
> >
> > One possible situation where this could happen is if you customize
> > gc-cons-threshold to a large number.
> 
> Do you actually mean gc-cons-threshold customized to a *small* number?

No, I meant what I wrote.

> It helps to increase the value of gc-cons-threshold at least tenfolds
> to run slow GC less often.

Yes, but then Emacs itself slows down, and when GC eventually happens,
it, too, takes a very long time.

I used to run with gc-cons-threshold customized to a very large value,
but stopped doing that, since the advantages were far too minor and
disadvantages far too annoying.

> Anyway, it would be good to mention this problem in the elisp manual.

You mean, user's manual, right?  This has nothing to do with Lisp
programming, it's a usage issue.

> Currently it suggests increasing `gc-cons-threshold' for a program
> that creates lots of Lisp data.  There are too many such Emacs
> packages

As long as ``lots of Lisp data'' isn't defined in some quantitative
terms, one cannot claim that ``too many Emacs packages'' do this.

> In addition to this problem, the manual could also mention the
> problem of GC duration increasing with the size of allocated Lisp
> objects.

Isn't it obvious that GC, at least its mark phase, is approximately
linear in the number of live Lisp objects?

> The advice for this problem could be the same: to set
> `gc-cons-threshold' to a larger value.

Based on my experience, I would object to such advice.

Re: GC (was: lists.texi)

[Juri Linkov]

>> It helps to increase the value of gc-cons-threshold at least tenfolds
>> to run slow GC less often.
>
> Yes, but then Emacs itself slows down, and when GC eventually
> happens, it, too, takes a very long time.

In my tests, when I have the default gc-cons-threshold set to 400000,
GC takes 1 sec.  When I increase it 100 times to 40000000, GC takes
the same 1 sec (and not 100 sec as if there were linear dependence).
And there is no slowdown.

> I used to run with gc-cons-threshold customized to a very large value,
> but stopped doing that, since the advantages were far too minor and
> disadvantages far too annoying.

Could you tell all disadvantages? (except of obvious one of memory use
which users with large memory can tolerate).

>> Anyway, it would be good to mention this problem in the elisp manual.
>
> You mean, user's manual, right?  This has nothing to do with Lisp
> programming, it's a usage issue.

No.  `gc-cons-threshold' and advice for its usage are documented in
the Emacs Lisp reference manual.  I don't object to documenting it
in the user's manual as well.

>> Currently it suggests increasing `gc-cons-threshold' for a program
>> that creates lots of Lisp data.  There are too many such Emacs
>> packages
>
> As long as ``lots of Lisp data'' isn't defined in some quantitative
> terms, one cannot claim that ``too many Emacs packages'' do this.

In quantitative terms ``lots of Lisp data'' could mean the default
value of `gc-cons-threshold'.  Then ``too many Emacs packages'' means
that with garbage-collection-messages equal to t, many Emacs commands
display the ``Garbage collecting...'' message.

>> In addition to this problem, the manual could also mention the
>> problem of GC duration increasing with the size of allocated Lisp
>> objects.
>
> Isn't it obvious that GC, at least its mark phase, is approximately
> linear in the number of live Lisp objects?

Yes, GC is linear in the number of *live* Lisp objects, but not garbage.
IIUC, the number of live objects GC traverses doesn't depend on the
value of `gc-cons-threshold'.

>> The advice for this problem could be the same: to set
>> `gc-cons-threshold' to a larger value.
>
> Based on my experience, I would object to such advice.

Your advice to look at `gc-cons-threshold' helped me enormously.
Now with a large value of `gc-cons-threshold' I have no slowdown
anymore.  It would be good to share this information with other
Emacs users by mentioning it in the documentation.

-- 
Juri Linkov
http://www.jurta.org/emacs/

Re: GC (was: lists.texi)

[Luc Teirlinck]

Juri Linkov wrote:

   In my tests, when I have the default gc-cons-threshold set to 400000,
   GC takes 1 sec.  When I increase it 100 times to 40000000, GC takes
   the same 1 sec (and not 100 sec as if there were linear dependence).
   And there is no slowdown.

Increasing gc-cons-threshold by a factor of 10 to 4M indeed produced a
marked speedup in my artificial tests.  My machine is too fast to
notice slowness problems due to CPU usage during actual Emacs use,
except in the case of outright bugs.

   Could you tell all disadvantages? (except of obvious one of memory use
   which users with large memory can tolerate).

Well, obviously if you have very little resident memory and set
gc-cons-threshold to a huge value, then conceivably your operating
system could wind up spending most of its time swapping memory.  Then
not only Emacs, but everything else as well, will become slow.  I do
not know whether that is what Eli is referring too.  Certainly, if you
have a reasonable amount of resident memory, increasing
gc-cons-threshold to 4M should not create any such problems and it
does speed up things.

Sincerely,

Luc.

Re: GC (was: lists.texi)

[Miles Bader]

On 6/25/05, Luc Teirlinck <teirllm@dms.auburn.edu> wrote:
> Well, obviously if you have very little resident memory and set
> gc-cons-threshold to a huge value, then conceivably your operating
> system could wind up spending most of its time swapping memory.  Then
> not only Emacs, but everything else as well, will become slow.  I do
> not know whether that is what Eli is referring too.  Certainly, if you
> have a reasonable amount of resident memory, increasing
> gc-cons-threshold to 4M should not create any such problems and it
> does speed up things.

It's certainly the case that most machines these days have vastly more
memory than even a few years ago.  For developers I think a practical
minimum is 512MB, for less demanding users, maybe 256MB (if you buy a
low-end budget computer, this is typically the amount of RAM it comes
with) -- but a 4MB gc threshold looks like nothing compared to either
one, and the current default (400KB) looks downright silly.

I also think OS memory management is much better these days, which
likewise suggests increasing the default limit.

-Miles
-- 
Do not taunt Happy Fun Ball.

Re: GC (was: lists.texi)

[Eli Zaretskii]

> From: Juri Linkov <juri@jurta.org>
> Cc: teirllm@dms.auburn.edu, ttn@gnu.org, emacs-devel@gnu.org
> Date: Sat, 25 Jun 2005 00:54:05 +0300
> 
> >> It helps to increase the value of gc-cons-threshold at least tenfolds
> >> to run slow GC less often.
> >
> > Yes, but then Emacs itself slows down, and when GC eventually
> > happens, it, too, takes a very long time.
> 
> In my tests, when I have the default gc-cons-threshold set to 400000,
> GC takes 1 sec.  When I increase it 100 times to 40000000, GC takes
> the same 1 sec (and not 100 sec as if there were linear dependence).
> And there is no slowdown.

I'm sorry to say, but you are just retracing my experience from years
ago.  I used to have gc-cons-threshold enlarged to 8MB, and at first
it looked like a wonderful idea, exactly as you say now.  But with
time, I liked the effects less and less, and eventually started using
the default values, which I do to this day.

> Could you tell all disadvantages? (except of obvious one of memory use
> which users with large memory can tolerate).

It turned out to be very slow in certain cases.  Unfortunately, I no
longer remember the details, but please keep in mind that your
observation of GC taking the same time no matter what could be true
only for certain patterns of consing.

It's possible, like Miles says, that my experience dates back to
machines which had 64 or 128MB of memory, and it is no longer relevant
nowadays (although 8MB compared to 128 is still a rather small
percentage).  But still, I would not recommend changing the default
setting without having several developers on several different
platforms run with the enlarged threshold for some prolonged period of
time.

> >> Currently it suggests increasing `gc-cons-threshold' for a program
> >> that creates lots of Lisp data.  There are too many such Emacs
> >> packages
> >
> > As long as ``lots of Lisp data'' isn't defined in some quantitative
> > terms, one cannot claim that ``too many Emacs packages'' do this.
> 
> In quantitative terms ``lots of Lisp data'' could mean the default
> value of `gc-cons-threshold'.  Then ``too many Emacs packages'' means
> that with garbage-collection-messages equal to t, many Emacs commands
> display the ``Garbage collecting...'' message.

(I always run with garbage-collection-messages set to t.)  The fact
that the message about GC is displayed might be evidence to what you
think, but then again it might not: IIRC, Emacs always does a GC
before it asks the OS for more heap.  So you might see the message
even if the total size of objects consed since last GC didn't cross
the threshold.  For example, if a package needs a large buffer, and
there's not enough contiguous memory in the pool Emacs maintains, I
think Emacs will GC even if the consing threshold was not crossed.

> >> The advice for this problem could be the same: to set
> >> `gc-cons-threshold' to a larger value.
> >
> > Based on my experience, I would object to such advice.
> 
> Your advice to look at `gc-cons-threshold' helped me enormously.
> Now with a large value of `gc-cons-threshold' I have no slowdown
> anymore.  It would be good to share this information with other
> Emacs users by mentioning it in the documentation.

If we find that my experience of yore is no longer relevant, I agree.
But then we should probably modify the default of the threshold
accordingly, instead of telling users to mess with it.  For example,
the default value could be dependent on the amount of installed
memory.

Re: GC

[Adrian Aichner]

Eli Zaretskii <eliz@gnu.org> writes:

> If we find that my experience of yore is no longer relevant, I agree.
> But then we should probably modify the default of the threshold
> accordingly, instead of telling users to mess with it.  For example,
> the default value could be dependent on the amount of installed
> memory.

Hi Eli,

isn't that the purpose of
gc-cons-percentage
?

-- 
Adrian Aichner
 mailto:adrian@xemacs.org
 http://www.xemacs.org/

Re: GC (was: lists.texi)

[Miles Bader]

On 6/25/05, Eli Zaretskii <eliz@gnu.org> wrote:
> If we find that my experience of yore is no longer relevant, I agree.
> But then we should probably modify the default of the threshold
> accordingly, instead of telling users to mess with it.  For example,
> the default value could be dependent on the amount of installed
> memory.

Yes I think that would be a good idea.  Setting the cons-threshold to
say 1 or 2% of RAM size would yield roughly the numbers which are
being recommended (at 1%, you'd get 640K on a 64MB system, and 5MB on
a 512MB system).

Getting that number is system-dependent of course, but there seems no
reason not to do it on systems where someone wants to write the code
(it can even be done in lisp on linux, by reading /proc/meminfo).

-Miles
-- 
Do not taunt Happy Fun Ball.

Re: GC

[Miles Bader]

On 6/25/05, Adrian Aichner <adrian@xemacs.org> wrote:
> > For example,
> > the default value could be dependent on the amount of installed
> > memory.
> 
> isn't that the purpose of
> gc-cons-percentage

There is no such variable in Emacs.

-Miles
-- 
Do not taunt Happy Fun Ball.

Re: GC

[Gaëtan LEURENT]

Miles Bader wrote on 25 Jun 2005 14:15:19 +0200:

> Yes I think that would be a good idea.  Setting the cons-threshold to
> say 1 or 2% of RAM size would yield roughly the numbers which are
> being recommended (at 1%, you'd get 640K on a 64MB system, and 5MB on
> a 512MB system).

This is maybe not a good idea for people who runs emacs on a big server
with a lot a memory and a lot of users (my emacs is running on a server
with 8Gb of RAM -- 66 users are currently using it --, but wasting 80Mo
between each GC doesn't seem very smart)

-- 
Gaëtan LEURENT

Re: GC (was: lists.texi)

[Eli Zaretskii]

> Date: Sat, 25 Jun 2005 21:15:19 +0900
> From: Miles Bader <snogglethorpe@gmail.com>
> Cc: Juri Linkov <juri@jurta.org>, emacs-devel@gnu.org
> 
> Getting that number is system-dependent of course, but there seems no
> reason not to do it on systems where someone wants to write the code
> (it can even be done in lisp on linux, by reading /proc/meminfo).

I'd say we should add a primitive to get the amount of available
memory.

Re: GC

[Eli Zaretskii]

> Cc: miles@gnu.org, Eli Zaretskii <eliz@gnu.org>, Juri Linkov <juri@jurta.org>,
>         emacs-devel@gnu.org
> From: gaetan.leurent@ens.fr (=?iso-8859-1?Q?Ga=EBtan?= LEURENT)
> Date: Sat, 25 Jun 2005 15:10:49 +0200
> 
> 
> Miles Bader wrote on 25 Jun 2005 14:15:19 +0200:
> 
> > Yes I think that would be a good idea.  Setting the cons-threshold to
> > say 1 or 2% of RAM size would yield roughly the numbers which are
> > being recommended (at 1%, you'd get 640K on a 64MB system, and 5MB on
> > a 512MB system).
> 
> This is maybe not a good idea for people who runs emacs on a big server
> with a lot a memory and a lot of users

The threshold will still be customizable.  Defaults are for the
frequent situations, they aren't supposed to cover all of them.

> (my emacs is running on a server
> with 8Gb of RAM -- 66 users are currently using it --, but wasting 80Mo
> between each GC doesn't seem very smart)

The default value of the GC threshold should probably be limited
anyway, using a fixed percent on large systems might hit some quota,
and even if it doesn't, it's not a good idea to have it grow linearly.

Re: GC (was: lists.texi)

[Richard M. Stallman]

    Yes I think that would be a good idea.  Setting the cons-threshold to
    say 1 or 2% of RAM size would yield roughly the numbers which are
    being recommended (at 1%, you'd get 640K on a 64MB system, and 5MB on
    a 512MB system).

    Getting that number is system-dependent of course, but there seems no
    reason not to do it on systems where someone wants to write the code
    (it can even be done in lisp on [GNU/]linux, by reading /proc/meminfo).

If you'd like to implement this, please go ahead.

    This is maybe not a good idea for people who runs emacs on a big server
    with a lot a memory and a lot of users (my emacs is running on a server
    with 8Gb of RAM -- 66 users are currently using it --, but wasting 80Mo
    between each GC doesn't seem very smart)

We could put a cap on the default made this way, of no more
than 10mb, say.  Or we could use a function that tapers off.

Re: GC

[Adrian Aichner]

Miles Bader <snogglethorpe@gmail.com> writes:

> On 6/25/05, Adrian Aichner <adrian@xemacs.org> wrote:
>> > For example,
>> > the default value could be dependent on the amount of installed
>> > memory.
>> 
>> isn't that the purpose of
>> gc-cons-percentage
>
> There is no such variable in Emacs.

Oh, so it's a XEmacs-only thing.

I am runing with gc-cons-percentage 0, disabling the feature, so I
can't really comment.

Just wanted to point out such a thing exists.

Adrian

>
> -Miles

-- 
Adrian Aichner
 mailto:adrian@xemacs.org
 http://www.xemacs.org/

Re: GC

[Miles Bader]

On 6/26/05, Adrian Aichner <adrian@xemacs.org> wrote:
> >> isn't that the purpose of
> >> gc-cons-percentage
> >
> > There is no such variable in Emacs.
> 
> Oh, so it's a XEmacs-only thing.

OK; guess if we add this feature, we should use the same variable name though.

As Gaëtan Leurent pointed out, it's also a good idea to apply min/max
bounds to the calculated value, to handle extreme cases; what does
xemacs do about that?

[I'm thinking a minimum of say the current default (400K), and a max
of oh, 8MB.]

-Miles
-- 
Do not taunt Happy Fun Ball.

Re: GC

[Adrian Aichner]

Miles Bader <snogglethorpe@gmail.com> writes:

> On 6/26/05, Adrian Aichner <adrian@xemacs.org> wrote:
>> >> isn't that the purpose of
>> >> gc-cons-percentage
>> >
>> > There is no such variable in Emacs.
>> 
>> Oh, so it's a XEmacs-only thing.
>
> OK; guess if we add this feature, we should use the same variable
> name though.
>
> As Gaëtan Leurent pointed out, it's also a good idea to apply min/max
> bounds to the calculated value, to handle extreme cases; what does
> xemacs do about that?

Oops, this feature not currently enabled in XEmacs!

See recompute_need_to_garbage_collect in alloc.c.

Here is its documentation from the trunk version of alloc.c anyway:

  DEFVAR_INT ("gc-cons-percentage", &gc_cons_percentage /*
*Percentage of memory allocated between garbage collections.

Garbage collection will happen if this percentage of the total amount of
memory used for data has been allocated since the last garbage collection.
However, it will not happen if less than `gc-cons-threshold' bytes have
been allocated -- this sets an absolute minimum in case very little data
has been allocated or the percentage is set very low.  Set this to 0 to
have garbage collection always happen after `gc-cons-threshold' bytes have
been allocated, regardless of current memory usage.

Garbage collection happens automatically when `eval' or `funcall' are
called.  (Note that `funcall' is called implicitly as part of evaluation.)
By binding this temporarily to a large number, you can effectively
prevent garbage collection during a part of the program.

See also `consing-since-gc'.
*/ );

So, gc-cons-threshold serves as the lower bound, and
gc-cons-percentage itself is the upper.

Adrian

>
> [I'm thinking a minimum of say the current default (400K), and a max
> of oh, 8MB.]
>
> -Miles

-- 
Adrian Aichner
 mailto:adrian@xemacs.org
 http://www.xemacs.org/

Re: GC

[Eli Zaretskii]

> From: Adrian Aichner <adrian@xemacs.org>
> Date: Sun, 26 Jun 2005 10:20:52 +0200
> Cc: Adrian Aichner <adrian@xemacs.org>, emacs-devel@gnu.org, miles@gnu.org
> 
> Oops, this feature not currently enabled in XEmacs!

To say nothing of the fact that it has a semantics different from what
we thought to implement:

> Garbage collection will happen if this percentage of the total amount of
> memory used for data has been allocated since the last garbage collection.
  ^^^^^^^^^^^^^^^^^^^^
We talked about a percentage of the installed physical memory, not of
memory used for data.

Re: GC

[Richard M. Stallman]

    So, gc-cons-threshold serves as the lower bound, and
    gc-cons-percentage itself is the upper.

I think I see a misunderstanding here about the meaning of upper
limit.  This doc string does not suggest there is any upper limit.

We could implement this feature, and add our own upper limit,
perhaps called gc-cons-max-threshold.

Re: GC

[Juri Linkov]

> To say nothing of the fact that it has a semantics different from what
> we thought to implement:
>
>> Garbage collection will happen if this percentage of the total amount of
>> memory used for data has been allocated since the last garbage collection.
>   ^^^^^^^^^^^^^^^^^^^^
> We talked about a percentage of the installed physical memory, not of
> memory used for data.

The semantics used by xemacs seems reasonable.  The speed of GC
depends on memory used for Lisp data, not on the total physical memory.
With the growth of Lisp data, GC becomes more slow, so it makes sense
to automatically increase the threshold to run GC less often.  Also this
percentage will work well for servers with large memory where users
will have the threshold proportional to used Lisp data memory.

-- 
Juri Linkov
http://www.jurta.org/emacs/

Re: GC

[Richard M. Stallman]

    > Garbage collection will happen if this percentage of the total amount of
    > memory used for data has been allocated since the last garbage collection.
      ^^^^^^^^^^^^^^^^^^^^
    We talked about a percentage of the installed physical memory, not of
    memory used for data.

I did not notice that difference before.  Over a long Emacs session,
it may not make much difference which one we do.  However, their
formula may avoid the need for the artificial upper bound that we were
talking about.

Re: GC

[Stefan Monnier]

> think, but then again it might not: IIRC, Emacs always does a GC
> before it asks the OS for more heap.  So you might see the message

I don't think this is true.  GC should only ever be called from eval
or funcall.  Several parts of the code assume that Fcons cannot call the GC,
for example.

In any case, here is my understanding of the situation:

The time taken by a single GC is roughly proportional to the total
(live+dead) heap size: the mark phase is proportional to the live-data size,
but the subsequent sweep phase is proportional to the total heap size.

Total heap size at the time of a GC is roughly equal to live-data +
gc-cons-threshold + unused-allocated.  The unused-allocated part of the
memory is basically due to fragmentation.

The frequency of GC is inversely proportional to gc-cons-threshold.
So the total portion of time used up by GC (the GC-overhead) is basically
proportional to:

   live-data + gc-cons-threshold + fragmentation
   ---------------------------------------------
               gc-cons-threshold

with a fixed gc-cons-threshold (as we have now), this boils down to

     live-data + fragmentation
     ------------------------- + 1
         gc-cons-threshold

So the GC-overhead currently grows with the live-data and with the
fragmentation.  This is one of the reasons why with a large heap, Emacs
tends to slow down.

Looking at the above equation one might think "let's bump gc-cons-threshold
way up" to make GC much cheaper.  The problem with it is that it tends to
increase fragmentation by delaying the reclaiming of memory (most serious
studies of memory fragmentation with non-moving memory allocator indicate
that an important factor to reduce fragmentation is prompt reclamation of
memory).

Making gc-cons-threshold proportional to the installed RAM sounds like a bad
idea to me: it's bound to be too small for some cases and much too large
for others.

The normal way to keep GC-overhead under control is to grow
gc-cons-threshold together with the heap size, such that the GC-overhead
stays constant (by making GCs less frequent when they get more
time-consuming).  Of course this may not always be best because by growing
gc-cons-threshold we may increase fragmentation, but "the best" is simply
not doable (not with a simple mark&sweep anyway).

I'd had already suggested a change to grow gc-cons-threshold as the heap
grows (a long time ago), and I see that XEmacs's gc-cons-percentage is
clean interface to such a feature.  I think we should introduce this
variable and give it a good non-zero default value.


        Stefan

Re: GC

[Richard M. Stallman]

    I'd had already suggested a change to grow gc-cons-threshold as the heap
    grows (a long time ago), and I see that XEmacs's gc-cons-percentage is
    clean interface to such a feature.  I think we should introduce this
    variable and give it a good non-zero default value.

I agree.  Would you like to do it?

Re: GC

[Stefan Monnier]

>>>>> "Richard" == Richard M Stallman <rms@gnu.org> writes:

>     I'd had already suggested a change to grow gc-cons-threshold as the heap
>     grows (a long time ago), and I see that XEmacs's gc-cons-percentage is
>     clean interface to such a feature.  I think we should introduce this
>     variable and give it a good non-zero default value.

> I agree.  Would you like to do it?

How 'bout the patch below.
It sets the default value to 0.1 (i.e. 10%), which means that the current
400KB threshold (on 32 bit systems) is used until the heap grows to 4MB.
A 4MB heap is not enormous, but it's not small either (my one week old
running Emacs process with 14 frames and 30 buffers has a heap of about
6MB).  This notion of "heap size" is not exactly what you'd expect (it
ignores buffers and a few other such things) but it reflects fairly well the
part of the heap that the GC actually cares about.


        Stefan


--- orig/src/alloc.c
+++ mod/src/alloc.c
@@ -180,6 +180,8 @@
 /* Number of bytes of consing since GC before another GC should be done. */
 
 EMACS_INT gc_cons_threshold;
+static EMACS_INT gc_cons_min_threshold;
+static Lisp_Object Vgc_cons_percentage;
 
 /* Nonzero during GC.  */
 
@@ -4966,8 +4968,29 @@
   gc_in_progress = 0;
 
   consing_since_gc = 0;
-  if (gc_cons_threshold < 10000)
-    gc_cons_threshold = 10000;
+  if (gc_cons_min_threshold < 10000)
+    gc_cons_min_threshold = 10000;
+
+  gc_cons_threshold = gc_cons_min_threshold;
+
+  if (FLOATP (Vgc_cons_percentage))
+    { /* Set gc_cons_threshold.  */
+      EMACS_INT total = 0;
+      EMACS_INT threshold;
+      total += total_conses  * sizeof (struct Lisp_Cons);
+      total += total_symbols * sizeof (struct Lisp_Symbol);
+      total += total_markers * sizeof (union Lisp_Misc);
+      total += total_string_size;
+      total += total_vectors * sizeof (struct Lisp_Vector);
+      total += total_vector_size * sizeof (Lisp_Object);
+      total += total_floats  * sizeof (struct Lisp_Float);
+      total += total_intervals * sizeof (struct interval);
+      total += total_strings * sizeof (struct Lisp_String);
+      
+      threshold = total * XFLOAT_DATA (Vgc_cons_percentage);
+      if (threshold > gc_cons_threshold)
+	gc_cons_threshold = threshold;
+    }
 
   if (garbage_collection_messages)
     {
@@ -6087,7 +6110,7 @@
   byte_stack_list = 0;
   staticidx = 0;
   consing_since_gc = 0;
-  gc_cons_threshold = 100000 * sizeof (Lisp_Object);
+  gc_cons_min_threshold = 100000 * sizeof (Lisp_Object);
 #ifdef VIRT_ADDR_VARIES
   malloc_sbrk_unused = 1<<22;	/* A large number */
   malloc_sbrk_used = 100000;	/* as reasonable as any number */
@@ -6124,7 +6147,7 @@
 void
 syms_of_alloc ()
 {
-  DEFVAR_INT ("gc-cons-threshold", &gc_cons_threshold,
+  DEFVAR_INT ("gc-cons-threshold", &gc_cons_min_threshold,
 	      doc: /* *Number of bytes of consing between garbage collections.
 Garbage collection can happen automatically once this many bytes have been
 allocated since the last garbage collection.  All data types count.
@@ -6132,7 +6155,15 @@
 Garbage collection happens automatically only when `eval' is called.
 
 By binding this temporarily to a large number, you can effectively
-prevent garbage collection during a part of the program.  */);
+prevent garbage collection during a part of the program.
+See also `gc-cons-percentage'.  */);
+
+  DEFVAR_LISP ("gc-cons-percentage", &Vgc_cons_percentage,
+	       doc: /* *Portion of the heap used for allocation.
+Garbage collection can happen automatically once this portion of the heap
+has been allocated since the last garbage collection.
+If this portion is smaller than `gc-cons-threshold', this is ignored.  */);
+  Vgc_cons_percentage = make_float (0.1);
 
   DEFVAR_INT ("pure-bytes-used", &pure_bytes_used,
 	      doc: /* Number of bytes of sharable Lisp data allocated so far.  */);