emacs-orgmode@gnu.org archives
 help / color / mirror / code / Atom feed
* [PATCH] Fix massive slowdown in org-id-find
@ 2015-03-23 13:51 Florian Beck
  2015-03-23 22:13 ` Nicolas Goaziou
  0 siblings, 1 reply; 9+ messages in thread
From: Florian Beck @ 2015-03-23 13:51 UTC (permalink / raw)
  To: emacs-orgmode

[-- Attachment #1: Type: text/plain, Size: 228 bytes --]

Hi,

the recent changes in org-id (presumably
8cdb2eef0f9f98f9e00a5e689decfe341fe0c6ec) lead to a massive slowdown.
org-id-find is slow as it is, now I find it almost unusable.

Attached patch provides a fix.
-- 
Florian Beck



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0362-org.el-Improve-speed-of-org-find-property.patch --]
[-- Type: text/x-diff, Size: 2620 bytes --]

From 9867f0f45befc26854920d759a2505adba5d486b Mon Sep 17 00:00:00 2001
From: Florian Beck <fb@miszellen.de>
Date: Mon, 23 Mar 2015 11:35:09 +0100
Subject: [PATCH 362/362] org.el: Improve speed of org-find-property

* lisp/org.el (org-re-property): New optional argument.
(org-find-property): Simplify value search.
---
 lisp/org.el | 28 +++++++++++++++++-----------
 1 file changed, 17 insertions(+), 11 deletions(-)

diff --git a/lisp/org.el b/lisp/org.el
index 85a8048..71c5e6e 100755
--- a/lisp/org.el
+++ b/lisp/org.el
@@ -6268,7 +6268,7 @@ takes into consideration inlinetasks."
 
 (defvar org-font-lock-keywords nil)
 
-(defsubst org-re-property (property &optional literal allow-null)
+(defsubst org-re-property (property &optional literal allow-null value)
   "Return a regexp matching a PROPERTY line.
 
 When optional argument LITERAL is non-nil, do not quote PROPERTY.
@@ -6276,14 +6276,22 @@ This is useful when PROPERTY is a regexp.  When ALLOW-NULL is
 non-nil, match properties even without a value.
 
 Match group 3 is set to the value when it exists.  If there is no
-value and ALLOW-NULL is non-nil, it is set to the empty string."
+value and ALLOW-NULL is non-nil, it is set to the empty string.
+
+With optional argument VALUE, match only property lines with
+that value; in this case, ALLOW-NULL is ignored.  VALUE is quoted
+unless LITERAL is non-nil."
   (concat
    "^\\(?4:[ \t]*\\)"
    (format "\\(?1::\\(?2:%s\\):\\)"
 	   (if literal property (regexp-quote property)))
-   (if allow-null
-       "\\(?:\\(?3:$\\)\\|[ \t]+\\(?3:.*?\\)\\)\\(?5:[ \t]*\\)$"
-     "[ \t]+\\(?3:[^ \r\t\n]+.*?\\)\\(?5:[ \t]*\\)$")))
+   (cond (value
+	  (format "[ \t]+\\(?3:%s\\)\\(?5:[ \t]*\\)$"
+		  (if literal value (regexp-quote value))))
+	 (allow-null
+	  "\\(?:\\(?3:$\\)\\|[ \t]+\\(?3:.*?\\)\\)\\(?5:[ \t]*\\)$")
+	 (t
+	  "[ \t]+\\(?3:[^ \r\t\n]+.*?\\)\\(?5:[ \t]*\\)$"))))
 
 (defconst org-property-re
   (org-re-property "\\S-+" 'literal t)
@@ -16331,12 +16339,10 @@ part of the buffer."
   (save-excursion
     (goto-char (point-min))
     (let ((case-fold-search t)
-	  (re (org-re-property property nil (not value))))
-      (catch 'exit
-	(while (re-search-forward re nil t)
-	  (when (if value (equal value (org-entry-get (point) property nil t))
-		  (org-entry-get (point) property nil t))
-	    (throw 'exit (progn (org-back-to-heading t) (point)))))))))
+	  (re (org-re-property property nil (not value) value)))
+      (when (re-search-forward re nil t)
+	(org-back-to-heading t)
+	(point)))))
 
 (defun org-delete-property (property)
   "In the current entry, delete PROPERTY."
-- 
2.1.0


^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [PATCH] Fix massive slowdown in org-id-find
  2015-03-23 13:51 [PATCH] Fix massive slowdown in org-id-find Florian Beck
@ 2015-03-23 22:13 ` Nicolas Goaziou
  2015-03-24  9:02   ` Sebastien Vauban
  2015-03-24 11:05   ` Florian Beck
  0 siblings, 2 replies; 9+ messages in thread
