Improve /= on large numbers of arguments
Affects  Status  Importance  Assigned to  Milestone  

 SBCL 
Undecided

Unassigned 
Bug Description
The current algorithm for /= does O(N^2) comparisons on N arguments. For large N, it would be more efficient to use an EQUALP hash table (or a hash table specialized for numbers). The crossover is somewhere around N=60, by experiment using a standard EQUALP hash table created with :size N.
(Use of SXHASH and a Bloom filter might be even faster.)
description:  updated 
Stas Boukarev (stassats) wrote :  #1 
Paul F. Dietz (paulfdietz) wrote :  #2 
It's more than the mandated minimum value of callarguments
You might as well ask who creates vectors with more than 1024 elements (the mandated minimum value of arraydimension
Stas Boukarev (stassats) wrote :  #3 
Are 60 argument calls to /= as frequent and useful as large arrays?
Paul F. Dietz (paulfdietz) wrote :  #4 
Specifically for /=? Probably not (although (apply #'/= list) is a nice way to ask if there are any duplicates in list.) The general (apply fn list) idiom occurs with many nary builtins, and it would be nice to be able to apply it to arbitrary lists. I know this is not completely portable.
Stas Boukarev (stassats) wrote :  #5 
(apply #'/= list) is a nice way to blow the stack.
Paul F. Dietz (paulfdietz) wrote :  #6 
Yes, it fails somewhere above 200000 parameters. That makes me wonder why callarguments
If lambda
John Cowan (johnwcowan) wrote :  #7 
Granted that >2 arguments is not a typical case, the argument list can be sorted and each consecutive pair compared for inequality. This is O(n log n) rather than O(n^2), though it does require n additional cons cells; it is slower but less space overhead than a hash table.
Who calls /= with 60 arguments? That's even more than callargumentslimit.