[Caml-list] Hashtbl and destructive operations on keys

[Caml-list] Hashtbl and destructive operations on keys

[Thomas Fischbacher]

Dear ocaml hackers,

I read the documentation in such a way that I must not assume that after
doing a Hashtbl.replace hash key new_val, I can destructively modify key
with impunity. (I do cons a new key at every Hashtbl.add.)

On the other hand (I have not looked into the sources), I am quite 
confident that the system _could_ give me the guarantee that 
nothing evil happens if I do so, and especially for the application I am 
presently working on, this would induce a noticeable performance gain,
due to reduced consing. (And performance is important here!)

So, could I please get this officially sanctioned? :-)


-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Hashtbl and destructive operations on keys

[Remi Vanicat]

Thomas Fischbacher <Thomas.Fischbacher@Physik.Uni-Muenchen.DE> writes:

> Dear ocaml hackers,
>
> I read the documentation in such a way that I must not assume that after
> doing a Hashtbl.replace hash key new_val, I can destructively modify key
> with impunity. (I do cons a new key at every Hashtbl.add.)
>
> On the other hand (I have not looked into the sources), I am quite 
> confident that the system _could_ give me the guarantee that 
> nothing evil happens if I do so, and especially for the application I am 
> presently working on, this would induce a noticeable performance gain,
> due to reduced consing. (And performance is important here!)
>
> So, could I please get this officially sanctioned? :-)

This is not an official answers, but it is what ocaml tell me :

# let tbl = create 10;;
val tbl : ('_a, '_b) Hashtbl.t = <abstr>
# let r = ref 10;;
val r : int ref = {contents = 10}
# replace tbl r 50;;
- : unit = ()
# r := 1;;
- : unit = ()
# find tbl r;;
Exception: Not_found.

So no, you can't modify in place the key without a danger. But :

# class myref (x:int) =
  object
     val mutable value = x
     method set n = value <- n
     method get = value
  end;;
class myref :
  int ->
  object
    val mutable value : int
    method get : int
    method set : int -> unit
  end
# let tbl = create 10;;
val tbl : ('_a, '_b) Hashtbl.t = <abstr>
# let r = new myref 10;;
val r : myref = <obj>
# replace tbl r 50;;
- : unit = ()
# r #set 1;;
- : unit = ()
# find tbl r;;
- : int = 50

It do work for object because the hash value of object depend on an
identifier that each object do have, and only of it. Two different
object (even with same field) have a different id, and a object never
change of id. The id can be none by using Oo.id.

-- 
Rémi Vanicat

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Hashtbl and destructive operations on keys

[Thomas Fischbacher]

On Mon, 22 Mar 2004, Remi Vanicat wrote:

> > So, could I please get this officially sanctioned? :-)
> 
> This is not an official answers, but it is what ocaml tell me :
> 
> # let tbl = create 10;;
> val tbl : ('_a, '_b) Hashtbl.t = <abstr>
> # let r = ref 10;;
> val r : int ref = {contents = 10}
> # replace tbl r 50;;
> - : unit = ()
> # r := 1;;
> - : unit = ()
> # find tbl r;;
> Exception: Not_found.

Please look closely at my original posting. This is not what I was 
intending to do.

What I rather want to do is roughly along the following lines:


let nonconsing_accum f_combine f_copy ht h_key h_val =
  if Hashtbl.mem ht h_key
  then Hashtbl.replace ht h_key 
      (f_combine (Hashtbl.find ht h_key) h_val)
  else Hashtbl.add ht (f_copy h_key) h_val
;;

let result =
  (
   let ht = Hashtbl.create 10 in
   let arr = Array.make 4 0 in
   for i = 0 to 1000 do
     for k = 0 to 4-1 do
       arr.(k) <- Random.int 5;
     done;
     nonconsing_accum (+) Array.copy ht arr 1;
   done;
   Hashtbl.fold (fun k v so_far -> (k,v)::so_far) ht [];
  )
;;

Former experience with CMU CL tells me that this technique of not 
unnecessarily consing hash keys can easily lead to a performance gain of 
a factor of 10 - depending on the application, of course.

But I have a very bad feeling about it as long as I do not have any 
guarantee that I really can re-use the corpus of a hash key passed to 
Hashtbl.replace.

Yes, one answer certainly is "just make the hash value a ref and work on 
its contents". But there are indeed some crazy situations where one is 
better off using the above technique.

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Hashtbl and destructive operations on keys

[Jacques Garrigue]

From: Thomas Fischbacher <Thomas.Fischbacher@Physik.Uni-Muenchen.DE>

