What does all-completions with COLLECTION == obarray return?

What does all-completions with COLLECTION == obarray return?

[Michael Heerdegen]

Hello,

in emacs -Q,

(cons
 (length obarray)
 (length (all-completions "" obarray)))

    ==> (1511 . 15039)

I don't understand why the second value is so much larger than the
first.  I would expect as many completions as interned symbols.


Some background:

In helm, we've found a really weird bug.  If you repeatedly evaluate,
with helm-mode on, the following:

--8<---------------cut here---------------start------------->8---
(let* ((hi-lock-face-defaults
        (list
         "hi-yellow"
         "hi-pink"
         "hi-green"
         "hi-blue"
         "hi-black-b"
         "hi-blue-b"
         "hi-red-b"
         "hi-green-b"
         "hi-black-hb")))
  (completing-read
   (format "Highlight using face (default %s): "
           (car hi-lock-face-defaults))
   (all-completions "" obarray)
   'facep t nil 'face-name-history hi-lock-face-defaults))
--8<---------------cut here---------------end--------------->8---

(just say C-g at each prompt), after ten or so iterations, it gets slow,
every time it takes twice as long as before until the prompt appears.
Soon it gets completely unusable freezing Emacs for a minute.

I debugged this and found out that after performing this test,
(all-completions "" obarray) does return a list with ~ a million
elements.  Since we use all-completions to create a candidate list for
completion, we have a million candidates then, and this is what makes
Helm slow.

(length (all-completions "" obarray)) seems to grow exponentially for
every iteration of the above code, but obarray remains constant in size.

What could be happening here?


Thanks,

Michael.

Re: What does all-completions with COLLECTION == obarray return?

[Stefan Monnier]

>  (length obarray)

Doesn't do what you think.  An obarray is a vector, and this just
returns the number of buckets in the hash-table.

Check "grep 1511 src/*.[ch]".


        Stefan

Re: What does all-completions with COLLECTION == obarray return?

[Michael Heerdegen]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> >  (length obarray)
>
> Doesn't do what you think.  An obarray is a vector, and this just
> returns the number of buckets in the hash-table.

Thanks, my imagination of obarray was indeed wrong.

I continued debugging, and found out that when following the recipe in
helm I posted, the obarray seems to be filled with more and more symbols
- with only a few names.

I wrote this test function:

