Re: Performance issue w/ `cl-loop`s `collect...into`

[Tianxiang Xiong]

IIUC the `(eq var cl--loop-accum-var)` is used to test whether the accumulation is `into` or not. If not, clauses like `collect(ing)` use a `cons-nreverse` rather than `nconc` algorithm, which is O(n) instead of O(n^2). Since we're doing `setcdr` in all cases where the accumulation is into a list, we're always O(n), so the optimization is unnecessary.

Attached is a new patch that uses `(cl--loop-accum-var)`.

On Sun, Apr 8, 2018 at 6:59 PM, Stefan Monnier <address@hidden> wrote:

> Here's a second, cleaner attempt that separates the `cl--loop-handle-accum`
> function into two functions, one to deal with lists and one to deal w/
> non-lists.
> The tail-tracking optimizing is also applied to `append(ing)` and
> `nconc(ing)`.

Thanks.  Looks good.
I see you've dropped the (eq var cl--loop-accum-var) optimization.
Have you tried to measure the effect?


        Stefan


> +(defun cl--loop-handle-accum (def)
[...]
> +  (cond
[...]
> +    (cl--loop-accum-var cl--loop-accum-var)

You can write this line as just

       (cl--loop-accum-var)


-- Stefan

0003-Optimize-collect.into.patch
Description: Text Data