From 2676d5a3bbb1e6f6a5af66477edfe3b4c849f4e7 Mon Sep 17 00:00:00 2001 From: kim Date: Sun, 26 Apr 2009 15:10:41 +0000 Subject: [PATCH] Some more optimisations git-svn-id: svn+ssh://idea.nguyen.vg/svn/sxsi/trunk/xpathcomp@358 3cdefd35-fc62-479d-8e8d-bae585ffb9ca --- Makefile | 15 +++++++++++---- ata.ml | 14 ++++++-------- hcons.ml | 8 ++++---- hcons.mli | 15 +++------------ ptset.ml | 4 ++-- tree.ml | 24 +++++++++++++++--------- utils.ml | 15 +++++++++++---- 7 files changed, 52 insertions(+), 43 deletions(-) diff --git a/Makefile b/Makefile index b4461a0..1c01ba6 100644 --- a/Makefile +++ b/Makefile @@ -1,6 +1,6 @@ INLINE=1000 DEBUG=false -PROFILE=true +PROFILE=false VERBOSE=false BASESRC=custom.ml memoizer.ml hcons.ml hlist.ml ptset.ml finiteCofinite.ml tag.ml tagSet.ml options.ml tree.ml ata.ml @@ -36,6 +36,7 @@ CXXINCLUDES = \ -IXMLTree/TextCollection CXXFLAGS = -O3 -Wall $(INCLUDEDIRS) -fPIC -std=c++0x + ifeq ($(VERBOSE),true) HIDE= else @@ -44,16 +45,22 @@ endif ifeq ($(DEBUG), true) CXX = g++ -DDEBUG -OCAMLOPT = ocamlopt -g -cc "$(CXX)" +DEBUG_FLAGS = -g SYNT_DEBUG = -ppopt -DDEBUG else -CXX = g++ -OCAMLOPT = ocamlopt -cc "$(CXX)" -ccopt -O3 -ccopt -std=c++0x -noassert -inline $(INLINE) +CXX = g++ endif + ifeq ($(PROFILE), true) +PROFILE_FLAGS = -p SYNT_PROF = $(SYNT_DEBUG) -ppopt -DPROFILE endif +OPT_FLAGS = $(DEBUG_FLAGS) $(PROFILE_FLAGS) + +OCAMLOPT = ocamlopt -cc "$(CXX)" $(OPT_FLAGS) -ccopt -O3 -ccopt -std=c++0x -noassert -inline $(INLINE) + + OCAMLFIND = ocamlfind OCAMLMKLIB = ocamlmklib OCAMLDEP = ocamldep diff --git a/ata.ml b/ata.ml index ebc74a5..6c97f55 100644 --- a/ata.ml +++ b/ata.ml @@ -1,8 +1,6 @@ INCLUDE "debug.ml" INCLUDE "utils.ml" - - type jump_kind = [ `TAG of Tag.t | `CONTAINS of string | `NOTHING ] (* Todo : move elsewhere *) @@ -67,8 +65,8 @@ struct match f.pos with | False -> 0 | True -> 1 - | Or (f1,f2) -> HASHINT3(PRIME2,HNode.hash f1,HNode.hash f2) - | And (f1,f2) -> HASHINT3(PRIME3,HNode.hash f1,HNode.hash f2) + | Or (f1,f2) -> HASHINT3(PRIME2,HNode.uid f1,HNode.uid f2) + | And (f1,f2) -> HASHINT3(PRIME3,HNode.uid f1,HNode.uid f2) | Atom(d,p,s) -> HASHINT4(PRIME4,hash_const_variant d,vb p,s) end @@ -230,7 +228,7 @@ module SetTagKey = struct type t = Ptset.Int.t*Tag.t let equal (s1,t1) (s2,t2) = (t1 == t2) && Ptset.Int.equal s1 s2 - let hash (s,t) = HASHINT2(Ptset.Int.hash s,Tag.hash t) + let hash (s,t) = HASHINT2(Ptset.Int.uid s, t) end module TransTable = Hashtbl @@ -650,7 +648,7 @@ END if Ptss.mem s c.sets then { c with results = IMap.add s (RS.concat r (IMap.find s c.results)) c.results} else - { hash = HASHINT2(c.hash,Ptset.Int.hash s); + { hash = HASHINT2(c.hash,Ptset.Int.uid s); sets = Ptss.add s c.sets; results = IMap.add s r c.results } @@ -682,7 +680,7 @@ END in let h,s = Ptss.fold - (fun s (ah,ass) -> (HASHINT2(ah,Ptset.Int.hash s), + (fun s (ah,ass) -> (HASHINT2(ah,Ptset.Int.uid s), Ptss.add s ass)) (Ptss.union c1.sets c2.sets) (0,Ptss.empty) in @@ -727,7 +725,7 @@ END let h_trans = Hashtbl.create 4096 let get_up_trans slist ptag a tree = - let key = (HASHINT2(SList.hash slist,Tag.hash ptag)) in + let key = (HASHINT2(SList.uid slist,ptag)) in try Hashtbl.find h_trans key with diff --git a/hcons.ml b/hcons.ml index 293b90f..eb60385 100644 --- a/hcons.ml +++ b/hcons.ml @@ -2,7 +2,7 @@ INCLUDE "utils.ml" module type S = sig type data - type t + type t val make : data -> t val node : t -> data val hash : t -> int @@ -13,7 +13,7 @@ module Make (H : Hashtbl.HashedType) : S with type data = H.t = struct type data = H.t type t = { id : int; - key : int; (* hash *) + key : int; node : data; } @@ -23,12 +23,12 @@ struct let gen_uid = let id = ref ~-1 in fun () -> incr id;!id - let equal t1 t2 = t1 == t2 || t1.id == t2.id + let equal = (==) module WH = Weak.Make( struct type _t = t type t = _t let hash = hash - let equal a b = H.equal a.node b.node + let equal a b = a==b || H.equal a.node b.node end) let pool = WH.create MED_H_SIZE let make x = diff --git a/hcons.mli b/hcons.mli index ceb33c2..49af121 100644 --- a/hcons.mli +++ b/hcons.mli @@ -1,21 +1,12 @@ module type S = sig type data - type t + type t val make : data -> t val node : t -> data val hash : t -> int val uid : t -> int val equal : t -> t -> bool end -module Make : - functor (H : Hashtbl.HashedType) -> -sig - type data = H.t - type t - val make : data -> t - val node : t -> data - val hash : t -> int - val uid : t -> int - val equal : t -> t -> bool -end + +module Make (H : Hashtbl.HashedType) : S with type data = H.t diff --git a/ptset.ml b/ptset.ml index 7a32602..3fd3d39 100644 --- a/ptset.ml +++ b/ptset.ml @@ -44,8 +44,8 @@ struct | _ -> false let hash = function | Empty -> 0 - | Leaf i -> HASHINT2(HALF_MAX_INT,H.hash i) - | Branch (b,i,l,r) -> HASHINT4(b,i,HNode.hash l, HNode.hash r) + | Leaf i -> HASHINT2(HALF_MAX_INT,H.uid i) + | Branch (b,i,l,r) -> HASHINT4(b,i,HNode.uid l, HNode.uid r) end ;; diff --git a/tree.ml b/tree.ml index 20f0505..1ed56b2 100644 --- a/tree.ml +++ b/tree.ml @@ -106,22 +106,28 @@ type t = { doc : tree; } let text_size t = text_size t.doc +module MemUnion = Hashtbl.Make (struct + type t = Ptset.Int.t*Ptset.Int.t + let equal (x,y) (z,t) = (Ptset.Int.equal x z)&&(Ptset.Int.equal y t) + let equal a b = equal a b || equal b a + let hash (x,y) = (* commutative hash *) + let x = Ptset.Int.hash x + and y = Ptset.Int.hash y + in + if x < y then HASHINT2(x,y) else HASHINT2(y,x) + end) let collect_tags tree = - let h_union = Hashtbl.create 511 in + let h_union = MemUnion.create BIG_H_SIZE in let pt_cup s1 s2 = - (* special case, since this is a union we want hash(s1,s2) = hash(s2,s1) *) - let x = Ptset.Int.hash s1 - and y = Ptset.Int.hash s2 in - let h = if x < y then HASHINT2(x,y) else HASHINT2(y,x)in try - Hashtbl.find h_union h + MemUnion.find h_union (s1,s2) with | Not_found -> let s = Ptset.Int.union s1 s2 in - Hashtbl.add h_union h s;s + MemUnion.add h_union (s1,s2) s;s in - let h_add = Hashtbl.create 511 in + let h_add = Hashtbl.create BIG_H_SIZE in let pt_add t s = let k = HASHINT2(Tag.hash t,Ptset.Int.hash s) in try @@ -130,7 +136,7 @@ let collect_tags tree = | Not_found -> let r = Ptset.Int.add t s in Hashtbl.add h_add k r;r in - let h = Hashtbl.create 511 in + let h = Hashtbl.create BIG_H_SIZE in let sing = Ptset.Int.singleton Tag.pcdata in let update t sb sa = let sbelow,safter = diff --git a/utils.ml b/utils.ml index ce08290..74bf778 100644 --- a/utils.ml +++ b/utils.ml @@ -10,19 +10,26 @@ THEN DEFINE INTSIZE = 63 DEFINE HALFINTSIZE = 31 DEFINE HALF_MAX_INT = 2305843009213693951 + DEFINE HPARAM = 65599 + DEFINE HPARAM2 = 4303228801 + DEFINE HPARAM3 = 282287506116799 + ELSE DEFINE WORDSIZE = 32 DEFINE HALFWORDSIZE = 16 DEFINE INTSIZE = 31 DEFINE HALFINTSIZE = 15 DEFINE HALF_MAX_INT = 536870911 + DEFINE HPARAM = 65599 + DEFINE HPARAM2 = 8261505 + DEFINE HPARAM3 = 780587199 + END -(* x+65599*y, as in Hashtbl.hash *) -DEFINE HASHINT2 (x,y) = ((x) + ( ((y) lsl 16) + ((y) lsl 8) - (y))) -DEFINE HASHINT3 (x,y,z) = (HASHINT2(HASHINT2(x,y),z)) -DEFINE HASHINT4 (x,y,z,t) = (HASHINT2((HASHINT2(HASHINT2(x,y),z)),t)) +DEFINE HASHINT2 (x,y) = ((x)+HPARAM*(y)) +DEFINE HASHINT3 (x,y,z) = ((x) + (y) * HPARAM + (z) * HPARAM2) +DEFINE HASHINT4 (x,y,z,t) = ((x) + (y) * HPARAM + (z)*HPARAM2 + (t)* HPARAM3) DEFINE PRIME1 = 7 DEFINE PRIME2 = 19 -- 2.17.1