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

[João Távora]

On Tue, Nov 14, 2023 at 11:47 AM Dmitry Gutov <dmitry@gutov.dev> wrote:

> I don't think it's unbounded, just high. And 12-element list is a nice
> size for this particular comparison. Programs using tiny list would in
> their majority be tiny as well, so it wouldn't matter.
>
> Though of course there are exceptions: compilers, for example.

Yes, of course, of which there are many in Lisp: every macro
is one.  And most of the uses for set difference operations that I
see in core seem to be for relatively small lists.  Just because
for large sets (at least for large list2), lists are inherently
not good anyway because quadratic ;-)

> > (defun myequal (a b)
> >    (equal a b))
> >
> > (setq cc (make-list 12 "blabla"))
> > (setq list2 (make-list 12 "shooveedoowaa"))
> >
> > (when nil
> >    ;; (0.106080265 4 0.03849865399999963)
> >    (benchmark-run 10000 (cl-set-difference cc list2 :test #'myequal))
> >    ;; (0.5504704210000001 39 0.394207416)
> >    (benchmark-run 10000 (seq-difference-3 cc list2 #'myequal))
> >
> >     )
> >
> > I get the 5.5x slowdown again (in one experiment, not shown,
>
> Right. This is still for the small lists case.

Not sure.  I don't have time to test now, but the custom #'myequal
predicates negates your seq-do shortcut (which is probably illegal anyway,
but let's pretend it isn't).  If that shortcut is negated, things
become slower than in the pred=#'equal case, no?

> > Your seq-difference-3 doesn't call seq-do like the original seq-difference
> > does, so the set difference operations for those custom sequences might
> > well be broken.  What's even more problematic is that it skips seq-do
> > entirely for certain predicates and not entirely for certain other
> > predicates.
>
> The way I understand this, is any new sequence type has to implement
> seq-do. As soon as that happens, a lot of (probably all) sequence
> functions in seq.el start working on that type.

Right.  But seq-difference-3 doesn't call into seq-do anymore,
at least not always and not in the same way.  So today, _before_
your seq-difference "skips-the-seq-do" optimization, a given person's
set difference operations would work just fine for their custom
data type.  The person is happy and doesn't care about seq.el's
performance.

One day they upgrade seq.el which comes with your optimization to
seq-difference, and that code is mysteriously broken.  Worse  for some
equality predicates it is broken  in a given way, for other equality
predicates it's a different error.

Can't you see the fundamental problem?

> > the application controls both the data type and knows exactly the shortcuts
> > taken.  But then "private library" is an oxymoron.
>
> An application shouldn't be customizing separate entry points.

Right.  We agree.  It makes no sense.

> Separate
> libs (providing new data types) can do that. E.g. if we have a lib
> providing lazy sequences, it can provide its own set of implementations
> for seq.el. And when doing that, make sure the resulting behavior is
> consistent between functions.

Right, but then if they fail the customization of the entry point
generic like not calling the right generics at the right time, then
_other_  customizations of _other_ generics won't be called, or will
be called too much.  Just like in your seq-difference-3 optimization
the user code breaks.

> > cl-{n}set-difference  are standard stuff in the CL world.   There are even
> > reference LOOP implementations (likely much more performant than ours,
> > though possibly not compatible with some non-standard edge cases our
> > cl-loop has of which I know a couple).
>
> I do believe it's helpful to have it around.

What is?

> > Seq-some also calls into a lot of user customizable code, so it'll
> > suffer from the same class of problems.  Say, are you going to skip
> > the seq-do generic sometimes there as well?
>
> I believe so.

Then my seq-do methods will just stop being called.

> It looks very much inspired, both in naming and in the implementation
> approach. But it's not a carbon copy (much farther from it than in
> cl-lib's example), and our VM is also quite different from JVM in
> performance characteristics.

OK, but naming and implementation are exactly the two least
important things that don't matter much here.  What matters are the
interfaces, the contracts for the implementor's interface and user's
interface: which would specify exactly how those generic functions
are expected to cooperate with each other.  This is what has to be
written down in a generic protocol.

João