Reduce performance penalty in Remove caused by method dispatch overhead for lists?

[frankluebeck]

When fixing a bug in a kernel method for Remove I noticed the following:

gap> l := List([1..100000], i->[i]);;
gap> while Length(l)>0 do Remove(l); od; time;
8
gap> l := List([1..100000], i->[i]);;
gap> while Length(l)>0 do Remove(l,Length(l)); od; time;
134912
gap> l := List([1..100000], i->[i]);;
gap> while Length(l)>0 do Unbind(l[Length(l)]); od; time;
12
gap> l := List([1..100000], i->[i]);;
gap> met := ApplicableMethod(Remove, [l,1]);
function( l, p ) ... end
gap> while Length(l)>0 do met(l, Length(l)); od; time;
152

This shows that

• the fast kernel function (which had a bug for plists with holes) is not really needed, just use Unbind
• we have still not addressed the general problem that it is sometimes far too expensive to compute the type of a list (almost all the time in the second loop of the example is spent on this, although all the information which is expensive to gather is completely irrelevant here)

I don't see a quick and compatible way to improve the second loop. If we proceeded as in other cases (the last I remember was Reversed) we could change Remove to a function which catches the main cases of internal lists efficiently and calls a newly introduced operation RemoveOp for other cases. The disadvantage of this approach is that current method installations for Remove must be adjusted.

But maybe this is not worth the effort and the time could be spent better on addressing the problem in general?

Further remarks:

• if I understand the (complicated) mechanism with the current kernel operation correctly, then the method met in the fourth loop of the example is never called and could be removed
• the current kernel method for Remove with one argument shrinks the memory allocated for a list when its length becomes less than 3/4 of the available entries. Maybe this should be done by UnbPlist in general?

[ChrisJefferson]

Could you (or one of the other GAP developers who has been around for a while) give a brief explanation of exactly what it is that makes lists slow, and an example or two or where it is useful? I've never really fully understood the problem (I know it is to do with detecting the type of the list)

[markuspf]

This seems related to #798 in some way.

[fingolfin]

We now have InstallEarlyMethod to deal with this kind of problem; fix in PR #5300