MERGE is slow

Bug #408889 reported by Nikodemus Siivola on 2009-08-04
8
This bug affects 1 person
Affects Status Importance Assigned to Milestone
SBCL
Wishlist
Unassigned

Bug Description

MERGE is terribly slow currently, as it is not optimized at all based on types known at compile time: the same generic code is used always.

At least common cases

  (merge 'vector vector1 vector2 ...)
  (merge 'list list1 list2 ...)

should be dealt with, and possibly some cross-type cases as well.

tags: added: easy
Karol Swietlicki (abcdef123456) wrote :

I'll try to do something about this.
No promises, as usual.

Karol Swietlicki

rrl (endian-sign) wrote :

Could someone review this patch please? Thanks.

tags: added: review
Antonis Kanouras (akanouras) wrote :

Typo @L71: "sequunce2" .

Just a passerby - this is not a review. :)

rrl (endian-sign) wrote :

Oops. I totally missed that one. Fixed.

Hi! Thank you for the patch. Here's some kind of review:

* the fact that the `sequunce2' typo was uncaught suggests that our regression tests don't cover that branch (or did the tests not run?). It would be nice if there were explicit tests for each of the branches in these new transforms.

* why do we need the :load-toplevel clauses in sort.lisp? Oh, because some of the things the deftransforms expand to are macros. That's going to lead to quite a substantial amount of code bloat; a simple (merge 'simple-vector ...) is going to expand into a heap of inline code. I think it would be better if there was a merge-vector function for the deftransform to expand to, at least if optimize space > optimize speed

* I don't think it's true that if you do (merge 'vector x1 x2 #'<) that it is necessarily true that x1 and x2 are vectors, but I think your transform assumes that it is. (Similarly, lists). I think you either need some explicit coercions, or you need to restrict the transforms' applicability. (You can probably put in the coercions only if you can't prove that they're unnecessary). Again, I think some test cases would have helped to find this.

* I don't know the answer to this: does &key (key function) mean that it is required that the &key argument is a function? What happens if it's not present. (Also, what happens if it's a symbol?)

To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers