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

[Stefan Monnier <monnier@IRO.UMontreal.CA>]

> 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.

I agree that the algorithmic complexity of "cons+nreverse" is no better
than that of the setcdr, but that doesn't mean that it's the same speed.
Since (eq var cl--loop-accum-var) is expected to be the most common
case, it'd be good to make sure that your patch doesn't make the
code slower, hence the need to test the performance.


        Stefan


> Attached is a new patch that uses `(cl--loop-accum-var)`.
>
> On Sun, Apr 8, 2018 at 6:59 PM, Stefan Monnier <monnier@iro.umontreal.ca>
> 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
>>
>>
>>