From: Nicolas Goaziou @ 2015-03-23 22:13 UTC (permalink / raw)
  To: Florian Beck; +Cc: emacs-orgmode

Hello,

Florian Beck <fb@miszellen.de> writes:

> the recent changes in org-id (presumably
> 8cdb2eef0f9f98f9e00a5e689decfe341fe0c6ec) lead to a massive slowdown.

Would you mind elaborating a bit? Slow down doing what? In which cases?
Could you profile it?

> org-id-find is slow as it is, now I find it almost unusable.
>
> Attached patch provides a fix.

Thanks. However, your patch is (partly) wrong.

> -	  (re (org-re-property property nil (not value))))
> -      (catch 'exit
> -	(while (re-search-forward re nil t)
> -	  (when (if value (equal value (org-entry-get (point) property nil t))
> -		  (org-entry-get (point) property nil t))
> -	    (throw 'exit (progn (org-back-to-heading t) (point)))))))))
> +	  (re (org-re-property property nil (not value) value)))
> +      (when (re-search-forward re nil t)
> +	(org-back-to-heading t)
> +	(point)))))

Here, it catches false positives, e.g., lines looking like properties in
example blocks. It also overlooks accumulated values. It should fail
with "make test".

However, the optional VALUE argument is nice (I think some profiling
would still be welcome, tho).


Regards,

-- 
Nicolas Goaziou

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [PATCH] Fix massive slowdown in org-id-find
  2015-03-23 22:13 ` Nicolas Goaziou
@ 2015-03-24  9:02   ` Sebastien Vauban
  2015-03-24 11:05   ` Florian Beck
  1 sibling, 0 replies; 9+ messages in thread
From: Sebastien Vauban @ 2015-03-24  9:02 UTC (permalink / raw)
  To: emacs-orgmode-mXXj517/zsQ

Nicolas Goaziou wrote:
> Florian Beck <fb-ZlLO5Ova5IRn68oJJulU0Q@public.gmane.org> writes:
>
>> the recent changes in org-id (presumably
>> 8cdb2eef0f9f98f9e00a5e689decfe341fe0c6ec) lead to a massive slowdown.
>
> Would you mind elaborating a bit? Slow down doing what? In which cases?
> Could you profile it?
>
>> org-id-find is slow as it is, now I find it almost unusable.
>>
>> Attached patch provides a fix.
>
> Thanks. However, your patch is (partly) wrong.
>
>> -	  (re (org-re-property property nil (not value))))
>> -      (catch 'exit
>> -	(while (re-search-forward re nil t)
>> -	  (when (if value (equal value (org-entry-get (point) property nil t))
>> -		  (org-entry-get (point) property nil t))
>> -	    (throw 'exit (progn (org-back-to-heading t) (point)))))))))
>> +	  (re (org-re-property property nil (not value) value)))
>> +      (when (re-search-forward re nil t)
>> +	(org-back-to-heading t)
>> +	(point)))))
>
> Here, it catches false positives, e.g., lines looking like properties in
> example blocks. It also overlooks accumulated values. It should fail
> with "make test".
>
> However, the optional VALUE argument is nice (I think some profiling
> would still be welcome, tho).

For my own information, does one know if it's possible to integrate
profiling tests in ERT?  So that one could write that if test X takes
more than 2 s (for example), the test would fail?

Best regards,
  Seb

-- 
Sebastien Vauban

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [PATCH] Fix massive slowdown in org-id-find
  2015-03-23 22:13 ` Nicolas Goaziou
  2015-03-24  9:02   ` Sebastien Vauban
@ 2015-03-24 11:05   ` Florian Beck
  2015-03-24 22:49     ` Florian Beck
  1 sibling, 1 reply; 9+ messages in thread
From: Florian Beck @ 2015-03-24 11:05 UTC (permalink / raw)
  To: emacs-orgmode


> Would you mind elaborating a bit? Slow down doing what? In which cases?

A fraction of a second vs 10 seconds when executing a function that
calls org-id-find. The slowdowwn is not quite as massive since I
cleaned up org-id-files a bit, however.

> Could you profile it?

I'll look into it.

> Here, it catches false positives, e.g., lines looking like properties in
> example blocks. It also overlooks accumulated values.

This is true. However that is not really relevant for id searches, is
it? In the worst case, you'll find ids in example, etc blocks when you
SEARCH for them.

I guess, you want to use org-find-property in other places as well. In
that case org-id-find could maybe use a faster, simplified version? Let
me see, if I can do some profiling tonight.

> It should fail with "make test".

Doesn't work for me (it hangs).

-- 
Florian Beck

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [PATCH] Fix massive slowdown in org-id-find
  2015-03-24 11:05   ` Florian Beck
