Optimizing MorphismsOfExternalHom in FinQuivers

[zickgraf]

Optimizing MorphismsOfExternalHom in FinQuivers comes down to optimizing the homomorphism structure:

https://github.com/homalg-project/Toposes/blob/0f4a0d1c29afb47da7f1e29e5ac407a599e33069/gap/ToposDerivedMethods.gi#L293-L311

This in turn comes down to optimizing the computation of the Limit of ExternalHomDiagram in FinSets:
https://github.com/homalg-project/FunctorCategories/blob/3937a2464545ba6d656997dd5fa08a225f9faf38/gap/PreSheaves.gi#L1390-L1399

This Limit is a binary equalizer, which is a Filtered in FinSets.

Structure of HomomorphismStructureOnObjects in FinQuivers:

https://github.com/homalg-project/FunctorCategories/blob/60b029a10930cf40b3b5caf31e7896edf660e2f7/gap/precompiled_categories/FinQuiversPrecompiled.gi#L80

The loops over the very large range deduped_26_1 are the expensive parts of the code.
The code selects (Filtered) all the numbers in deduped_26_1 for which a certain equality holds.
The equality compares two 4-digit numbers in base deduped_31_1.
The number on the left-hand side of the equality is [ deduped_1_2, deduped_1_2, deduped_2_2, deduped_2_2 ] (little-endian, i.e. least significant bit first).
deduped_1_2 and deduped_2_2 can easily be enumerated, because they are constructed as i -> REM_INT( QUO_INT( i, ... ), deduped_31_1 ).
The digits of the number on the right-hand side of the equality come from compositions of maps in FinSets. The first and the third digit arise from a composition with a REM_INT construction, the second and the forth digit arise from a composition with a REM_INT( QUO_INT( i, ... ), ... ) construction. So this is more intricate and probably the source of the semantics of the whole construction.

I see two approaches for further optimizations:

1. Compare the two numbers digit-wise and only compute digit n + 1 if digit n matches (i.e. reduce the work done in the loops over deduped_26_1).
2. Enumerate the selected numbers in the result using combinatorics instead of checking all possible combinations (i.e. get rid of the loops over deduped_26_1 completely).

Both optimizations seem to go beyond the usual peephole optimizations implemented in logic functions and templates, so they have to be done manually first. Afterwards we can look at how to teach those strategies to the compiler.

@mohamed-barakat: I think you once said that you could read off the length of the result easily from the input. If you could also construct the numbers in the result with a similar reasoning, that would directly give us solution 2.

[mohamed-barakat]

Thank you a lot for the thorough analysis.

@mohamed-barakat: I think you once said that you could read off the length of the result easily from the input. If you could also construct the numbers in the result with a similar reasoning, that would directly give us solution 2.

Only in special cases, e.g., when the second argument is the subobject classifier.