src/Pure/Concurrent/par_list.ML
author hoelzl
Wed, 02 Apr 2014 18:35:01 +0200
changeset 56369 2704ca85be98
parent 52945 13687b130f1f
child 58993 302104d8366b
permissions -rw-r--r--
moved generic theorems from Complex_Analysis_Basic; fixed some theorem names
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
28199
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
     1
(*  Title:      Pure/Concurrent/par_list.ML
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
     2
    Author:     Makarius
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
     3
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
     4
Parallel list combinators.
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
     5
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
     6
Notes:
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
     7
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
     8
  * These combinators only make sense if the operator (function or
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
     9
    predicate) applied to the list of operands takes considerable
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    10
    time.  The overhead of scheduling is significantly higher than
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    11
    just traversing the list of operands sequentially.
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    12
28358
5d79c5d68459 tuned comments;
wenzelm
parents: 28357
diff changeset
    13
  * The order of operator application is non-deterministic.  Watch out
28199
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    14
    for operators that have side-effects or raise exceptions!
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    15
*)
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    16
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    17
signature PAR_LIST =
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    18
sig
44265
b94951f06e48 export Par_List.managed_results, to enable specific treatment of results apart from default Par_Exn.release_first;
wenzelm
parents: 44247
diff changeset
    19
  val managed_results: string -> ('a -> 'b) -> 'a list -> 'b Exn.result list
41711
3422ae5aff3a more tracing information via Par_List.map_name;
wenzelm
parents: 41675
diff changeset
    20
  val map_name: string -> ('a -> 'b) -> 'a list -> 'b list
28199
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    21
  val map: ('a -> 'b) -> 'a list -> 'b list
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    22
  val get_some: ('a -> 'b option) -> 'a list -> 'b option
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    23
  val find_some: ('a -> bool) -> 'a list -> 'a option
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    24
  val exists: ('a -> bool) -> 'a list -> bool
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    25
  val forall: ('a -> bool) -> 'a list -> bool
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    26
end;
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    27
29368
503ce3f8f092 renamed structure ParList to Par_List;
wenzelm
parents: 29120
diff changeset
    28
structure Par_List: PAR_LIST =
28199
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    29
struct
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    30
41673
1c191a39549f support named tasks, for improved tracing;
wenzelm
parents: 41672
diff changeset
    31
fun managed_results name f xs =
41675
0f0f6212d6c6 tuned trivial cases;
wenzelm
parents: 41674
diff changeset
    32
  if null xs orelse null (tl xs) orelse
0f0f6212d6c6 tuned trivial cases;
wenzelm
parents: 41674
diff changeset
    33
      not (Multithreading.enabled ()) orelse Multithreading.self_critical ()
0f0f6212d6c6 tuned trivial cases;
wenzelm
parents: 41674
diff changeset
    34
  then map (Exn.capture f) xs
0f0f6212d6c6 tuned trivial cases;
wenzelm
parents: 41674
diff changeset
    35
  else
49319
f4b91a3a5f0f more robust interrupt handling;
wenzelm
parents: 47404
diff changeset
    36
    uninterruptible (fn restore_attributes => fn () =>
f4b91a3a5f0f more robust interrupt handling;
wenzelm
parents: 47404
diff changeset
    37
      let
52945
13687b130f1f retain current task priority, to avoid distortion due to local forks (e.g. sledgehammer query operation);
wenzelm
parents: 49319
diff changeset
    38
        val (group, pri) =
13687b130f1f retain current task priority, to avoid distortion due to local forks (e.g. sledgehammer query operation);
wenzelm
parents: 49319
diff changeset
    39
          (case Future.worker_task () of
13687b130f1f retain current task priority, to avoid distortion due to local forks (e.g. sledgehammer query operation);
wenzelm
parents: 49319
diff changeset
    40
            SOME task =>
13687b130f1f retain current task priority, to avoid distortion due to local forks (e.g. sledgehammer query operation);
wenzelm
parents: 49319
diff changeset
    41
              (Future.new_group (SOME (Task_Queue.group_of_task task)), Task_Queue.pri_of_task task)
13687b130f1f retain current task priority, to avoid distortion due to local forks (e.g. sledgehammer query operation);
wenzelm
parents: 49319
diff changeset
    42
          | NONE => (Future.new_group NONE, 0));
49319
f4b91a3a5f0f more robust interrupt handling;
wenzelm
parents: 47404
diff changeset
    43
        val futures =
52945
13687b130f1f retain current task priority, to avoid distortion due to local forks (e.g. sledgehammer query operation);
wenzelm
parents: 49319
diff changeset
    44
          Future.forks {name = name, group = SOME group, deps = [], pri = pri, interrupts = true}
49319
f4b91a3a5f0f more robust interrupt handling;
wenzelm
parents: 47404
diff changeset
    45
            (map (fn x => fn () => f x) xs);
f4b91a3a5f0f more robust interrupt handling;
wenzelm
parents: 47404
diff changeset
    46
        val results =
f4b91a3a5f0f more robust interrupt handling;
wenzelm
parents: 47404
diff changeset
    47
          restore_attributes Future.join_results futures
f4b91a3a5f0f more robust interrupt handling;
wenzelm
parents: 47404
diff changeset
    48
            handle exn =>
f4b91a3a5f0f more robust interrupt handling;
wenzelm
parents: 47404
diff changeset
    49
              (if Exn.is_interrupt exn then Future.cancel_group group else (); reraise exn);
f4b91a3a5f0f more robust interrupt handling;
wenzelm
parents: 47404
diff changeset
    50
      in results end) ();
28199
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    51
44247
270366301bd7 more systematic handling of parallel exceptions;
wenzelm
parents: 44113
diff changeset
    52
fun map_name name f xs = Par_Exn.release_first (managed_results name f xs);
41711
3422ae5aff3a more tracing information via Par_List.map_name;
wenzelm
parents: 41675
diff changeset
    53
fun map f = map_name "Par_List.map" f;
28199
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    54
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    55
fun get_some f xs =
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    56
  let
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    57
    exception FOUND of 'b option;
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    58
    fun found (Exn.Exn (FOUND some)) = some
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    59
      | found _ = NONE;
40700
4b4dfe05b5d7 clarified Par_List.managed_results, with explicit propagation of outermost physical interrupt to forked futures (e.g. to make timeout apply here as expected and prevent zombies);
wenzelm
parents: 37865
diff changeset
    60
    val results =
41673
1c191a39549f support named tasks, for improved tracing;
wenzelm
parents: 41672
diff changeset
    61
      managed_results "Par_List.get_some"
1c191a39549f support named tasks, for improved tracing;
wenzelm
parents: 41672
diff changeset
    62
        (fn x => (case f x of NONE => () | some => raise FOUND some)) xs;
28199
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    63
  in
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    64
    (case get_first found results of
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    65
      SOME y => SOME y
44247
270366301bd7 more systematic handling of parallel exceptions;
wenzelm
parents: 44113
diff changeset
    66
    | NONE => (Par_Exn.release_first results; NONE))
28199
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    67
  end;
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    68
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    69
fun find_some P = get_some (fn x => if P x then SOME x else NONE);
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    70
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    71
fun exists P = is_some o get_some (fn x => if P x then SOME () else NONE);
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    72
fun forall P = not o exists (not o P);
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    73
e63d05ceec24 Parallel list combinators.
wenzelm
parents:
diff changeset
    74
end;