X-Git-Url: http://git.nguyen.vg/gitweb/?a=blobdiff_plain;f=src%2Fruntime.ml;h=0be30a75a825492b2c30f5f6508336c0552ff323;hb=4bbc27978a8e7d36b9d8c47f8b4dd0cf7b654fc6;hp=d74c26aefcbf93c8338a2af6f03a3702691b7a5f;hpb=63db110485e97e189313abd1a6ce1bedf941d76d;p=SXSI%2Fxpathcomp.git diff --git a/src/runtime.ml b/src/runtime.ml index d74c26a..0be30a7 100644 --- a/src/runtime.ml +++ b/src/runtime.ml @@ -8,6 +8,8 @@ module type S = sig type result_set val top_down_run : Ata.t -> Tree.t -> Tree.node -> result_set val bottom_up_run : Ata.t -> Tree.t -> Compile.text_query * string -> result_set + val grammar_run : Ata.t -> Grammar.t -> unit -> result_set + end module Make (U : ResJIT.S) : S with type result_set = U.NS.t = @@ -85,11 +87,12 @@ module Make (U : ResJIT.S) : S with type result_set = U.NS.t = in let lvl3 = Array.fold_left (fun acc a -> - Array.fold_left (fun acc2 a2 -> - Array.fold_left - (fun acc3 a3 -> if a3 == dummy then acc3 else acc3+1) acc2 a2) - acc a) 0 d - in + Array.fold_left (fun acc2 a2 -> + Array.fold_left + (fun acc3 a3 -> if a3 != dummy then acc3+1 else acc3) + acc2 a2) + acc a) 0 d + in fprintf fmt "L3JIT Statistics: \t%i entries \t%i used L1 lines @@ -116,12 +119,12 @@ module Make (U : ResJIT.S) : S with type result_set = U.NS.t = Translist.fold (fun t (a1, a2) -> let _, _, _, f = Transition.node t in let (_, _, fs1), (_, _, fs2) = Formula.st f in - (StateSet.union s1 fs1, StateSet.union s2 fs2) + (StateSet.union a1 fs1, StateSet.union a2 fs2) ) trl (StateSet.empty, StateSet.empty) in let ns1 = StateSet.inter s1 orig_s1 and ns2 = StateSet.inter s2 orig_s2 in - let res, ops, todo = eval_trans auto ns1 ns2 trl in + let res, ops, todo = eval_trans auto s1 s2 trl in let code, not_marking = ResJIT.compile ops in let todo_code, todo_notmarking = List.fold_left (fun (l, b) (p, q, o) -> let c, b' = ResJIT.compile o in @@ -185,13 +188,15 @@ module Make (U : ResJIT.S) : S with type result_set = U.NS.t = let cache_apply cache auto tlist s1 s2 = let f = gen_code auto tlist s1 s2 in + TRACE("grammar", 2, __ "Inserting: %i, %a, %a\n%!" + (Uid.to_int tlist.Translist.Node.id) StateSet.print s1 StateSet.print s2); add cache tlist s1 s2 f; f end DEFINE LOOP (t, states, ctx) = ( let _t = (t) in TRACE("top-down-run", 3, - __ "Entering node %i (tag %s, context %i) with states %a\n%!" + __ "Entering node %i with loop (tag %s, context %i) with states %a\n%!" (Node.to_int _t) (Tag.to_string (Tree.tag tree _t)) (Node.to_int (ctx)) @@ -205,6 +210,12 @@ DEFINE LOOP (t, states, ctx) = ( DEFINE LOOP_TAG (t, states, tag, ctx) = ( let _t = (t) in (* to avoid duplicating expression t *) + TRACE("top-down-run", 3, + __ "Entering node %i with loop_tag (tag %s, context %i) with states %a\n%!" + (Node.to_int _t) + (Tag.to_string (tag)) + (Node.to_int (ctx)) + (StateSet.print) (states)); if _t == Tree.nil then nil_res else l2jit_dispatch @@ -255,9 +266,11 @@ DEFINE LOOP_TAG (t, states, tag, ctx) = ( | L2JIT.NOP () -> nil_res | L2JIT.FIRST_CHILD s -> LOOP ((Tree.first_child tree t), s, ctx) | L2JIT.NEXT_SIBLING s -> LOOP ((Tree.next_sibling tree t), s, ctx) +(* | L2JIT.NEXT_SIBLING s -> LOOP ((Tree.next_node_before tree t ctx), s, ctx) *) | L2JIT.FIRST_ELEMENT s -> LOOP ((Tree.first_element tree t), s, ctx) | L2JIT.NEXT_ELEMENT s -> LOOP ((Tree.next_element tree t), s, ctx) +(* | L2JIT.NEXT_ELEMENT s -> LOOP ((Tree.next_node_before tree t ctx), s, ctx) *) | L2JIT.TAGGED_DESCENDANT (s, tag) -> LOOP_TAG ((Tree.tagged_descendant tree t tag), s, tag, ctx) @@ -304,7 +317,9 @@ DEFINE LOOP_TAG (t, states, tag, ctx) = ( s,empty_slot in - LOOP (root, states, ctx) + let r = LOOP (root, states, ctx) in + (*L3JIT.stats err_formatter cache3; *) + r let full_top_down_run auto states tree root = (*Ata.init (); *) @@ -313,6 +328,7 @@ DEFINE LOOP_TAG (t, states, tag, ctx) = ( let top_down_run auto tree root = (*Ata.init (); *) let res, slot = full_top_down_run auto auto.init tree root in + slot.(StateSet.min_elt auto.topdown_marking_states) @@ -408,5 +424,165 @@ DEFINE LOOP_TAG (t, states, tag, ctx) = ( slot.(StateSet.min_elt auto.topdown_marking_states) +(* Grammar run *) + module ArrayPool = + struct + let pool = Queue.create () + let create dummy = + if Queue.is_empty pool then + Array.create 16 dummy + else + Queue.take pool + let create dummy = Array.create 16 dummy + let free p = Queue.add p pool + end + + + let grammar_run auto g () = + + let start_symbol = (Node.of_int 0) in + let dummy_leaf = Grammar.Leaf (Node.nil) in + + let res_len = (StateSet.max_elt auto.states) + 1 in + let empty_slot = Array.create res_len U.NS.empty in + let nil_res = auto.bottom_states, empty_slot in + let empty_res = StateSet.empty, empty_slot in + let cache3 = L3JIT.create () in + let dummy2 = (StateSet.empty, StateSet.empty, Translist.nil) in + let cache2 = Cache.Lvl2.create 512 dummy2 in + let tmp1 = Array.create 16 dummy_leaf in + let tmp2 = Array.create 16 dummy_leaf in + let get_trans tag states = + let c = Cache.Lvl2.find cache2 tag (Uid.to_int states.StateSet.Node.id) in + if c == dummy2 then + let c = + StateSet.fold (fun q tr_acc -> + List.fold_left + (fun ((lstates, rstates, tacc) as acc) (ts, trs) -> + if TagSet.mem (Tag.translate tag) ts then + let _, _, _, phi = Transition.node trs in + let (_,_,l),(_,_,r) = Formula.st phi in + (StateSet.union l lstates, + StateSet.union r rstates, + Translist.cons trs tacc) + else acc) + tr_acc (Hashtbl.find auto.trans q) + ) states (StateSet.empty, StateSet.empty, Translist.nil) + in + begin + Cache.Lvl2.add cache2 tag (Uid.to_int states.StateSet.Node.id) c; + c + end + else c + in + let rec start_loop idx states = + TRACE("grammar", 2, __ "Node %i\n%!" (Node.to_int idx)); + if idx < Node.null then nil_res + else if StateSet.is_empty states then empty_res + else begin + let symbol = Grammar.get_symbol_at g start_symbol idx in + if Grammar.is_terminal symbol then + let symbol = Grammar.terminal symbol in + let tag = Grammar.tag symbol in + let lst, rst, trans = get_trans tag states in + let fs = Grammar.first_child g start_symbol idx in + let s1, slot1 = start_loop fs lst in + let s2, slot2 = start_loop (Grammar.next_sibling g start_symbol fs) rst in + let opcode = L3JIT.find cache3 trans s1 s2 in + if opcode == L3JIT.dummy then (L3JIT.cache_apply cache3 auto trans s1 s2) empty_slot slot1 slot2 (Obj.magic ()) (Obj.magic ()) + else opcode empty_slot slot1 slot2 (Obj.magic ()) (Obj.magic()) + else + let tn = Grammar.non_terminal symbol in + let nparam = Grammar.num_params tn in + let a_param = tmp1 (*ArrayPool.create dummy_leaf*) in + let child = ref (Grammar.first_child g start_symbol idx) in + for i = 0 to nparam - 1 do + let c = !child in + a_param.(i) <- Grammar.Leaf c; + child := Grammar.next_sibling g start_symbol c; + done; + (*let a_param = Array.init nparam + (fun _ -> let c = !child in + child := Grammar.next_sibling g start_symbol c; + Grammar.Leaf c) + in *) + rule_loop tn a_param states + + end + and counter = ref 0 + and rule_loop (t : Grammar.n_symbol) a_param states = + + incr counter; + if !counter land 8191 == 0 then Gc.minor(); + + let id1 = Grammar.get_id1 g t in + let id2 = Grammar.get_id2 g t in + let param_pos = Grammar.get_param_pos g t in + let nparam1 = Grammar.num_children id1 in + let nparam2 = + if Grammar.is_terminal id2 && Grammar.is_nil g (Grammar.terminal id2) then 0 + else Grammar.num_children id2 + in + let a_param1 = (*ArrayPool.create dummy_leaf*) tmp2 (* Array.create nparam1 dummy_leaf *) in + let a_param2 = Array.create nparam2 dummy_leaf (* Array.create nparam2 dummy_leaf *) in + let i = param_pos - 2 in + (*Array.blit a_param 0 a_param1 0 (i+1); (* Pass parameters before id2 *) *) + (* Array.blit is too slow *) + for k = 0 to i do + a_param1.(k) <- a_param.(k); + done; + a_param1.(i+1) <- Grammar.Node(id2, a_param2); (* id2( ... ) *) + (*Array.blit a_param (i + nparam2 + 1) a_param1 (i+2) (nparam1 - i - 2); (* Pass parameters after id2 *) *) + for k = 0 to nparam1 - i -3 do + a_param1.(i+2+k) <- a_param.(i + nparam2 + 1 + k); + done; + (*Array.blit a_param (i + 1) a_param2 0 nparam2; (* parameters below id2 *) *) + for k = 0 to nparam2 - 1 do + a_param2.(k) <- a_param.(i+1+k) + done; + for i = 0 to nparam1 do + a_param.(i) <- a_param1.(i) + done; + if Grammar.is_non_terminal id1 then + let id1 = Grammar.non_terminal id1 in + rule_loop id1 a_param states + else + let id1 = Grammar.terminal id1 in + terminal_loop id1 a_param states + + and terminal_loop (symbol : Grammar.t_symbol) a_param states = + if Grammar.is_nil g symbol then nil_res else begin + (* todo factor in from start_loop *) + let tag = Grammar.tag symbol in + let lst, rst, trans = get_trans tag states in + let s1, slot1 = partial_loop a_param.(0) lst in + let s2, slot2 = partial_loop a_param.(1) rst in + let opcode = L3JIT.find cache3 trans s1 s2 in + if opcode == L3JIT.dummy then (L3JIT.cache_apply cache3 auto trans s1 s2) empty_slot slot1 slot2 (Obj.magic ()) (Obj.magic ()) + else + opcode empty_slot slot1 slot2 (Obj.magic()) (Obj.magic()) + + (* End: TODO refactor *) + + end + + and partial_loop l states = + match l with + | Grammar.Leaf id -> start_loop id states + | Grammar.Node (id, a_param) -> + if Grammar.is_terminal id then terminal_loop (Grammar.terminal id) a_param states + else rule_loop (Grammar.non_terminal id) a_param states + in + (*L3JIT.stats err_formatter cache3; *) + let _, slot = start_loop (Node.null) auto.init in + slot.(StateSet.min_elt auto.topdown_marking_states) + ;; + + + + + + + end