Regression: Importing ZArith leads to setoid_rewrite performance degradation

Aperta
  • Qualcosa non va?
#200 2 commenti 0 reazioni 0 assegnatari Vedi su GitHub

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
4/5
Tempo stimato
3-5 giorni
Idoneità per principianti
42/100
Tipo di issue
Bug
Chiarezza
Abbastanza chiara
Stato di attività
Ferma
Ambito
tooling

Direzione di ricerca

Inizia eseguendo la dimostrazione minima fornita con la Stdlib corrente, quindi confronta il comportamento quando si importa ZArith con quello quando si importa Ncring. Esamina gli import di Znumtheory e Ncring e gli hint di typeclass per gli anelli elencati, usando l’esempio Remove Hints come diagnostica. Il lavoro è completato quando la dimostrazione setoid_rewrite non supera più il timeout di un secondo dopo l’importazione di ZArith.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

In the following proof, setoid_rewrite works fine on older versions of the stdlib (sometime between 8.20 and 9.0, I think) but it takes over 30 seconds on more recent versions of the standard library. I don't think the rocq version matters but I have tested with master and a snapshot of master from late February.

From Corelib Require Import PrimInt63 Uint63Axioms.
Require Import Corelib.Strings.PrimString.
Require Import Corelib.BinNums.IntDef.
Require Import Corelib.Numbers.BinNums.
From Corelib Require Import Setoid.
From Stdlib Require Import ZArith.

Axiom N_to_nat : N -> nat.
Axiom N_modulo : N -> N -> N.
Axiom N_mod_0_r : forall x, N_modulo x N0 = N0.

Goal forall x,
  Init.Nat.min 
    (IntDef.Z.to_nat (to_Z PrimString.max_length))
    (N_to_nat (N_modulo x N0))
  = 0%nat.
Proof.
  Timeout 1 setoid_rewrite N_mod_0_r.
Abort.

AFAICT the change is related to Znumtheory pulling in libraries like Ncring but I am not 100% sure. A similar slowdown can be seen when importing just Ncring instead of ZArith in the example above. In that case, the slowdown can be fixed by disabling these typeclass instances:

Remove Hints  ring_setoid : typeclass_instances.
Remove Hints  ring_plus_comp : typeclass_instances.
Remove Hints  ring_mult_comp : typeclass_instances.
Remove Hints  ring_sub_comp : typeclass_instances.

But this does not suffice to fix the slowdown when importing all of ZArith.

Lingua principale
Rocq Prover
Stelle
45
Fork
39
Merge medio
1g 13h
PR unite (30g)
3

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di rocq-prover/stdlib

Tutte le issue di rocq-prover/stdlib

Issue simili

Altre issue su DevTools

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.