Re: increment slowdown

["Ruud H.G. van Tol" <rvtol@isolution.nl>]

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