[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

None

Activity

Show:
Alex Miller
January 4, 2021, 7:13 PM

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.

Alex Miller
January 5, 2021, 3:42 PM

Marking this NR for now, but please reopen (or comment with more info) if you have it.

Alexander Kiel
January 5, 2021, 4:02 PM

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

Alexander Kiel
January 5, 2021, 5:36 PM

Sorry, I did not reopen the issue. Please see my last comment for patch and explanation.

Assignee

Unassigned

Reporter

Alexander Kiel

Labels

Approval

None

Patch

Code

Priority

Major