[Agda] type check cost

Sergei Meshveliani mechvel at botik.ru
Sun Aug 20 15:22:23 CEST 2017


Dear Agda developers,

Please, investigate the possibility to reduce the type check cost
for Agda programs.


Example of application
----------------------

The library DoCon-A-0.04.1 needs the minimum of  8 Gb 
heap to type-check at a single command,
and for -M8G, the time is  60 minutes  for a 3 GHz machine.

DoCon-A-2.00  needs the minimum of  11 Gb,  and it takes  70 minutes.

DoCon-A-2.00  adds several methods. But there is only one of them 
that may pretend to complicate type-checking. This is a proof for 
an optimized method for fraction addition. There is a hierarchy of 
parametrized modules. The method does not bring any new structures or 
new parametrized module, but it uses several instances of existing 
modules.

In both programs, the longest type-check place is the module    
                                                      Int.Integer2
(1/5 of all the time).
This is because it uses certain instances of almost all the generic 
structures and imports certain instances of all parametric modules
implemented in the DoCon-A library.

Now, each step in developing the library will probably increase the 
memory requirement on somewhat 1/4.

On the other hand, DoCon-A-2.00 supports only about 1/100 of the methods
in the DoCon library written in Haskell in 1990-ies
(but it contains many definitions and proofs which are not in DoCon).



This is not my personal problem
-------------------------------
I expect that anyone who tries to implement any essential generic 
mathematical library in Agda will be stopped by this barrier.


Main problem
------------
Probably, this is an internal type representation that does not really 
use sharing, so that large subterms are copied many times.


I also have a specific question
-------------------------------

I wrote earlier of the example, when type-checking  (s , t)  costs
infinitely much, while adding the type declaration for this pair makes
it cost small. And I expect that in the first variant the result is
going to be "unsolved metas".

DoCon-A-2.00 takes 70 minutes to type-check for the -M11G option.
May it happen so that adding a type declaration somewhere in a lucky
place will reduces the cost essentially?

Regards,

------
Sergei




More information about the Agda mailing list