> What I rather want to do is roughly along the following lines:
> 
> 
> let nonconsing_accum f_combine f_copy ht h_key h_val =
>   if Hashtbl.mem ht h_key
>   then Hashtbl.replace ht h_key 
>       (f_combine (Hashtbl.find ht h_key) h_val)
>   else Hashtbl.add ht (f_copy h_key) h_val
> ;;
> 
> let result =
>   (
>    let ht = Hashtbl.create 10 in
>    let arr = Array.make 4 0 in
>    for i = 0 to 1000 do
>      for k = 0 to 4-1 do
>        arr.(k) <- Random.int 5;
>      done;
>      nonconsing_accum (+) Array.copy ht arr 1;
>    done;
>    Hashtbl.fold (fun k v so_far -> (k,v)::so_far) ht [];
>   )
> ;;
> 
> Former experience with CMU CL tells me that this technique of not 
> unnecessarily consing hash keys can easily lead to a performance gain of 
> a factor of 10 - depending on the application, of course.
> 
> But I have a very bad feeling about it as long as I do not have any 
> guarantee that I really can re-use the corpus of a hash key passed to 
> Hashtbl.replace.

If I understand correctly your intention, you are asking whether
Hashtbl.replace may end-up putting parts of your key inside the
hash table?
Looking at the source code for Hashtbl.replace, this may only happen
if an equivalent key was not already in the table, and since your
program only calls replace for keys already in the table, this is safe.

But you probably already know that, so what you really want is a
sentence like "the key itself is inserted in the hashtable only if
there was no element to replace, otherwise the original key is kept"
added to the documentation.
Note however that such a comment may be seen as an overspecification:
it is more confusing than useful for normal use...

Moreover, the behaviour for the Map module is different: there, the
new key is used. (This is for the add function, but it happens to have
the same semantics as Hashtbl.replace)
And this is also different from using Hashtbl.remove followed by
Hashtbl.add, which was supposed to have the same semantics as
Hashtbl.replace.

> Yes, one answer certainly is "just make the hash value a ref and work on 
> its contents". But there are indeed some crazy situations where one is 
> better off using the above technique.

I'm wondering what kind of crazy situation.
Looks to me that that using a ref would be more efficient:
  let nonconsing_accum f_combine f_copy ht h_key h_val =
    try
      let h_ref = Hashtbl.find ht h_key in
      h_ref := f_combine !h_ref h_val
    with Not_found ->
      Hashtbl.add ht (f_copy h_key) (ref h_val)
  ;;
In your approach your are accessing 3 times the hash table, where once
should be enough.

However one might argue that nonconsing_accum should be a primitive on
hashtables, as it can be implemented more efficiently by directly
accessing the internal representation.

Jacques Garrigue

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Hashtbl and destructive operations on keys

[Correnson Loïc]

Hi!
Notice also that implementing your own hashtbl would not be so far
difficult.
For your dedicated use, the code for hashing and replacing this key to that
value would not exceed 10 lines,
assuming you can reuse Ocaml's hashing function and implements hash
collision with a simple array and associative lists.

Instead, your *codes* to work around Hashtbl with or without references may
never answer your question and will remain actually under specified and
fragile for your own purpose. Moreover, it is clear in your case that the
capability for ocaml hash tables to register several values for one key is
useless, since your always use replace and never add for existing key. To
finish with, your work-around code uses 3 times the hashtbl functions, hence
you hash the key 3 times. This is incompatible with looking for performance!

In my opinion, libraries always provide correct implementation for
prototyping or for reference implementation (e.g. for testing purpose).
However, ocaml library are always highly performant for normal use, and this
is why programming with ocaml is efficient.
Then, when facing a very low level performance constraint -- which in my
opinon should be exhibit first -- , one must look for a dedicated
implementation and not spent time in work arounf existing stuff.
    LC.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Hashtbl and destructive operations on keys

[Thomas Fischbacher]

On Tue, 23 Mar 2004, Correnson Loïc wrote:

> Notice also that implementing your own hashtbl would not be so far
> difficult.

Yes, I know, and I did so in lisp before. But one thing you must not 
forget: when doing research, your primary constraint is time. You want to 
get problem X solved with as little effort as possible (since everyone 
looks at your scientific throughput - already assuming your research is of 
reasonable quality). Note that I am not talking about 
compiler/language/other CS research here! Every day, you have a certain 
amount of mental energy which you can use. And you do not want to spend 
too much of it on low-level details like implementing your own hashing 
functions when you have more pressing problems in your mind, like 
devising a new and contrived algorithm to solve a new and contrived 
problem, or like the actual background of the problem you are 
investigating.

