Re: What's missing in ELisp that makes people want to use cl-lib?

[Michael Heerdegen]

João Távora <joaotavora@gmail.com> writes:

> Now really, sure?  What about those generic functions that you
> presumably have to shortcut?  Won't it break an existing contract to
> users that all of the sudden you're not calling them anymore for
> certain types of sequence?

If you don't make a mess, no.  It's of course possible to choose
different implementations (algorithms) for different types of sequences.
There a few technical reasons why seq.el should be slower.

> And how are you going to do this without introducing non-destructive
> versions of the seq.el utils?

That's a thing we probably can't do, yes.  But this shouldn't lead to
algorithms reaching a different complexity class, or running slower by a
factor N with large N.

Do we have places in the Emacs Elisp sources where this would make a
significant difference?

>  And wasn't it a goal here to end up with a smaller dictionary of such
> utils?  Won't it bloat up comparibly to cl-lib while still being less
> versatile?

The result will still be much smaller than cl-lib.  The idea is of
course not to use nonsense algorithms just to spare some dozens of
Bytes.

> > These kinds of benchmarks are more or less irrelevant.
>
> I beg to differ, I think a recommended sequence processing
> function that needlessly conses and takes orders of magnitude more
> time to do its job is really quite relevant.  Elisp is still a
> "LISt Processing" language by and large.
>
> But also, I have to ask: what _would_ be a relevant benchmark
> to you?

You misunderstood.  Of course do these benchmarks matter very much, but
as I said, please, this thread is not a seq.el bug report.  What I said
is that benchmarks do not much tell us about how our future treatment of
cl-lib should look like as long as seq.el can be improved and sped up
and you argument with seq.el efficiency.

> Just for cl-set-{n}difference, I'm seeing significant usage in core
> right now, direct _and_ indirect.  I'm not sure all the authors, let
> alone users, of these packages would like to learn that these parts of
> their code have suddenly become a full order of magnitude slower, let
> alone users using such things, by virtue of some cl-lib.el -> seq.el
> operation as is being suggested here.

These actually do not really fit in seq.el but would rather be a natural
part of set.el.

> No, the point is that it hasn't.  Some of the destructive versions
> weren't even destructive at all!  if you take a look at my code you'll
> notice I optimized cl-lib considerably in very few cases.
> There's a lot more that can be optimized there.

Other parts were optimized in the time, of course.

> The seq.el file has "optimized implementation for lists section" by
> tweaking the generics for lists.  I find plausible the designer of
> seq.el noticed that it is still much slower to do this but wanted to
> keep a specific generic function contract anyway.

Again, such a contract does _not_ per se have implications about
efficiency.  A seq.el implementation of a generic function for lists can
find the type is 'list' and then use exactly the same algorithm as
cl-lib.  All you have to do additionally is one check (`listp').
This is currently not the case everywhere in seq.el, some algorithms
perform repeated, strictly speaking redundant, tests, but that can (and
should be, where it matters) avoided.

> Finally, please note I'm not trying to bash seq.el.  I think it
> has its place -- polymorphic sequences are great, if I ever
> need them -- , but its use should _also_ be discriminate, not
> indiscriminate.  Same for your set.el idea: IMHO it's very welcome,
> but I think it will suffer (and gain, of course) from the same
> kind of tradeoffs as seq.el.

The only relevant question for me in this message is: is an improved
seq.el good enough to replace the sequence functions in cl-lib?  I think
it is.

To convince Eli that it is not, he would need something like a real-life
case where the seq.el functions make some program significantly slower,
and where we know that this can't be improved in seq.el (something like
sorting a million three-element lists in a row is not a good example).


Michael.