CookBook/Recipes/Timing.thy
author Christian Urban <urbanc@in.tum.de>
Wed, 11 Mar 2009 17:38:17 +0000
changeset 167 3e30ea95c7aa
parent 157 76cdc8f562fc
child 168 009ca4807baa
permissions -rw-r--r--
added temporarily some timing test about conversions and simprocs
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
154
e81ebb37aa83 updated to repository version; added a section about timing
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     1
theory Timing
e81ebb37aa83 updated to repository version; added a section about timing
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     2
imports "../Base"
e81ebb37aa83 updated to repository version; added a section about timing
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     3
begin
e81ebb37aa83 updated to repository version; added a section about timing
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     4
167
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
     5
section {* Measuring Time\label{rec:timing} *} 
154
e81ebb37aa83 updated to repository version; added a section about timing
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     6
e81ebb37aa83 updated to repository version; added a section about timing
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     7
text {*
e81ebb37aa83 updated to repository version; added a section about timing
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     8
 {\bf Problem:}
e81ebb37aa83 updated to repository version; added a section about timing
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     9
  You want to measure the running time of a tactic or function.\smallskip
e81ebb37aa83 updated to repository version; added a section about timing
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    10
e81ebb37aa83 updated to repository version; added a section about timing
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    11
  {\bf Solution:} Time can be measured using the function 
e81ebb37aa83 updated to repository version; added a section about timing
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    12
  @{ML start_timing} and @{ML end_timing}.\smallskip
e81ebb37aa83 updated to repository version; added a section about timing
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    13
167
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    14
  Assume the following function defined in Isabelle. 
154
e81ebb37aa83 updated to repository version; added a section about timing
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    15
*}
e81ebb37aa83 updated to repository version; added a section about timing
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    16
155
Christian Urban <urbanc@in.tum.de>
parents: 154
diff changeset
    17
fun 
Christian Urban <urbanc@in.tum.de>
parents: 154
diff changeset
    18
 ackermann:: "(nat * nat) \<Rightarrow> nat"
Christian Urban <urbanc@in.tum.de>
parents: 154
diff changeset
    19
where
Christian Urban <urbanc@in.tum.de>
parents: 154
diff changeset
    20
    "ackermann (0, n) = n + 1"
Christian Urban <urbanc@in.tum.de>
parents: 154
diff changeset
    21
  | "ackermann (m, 0) = ackermann (m - 1, 1)"
Christian Urban <urbanc@in.tum.de>
parents: 154
diff changeset
    22
  | "ackermann (m, n) = ackermann (m - 1, ackermann (m, n - 1))"
Christian Urban <urbanc@in.tum.de>
parents: 154
diff changeset
    23
167
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    24
text {* 
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    25
  We can now measure how long the simplifier takes to verify a datapoint
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    26
  of this function. The timing can be done using the following wrapper function:
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    27
*}
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    28
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    29
ML{*fun timing_wrapper tac st =
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    30
let 
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    31
  val t_start = start_timing ();
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    32
  val res = tac st;
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    33
  val t_end = end_timing t_start;
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    34
in
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    35
  (warning (#message t_end); res)
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    36
end*}
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    37
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    38
text {*
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    39
  Note that this function also takes a state @{text "st"} as an argument and
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    40
  applies this state to the tactic. This is because tactics are lazy functions
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    41
  and we need to force them to run, otherwise the timing will be meaningless.
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    42
  The used time will be calculated as the end time minus the start time.
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    43
  The wrapper can now be used in the proof
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    44
*}
154
e81ebb37aa83 updated to repository version; added a section about timing
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    45
155
Christian Urban <urbanc@in.tum.de>
parents: 154
diff changeset
    46
lemma "ackermann (3, 4) = 125"
Christian Urban <urbanc@in.tum.de>
parents: 154
diff changeset
    47
apply(tactic {* 
167
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    48
  timing_wrapper (simp_tac (@{simpset} addsimps @{thms "nat_number"}) 1) *})
155
Christian Urban <urbanc@in.tum.de>
parents: 154
diff changeset
    49
done
154
e81ebb37aa83 updated to repository version; added a section about timing
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    50
167
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    51
text {*
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    52
  where it returns something on the cale of 3 seconds.
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    53
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    54
  \begin{readmore}
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    55
  Basic functions regarding timing are defined in @{ML_file 
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    56
  "Pure/ML-Systems/polyml_common.ML"} (for the PolyML compiler). Some more
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    57
  advanced functions are defined in @{ML_file "Pure/General/output.ML"}.
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    58
  \end{readmore}
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    59
*}
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    60
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    61
3e30ea95c7aa added temporarily some timing test about conversions and simprocs
Christian Urban <urbanc@in.tum.de>
parents: 157
diff changeset
    62
154
e81ebb37aa83 updated to repository version; added a section about timing
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    63
end