Re: increment slowdown

On 2026-03-10 14:58, Bill Allombert wrote:
 > On Tue, Mar 10, 2026 at 02:05:38PM +0100, Ruud H.G. van Tol wrote:

 >> oeis.A005228:
 >>
 >> ? lista1(len)= my(r=List(1), d=1); while(#r<len, setsearch(r, d++) 
&& d++;
 >> listput(~r, r[#r]+d)); Vec(r);
 >> [...]
 >>
 >> ? lista2(len)= my(r=List(1), d=1); while(#r<len, d++; setsearch(r, d) &&
 >> d++; listput(~r, r[#r]+d)); Vec(r);
 >> [...]
 >>
 >> The first variant has the d++ inside the setsearch() call, and is much
 >> slower.
 >
 > Yes, this is a known limitation of the copy optimiser.
 > It is not able to check that d++ does not modify r, so it copies r.
 >
 > Imagine this example
 > r=[1,1,2];vecsearch(r,r[1]--)
 > the correct result is 0.
 > but
 > ? r=[1,1,2];r[1]--;vecsearch(r,r[1])
 > %14 = 1
 >
 > In general, to avoid this limitation, do not use the return values of 
x++ and
 > x+= , x-= , x*= etc.

Understood. That is indeed a tricky one to optimize for.
Maybe https://en.wikipedia.org/wiki/Peephole_optimization
Solving this, would make existing code run considerably faster, so is a 
nice challenge.



Another slightly faster variant:

? lista4(len)= my(d=1, r=List([1])); while(#r<len, setsearch(r, d+1) && 
d++; listput(~r, r[#r]+d++)); Vec(r);

? lista4(10001)[-10..-1]
cpu time = 11 ms, real time = 11 ms.
%20 = [50793733, 50803858, 50813984, 50824111, 50834239, 50844368, 
50854498, 50864629, 50874761, 50884894]


And a variant that sets d only once per iteration:

? lista5(len)= my(d=1, r=List([1])); while(#r<len, d+=2-!setsearch(r, 
d+1); listput(~r, r[#r]+d)); Vec(r);

? lista5(10001)[-10..-1]
cpu time = 12 ms, real time = 12 ms.
%30 = [50793733, 50803858, 50813984, 50824111, 50834239, 50844368, 
50854498, 50864629, 50874761, 50884894]


A way out might also be to support setsearch(~r, ...).

-- Ruud