Crisp caching is broken (presumably)

[zickgraf]

I'm not sure if the following is a bug, but it is unexpected for me. Consider the following code:

LoadPackage( "CAP" );

SetDefaultCachingCrisp();

cat := CreateCapCategory( );
myobj := SymmetricGroup( 3 );
AddObject( cat, myobj );

AddKernelObject( cat, function( a )
    
    Display( "KernelObject" );
    
    return myobj;
    
end );

AddIsEqualForMorphisms( cat, function( a, b )
    
    return true;
    
end );

AddIsEqualForCacheForMorphisms( cat, function( a, b )
    
    return true;
    
end );

Finalize( cat );

mymor1 := GroupHomomorphismByImages( myobj, myobj );
AddMorphism( cat, mymor1 );
KernelObject( mymor1 );


mymor2 := GroupHomomorphismByImages( myobj, myobj );
AddMorphism( cat, mymor2 );
KernelObject( mymor2 );

mymor1 := fail;
mymor2 := fail;

GASMAN( "collect" );
Display( "collected" );

mymor := GroupHomomorphismByImages( myobj, myobj );
AddMorphism( cat, mymor );
KernelObject( mymor );

Since I use crisp caching and all my morphisms are equal (w.r.t. IsEqualForCacheForMorphisms), I expect the last KernelObject( mymor ); not to trigger a computation. However, it does, because the keys of cat!.caches.KernelObject are a weak pointer list although IsCrispCache( cat!.caches.KernelObject ) is true.

The documentation in ToolsForHomalg states

However, caches can be set to store the value permanently (crisp)

This is true, the value is stored in a non-weak pointer list. However, is there a situation where it makes sense to permanently store the value but drop the lookup key? And: cat!.caches.KernelObject actually has an entry crisp_keys which is never populated.

So I'm not sure if

1. this is working as intended,
2. CAP is using ToolsForHomalg in a wrong way (for example, maybe it should populate cat!.caches.KernelObject!.crisp_keys?),
3. this is a bug in ToolsForHomalg.

Another note: Thinking about it, I do not think it is necessary to use a crisp cache when using IsIdenticalObj for the equality of morphisms: If I lose access to a morphism, I will never again be able to create a morphism which is equal to it (w.r.t. IsEqualForMorphisms = IsIdenticalObj). Thus, I cannot even generate equal input, so I do not have to think about equal output. The only thing I should not do is flush the caches. However, this is never done in CAP/ToolsForHomalg, or am I wrong?

[zickgraf]

Thinking more about this, I think this is actually working as intended and I have even given the explanation in my note above :D

Assume that we compare morphisms with IsIdenticalObj. If we lose access to the morphism, we can remove it from the cache, as we can never construct a morphism equal to the original one anyway. However, we must make sure that we keep the value even if it is never referenced anymore (in this case, a "flush" could actually occur by the garbage collection).

This leads to further thoughts:

1. Can/should the cached value be deleted if the keys are deleted? (saving memory)
2. If an operation depends on a random source, crisp caching does not save me: If I lose access to the input, the keys might be dropped. If I then manage to construct an input equal to the original one later on and apply the operation again, I might get a different result.
3. If the value is not referenced anymore, in which way can it still be relevant for the specification "equal input must give equal output"? If this is simply a technical statement about all objects/morphisms currently existing in my session, a value which is not referenced anywhere does not influence the statement.

I will have to think about this.

[sebastianpos]

The crisp caching was designed to facilitate the implementation of categories which use IsIdenticalObj for IsEqualForObjects. In this case, the input cache can nevertheless be weak, since, as you stated, if I lose my reference to an object, I can virtually never create an equal object again in the same session. The output cache is crisp, since otherwise, concatenation of basic operations would fail to satisfy "equal input must give equal output", as it is described in Example 2.6 of the CAP manual.

Of course, the choice of this behaviour relies on the fact that, once a reference to an object is lost, it is virtually impossible to create an equal object in the same session again. If you are interested in having "really crisp" caches for situations where it is possible to create once lost objects again, then we can think about a solution for that. However, I don't see yet a situation of relevance for such a behaviour.

[zickgraf]

Thanks for the thorough explanation!

If you are interested in having "really crisp" caches for situations where it is possible to create once lost objects again, then we can think about a solution for that. However, I don't see yet a situation of relevance for such a behaviour.

We once had such a situation in FinSetsForCAP (for reference: https://github.com/homalg-project/FinSetsForCAP/issues/20). There we could change the representation of the input in a way which was stable under IsEqualForObjects, but the corresponding output would be different with regard to IsEqualForObjects. Since then I thought that crisp caching would save me in such a situation :D However, this was solved in another way, so there is no need for action.

This settles the second of my points above. I would like to keep this issue open until I have thought more about 1. and 3., if that's fine with you.

[zickgraf]

I have now looked at Example 2.6 in the CAP manual and I'm a bit confused. If I understand everything correctly, this is a situation where it is possible to create once lost objects again: I can forget the object A but later reconstruct it again using the zero matrix. Thus, in this situation crisp caching would not save me, or am I missing something?

[sebastianpos]

Yes, you are right. Indeed, in that example, you would need what I called "really crisp" caches above, which, apparently, we do not support yet.

Nevertheless, the example is still valid for explaining my point on why the crisp cache cannot lose its output.

Moreover, in an actual implementation of a situation like Example 2.6, I would recommend to use IsIdenticalObj for IsEqualForObjects + crisp caching as it is implemented at the moment.

[zickgraf]

Nevertheless, the example is still valid for explaining my point on why the crisp cache cannot lose its output.

Ah, I now understand that this also addresses my third point: even if a value is not referenced anymore, it could still have influenced another value which might be still referenced.

Then only my first point remains. If the keys are dropped, could we then also drop the value? I do not see a reason why we would have to keep it, but all of this seems rather intricate.

Moreover, in an actual implementation of a situation like Example 2.6, I would recommend to use IsIdenticalObj for IsEqualForObjects + crisp caching as it is implemented at the moment.

I will try to update the example accordingly, if that's okay.