MERGE is slow

[Nikodemus Siivola]

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.

[Karol Swietlicki (abcdef123456)]

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

Karol Swietlicki

[rrl (endian-sign)]

Could someone review this patch please? Thanks.

[Antonis Kanouras (akanouras)]

Typo @L71: "sequunce2" .

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

[rrl (endian-sign)]

Oops. I totally missed that one. Fixed.

[Christophe Rhodes (csr21-cantab)]

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?)