possible json.el optimization: json-alist-p and json-plist-p recursion

possible json.el optimization: json-alist-p and json-plist-p recursion

[Ted Zlatanov]

I ran into a very deep recursion with `json-encode' because
`json-alist-p' is unnecessarily recursive.  This is not a bug, just
something that can be optimized because (it seems) Emacs Lisp doesn't do
good tail recursion optimization in this case.

#+begin_src lisp
(defun json-alist-p (list)
  "Non-null if and only if LIST is an alist."
  (or (null list)
      (and (consp (car list))
           (json-alist-p (cdr list)))))
#+end_src

I wanted to ask if this was an OK replacement:

#+begin_src lisp
(defun gnus-sync-json-alist-p (list)
  "Non-null if and only if LIST is an alist."
  (let ((p list))
    (while (consp p)
      (setq p (if (consp (car-safe p))
                  (cdr p)
                'not-alist)))
    (null p)))
#+end_src

`json-plist-p' needs a similar treatment:

#+begin_src lisp
(defun json-plist-p (list)
  "Non-null if and only if LIST is a plist."
  (or (null list)
      (and (keywordp (car list))
           (consp (cdr list))
           (json-plist-p (cddr list)))))
#+end_src

Could be:

#+begin_src lisp
(defun gnus-sync-json-plist-p (list)
  "Non-null if and only if LIST is a plist."
  (let ((p list))
    (while (consp p)
      (setq p (if (and (keywordp (car-safe list))
                       (consp (cdr-safe p)))
                  (cddr p)
                'not-plist)))
    (null p)))
#+end_src

I don't know json.el so maybe I missed something subtle.  CC to Edward
O'Connor.  Let me know and I'll install in trunk if this is OK.

Thanks
Ted

Re: possible json.el optimization: json-alist-p and json-plist-p recursion

[Stefan Monnier]

> I ran into a very deep recursion with `json-encode' because
> `json-alist-p' is unnecessarily recursive.  This is not a bug, just
> something that can be optimized because (it seems) Emacs Lisp doesn't do
> good tail recursion optimization in this case.

Emacs Lisp doesn't do any tail recursion optimization (to some extent
because it's pretty difficult to do with a dynamically scoped languages,
so hopefully we'll be able to change this for the lexically scoped
dialect) and its function calls are expensive, so it does not handle
recursion very well, indeed (yes, this is sad).

> #+begin_src lisp
> (defun json-alist-p (list)
>   "Non-null if and only if LIST is an alist."
>   (or (null list)
>       (and (consp (car list))
>            (json-alist-p (cdr list)))))
> #+end_src

> I wanted to ask if this was an OK replacement:

> #+begin_src lisp
> (defun gnus-sync-json-alist-p (list)
>   "Non-null if and only if LIST is an alist."
>   (let ((p list))
>     (while (consp p)
>       (setq p (if (consp (car-safe p))
>                   (cdr p)
>                 'not-alist)))
>     (null p)))
> #+end_src

I guess it's OK tho "car-safe" seems unneeded since you've just tested
consp before (note that the original code didn't even check (consp p)
and just signaled an error if `list' is not a proper list).

Oh, and you don't need to copy `list' into `p', you can work on `list' directly.

>     (while (consp p)
>       (setq p (if (and (keywordp (car-safe list))
>                        (consp (cdr-safe p)))

Same here about car-safe and cdr-safe, and additionally, I think you
don't want to test `list' but `p' instead (tho here again, you probably
want to work on `list' directly without using a `p').


        Stefan

Re: possible json.el optimization: json-alist-p and json-plist-p recursion

[Ted Zlatanov]

On Thu, 13 Oct 2011 10:31:30 -0400 Stefan Monnier <monnier@iro.umontreal.ca> wrote: 

>> I ran into a very deep recursion with `json-encode' because
>> `json-alist-p' is unnecessarily recursive.  This is not a bug, just
>> something that can be optimized because (it seems) Emacs Lisp doesn't do
>> good tail recursion optimization in this case.

SM> Emacs Lisp doesn't do any tail recursion optimization (to some extent
SM> because it's pretty difficult to do with a dynamically scoped languages,
SM> so hopefully we'll be able to change this for the lexically scoped
SM> dialect) and its function calls are expensive, so it does not handle
SM> recursion very well, indeed (yes, this is sad).

It's usually not a problem but in this case a "proper" recursive
approach is broken, unfortunately.  I only noticed it because I was
calling `json-encode' on large lists, which is not typical usage...

SM> I guess it's OK tho "car-safe" seems unneeded since you've just tested
SM> consp before (note that the original code didn't even check (consp p)
SM> and just signaled an error if `list' is not a proper list).

SM> Oh, and you don't need to copy `list' into `p', you can work on `list' directly.
...
SM> Same here about car-safe and cdr-safe, and additionally, I think you
SM> don't want to test `list' but `p' instead (tho here again, you probably
SM> want to work on `list' directly without using a `p').

Good points, I had the `car-safe' and `cdr-safe' calls left over from
earlier code, and I was copying into p unnecessarily.  This is better, I
think:

#+begin_src lisp
(defun gnus-sync-json-alist-p (list)
  "Non-null if and only if LIST is an alist."
  (while (consp list)
    (setq list (if (consp (car list))
                   (cdr list)
                 'not-alist)))
  (null list))

(defun gnus-sync-json-plist-p (list)
  "Non-null if and only if LIST is a plist."
  (while (consp list)
    (setq list (if (and (keywordp (car list))
                        (consp (cdr list)))
                   (cddr list)
                 'not-plist)))
  (null list))

#+end_src

Thanks
Ted

Re: possible json.el optimization: json-alist-p and json-plist-p recursion

[Ted Zlatanov]

On Thu, 13 Oct 2011 12:07:22 -0400 Ted Zlatanov <tzz@lifelogs.com> wrote: 

TZ> Good points, I had the `car-safe' and `cdr-safe' calls left over from
TZ> earlier code, and I was copying into p unnecessarily.  This is better, I
TZ> think:

#+begin_src lisp
(defun gnus-sync-json-alist-p (list)
  "Non-null if and only if LIST is an alist."
  (while (consp list)
    (setq list (if (consp (car list))
		   (cdr list)
		 'not-alist)))
  (null list))

(defun gnus-sync-json-plist-p (list)
  "Non-null if and only if LIST is a plist."
  (while (consp list)
    (setq list (if (and (keywordp (car list))
			(consp (cdr list)))
		   (cddr list)
		 'not-plist)))
  (null list))
#+end_src

Emacs Lisp doesn't have `alist-p' or `plist-p' which these functions
could provide.  So instead of fixing just json.el, can I move these
functions to the core and rewrite json.el accordingly?  I think that
would be useful.  

But here's why I didn't just do it: these functions are exclusive,
meaning they don't accept a general list that has cons cells.  So this
example list is OK with `assq' but would fail the proposed `alist-p':

(assq 1 '((1 . 2) 3))

WDYT?  Should I change the name to `[ap]list-pure-p' or something like
that?  Or is this too limited to be generally useful?

Thanks
Ted

Re: possible json.el optimization: json-alist-p and json-plist-p recursion

[Stefan Monnier]

> Emacs Lisp doesn't have `alist-p' or `plist-p' which these functions
> could provide.  So instead of fixing just json.el, can I move these
> functions to the core and rewrite json.el accordingly?  I think that
> would be useful.

I haven't seen any other package use such primitives, so I'm not
convinced it deserves to be in the core.


        Stefan

Re: possible json.el optimization: json-alist-p and json-plist-p recursion

[Ted Zlatanov]

On Fri, 14 Oct 2011 10:58:05 -0400 Stefan Monnier <monnier@iro.umontreal.ca> wrote: 

>> Emacs Lisp doesn't have `alist-p' or `plist-p' which these functions
>> could provide.  So instead of fixing just json.el, can I move these
>> functions to the core and rewrite json.el accordingly?  I think that
>> would be useful.

SM> I haven't seen any other package use such primitives, so I'm not
SM> convinced it deserves to be in the core.

OK, I'll commit my change just to json.el.  Can I bump the version to
1.3 to reflect the bug fix?  I need to know about it from my package,
which is in Gnus and thus must work even when this bug exists in older
Emacs or json.el releases.

Thanks
Ted

Re: possible json.el optimization: json-alist-p and json-plist-p recursion

[Edward O'Connor]

> Can I bump the version to 1.3 to reflect the bug fix?

Please do.


Ted

Re: possible json.el optimization: json-alist-p and json-plist-p recursion

[Ted Zlatanov]

On Fri, 14 Oct 2011 10:02:38 -0700 "Edward O'Connor" <hober0@gmail.com> wrote: 

>> Can I bump the version to 1.3 to reflect the bug fix?
EO> Please do.

I pushed this out; thanks to you and Stefan for the help.

Ted

Re: possible json.el optimization: json-alist-p and json-plist-p recursion

[Edward O'Connor]

> I ran into a very deep recursion with `json-encode' because
> `json-alist-p' is unnecessarily recursive.  This is not a bug, just
> something that can be optimized[...]
> I wanted to ask if this was an OK replacement:

Sounds good to me, modulo Stefan's comments earlier.


Thanks,
Ted