diff options
| author | letouzey | 2013-08-22 14:29:31 +0000 |
|---|---|---|
| committer | letouzey | 2013-08-22 14:29:31 +0000 |
| commit | 9abbc22bd4001082681bffb881077a66e658a23a (patch) | |
| tree | 8c68741543462dcf2e6fe7feeb8f7a907b409c5c /lib | |
| parent | d475ff0d4427fc1c3859fc5d8d0cb7cc0a32a14e (diff) | |
More complete hashcons : lists (dirpath), arrays (constr)
Earlier, the elements of constr arrays were hash-consed, but not the
array itself. This helps a bit when the same (f a1 ... an) is manipulated
a lot : -20% in the size of opaque terms in Integral_domain.vo and Nsatz.vo
Similarly it's interesting to hash-cons sub-lists for dirpaths,
since in Coq.A.B and Coq.A.C we could share Coq.A.
With this patch, the hash-consing of constr seems quasi-optimal:
Pierre-Marie's marshal compactor is unable to shrink opaque tables by
more than 2%, and this difference seems to be due to untyped compaction
(for the compactor Rel 1 = Prop Pos).
git-svn-id: svn+ssh://scm.gforge.inria.fr/svn/coq/trunk@16723 85f007b7-540e-0410-9357-904b9bb8a0f7
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/hashcons.ml | 19 | ||||
| -rw-r--r-- | lib/hashcons.mli | 6 |
2 files changed, 25 insertions, 0 deletions
diff --git a/lib/hashcons.ml b/lib/hashcons.ml index db502c90ca..b33a200584 100644 --- a/lib/hashcons.ml +++ b/lib/hashcons.ml @@ -126,6 +126,25 @@ let register_hcons h u = (* Basic hashcons modules for string and obj. Integers do not need be hashconsed. *) +(* list *) +module type SomeData = sig type t end +module Hlist (D:SomeData) = + Make( + struct + type t = D.t list + type u = (t -> t) * (D.t -> D.t) + let hashcons (hrec,hdata) = function + | x :: l -> hdata x :: hrec l + | l -> l + let equal l1 l2 = + l1 == l2 || + match l1, l2 with + | [], [] -> true + | x1::l1, x2::l2 -> x1==x2 && l1==l2 + | _ -> false + let hash = Hashtbl.hash + end) + (* string *) module Hstring = Make( struct diff --git a/lib/hashcons.mli b/lib/hashcons.mli index 2f86174b22..ae7d6b9d9a 100644 --- a/lib/hashcons.mli +++ b/lib/hashcons.mli @@ -91,5 +91,11 @@ val recursive2_hcons : module Hstring : (S with type t = string and type u = unit) (** Hashconsing of strings. *) +module type SomeData = sig type t end + +module Hlist (D:SomeData) : + (S with type t = D.t list and type u = (D.t list -> D.t list)*(D.t->D.t)) +(** Hashconsing of lists. *) + module Hobj : (S with type t = Obj.t and type u = (Obj.t -> Obj.t) * unit) (** Hashconsing of OCaml values. *) |