@ 2015-03-24 22:49     ` Florian Beck
  2015-03-25 11:31       ` Jacob Nielsen
  2015-03-25 13:04       ` Nicolas Goaziou
  0 siblings, 2 replies; 9+ messages in thread
From: Florian Beck @ 2015-03-24 22:49 UTC (permalink / raw)
  To: emacs-orgmode

>> Could you profile it?

Here are the results:

With my setup and the patch I get, using

(let ((time (current-time)))
  (org-id-find "zangwill.nick_2014:aesthetic.judgment")
  (format "%ss" (time-to-seconds (time-subtract (current-time) time))))

--> "0.027756516s"

Without my patch, the result is

--> "16.104403749s"

profile-report returns:

- command-execute                                               16095  99%
 - call-interactively                                           16095  99%
  - funcall-interactively                                       15905  98%
   - eval-last-sexp                                             15879  98%
    - elisp--eval-last-sexp                                     15879  98%
     - eval                                                     15879  98%
      - let                                                     15879  98%
       - org-id-find                                            15879  98%
        - org-id-find-id-in-file                                15879  98%
         - org-find-entry-with-id                               15879  98%
          - org-find-property                                   15879  98%
           - save-excursion                                     15879  98%
            - let                                               15879  98%
             - catch                                            15879  98%
              - while                                           15879  98%
               - if                                             13311  82%
                - if                                            13311  82%
                 - equal                                        13311  82%
                  - org-entry-get                               11955  74%
                   - org-get-property-block                      8876  55%
                    - org-inlinetask-in-task-p                   3329  20%
                       org-inlinetask-outline-regexp                 12   0%
                    - org-back-to-heading                        3009  18%
                     - outline-back-to-heading                   2000  12%
                        outline-on-heading-p                        4   0%
                      org-before-first-heading-p                  880   5%
                      org-get-limited-outline-regexp                 24   0%
                   - #<compiled 0x3e8f1b9>                        939   5%
                      match-string-no-properties                   44   0%
   - execute-extended-command                                      20   0%
    - sit-for                                                      16   0%
       redisplay                                                   16   0%
    + command-execute                                               4   0%
   + previous-line                                                  6   0%
  + byte-code                                                     190   1%
+ timer-event-handler                                              15   0%
+ ...                                                               0   0%



-- 
Florian Beck

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [PATCH] Fix massive slowdown in org-id-find
  2015-03-24 22:49     ` Florian Beck
@ 2015-03-25 11:31       ` Jacob Nielsen
  2015-03-25 13:04       ` Nicolas Goaziou
  1 sibling, 0 replies; 9+ messages in thread
From: Jacob Nielsen @ 2015-03-25 11:31 UTC (permalink / raw)
  To: emacs-orgmode

I have this in one of my org files:
# -*- cache-long-scans: nil; -*-
# This makes forward-line much faster and thus org-goto-line and thus
org-table-sum (C-c +)

Does setting cache-long-scans to nil help in this case also ?

Best,
Jacob

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [PATCH] Fix massive slowdown in org-id-find
  2015-03-24 22:49     ` Florian Beck
  2015-03-25 11:31       ` Jacob Nielsen
@ 2015-03-25 13:04       ` Nicolas Goaziou
  2015-03-30 20:43         ` Florian Beck
  1 sibling, 1 reply; 9+ messages in thread
From: Nicolas Goaziou @ 2015-03-25 13:04 UTC (permalink / raw)
  To: Florian Beck; +Cc: emacs-orgmode

Florian Beck <fb@miszellen.de> writes:

