backtracking / ocaml-hashcons Goto Github PK

let create sz =
  let sz = if sz < 7 then 7 else sz in
  let sz = if sz > Sys.max_array_length then Sys.max_array_length else sz in
  let emptybucket = Weak.create 0 in
  { table = Array.make sz emptybucket;
    totsize = 0;
    limit = 3; }

let clear t =
  let emptybucket = Weak.create 0 in
  for i = 0 to Array.length t.table - 1 do t.table.(i) <- emptybucket done;
  t.totsize <- 0;
  t.limit <- 3

I am doing a port of this library to F# and this is having me scratching my head. How is this possibly not an error?

Looking at the implementation of hashcons.ml it seems to grow the weak set very slowly (by +3) every time.
That is the same bug that got fixed in OCaml long ago: ocaml/ocaml@db20929

Why3 also seems to have switched to using Weak directly: https://gitlab.inria.fr/why3/why3/-/commit/059eda2a2758a857359d88828afd4bcf0e07e27a

There are other hash-consing libraries on opam (e.g. https://git.zapashcanon.fr/zapashcanon/hc/src/branch/master/src/hc.ml), but this one is more complete (it saves the hash key in a field for easy computation of other hashes, and has hash set and map implementations).

It would be nice to get a release of the current state just to have dune as a build system

I'm using ocaml-dns, which depends on this repo, and opium, which depends on hmap, in one project.

While buiding (using jbuilder), I came across this:

File "_none_", line 1:
Error: Files /home/qli/.opam/4.04.0/lib/hmap/hmap.cmxa
       and /home/qli/.opam/4.04.0/lib/hashcons/hmap.cmx
              both define a module named Hmap

I guess it's related to ocaml's name space problem? To work around this, I moved Hmap and Hset which are defined at the top level into module Hashcons, and local-pinned to it.

It may not be a problem specific to this lib, but if maintainer thinks it's a solution I could upstream it and make a PR, or if there are other solutions, I'm glad to hear. : )

      match Weak.get_copy bucket i with
        | Some v when v.node = d ->
	    begin match Weak.get bucket i with
              | Some v -> v
              | None -> loop (i+1)
            end
        | _ -> loop (i+1)

The above fragment starts at line 120 in hashcons.ml. I have 3 questions:

1. Is the shallow copy necessary? Unfortunately, in .NET the shallow copy is a restricted member of an object so I cannot call it from the outside. Would the following rewrite without the shallow copy work?

            match bucket.[i] with
            | Some v when v.node = d -> v
            | _ -> loop (i+1)

2. Does it really improve performance? I am guessing this is why it has been written this way, but I am skeptical that copying a object and then comparing it, before checking the bucket again is more efficient than just comparing it. Also, I am not sure about OCaml, but in .NET I am reading that the in-built shallow copy has some overhead compared to the manual one so that is one more thing to watch out for.

3. The way the None case is implemented is somewhat nonsensical to me since instead of looping to the next object, presumably it would be better to reuse the current empty slot in the bucket since it is already known that the equality check succeeded. I am assuming that the node should be unique in the bucket and that there will be no need to compare it with the others. Is there something I am missing here?