* possible json.el optimization: json-alist-p and json-plist-p recursion @ 2011-10-13 13:51 Ted Zlatanov 2011-10-13 14:31 ` Stefan Monnier 2011-10-13 16:02 ` Edward O'Connor 0 siblings, 2 replies; 9+ messages in thread From: Ted Zlatanov @ 2011-10-13 13:51 UTC (permalink / raw) To: emacs-devel; +Cc: 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 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: possible json.el optimization: json-alist-p and json-plist-p recursion 2011-10-13 13:51 possible json.el optimization: json-alist-p and json-plist-p recursion Ted Zlatanov @ 2011-10-13 14:31 ` Stefan Monnier 2011-10-13 16:07 ` Ted Zlatanov 2011-10-13 16:02 ` Edward O'Connor 1 sibling, 1 reply; 9+ messages in thread From: Stefan Monnier @ 2011-10-13 14:31 UTC (permalink / raw) To: emacs-devel > 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: possible json.el optimization: json-alist-p and json-plist-p recursion 2011-10-13 14:31 ` Stefan Monnier @ 2011-10-13 16:07 ` Ted Zlatanov 2011-10-14 14:09 ` Ted Zlatanov 0 siblings, 1 reply; 9+ messages in thread From: Ted Zlatanov @ 2011-10-13 16:07 UTC (permalink / raw) To: emacs-devel 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: possible json.el optimization: json-alist-p and json-plist-p recursion 2011-10-13 16:07 ` Ted Zlatanov @ 2011-10-14 14:09 ` Ted Zlatanov 2011-10-14 14:58 ` Stefan Monnier 0 siblings, 1 reply; 9+ messages in thread From: Ted Zlatanov @ 2011-10-14 14:09 UTC (permalink / raw) To: emacs-devel 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: possible json.el optimization: json-alist-p and json-plist-p recursion 2011-10-14 14:09 ` Ted Zlatanov @ 2011-10-14 14:58 ` Stefan Monnier 2011-10-14 16:33 ` Ted Zlatanov 0 siblings, 1 reply; 9+ messages in thread From: Stefan Monnier @ 2011-10-14 14:58 UTC (permalink / raw) To: emacs-devel > 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: possible json.el optimization: json-alist-p and json-plist-p recursion 2011-10-14 14:58 ` Stefan Monnier @ 2011-10-14 16:33 ` Ted Zlatanov 2011-10-14 17:02 ` Edward O'Connor 0 siblings, 1 reply; 9+ messages in thread From: Ted Zlatanov @ 2011-10-14 16:33 UTC (permalink / raw) To: emacs-devel 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: possible json.el optimization: json-alist-p and json-plist-p recursion 2011-10-14 16:33 ` Ted Zlatanov @ 2011-10-14 17:02 ` Edward O'Connor 2011-10-17 17:41 ` Ted Zlatanov 0 siblings, 1 reply; 9+ messages in thread From: Edward O'Connor @ 2011-10-14 17:02 UTC (permalink / raw) To: emacs-devel > Can I bump the version to 1.3 to reflect the bug fix? Please do. Ted ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: possible json.el optimization: json-alist-p and json-plist-p recursion 2011-10-14 17:02 ` Edward O'Connor @ 2011-10-17 17:41 ` Ted Zlatanov 0 siblings, 0 replies; 9+ messages in thread From: Ted Zlatanov @ 2011-10-17 17:41 UTC (permalink / raw) To: emacs-devel 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: possible json.el optimization: json-alist-p and json-plist-p recursion 2011-10-13 13:51 possible json.el optimization: json-alist-p and json-plist-p recursion Ted Zlatanov 2011-10-13 14:31 ` Stefan Monnier @ 2011-10-13 16:02 ` Edward O'Connor 1 sibling, 0 replies; 9+ messages in thread From: Edward O'Connor @ 2011-10-13 16:02 UTC (permalink / raw) To: emacs-devel > 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 ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2011-10-17 17:41 UTC | newest] Thread overview: 9+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2011-10-13 13:51 possible json.el optimization: json-alist-p and json-plist-p recursion Ted Zlatanov 2011-10-13 14:31 ` Stefan Monnier 2011-10-13 16:07 ` Ted Zlatanov 2011-10-14 14:09 ` Ted Zlatanov 2011-10-14 14:58 ` Stefan Monnier 2011-10-14 16:33 ` Ted Zlatanov 2011-10-14 17:02 ` Edward O'Connor 2011-10-17 17:41 ` Ted Zlatanov 2011-10-13 16:02 ` Edward O'Connor
Code repositories for project(s) associated with this external index https://git.savannah.gnu.org/cgit/emacs.git https://git.savannah.gnu.org/cgit/emacs/org-mode.git This is an external index of several public inboxes, see mirroring instructions on how to clone and mirror all data and code used by this external index.