>>> Could you profile it?
>
> Here are the results:
>
> With my setup and the patch I get, using
>
> (let ((time (current-time)))
>   (org-id-find "zangwill.nick_2014:aesthetic.judgment")
>   (format "%ss" (time-to-seconds (time-subtract (current-time) time))))
>
> --> "0.027756516s"
>
> Without my patch, the result is
>
> --> "16.104403749s"
>
> profile-report returns:
>
> - command-execute                                               16095  99%
>  - call-interactively                                           16095  99%
>   - funcall-interactively                                       15905  98%
>    - eval-last-sexp                                             15879  98%
>     - elisp--eval-last-sexp                                     15879  98%
>      - eval                                                     15879  98%
>       - let                                                     15879  98%
>        - org-id-find                                            15879  98%
>         - org-id-find-id-in-file                                15879  98%
>          - org-find-entry-with-id                               15879  98%
>           - org-find-property                                   15879  98%
>            - save-excursion                                     15879  98%
>             - let                                               15879  98%
>              - catch                                            15879  98%
>               - while                                           15879  98%
>                - if                                             13311  82%
>                 - if                                            13311  82%
>                  - equal                                        13311  82%
>                   - org-entry-get                               11955  74%
>                    - org-get-property-block                      8876  55%
>                     - org-inlinetask-in-task-p                   3329  20%
>                        org-inlinetask-outline-regexp                 12   0%
>                     - org-back-to-heading                        3009  18%
>                      - outline-back-to-heading                   2000  12%
>                         outline-on-heading-p                        4   0%
>                       org-before-first-heading-p                  880   5%
>                       org-get-limited-outline-regexp                 24   0%
>                    - #<compiled 0x3e8f1b9>                        939   5%
>                       match-string-no-properties                   44   0%
>    - execute-extended-command                                      20   0%
>     - sit-for                                                      16   0%
>        redisplay                                                   16   0%
>     + command-execute                                               4   0%
>    + previous-line                                                  6   0%
>   + byte-code                                                     190   1%
> + timer-event-handler                                              15   0%
> + ...                                                               0   0%


Thank you. 

Could you also send and updated patch containing the VALUE optional
argument to `org-re-property' and changing modifying only the (re ...)
line in `org-find-property', with a new profiling?

Regards,

^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [PATCH] Fix massive slowdown in org-id-find
  2015-03-25 13:04       ` Nicolas Goaziou
@ 2015-03-30 20:43         ` Florian Beck
  2015-03-31 10:01           ` Nicolas Goaziou
  0 siblings, 1 reply; 9+ messages in thread
From: Florian Beck @ 2015-03-30 20:43 UTC (permalink / raw)
  To: emacs-orgmode

[-- Attachment #1: Type: text/plain, Size: 2328 bytes --]

Hello,

[sorry for the delay, I had some git SNAFUs]

> Could you also send and updated patch containing the VALUE optional
> argument to `org-re-property' and changing modifying only the (re ...)
> line in `org-find-property', with a new profiling?

Seems like this does trick. I don't really understand why, though. The
previous profiling seemed to indicate that most of the time was spent in
`org-entry-get' (that's why I removed it). Anyway, many thanks for
helping me out. Much appreciated.

I attached the new patch.

(let ((time (current-time)))
   (org-id-find "zangwill.nick_2014:aesthetic.judgment")
   (format "%ss" (time-to-seconds (time-subtract (current-time) time))))

--> "0.032598146s"

Here is the profiler report:

- command-execute                                                 215  89%
 - call-interactively                                             215  89%
  - funcall-interactively                                         140  58%
   + execute-extended-command                                      92  38%
   - eval-last-sexp                                                35  14%
    - elisp--eval-last-sexp                                        35  14%
     - eval                                                        35  14%
      - let                                                        35  14%
       - org-id-find                                               35  14%
        - org-id-find-id-in-file                                   35  14%
         - org-find-entry-with-id                                  35  14%
          - org-find-property                                      35  14%
           - save-excursion                                        35  14%
            - let                                                  35  14%
             - catch                                               35  14%
                while                                              35  14%
   + next-line                                                     13   5%
  + byte-code                                                      75  31%
+ redisplay_internal (C function)                                  15   6%
+ timer-event-handler                                              11   4%
+ ...                                                               0   0%

-- 
Florian Beck


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: 0001-org.el-Allow-searching-for-specific-property-value.patch --]
[-- Type: text/x-diff, Size: 2317 bytes --]

From 389d8cec4406c394f3bf955726823951b014f6aa Mon Sep 17 00:00:00 2001
From: Florian Beck <fb@miszellen.de>
Date: Mon, 30 Mar 2015 22:27:36 +0200
Subject: [PATCH] org.el: Allow searching for specific property value

* lisp/org.el (org-re-property): New optional argument.
(org-find-property): Use it.
---
 lisp/org.el | 20 ++++++++++++++------
 1 file changed, 14 insertions(+), 6 deletions(-)

