GNU bug report logs - #76017
31.0.50; Which args can cl-nintersection and cl-nset-difference mutate?

Previous Next

Full log

Message #11 received at 76017 <at> debbugs.gnu.org (full text, mbox):

From: "Basil L. Contovounesios" <basil <at> contovou.net>
To: Pip Cet <pipcet <at> protonmail.com>
Cc: Mattias Engdegård <mattias.engdegard <at> gmail.com>,
 Stefan Monnier <monnier <at> iro.umontreal.ca>, 76017 <at> debbugs.gnu.org
Subject: Re: bug#76017: 31.0.50; Which args can cl-nintersection and
 cl-nset-difference mutate?
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

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.