Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Universe Polymorphism checking inside opaque terms? (Difference between [Qed.] vs [Opaque]) #48

Open
JasonGross opened this issue Jun 26, 2013 · 7 comments

Comments

@JasonGross
Copy link

I have some code in a file Functor.v, that when I change two lemmas from Lemma foo : fooT. ... Qed. to Lemma foo : fooT. ... Defined. Global Opaque foo., the time to compile another file shoots up from around 4 minutes to around 90 minutes (I think; I haven't yet fully tracked down the issue, but I'm somewhat confident this is the issue).

With Qeds, the times are:

jgross@cagnode17:~/catdb$ time coqc -q -I . -dont-load-proofs LaxCommaCategory

real    3m47.426s
user    3m45.970s
sys     0m1.300s
jgross@cagnode17:~/catdb$ time coqc -q -I . LaxCommaCategory

real    4m3.526s
user    4m1.895s
sys     0m1.300s

With Defined + Opaque, the time is

real    119m57.947s
user    118m8.419s
sys     0m2.748s

Is universe polymorphism checked differently for Qeded lemmas vs opaque lemmas?

@mattam82
Copy link
Member

Le 26 juin 2013 à 21:15, Jason Gross notifications@github.com a écrit :

I have some code in a file Functor.v, that when I change two lemmas from Lemma foo : fooT. ... Qed. to Lemma foo : fooT. ... Defined. Global Opaque foo., the time to compile another file shoots up from around 4 minutes to around 90 minutes (I think; I haven't yet fully tracked down the issue, but I'm somewhat confident this is the issue).

That's quite possible. As others have mentioned on coq-club, the kernel conversion does
not respect opacity information and might hence unfold large proof terms while the unification
algorithm doesn't. Due to the backtracking semantics of unification, if somewhere a unification
failed on a first order unification f t = f u where f is opaque, but succeeded globally, the
kernel conversion will likely take the same path, fail on first order unification as well
but additionally try unifying the expansions of [f], resulting in disastrous performance.
Honoring the opaque flag would endanger subject reduction though. We could reorder conversions
to try expansion at very last resort but that might raise other problems…
Btw, for your performance problems, I'd be curious if you tried branch projbundle of
https://www.pps.univ-paris-diderot.fr/~sozeau/repos/CoqUnivs which contains a version of
Coq deactivating universes but using an optimized representation of record projections.

-- Matthieu

@JasonGross
Copy link
Author

I have not tried that branch. I just tried to compile it, and got

$ ./configure -debug -prefix "$(readlink -f ~/.local64)"
...
$ make -j16 -k
...
$ make -j16 -k
make --warn-undefined-variable --no-builtin-rules -f Makefile.build "world"
make[1]: Entering directory `/afs/csail.mit.edu/u/j/jgross/CoqUnivs'
OCAMLDEP  ide/coqide_main_opt.ml
make[1]: Leaving directory `/afs/csail.mit.edu/u/j/jgross/CoqUnivs'
make[1]: Entering directory `/afs/csail.mit.edu/u/j/jgross/CoqUnivs'
CHECK revision
COQC      theories/Numbers/Integer/BigZ/BigZ.v
make[1]: *** [theories/Numbers/Integer/BigZ/BigZ.vo] Segmentation fault
make[1]: *** [theories/Numbers/Integer/BigZ/BigZ.vo] Deleting file `theories/Numbers/Integer/BigZ/BigZ.glob'
make[1]: Target `world' not remade because of errors.
make[1]: Leaving directory `/afs/csail.mit.edu/u/j/jgross/CoqUnivs'
make: *** [world] Error 2
make: Target `NOARG' not remade because of errors.

I will now try it without the -debug flag.

@JasonGross
Copy link
Author

I have tried removing the arguments to ./configure; I still get a segfault. Is is possible that my version of ocaml 4.00.1 is too new or something?

@JasonGross
Copy link
Author

Oh, oops, that was the master branch. Trying the projbundle branch now.

@mattam82
Copy link
Member

Hi Jason,

I think it's the native compiler's fault. Try ./configure with -no-native-compiler.
-- Matthieu

Le 27 juin 2013 à 21:45, Jason Gross notifications@github.com a écrit :

I have not tried that branch. I just tried to compile it, and got

$ ./configure -debug -prefix "$(readlink -f ~/.local64)"
...
$ make -j16 -k
...
$ make -j16 -k
make --warn-undefined-variable --no-builtin-rules -f Makefile.build "world"
make[1]: Entering directory /afs/csail.mit.edu/u/j/jgross/CoqUnivs' OCAMLDEP ide/coqide_main_opt.ml make[1]: Leaving directory/afs/csail.mit.edu/u/j/jgross/CoqUnivs'
make[1]: Entering directory /afs/csail.mit.edu/u/j/jgross/CoqUnivs' CHECK revision COQC theories/Numbers/Integer/BigZ/BigZ.v make[1]: *** [theories/Numbers/Integer/BigZ/BigZ.vo] Segmentation fault make[1]: *** [theories/Numbers/Integer/BigZ/BigZ.vo] Deleting filetheories/Numbers/Integer/BigZ/BigZ.glob'
make[1]: Target world' not remade because of errors. make[1]: Leaving directory/afs/csail.mit.edu/u/j/jgross/CoqUnivs'
make: *** [world] Error 2
make: Target `NOARG' not remade because of errors.
I will now try it without the -debug flag.


Reply to this email directly or view it on GitHub.

@JasonGross
Copy link
Author

I was able to compile the projbundle branch and attempted to test it. It failed very early, on something equivalent to

Record Foo :=
  {
    foo := 1;
    bar : foo = foo
  }.

with Anomaly: lookup_projection: constant is not a projection. Please report.

@JasonGross
Copy link
Author

By the way, I've tried comparing the performance of Coq 8.4 vs HoTT/coq on a small change from Qed to Defined + Opaque. The diff (to be applied to https://bitbucket.org/JasonGross/catdb/commits/4eb6407c6ca3200bebefaa3a1834d05c49b01846), along with a full list of the performance changes, is at https://gist.github.com/JasonGross/5894311. Interestingly, in Coq 8.4, the Defined + Opaque version is about 1 minute (about 7%) slower, picked up entirely in AdjointPointwise.v. In HoTT/coq, the Defined + Opaque version is about 234 minutes (about 220%) slower; 232 of these minutes are picked up in SpecializedLaxCommaCategory.v (largely, I believe, on two failed applys), another minute in AdjointPointwise.v, and the remaining minute scattered across the remaining files.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants