[Spec2] Fix Performance Issue of Unform in every-impl
Description
Problem
The implementation of unform* in every-impl uses clojure.core/count to determine the end of the collection it loops over. In case the collection is a list, count is O(n). Because count is called at every loop iteration, unforming becomes O(n^2).
I found this performance issue while profiling an application that uses lists with a size of 500. The speedup after the patch is 3.
Solution
I simply used the vseq binding that was already there, but unused. The same vseq binding is used above in conform* in exactly the same situation.
Patch
CLJ-2598-1.patch
Environment
Activity
Sorry, I did not reopen the issue. Please see my last comment for patch and explanation.
Sorry for the wrong patch format. I created CLJ-2598-2.patch according to the docu.
The collection I encountered was a sequence obtained from take. My patch is in unform* not inconform*. The indexed? check is in conform*. If you like me to add a separate implementation for indexed collections, avoiding seq, I could do it. Maybe even in a separate issue. My patch doesn’t introduce seq.
Patch
CLJ-2598-2.patch
Marking this NR for now, but please reopen (or comment with more info) if you have it.
It seems like the O(n^2) would only happen if x is `indexed?` but not `counted?`. Lists/seqs are not indexed so would not go through this case. I'm kind of curious what type fits in that combination that you're seeing this with (usually something indexed like a vector also has a known sublinear count function). Can you supply an example (or better, a test)?
I think the intent of not using vseq in this branch is specifically to avoid seq'ing a non-seq. In summary, this does not look like a good fix to the problem. Probably pulling out (count x) so it's done once seems better.
Also, the patch is not proper patch format for use with git apply (this is a diff) - see https://clojure.org/dev/developing_patches#_coding for a how to on making patches that can be applied.
