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

[João Távora]

On Tue, Nov 14, 2023 at 2:46 PM Michael Heerdegen
<michael_heerdegen@web.de> wrote:
>
> 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.

Beg to differ.  See my latest benchmarks sent to Dmitry and his
updated code in feature/cl-lib-improvements.  Sure, it can be argues
that you can make it not as horribly slow as it is in some cases,
but never quite as fast.  And you'll be breaking compatibility all
the way, the further you go.

> > 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.

Of course, algorithms don't change complexity :-) That would have
been too terrible.  But when you compare non-destructive versions of
some seq operations to cl-lib destructive operations "that we
probably can't do", you will see large N.  A snippet from my results
(again, see message to Dmitry with these files).

("set difference, small lists, custom pred"
  (cl-nset-difference "FASTEST" 0.201229483 15 0.11990391199999983)
  (cl-set-difference "5.0x SLOWER" 1.002034638 39 0.31673883500000066)
  (seq-difference-3 "15.6x (rel 3.1x) SLOWER" 3.136544874 194
   1.7686539850000003)
  (seq-difference "18.9x (rel 1.2x) SLOWER" 3.795912411 260
 2.140581182000002))
 ("set difference, big lists, custom pred"
  (cl-nset-difference "FASTEST" 0.011600632 0 0.0)
  (cl-set-difference "5.4x SLOWER" 0.062588482 1 0.008457714000000394)
  (seq-difference-3 "18.1x (rel 3.4x) SLOWER" 0.21003662699999998 12
   0.10525734000000142)
  (seq-difference "25.5x (rel 1.4x) SLOWER" 0.29535328699999996 19
 0.16559472099999972))

Where seq-difference-3's is what I think is Dmitry's best attempt
so far.

> 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.

It's completely unfair to compare seq.el to cl-lib.el in general.
You should be comparing to the cl-lib's sequence dictionary.

This is such a common (and annoying I must say) misconception

Here's the sequences dictionary summarized directly from the
CL Hyperspec.

   https://www.lispworks.com/documentation/lw70/CLHS/Body/c_sequen.htm

Notice how neatly organized it is.  Compare it to the seq.el shortdoc.
I don't see a big difference in size, do you?  When compared directly
to the cl-lib.el versions seq.el are almost always less versatile
and often greatly less versatile (not to mention slow as heck at least
int the current form).

Sure it has interesting things like seq-group, but it is missing
other interesting things like the "mismatch" operations, and
super-important things like destructive versions of things.

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

But they're there.  Are they bloat?  I think it's pretty good to
have these "set difference" operations on lists, even if it obviously
the naming is off (as it is in mnay other languages by the way).

Anyway naming aside sometimes it's just what you want.  Of course,
if you also want fast, use cl-lib.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.

And so were seq's

>
> > 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.

Of course it does.  The "list optimizations" I pointed to, are
designed for efficiency, to state the obvious.  And they already break
the contract laid out in the very spare seq.el documentation
that I only need to implement those 6 or 7 generics to have
a fully functioning custom seq.  I need only make something based
on lists or arrays to be bitten in the tail by those optimizations.
And even without this "based on lists" thing, the seq-contains-p
performance hog had to be circumvented by changing the contract,
changing the imaginary lines where it said

   "the user agrees to implement seq-contains-p"

to

   "the user agrees to implement seq-contains-pred"

> > 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.

An "improved" seq.el?  Sure, maybe.  As we say in my country,
"if my grandmother had wheels whe should be school bus".  Let's see
what wheels you put on seq.el.

Currently, please no.  DO use seq.el for custom sequences, or when
there is good suspicion that custom sequences might appear.  Do NOT
use seq.el for macro expansions, bread and butter list processing, etc.
Do NOT use seq-let for example in anything that might eventually
be called many times.

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

I think we should be cautious instead, and take those benchmarks
seriously (like Dmitry is taking them).

João