> For your dedicated use, the code for hashing and replacing this key to that
> value would not exceed 10 lines,
> assuming you can reuse Ocaml's hashing function and implements hash
> collision with a simple array and associative lists.

This suggestion is not far away from "why don't you use C right away?" - I 
do not want to, I want to make use of available powerful tools to I do not 
have to spend too much time on uninteresting low-level details.

> Instead, your *codes* to work around Hashtbl with or without references may
> never answer your question and will remain actually under specified and
> fragile for your own purpose.

That's precisely why I asked for additional specification.

> Moreover, it is clear in your case that the
> capability for ocaml hash tables to register several values for one key is
> useless, since your always use replace and never add for existing key.

This is in fact true, but then I must ask whether the "other", more usual 
type of hashes provided e.g. by LISP isn't the one that is more widely 
used, and if there really is so much of an overhead in this feature, 
why ocaml does not provide the other type of hashes?

> To
> finish with, your work-around code uses 3 times the hashtbl functions, hence
> you hash the key 3 times. This is incompatible with looking for performance!

Before I talk long... look at the following example:

let ht = Hashtbl.create 1000000;;

for i = 0 to 1000000 do
  let s = String.create 5 in
  for k = 0 to 5-1 do String.set s k (Char.chr ((i lsr (k lsl 2)) land 
15)) done;
  Hashtbl.add ht s i;
done;;

(* Linux-specific... *)

let h = open_in "/proc/self/status" in
let rec scan () =
  let line = input_line h in
  if String.sub line 0 7 = "VmSize:"
  then (close_in h; line)
  else scan()
in Printf.printf "MEM: %s" (scan())
;;

Try it. Then substitute the Hashtbl.add s i by Hashtbl.add s (ref i). 
You'll see that there is roughly 25% difference in RAM consumption. Now, 
if you are working close to the limit of virtual address space, or even 
only if this 25% makes the difference whether your program has to page out 
or not, this is indeed relevant.

But of course, it would be terrific if there were officially 
sanctioned variants of the hashtable functions that take a pre-computed 
hash key as an extra arg.

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Hashtbl and destructive operations on keys

[Oliver Bandel]

On Tue, Mar 23, 2004 at 12:13:14AM +0100, Thomas Fischbacher wrote:
[...]
> 
> let nonconsing_accum f_combine f_copy ht h_key h_val =
>   if Hashtbl.mem ht h_key
>   then Hashtbl.replace ht h_key 
>       (f_combine (Hashtbl.find ht h_key) h_val)
>   else Hashtbl.add ht (f_copy h_key) h_val
> ;;
> 

Why don't you sample all values first and afteryou have done it,
using a function to apply your f_combine to all stuff, you get
for each of the keys?
You can get all values for a key with Hashtbl.find_all.
So you only have to remember, which keys are in the hashtbl
and then apply your f_combine to each of that keys.

That also ha sthe advantage that you are free to apply
different functions to your hashtbl-values, because you
have saved all your values inside of the hash.

So you may apply (+) as well as (*) or others, once you have
sampled all your data.

Because you are testing the existence of the key with each
new value you want to insert in your hashtbl, you have
unnecessary calls with each insert-operation (with each
call to nonconsing_accum).

IMHO it makes more sense to sample all data with Hashtbl.add
first, and then do your operations on a per-key base
with Hashtbl.find_all.

(I hope I didn't miss your point.)

Ciao,
   Oliver

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Hashtbl and destructive operations on keys

[Oliver Bandel]

On Mon, Mar 22, 2004 at 07:16:57PM +0100, Thomas Fischbacher wrote:
> 
> Dear ocaml hackers,
> 
> I read the documentation in such a way that I must not assume that after
> doing a Hashtbl.replace hash key new_val, I can destructively modify key
> with impunity. (I do cons a new key at every Hashtbl.add.)


When you modify the key, you will have the problem
not to get directly to your data (your hash-value).

But with Hashtbl.fold you can find anything in the hashtbl,
that was not destrctively overwritten.

So, if you throw away your key (why should one do that?),
you can find your value nevertheless with Hashtbl.fold.




> 
> On the other hand (I have not looked into the sources), I am quite 
> confident that the system _could_ give me the guarantee that 
> nothing evil happens if I do so, and especially for the application I am 
> presently working on, this would induce a noticeable performance gain,
> due to reduced consing. (And performance is important here!)

You mean that the key is overwritten in-place,
because these imperative features are fast?!


> 
> So, could I please get this officially sanctioned? :-)

