Subject: bug#76017: 31.0.50; Which args can cl-nintersection and cl-nset-difference mutate?

From: "Basil L. Contovounesios" <[email-masked]>
Date: Sun, 02 Feb 2025 20:13:14 +0100

Pip Cet [2025-02-02 18:30 +0000] wrote:

> So no storage is ever reused, right?

Right.

> So is this about the optimizations that cl-nintersection might in theory
> one day perform, but didn't do in 1993 and doesn't do today?

Yes, but more importantly about fixing the inconsistent docs.

>> - It is the weaker of the two requirements, thus backward-compatible.
>
> "weaker" in the sense that it gives the Lisp hacker more options, and
> the Lisp implementor fewer options.  I think we should go for "simpler":
> assume both arguments may be mutated, and don't worry about specifying
> them in the "right" order.

It may be 'simpler' by some measure but it's also less backward-compatible.

>> - Set difference implementations do not naturally benefit from modifying
>>   the second set (though I would love to see a counterexample).
>
> I'm not sure I agree.  If you've got a cheap population count, you start
> with the smaller set and throw out unnecessary elements, returning that
> set.

Not sure I understand how that works - could you give an example please?

Given that set difference is not commutative, I don't immediately see
how picking the smaller set can help.  And since set difference is the
complement of the second set wrt the first, I don't immediately see how
any of the population (and thus storage) of the second set can survive
the operation (i.e. be reused to greater effect than by reusing the
first set's).

>> - Callers of cl-nintersection having to ensure both arguments are safe
>>   to mutate (e.g. through excessive copying) could diminish any
>>   performance benefit it has over cl-intersection.
>
> Which is 0, right?

Today it's actually worse than 0, since there's the funcall overhead in
the absence of inlining.  Hence 'any [potential] performance benefit'.

Thanks,
-- 
Basil