diff --git a/lisp/org.el b/lisp/org.el
index cf37950..4f61123 100755
--- a/lisp/org.el
+++ b/lisp/org.el
@@ -6254,7 +6254,7 @@ takes into consideration inlinetasks."
 
 (defvar org-font-lock-keywords nil)
 
-(defsubst org-re-property (property &optional literal allow-null)
+(defsubst org-re-property (property &optional literal allow-null value)
   "Return a regexp matching a PROPERTY line.
 
 When optional argument LITERAL is non-nil, do not quote PROPERTY.
@@ -6262,14 +6262,22 @@ This is useful when PROPERTY is a regexp.  When ALLOW-NULL is
 non-nil, match properties even without a value.
 
 Match group 3 is set to the value when it exists.  If there is no
-value and ALLOW-NULL is non-nil, it is set to the empty string."
+value and ALLOW-NULL is non-nil, it is set to the empty string.
+
+With optional argument VALUE, match only property lines with
+that value; in this case, ALLOW-NULL is ignored.  VALUE is quoted
+unless LITERAL is non-nil."
   (concat
    "^\\(?4:[ \t]*\\)"
    (format "\\(?1::\\(?2:%s\\):\\)"
 	   (if literal property (regexp-quote property)))
-   (if allow-null
-       "\\(?:\\(?3:$\\)\\|[ \t]+\\(?3:.*?\\)\\)\\(?5:[ \t]*\\)$"
-     "[ \t]+\\(?3:[^ \r\t\n]+.*?\\)\\(?5:[ \t]*\\)$")))
+   (cond (value
+	  (format "[ \t]+\\(?3:%s\\)\\(?5:[ \t]*\\)$"
+		  (if literal value (regexp-quote value))))
+	 (allow-null
+	  "\\(?:\\(?3:$\\)\\|[ \t]+\\(?3:.*?\\)\\)\\(?5:[ \t]*\\)$")
+	 (t
+	  "[ \t]+\\(?3:[^ \r\t\n]+.*?\\)\\(?5:[ \t]*\\)$"))))
 
 (defconst org-property-re
   (org-re-property "\\S-+" 'literal t)
@@ -16323,7 +16331,7 @@ part of the buffer."
   (save-excursion
     (goto-char (point-min))
     (let ((case-fold-search t)
-	  (re (org-re-property property nil (not value))))
+	  (re (org-re-property property nil (not value) value)))
       (catch 'exit
 	(while (re-search-forward re nil t)
 	  (when (if value (equal value (org-entry-get (point) property nil t))
-- 
2.1.0


^ permalink raw reply	[flat|nested] 9+ messages in thread

* Re: [PATCH] Fix massive slowdown in org-id-find
  2015-03-30 20:43         ` Florian Beck
@ 2015-03-31 10:01           ` Nicolas Goaziou
  0 siblings, 0 replies; 9+ messages in thread
From: Nicolas Goaziou @ 2015-03-31 10:01 UTC (permalink / raw)
  To: Florian Beck; +Cc: emacs-orgmode

Florian Beck <fb@miszellen.de> writes:

> Seems like this does trick. I don't really understand why, though.The
> previous profiling seemed to indicate that most of the time was spent in
> `org-entry-get' (that's why I removed it).

`org-entry-get' is quite fast by itself. However it was called on every
entry with an :ID: property, which seems to include a lot of candidates
in your setup. Now it also requires :ID: value to match the one you're
looking for.

> I attached the new patch.

Applied. Thank you.

I added TINYCHANGE at the end of the commit message since you don't seem
to have signed the FSF papers. Please correct me if I'm wrong.

Regards,

^ permalink raw reply	[flat|nested] 9+ messages in thread

end of thread, other threads:[~2015-03-31 10:00 UTC | newest]

Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2015-03-23 13:51 [PATCH] Fix massive slowdown in org-id-find Florian Beck
2015-03-23 22:13 ` Nicolas Goaziou
2015-03-24  9:02   ` Sebastien Vauban
2015-03-24 11:05   ` Florian Beck
2015-03-24 22:49     ` Florian Beck
2015-03-25 11:31       ` Jacob Nielsen
2015-03-25 13:04       ` Nicolas Goaziou
2015-03-30 20:43         ` Florian Beck
2015-03-31 10:01           ` Nicolas Goaziou

Code repositories for project(s) associated with this inbox:

	https://git.savannah.gnu.org/cgit/emacs/org-mode.git

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).