--8<---------------cut here---------------start------------->8---
(defun my-find-doubles ()
  (let ((table (make-hash-table :size 65000 :test #'equal)))
    (mapatoms (lambda (symbol) (if (gethash (symbol-name symbol) table)
                              (message "%S" (symbol-name symbol))
                            (puthash (symbol-name symbol) t table))))))
--8<---------------cut here---------------end--------------->8---

I would expect that whenever it gets called, it produces no output.

Before running the recipe, it indeed prints nothing.  But after the
first time:

"Bahá'í Date"
"Insert Bahá'í"
"…"

These three symbol names all include non-ascii chars, sorry if they
should have been posted incorrectly.

The effect seems to be exponential or worse, soon I see:


"Bahá'í Date" [8191 times]
"Insert Bahá'í" [8191 times]
"…" [8191 times]

after a few more trials.

What could be happening here?


Thanks,

Michael.

Re: What does all-completions with COLLECTION == obarray return?

[Stefan Monnier]

> I continued debugging, and found out that when following the recipe in
> helm I posted, the obarray seems to be filled with more and more symbols
> - with only a few names.

The recipe seems to do something nasty to the obarray.  But I don't
recall seeing this recipe.  Could you resend it?


        Stefan

Re: What does all-completions with COLLECTION == obarray return?

[Michael Heerdegen]

Stefan Monnier <monnier@IRO.UMontreal.CA> writes:

> The recipe seems to do something nasty to the obarray.  But I don't
> recall seeing this recipe.  Could you resend it?

It was just this:

--8<---------------cut here---------------start------------->8---
(let* ((hi-lock-face-defaults
        (list
         "hi-yellow"
         "hi-pink"
         "hi-green"
         "hi-blue"
         "hi-black-b"
         "hi-blue-b"
         "hi-red-b"
         "hi-green-b"
         "hi-black-hb")))
  (completing-read
   (format "Highlight using face (default %s): "
           (car hi-lock-face-defaults))
   (all-completions "" obarray)
   'facep t nil 'face-name-history hi-lock-face-defaults))
--8<---------------cut here---------------end--------------->8---

with helm-mode on.

AFAICT we don't try to manipulate obarray directly (of course).  What
nasty things could we be doing?


Thanks,

Michael.

Re: What does all-completions with COLLECTION == obarray return?

[Stefan Monnier]

>> The recipe seems to do something nasty to the obarray.  But I don't
>> recall seeing this recipe.  Could you resend it?

> It was just this:

> --8<---------------cut here---------------start------------->8---
> (let* ((hi-lock-face-defaults
>         (list
>          "hi-yellow"
>          "hi-pink"
>          "hi-green"
>          "hi-blue"
>          "hi-black-b"
>          "hi-blue-b"
>          "hi-red-b"
>          "hi-green-b"
>          "hi-black-hb")))
>   (completing-read
>    (format "Highlight using face (default %s): "
>            (car hi-lock-face-defaults))
>    (all-completions "" obarray)
>    'facep t nil 'face-name-history hi-lock-face-defaults))
> --8<---------------cut here---------------end--------------->8---

This code looks OK (though I'd pass obarray directly without going
through all-completions).

> with helm-mode on.
> AFAICT we don't try to manipulate obarray directly (of course).  What
> nasty things could we be doing?

I don't know.  I expected the recipe to demonstrate the kinds of
problems you're seeing, so I guess I lack other parts of the recipe.


        Stefan

Re: What does all-completions with COLLECTION == obarray return?

[Michael Heerdegen]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

> I don't know.  I expected the recipe to demonstrate the kinds of
> problems you're seeing, so I guess I lack other parts of the recipe.

The "other parts" were just that if you repeat the recipe eight times or
so, Emacs gets slower an then freezes for longer and longer periods
before the minibuffer appears, and that is because obarray grows so
massively.  All that in a minimal helm environment - helm.sh, if it says
something to you.

The answer must be in the implementation of helminized completing read,
but I could not find something obviously unorthodox in the code wrt
obarray.

I'll try to step through the code and find out where something gets
actually added to obarray.


Thanks,

Michael.

Re: What does all-completions with COLLECTION == obarray return?

[Michael Heerdegen]

Michael Heerdegen <michael_heerdegen@web.de> writes:

> I'll try to step through the code and find out where something gets
> actually added to obarray.

I was lucky and could condense a recipe for emacs -Q out of the Helm
code we use:

--8<---------------cut here---------------start------------->8---
(progn
  (intern "Bahá'í Date") ;this happens when requiring org
  (let* ((collection (all-completions "" obarray))
         (test #'facep)
         (predicate `(lambda (elm)
                       (condition-case err
                           (if (eq (quote ,test) 'commandp)
                               (funcall (quote ,test) (intern elm))
                             (funcall (quote ,test) elm))
                         (wrong-type-argument
                          (funcall (quote ,test) (intern elm)))))))
    (ignore (all-completions "" collection predicate))
    ;; Test if "Bahá'í Date" is the name of more than one interned symbol
    (when (let ((i 0))
            (catch 'done
              (mapatoms (lambda (s) (when (string= (symbol-name s) "Bahá'í Date")
                                 (if (< i 1) (setq i 1) (throw 'done t)))))
              nil))
      (message "Gotcha!"))))
--8<---------------cut here---------------end--------------->8---

Copy this into scratch in emacs -Q and hit C-x C-e.  I get "Gotcha!",
meaning that after evaluation, there is more than one interned symbol
named "Bahá'í Date".

I guess this should not happen, so it is a bug in Emacs in think.


Thanks,

Michael.