[ANN] faster org-table-to-lisp

[ANN] faster org-table-to-lisp

[tbanelwebmin]

Hi The List.

Here is an alternative, faster version of org-table-to-lisp. It can be
more than 100 times faster.

#+BEGIN_SRC elisp
(defun org-table-to-lisp-faster (&optional org-table-at-p-done)
  "Convert the table at point to a Lisp structure.
The structure will be a list.  Each item is either the symbol `hline'
for a horizontal separator line, or a list of field values as strings.
The table is taken from the buffer at point.
When the optional ORG-TABLE-AT-P-DONE parameter is not nil, it is
assumed that (org-at-table-p) was already called."
  (or org-table-at-p-done (org-at-table-p) (user-error "No table at point"))
  (save-excursion
    (goto-char (org-table-begin))
    (let ((end (org-table-end))
          (row)
          (table))
      (while (< (point) end)
        (setq row nil)
        (search-forward "|" end)
        (if (looking-at "-")
            (progn
              (search-forward "\n" end)
              (push 'hline table))
          (while (not (search-forward-regexp "\\=\n" end t))
            (unless (search-forward-regexp "\\=\\s-*\\([^|]*\\)" end t)
              (user-error "Malformed table at char %s" (point)))
            (let ((b (match-beginning 1))
          (e (match-end       1)))
              (and (search-backward-regexp "[^ \t]" b t)
               (forward-char 1))
              (push
           (buffer-substring-no-properties b (point))
           row)
          (goto-char (1+ e))))
          (push (nreverse row) table)))
      (nreverse table))))
#+END_SRC

Bellow is an example of a large table borrowed from the Datamash
software. On my PC, the reproducible benches show:
- Traditional org-table-to-lisp: 130 seconds
- Alternative org-table-to-lisp: 0.8 seconds (not compiled)

It is faster because it operates directly on the buffer with
(search-forward-regexp). Whereas the standard function splits a string
extracted from the buffer.

This function is a drop-in replacement for the standard one. It can
benefit to Babel and Gnuplot.

Would it make sense to upgrade Org Mode code base?


Beware! The optional parameter has a slightly different meaning for both
functions:
- for the traditional function, it is a string representing an Org table
- for the alternative function, it is a Boolean telling whether
(org-table-at-p) has been called or not

This difference makes no difference for the use cases in the code base.
The function is always called without a parameter, or as:

#+BEGIN_SRC elisp
(org-table-to-lisp
  (buffer-substring-no-properties
    (org-table-begin)
    (org-table-end)))
#+END_SRC



Here is the reproducible bench. It is a self-contained, Org Mode file to
be opened in Emacs.
wget http://tbanelwebmin.free.fr/OrgMode/bench-org-table-to-lisp.org.gz

Re: [ANN] faster org-table-to-lisp

[Nicolas Goaziou]

Hello,

tbanelwebmin <tbanelwebmin@free.fr> writes:

> Here is an alternative, faster version of org-table-to-lisp. It can be
> more than 100 times faster.

Great! Thank you!

> #+BEGIN_SRC elisp
> (defun org-table-to-lisp-faster (&optional org-table-at-p-done)
>   "Convert the table at point to a Lisp structure.
> The structure will be a list.  Each item is either the symbol `hline'
> for a horizontal separator line, or a list of field values as strings.
> The table is taken from the buffer at point.
> When the optional ORG-TABLE-AT-P-DONE parameter is not nil, it is
> assumed that (org-at-table-p) was already called."

Since you're changing the signature, I suggest to provide the table
element instead of ORG-AT-TABLE-P. AFAICT, `org-babel-read-element',
through `org-babel-read-table', would greatly benefit from this.

Or, to be backward compatible, I suggest

  &optional TEXT TABLE

>   (or org-table-at-p-done (org-at-table-p) (user-error "No table at point"))
>   (save-excursion
>     (goto-char (org-table-begin))
>     (let ((end (org-table-end))
>           (row)
>           (table))

Nitpick:

    (row nil)
    (table nil)

>       (while (< (point) end)
>         (setq row nil)
>         (search-forward "|" end)
>         (if (looking-at "-")
>             (progn
>               (search-forward "\n" end)

(forward-line)

>               (push 'hline table))
>           (while (not (search-forward-regexp "\\=\n" end t))

(unless (eolp)
  ...)

>             (unless (search-forward-regexp "\\=\\s-*\\([^|]*\\)" end t)
>               (user-error "Malformed table at char %s" (point)))

A row may not be properly ended. It doesn't warrant an error. Could you
make it more tolerant?

Also `search-forward-regexp' -> `re-search-forward', i.e., use the
original.

>             (let ((b (match-beginning 1))
>           (e (match-end       1)))

Nitpick: spurious spaces.

>               (and (search-backward-regexp "[^ \t]" b t)
>                (forward-char 1))

  (skip-chars-backward " \t")

> It is faster because it operates directly on the buffer with
> (search-forward-regexp). Whereas the standard function splits a string
> extracted from the buffer.

You are right. I guess the initial implementation didn't have these
monster tables in mind.

> This function is a drop-in replacement for the standard one. It can
> benefit to Babel and Gnuplot.
>
> Would it make sense to upgrade Org Mode code base?

Certainly. Could you add an entry in ORG-NEWS, in "Miscellaneous"?

Regards,

-- 
Nicolas Goaziou

Re: [ANN] faster org-table-to-lisp

[tbanelwebmin]

Le 30/04/2020 à 10:09, Nicolas Goaziou a écrit :

> Hello,
>
> tbanelwebmin <tbanelwebmin@free.fr> writes:
>
>> Here is an alternative, faster version of org-table-to-lisp. It can be
>> more than 100 times faster.
> Great! Thank you!
>
>> #+BEGIN_SRC elisp
>> (defun org-table-to-lisp-faster (&optional org-table-at-p-done)
>>   "Convert the table at point to a Lisp structure.
>> The structure will be a list.  Each item is either the symbol `hline'
>> for a horizontal separator line, or a list of field values as strings.
>> The table is taken from the buffer at point.
>> When the optional ORG-TABLE-AT-P-DONE parameter is not nil, it is
>> assumed that (org-at-table-p) was already called."
> Since you're changing the signature, I suggest to provide the table
> element instead of ORG-AT-TABLE-P. AFAICT, `org-babel-read-element',
> through `org-babel-read-table', would greatly benefit from this.
>
> Or, to be backward compatible, I suggest
>
>   &optional TEXT TABLE
>
>>   (or org-table-at-p-done (org-at-table-p) (user-error "No table at point"))
>>   (save-excursion
>>     (goto-char (org-table-begin))
>>     (let ((end (org-table-end))
>>           (row)
>>           (table))
> Nitpick:
>
>     (row nil)
>     (table nil)
>
>>       (while (< (point) end)
>>         (setq row nil)
>>         (search-forward "|" end)
>>         (if (looking-at "-")
>>             (progn
>>               (search-forward "\n" end)
> (forward-line)
>
>>               (push 'hline table))
>>           (while (not (search-forward-regexp "\\=\n" end t))
> (unless (eolp)
>   ...)
>
>>             (unless (search-forward-regexp "\\=\\s-*\\([^|]*\\)" end t)
>>               (user-error "Malformed table at char %s" (point)))
> A row may not be properly ended. It doesn't warrant an error. Could you
> make it more tolerant?
>
> Also `search-forward-regexp' -> `re-search-forward', i.e., use the
> original.
>
>>             (let ((b (match-beginning 1))
>>           (e (match-end       1)))
> Nitpick: spurious spaces.
>
>>               (and (search-backward-regexp "[^ \t]" b t)
>>                (forward-char 1))
>   (skip-chars-backward " \t")
>
>> It is faster because it operates directly on the buffer with
>> (search-forward-regexp). Whereas the standard function splits a string
>> extracted from the buffer.
> You are right. I guess the initial implementation didn't have these
> monster tables in mind.
>
>> This function is a drop-in replacement for the standard one. It can
>> benefit to Babel and Gnuplot.
>>
>> Would it make sense to upgrade Org Mode code base?
> Certainly. Could you add an entry in ORG-NEWS, in "Miscellaneous"?
>
> Regards,
>
Thanks Nicolas for your nice suggestions. I've taken them into
account. Particularly, the use of (skip-chars-backward " \t") gave a
small additional speedup, and simplified the code.

I found a way to ensure full backward compatibility. I keep the same
signature. When a table is given as a string parameter, it is inserted
into a temporary buffer, which is then parsed. Overall, the resulting
speed is quite satisfactory.

I also made the function more tolerant to ill-formed tables: missing
"|" or excess of spaces at the end of a row are now gracefully
accepted.

Regards
Thierry

#+BEGIN_SRC elisp
(defun org-table-to-lisp (&optional txt)
  "Convert the table at point to a Lisp structure.
The structure will be a list.  Each item is either the symbol `hline'
for a horizontal separator line, or a list of field values as strings.
The table is taken from the parameter TXT, or from the buffer at point."
  (if txt
      (with-temp-buffer
        (insert txt)
        (goto-char (point-min))
        (org-table-to-lisp))
    (unless (org-at-table-p) (user-error "No table at point"))
    (save-excursion
      (goto-char (org-table-begin))
      (let ((end (org-table-end))
            (row nil)
            (table nil))
        (while (< (point) end)
          (setq row nil)
          (search-forward "|" end)
          (if (looking-at "-")
              (progn
                (forward-line)
                (push 'hline table))
            (while (not (re-search-forward "\\=\\s-*\n" end t))
              (unless (re-search-forward "\\=\\s-*\\([^|\n]*\\)\\(|?\\)" end t)
                (user-error "Malformed table at char %s" (point)))
              (goto-char (match-end 1))
              (skip-chars-backward " \t" (match-beginning 1))
              (push
               (buffer-substring-no-properties (match-beginning 1) (point))
               row)
              (goto-char (match-end 2)))
            (push (nreverse row) table)))
        (nreverse table)))))
#+END_SRC


* Version 9.4 (not yet released)
** Miscellaneous
*** Faster org-table-to-lisp

The new implementation can be more than 100 times faster. This enhances
responsiveness of Babel or Gnuplot blocks handling thousands long tables.

Re: [ANN] faster org-table-to-lisp

[Daniele Nicolodi]

Hello,

On 30-04-2020 14:28, tbanelwebmin wrote:
> * Version 9.4 (not yet released)
> ** Miscellaneous
> *** Faster org-table-to-lisp
> 
> The new implementation can be more than 100 times faster. This enhances
> responsiveness of Babel or Gnuplot blocks handling thousands long tables.

Nitpicking: I think "handling thousands long tables" should be "handling
tables with thousands of (rows|columns|cells)" (pick the appropriate
one), but probably "handling very large tables" is just good enough.

Cheers,
Dan

Re: [ANN] faster org-table-to-lisp

[tbanelwebmin]

Better, thanks Daniele
Let's go for "handling very large tables"
Regards
Thierry

Le 30/04/2020 à 22:47, Daniele Nicolodi a écrit :

> Hello,
>
> On 30-04-2020 14:28, tbanelwebmin wrote:
>> * Version 9.4 (not yet released)
>> ** Miscellaneous
>> *** Faster org-table-to-lisp
>>
>> The new implementation can be more than 100 times faster. This enhances
>> responsiveness of Babel or Gnuplot blocks handling thousands long tables.
> Nitpicking: I think "handling thousands long tables" should be "handling
> tables with thousands of (rows|columns|cells)" (pick the appropriate
> one), but probably "handling very large tables" is just good enough.
>
> Cheers,
> Dan
>
>
>

Re: [ANN] faster org-table-to-lisp

[Nicolas Goaziou]

tbanelwebmin <tbanelwebmin@free.fr> writes:

> I found a way to ensure full backward compatibility. I keep the same
> signature. When a table is given as a string parameter, it is inserted
> into a temporary buffer, which is then parsed. Overall, the resulting
> speed is quite satisfactory.

Awwww, you didn't like my ELEMENT suggestion.

> I also made the function more tolerant to ill-formed tables: missing
> "|" or excess of spaces at the end of a row are now gracefully
> accepted.

Great!

>             (while (not (re-search-forward "\\=\\s-*\n" end t))

(re-search-forward "\\=..." ...) -> (looking-at "..." ...)

Note that Org does not use \\s- but the simpler [ \t].

Also, the regexp assumes the table end with a newline character, which
may not be the case.

>               (unless (re-search-forward "\\=\\s-*\\([^|\n]*\\)\\(|?\\)" end t)
>                 (user-error "Malformed table at char %s" (point)))

This cannot happen. The regexp above matches anything, i.e., the empty
string.

>               (goto-char (match-end 1))
>               (skip-chars-backward " \t" (match-beginning 1))
>               (push
>                (buffer-substring-no-properties (match-beginning 1) (point))
>                row)
>               (goto-char (match-end 2)))
>             (push (nreverse row) table)))
>         (nreverse table)))))

I applied your suggestion, with a few simplifications. Hopefully, it
squeezed a bit more the execution time. Let me know!

> The new implementation can be more than 100 times faster. This enhances
> responsiveness of Babel or Gnuplot blocks handling thousands long
> tables.

Looks good. However, we didn't change the signature, so I didn't add
this to ORG-NEWS. It is in the commit message, tho.

Thank you!

Re: [ANN] faster org-table-to-lisp

[tbanelwebmin]

Nicolas, how did you do that? Your version is 25% faster than mine,
and the code is 33% shorter! Very elegant.

Le 01/05/2020 à 00:35, Nicolas Goaziou a écrit :

> tbanelwebmin <tbanelwebmin@free.fr> writes:
>
>> I found a way to ensure full backward compatibility. I keep the same
>> signature. When a table is given as a string parameter, it is inserted
>> into a temporary buffer, which is then parsed. Overall, the resulting
>> speed is quite satisfactory.
> Awwww, you didn't like my ELEMENT suggestion.

Sorry, I may not understood what you said:
= Since you're changing the signature, I suggest to provide the table
= element instead of ORG-AT-TABLE-P. AFAICT, `org-babel-read-element',
= through `org-babel-read-table', would greatly benefit from this.

Could you elaborate (if still relevant)?

>
>> I also made the function more tolerant to ill-formed tables: missing
>> "|" or excess of spaces at the end of a row are now gracefully
>> accepted.
> Great!
>
>>             (while (not (re-search-forward "\\=\\s-*\n" end t))
> (re-search-forward "\\=..." ...) -> (looking-at "..." ...)

The side effect of `re-search-forward' was to advance point, while
`looking-at' don't move. This does not matter anymore.

>
> Note that Org does not use \\s- but the simpler [ \t].
>
> Also, the regexp assumes the table end with a newline character, which
> may not be the case.
>
>>               (unless (re-search-forward "\\=\\s-*\\([^|\n]*\\)\\(|?\\)" end t)
>>                 (user-error "Malformed table at char %s" (point)))
> This cannot happen. The regexp above matches anything, i.e., the empty
> string.

Right! I didn't noticed...

>
>>               (goto-char (match-end 1))
>>               (skip-chars-backward " \t" (match-beginning 1))
>>               (push
>>                (buffer-substring-no-properties (match-beginning 1) (point))
>>                row)
>>               (goto-char (match-end 2)))
>>             (push (nreverse row) table)))
>>         (nreverse table)))))
> I applied your suggestion, with a few simplifications. Hopefully, it
> squeezed a bit more the execution time. Let me know!

Yes! 25%
My two unit tests give correct results.

>
>> The new implementation can be more than 100 times faster. This enhances
>> responsiveness of Babel or Gnuplot blocks handling thousands long
>> tables.
> Looks good. However, we didn't change the signature, so I didn't add
> this to ORG-NEWS. It is in the commit message, tho.
>
> Thank you!
>
Nice team work, thank you too!
Thierry Banel

Re: [ANN] faster org-table-to-lisp

[Nicolas Goaziou]

Hello,

tbanelwebmin <tbanelwebmin@free.fr> writes:

> Nicolas, how did you do that? Your version is 25% faster than mine,
> and the code is 33% shorter! Very elegant.

Thank you. There's nothing fancy, really.

The main difference is that it does not call `org-table-end'. Minor
tweaks are:

- use simpler regexps,
- call `skip-chars-forward' whenever possible.

> Sorry, I may not understood what you said:
> = Since you're changing the signature, I suggest to provide the table
> = element instead of ORG-AT-TABLE-P. AFAICT, `org-babel-read-element',
> = through `org-babel-read-table', would greatly benefit from this.
>
> Could you elaborate (if still relevant)?

If you know the table ELEMENT, you don't need to check if you're at
a table, nor do you need to compute table boundaries. We could have made
use of this information to avoid a call to `org-at-table-p', much like
your initial intent.

Thinking about it, we don't even need to call `org-at-table-p' at all.
Indeed, this is a low-level, non-interactive, function. We can
reasonably expect the callers to check if they are really at a table in
the first place.

It would increase speed for this function noticeably, and the ELEMENT
argument would not be relevant anymore.

WDYT?

> The side effect of `re-search-forward' was to advance point, while
> `looking-at' don't move.

Ah true. I overlooked that.

Regards,

-- 
Nicolas Goaziou

Re: [ANN] faster org-table-to-lisp

[tbanelwebmin]

Le 01/05/2020 à 12:15, Nicolas Goaziou a écrit :

> Hello,
>
> tbanelwebmin <tbanelwebmin@free.fr> writes:
>
>> Nicolas, how did you do that? Your version is 25% faster than mine,
>> and the code is 33% shorter! Very elegant.
> Thank you. There's nothing fancy, really.
>
> The main difference is that it does not call `org-table-end'. Minor
> tweaks are:
>
> - use simpler regexps,
> - call `skip-chars-forward' whenever possible.

I realized that not calling `org-table-end' may cause a corner case:

| 2 | b |
| c | d |
#+TBLFM: @1$1=2||3

is read as:
(("2" "b") ("c" "d") ("" "3"))
because of the "|" just below the table.

This can be fixed by changing the ending condition from
  (while (search-forward "|" (line-end-position) t)
to
  (while (re-search-forward "^[ \t]*|" (line-end-position) t)

Not a big deal.

>> Sorry, I may not understood what you said:
>> = Since you're changing the signature, I suggest to provide the table
>> = element instead of ORG-AT-TABLE-P. AFAICT, `org-babel-read-element',
>> = through `org-babel-read-table', would greatly benefit from this.
>>
>> Could you elaborate (if still relevant)?
> If you know the table ELEMENT, you don't need to check if you're at
> a table, nor do you need to compute table boundaries. We could have made
> use of this information to avoid a call to `org-at-table-p', much like
> your initial intent.
>
> Thinking about it, we don't even need to call `org-at-table-p' at all.
> Indeed, this is a low-level, non-interactive, function. We can
> reasonably expect the callers to check if they are really at a table in
> the first place.
>
> It would increase speed for this function noticeably, and the ELEMENT
> argument would not be relevant anymore.
>
> WDYT?

I do agree. We can expect callers to be on a table. If they are not,
they will get `nil', and instantly notice it.

>> The side effect of `re-search-forward' was to advance point, while
>> `looking-at' don't move.
> Ah true. I overlooked that.
>
> Regards,
> -- 
> Nicolas Goaziou
>
Have fun,
Thierry Banel

Re: [ANN] faster org-table-to-lisp

[Nicolas Goaziou]

tbanelwebmin <tbanelwebmin@free.fr> writes:

> I realized that not calling `org-table-end' may cause a corner case:
>
> | 2 | b |
> | c | d |
>
> #+TBLFM: @1$1=2||3

Indeed. I also realized this, and fixed it a couple of hours ago. You
will notice I shamelessly used your "\\="© trick! :)

> I do agree. We can expect callers to be on a table. If they are not,
> they will get `nil', and instantly notice it.

Great. I removed the check and added an entry in ORG-NEWS. It shouldn't
make any speed difference in your monster table, because it is located
right after a headline. It will, however, help tremendously in tables
buried deep within a section.

Re: [ANN] faster org-table-to-lisp

[tbanelwebmin]

Le 01/05/2020 à 15:11, Nicolas Goaziou a écrit :

> Indeed. I also realized this, and fixed it a couple of hours ago. You
> will notice I shamelessly used your "\\="© trick! :)

This kind of shamelessness builds great communities :)

> Great. I removed the check and added an entry in ORG-NEWS. It shouldn't
> make any speed difference in your monster table, because it is located
> right after a headline. It will, however, help tremendously in tables
> buried deep within a section.

Well done.
There is a last cleanup that can be achieved
(or not, doesn't really matter):
simplifying two calls located in org-table.el:

(org-table-to-lisp
  (buffer-substring-no-properties (org-table-begin) (org-table-end)))

to:

(org-table-to-lisp)

Re: [ANN] faster org-table-to-lisp

[Nicolas Goaziou]

Hello,

tbanelwebmin <tbanelwebmin@free.fr> writes:

> There is a last cleanup that can be achieved
> (or not, doesn't really matter):
> simplifying two calls located in org-table.el:
>
> (org-table-to-lisp
>   (buffer-substring-no-properties (org-table-begin) (org-table-end)))
>
> to:
>
> (org-table-to-lisp)

Indeed. Done. Thank you.

Regards,

-- 
Nicolas Goaziou