Again: When you throw away your key, you will not have
_direct_ access to your value. So if you need that
direct access, you have a problem.
If it is not necessary to get directly to that data and you
are happy with finding the key-value pairs after you have
inserted all stuff into the hashtbl, then you can throw away
your key, if you want to.

Ciao,
   Oliver

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Hashtbl and destructive operations on keys

[Oliver Bandel]

On Mon, Mar 22, 2004 at 08:09:35PM +0100, Remi Vanicat wrote:
> Thomas Fischbacher <Thomas.Fischbacher@Physik.Uni-Muenchen.DE> writes:
> 
> > Dear ocaml hackers,
> >
> > I read the documentation in such a way that I must not assume that after
> > doing a Hashtbl.replace hash key new_val, I can destructively modify key
> > with impunity. (I do cons a new key at every Hashtbl.add.)
> >
> > On the other hand (I have not looked into the sources), I am quite 
> > confident that the system _could_ give me the guarantee that 
> > nothing evil happens if I do so, and especially for the application I am 
> > presently working on, this would induce a noticeable performance gain,
> > due to reduced consing. (And performance is important here!)
> >
> > So, could I please get this officially sanctioned? :-)
> 
> This is not an official answers, but it is what ocaml tell me :
> 
> # let tbl = create 10;;
> val tbl : ('_a, '_b) Hashtbl.t = <abstr>
> # let r = ref 10;;
> val r : int ref = {contents = 10}
> # replace tbl r 50;;
> - : unit = ()
> # r := 1;;
> - : unit = ()
> # find tbl r;;
> Exception: Not_found.
> 
> So no, you can't modify in place the key without a danger. But :
> 
> # class myref (x:int) =
>   object
>      val mutable value = x
>      method set n = value <- n
>      method get = value
>   end;;
> class myref :
>   int ->
>   object
>     val mutable value : int
>     method get : int
>     method set : int -> unit
>   end
> # let tbl = create 10;;
> val tbl : ('_a, '_b) Hashtbl.t = <abstr>
> # let r = new myref 10;;
> val r : myref = <obj>
> # replace tbl r 50;;
> - : unit = ()
> # r #set 1;;
> - : unit = ()
> # find tbl r;;
> - : int = 50
> 
> It do work for object because the hash value of object depend on an
> identifier that each object do have, and only of it. Two different
> object (even with same field) have a different id, and a object never
> change of id. The id can be none by using Oo.id.


Seems to me that the problem with the references is that they also
are uniqe:

        Objective Caml version 3.04

# open Hashtbl;;
# let tbl = create 10;;
val tbl : ('_a, '_b) Hashtbl.t = <abstr>
# let k = ref 111;;
val k : int ref = {contents = 111}
# replace tbl k "first_value";;
- : unit = ()
# find tbl k;;
- : string = "first_value"
# find tbl (ref 111);;
- : string = "first_value"
# k := 777;;
- : unit = ()
# find tbl k;;
Exception: Not_found.
# find tbl (ref 111);;
Exception: Not_found.
# k := 111;;
- : unit = ()
# find tbl k;;
- : string = "first_value"
# find tbl (ref 111);;
- : string = "first_value"
# (ref 111) = ref (111)
- : bool = true
# (ref 111) == (ref 111);;
- : bool = false



So, it seems to me, that the reference is unique, and
that the value of the reference as well as the reference
as a certain memory-object is - both together -
the valid key.

if you may use Hashtbl.iter and a function like this one:

let print k v = print_int !k; print_string "  =>  "; print_endline v;;

then you can print out all values inside the hashtbl.

When you do that with the valid reference-key,
you will get:
# iter print tbl;;
111  =>  first_value

if you have changed the reference/key with say
k := 45267

you will get:

# iter print tbl;;
45267  =>  first_value



and so on...

I tried some more things, and if you insert a value
directly like this one:

replace tbl (ref 444);;

you can always get it back with
find tbl (ref 444) 

What seems unnatural, if my first suggestion (value + memory-obj.
is necessary to be a valid unique key) is correct.
So it is not. :(


When you have inserted a value with a reference,
and then after that you change the reference, please use
the
iter print tbl;;

and you will see that your value is in the Hashtbl,
even if it can't be found.
But the key has changed and is not available directly
via this key-reference until the key will be changed
back to it's initial value (see above example).

If you have changed a reference-key and overwrite
it with replace, you will have TWO entries in the
hastbl with the same key, at least when you
use the above print-function in
iter print tbl;;

But you can't find both entires when using Hashtbl.find_all.

So data will not be lost, you can get it back when
using Hashtbl.iter.
At least fo those cases I've tested (which may not necessarily be a
complete set of test cases).




Ciao,
   Oliver

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners