[Caml-list] replay debugger

[Caml-list] replay debugger

[Yoann Padioleau]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 514 bytes --]


Y'a t'il de la doc sur le fonctionnement interne du debuggger.
Comment ca marche ? comment ki fait pour revenir en arriere ?



-- 
          Yoann  Padioleau,  INSA de Rennes, France,
Opinions expressed here are only mine. Je n'écris qu'à titre personnel.
**____   Get Free. Be Smart.  Simply use Linux and Free Software.   ____**
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] replay debugger

[Xavier Leroy]

[The question was: how does the OCaml debugger implements reverse execution?]

> Y'a t'il de la doc sur le fonctionnement interne du debuggger.
> Comment ca marche ? comment ki fait pour revenir en arriere ?

Like all "time-travel" debuggers: by periodic checkpointing.  That is,
it saves the state of the program from time to time, and uses these
checkpoints to restore the state of the program at any time.  E.g.
say you stop the program and wish to execute it backwards one step.
Find the most recent checkpoint, which was taken N steps ago;
duplicate it, and run one copy N-1 steps forward.

We learnt this trick from Andrew Tolmach's thesis:
        http://www.cs.pdx.edu/~apt/thesis.ps.Z
The only difference between Tolmach's system and ocamldebug is that
the former uses first-class continuations to capture the checkpoints,
while ocamldebug uses the fork() Unix system call.  Thus, each
checkpoint is really a separate process, and all of them communicate
with the debugger via sockets.

- Xavier Leroy
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] replay debugger

[Fergus Henderson]

On 04-Oct-2001, Xavier Leroy <xavier.leroy@inria.fr> wrote:
> [The question was: how does the OCaml debugger implements reverse execution?]
> 
> > Y'a t'il de la doc sur le fonctionnement interne du debuggger.
> > Comment ca marche ? comment ki fait pour revenir en arriere ?
> 
> Like all "time-travel" debuggers: by periodic checkpointing.

I think that comment could be misleading.

According to the Academic Press Dictionary of Science and Technology,
"checkpoint" means

 |      [...] Computer Programming.  A designated point in a program where
 |      processing is interrupted and all status information is recorded
 |      in order to be able to restart the process at that point, thus
 |      avoiding the necessity to repeat the processing from the beginning.

So I think it would be reasonable to interpret Xavier's comment as
meaning that you must periodically save the entire state of the program.

But that's not how logic programming debuggers, such as those for Mercury
and various Prolog implementations, do it.  Rather than periodically
checkpointing the entire state, these systems keep an incremental record
of all destructive updates performed, on a separate stack called the
"trail".  On backtracking, the system will unwind the trail,
restoring all the modified objects to their original values.

Now, this may be a matter of terminology.  I consider "checkpointing"
and "trailing" to be two different ways of achieving the same result
("replay debugging", in this case, or more generally "roll-back capability"). 
But maybe Xavier had in mind a broader definition of "checkpointing",
which would encompass trailing.

> We learnt this trick from Andrew Tolmach's thesis:
>         http://www.cs.pdx.edu/~apt/thesis.ps.Z

Looking at the details here [or at least those which show up on the first
few pages -- after that, ghostview reports a Postscript error :-( ],
it seems that the technique described here is actually much more
similar to typical Prolog implementations than Ocaml's fork()-based
implementation.  In particular, Tolmach uses a "history log", which
sounds like it would be pretty much identical to the Prolog trail,
for recording updates to mutable data structures.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] replay debugger

[Xavier Leroy]

> > Like all "time-travel" debuggers: by periodic checkpointing.
> 
> I think that comment could be misleading.
> [Another way to do replay: undo trail]

OK, I agree my comment was an excessive generalization.  As you said,
an undo trail can also be maintained, although this is not what the
OCaml debugger does.

> > We learnt this trick from Andrew Tolmach's thesis:
> >         http://www.cs.pdx.edu/~apt/thesis.ps.Z
> 
> Looking at the details here [or at least those which show up on the first
> few pages -- after that, ghostview reports a Postscript error :-( ],
> it seems that the technique described here is actually much more
> similar to typical Prolog implementations than Ocaml's fork()-based
> implementation.  In particular, Tolmach uses a "history log", which
> sounds like it would be pretty much identical to the Prolog trail,
> for recording updates to mutable data structures.

Tolmach's debugger uses a undo trail to deal with I/O and mutable data
structures, but relies on call/cc to do checkpointing on the "control"
part of the program execution.  So, it's somewhere in between.

- Xavier Leroy
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

[Caml-list] Beware of compare (and Ocaml beaten by Java)

[Mattias Waldau]

Why isn't compare compiled as '-'? According to the definition
of compare this should be okay.

The reason why I am asking this can be found below.

/mattias


Suffix arrays are very efficient for fast string searching 
in big texts. I implemented a first nice version, which 
took 40 s to run on my P4, when applied to the bible (4.5 MB)

The core of the slow program is

(* compare two substrings of the SAME text 
   [compare x y] returns [0] if [x=y], a negative integer if
   [x<y], and a positive integer if [x>y] *)
let rec same_substr_compare str idx1 idx2 : int =
  let length = String.length str in
  (* shortest string is smaller *)
  if idx1 = length then -1 else
  if idx2 = length then 1 else 
  (* compare one char *)
  let res = compare str.[idx1] str.[idx2] in
  (* char was equal, recurse *)
  if res = 0 then same_substr_compare str (idx1+1) (idx2+1)
  (* char was different, finished *)
  else res ;;

(* create and sort index array for string *)
let create_index str : int array =
  let idx = Array.init (String.length str) (fun ii -> ii) in
  Array.stable_sort (same_substr_compare str) idx;
  idx ;;

However, a colleague implemented it using Java. His code 
only takes 15 s to run.

Thus, I had to further tune the code by replacing 'compare' 
with '-', inlining better and removing bound-checking 
on strings and arrays. The new version runs in 10 s. 

During this lesson I learned that
1. compare is incredible slow! By replacing

	let res = compare str.[idx1] str.[idx2] in

with
	
	let res = (-) (int_of_char str.[idx1]) (int_of_char str.[idx2]) in

the run-time of the complete program went down 
from 20 s to 10 s.

2. Tail-recursive comparation is faster than using a 
loop and exit (runtime down from 80s to 60s). See the file
other_compares.ml in the nice version for these other attempts, 
one example is

exception Result of int ;;
let substr_compare str idx1 idx2 : int =
  let res = compare str.[idx1] str.[idx2] in
  if res <> 0 then res 
  else try
    let length = String.length str in
    let max_size = if idx1 > idx2 then
      length - idx1 
    else length - idx2 in
    for offset = 1 to max_size - 1 do
      let res = compare str.[idx1+offset] str.[idx2+offset] in
      if res<>0 then raise (Result res);
    done;
    0
  with Result res -> res ;;

3. Mergesort (=Array.stable_sort) is faster than 
heapsort (=Array.sort). (runtime down from 60s to 40s).
(I also tried quicksort (=Sort.array), but after 8 hours
it still hadn't finished.)

4. The rest is inline and removing bounds checking.

This is the first time I got beaten by Java, I will 
have to reevaluate Java. Note that Java still does 
bounds checking!

/mattias

The nice version is at 
http://www.abc.se/~m10217/download/mans.tar.bz2

The fast version is at
http://www.abc.se/~m10217/download/mans.opt.tar.bz2

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Beware of compare (and Ocaml beaten by Java)

[Xavier Leroy]

> Why isn't compare compiled as '-'? According to the definition
> of compare this should be okay.

I assume you mean "compare at type int -> int -> int", because for
types represented as pointers, pointer subtraction wouldn't give
reliable results -- for one thing, the GC can move blocks around.

Even on integer arguments, "-" cannot be used due to arithmetic
overflow:

  compare min_int max_int = -1    (* correct *)
  min_int - max_int = 1           (* incorrect *)

So, replacing "compare" by "-" is only valid for small integer types
such as "char" and enumerated datatypes, and I felt this wasn't
important enough to implement.  (Given your example, you'll disagree,
of course.)

> The core of the slow program is
> 
> (* compare two substrings of the SAME text 
>    [compare x y] returns [0] if [x=y], a negative integer if
>    [x<y], and a positive integer if [x>y] *)
> let rec same_substr_compare str idx1 idx2 : int =
>   let length = String.length str in
>   (* shortest string is smaller *)
>   if idx1 = length then -1 else
>   if idx2 = length then 1 else 
>   (* compare one char *)
>   let res = compare str.[idx1] str.[idx2] in
>   (* char was equal, recurse *)
>   if res = 0 then same_substr_compare str (idx1+1) (idx2+1)
>   (* char was different, finished *)
>   else res ;;

I get the impression that same_substr_compare never returns 0; is this
intentional?

> 3. Mergesort (=Array.stable_sort) is faster than 
> heapsort (=Array.sort). (runtime down from 60s to 40s).
> (I also tried quicksort (=Sort.array), but after 8 hours
> it still hadn't finished.)

This is a bit surprising: you might have hit one of those cases where
Quicksort is O(n^2), but it could also be the case that Sort.array
malfunctions because your comparison function is not a proper
comparison function (it doesn't return 0 for equal things).

- Xavier Leroy
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

RE: [Caml-list] Beware of compare (and Ocaml beaten by Java)

[Mattias Waldau]

> I assume you mean "compare at type int -> int -> int", because for
> types represented as pointers, pointer subtraction wouldn't give
> reliable results -- for one thing, the GC can move blocks around.

Yes.

> 
> Even on integer arguments, "-" cannot be used due to arithmetic
> overflow:
> 
>   compare min_int max_int = -1    (* correct *)
>   min_int - max_int = 1           (* incorrect *)
> 
> So, replacing "compare" by "-" is only valid for small integer types
> such as "char" and enumerated datatypes, and I felt this wasn't
> important enough to implement.  (Given your example, you'll disagree,
> of course.)

Yes, you are right, overflow is a problem. Maybe using "-" instead of 
compare should just be a tip instead next to the documentation of compare.

> 
> > The core of the slow program is
> > 
> > (* compare two substrings of the SAME text 
> >    [compare x y] returns [0] if [x=y], a negative integer if
> >    [x<y], and a positive integer if [x>y] *)
> > let rec same_substr_compare str idx1 idx2 : int =
> >   let length = String.length str in
> >   (* shortest string is smaller *)
> >   if idx1 = length then -1 else
> >   if idx2 = length then 1 else 
> >   (* compare one char *)
> >   let res = compare str.[idx1] str.[idx2] in
> >   (* char was equal, recurse *)
> >   if res = 0 then same_substr_compare str (idx1+1) (idx2+1)
> >   (* char was different, finished *)
> >   else res ;;
> 
> I get the impression that same_substr_compare never returns 0; is this
> intentional?

Since I compare substrings of the same string from different positions 
to the end of the string, there will never be any identical 
substrings (one of them will always be shorter).

> 
> > 3. Mergesort (=Array.stable_sort) is faster than 
> > heapsort (=Array.sort). (runtime down from 60s to 40s).
> > (I also tried quicksort (=Sort.array), but after 8 hours
> > it still hadn't finished.)
> 
> This is a bit surprising: you might have hit one of those cases where
> Quicksort is O(n^2), but it could also be the case that Sort.array
> malfunctions because your comparison function is not a proper
> comparison function (it doesn't return 0 for equal things).

It worked on smaller datasets, so I think I found an O(n^2)-case.
My Java-collegue had the same problem and had to implement merge sort.
I didn't look into it a lot.

> 
> - Xavier Leroy
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Beware of compare (and Ocaml beaten by Java)

[Pierre Weis]

[...]
> It worked on smaller datasets, so I think I found an O(n^2)-case.
> My Java-collegue had the same problem and had to implement merge sort.
> I didn't look into it a lot.

I would be extremely interested at having a look at your collegue's
Java code. You may have used slightly different algorithms that could
explain the observed behaviour ...

Could you please send us the Java code ?

Regards,

Pierre Weis

INRIA, Projet Cristal, Pierre.Weis@inria.fr, http://pauillac.inria.fr/~weis/


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] Beware of compare (and Ocaml beaten by Java)

[Chris Hecker]

At 10:12 AM 11/30/01 +0100, Pierre Weis wrote:
>I would be extremely interested at having a look at your collegue's
>Java code. You may have used slightly different algorithms that could
>explain the observed behaviour ...
>Could you please send us the Java code ?

I'd be interested in a short report on this if anybody has the time to write one up to the list.  Was there a different algorithm, or was it an actual performance difference?

Chris


-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

[Caml-list] bytegen.comp_expr error when doing object copying

[Neil Inala]

Perhaps this should go to caml-bugs only, but I thought discussions
on the list might disambiguate some assumptions I'm making.  Also
I'm not sure it's a bug.  In the code below (section 1), everything
seems to work fine.  The code compiles with no problems.  In the
almost-identical code section 2, the compiler emits the following:

v/64
>> Fatal error: Bytegen.comp_expr: var v_64
Uncaught exception: Misc.Fatal_error

Now, I know why this happens; in code section 2, the val v is
declared only after the definition of make_altered_self.  So when
the compiler gets to the object copying expression {< v = 5 >},
it has no variable v available to it.  It seems to me, however,
that the compiler should either not give an error or emit a
different error.

Not giving an error would fit with my intuition that, in defining
the code for the object, I should be able to reference variables
defined anywhere in the same scope.  (note: I haven't experimented
here with modules or signatures, but I have the feeling that
if I were to declare signatures first the code in section 2
would compile fine).

As for giving a different error, some experimentation indicates
what might be a better way of reporting this.  If we replace the
{< v = 5 >} with {< v2 = 5 >}, for example, the compiler says
"Unbound instance variable v2".  If we replace the {< v = 5 >}
with {< v = 5.0 >}, the error is "This expression has type float
but is here used with type int".  These are both more informative,
and neither is of the same class of error as
"Fatal error: Bytegen.comp_expr".  This is because the compiler
does type checking before it does byte code generation, and does
so based on the entire section of code that it slurps in, as we
see in code section 3, excerpted from
ocaml-src-3.02/driver/compile.ml.  Yet byte generation can only
generate code based on what it has already seen added to its
available environment.  This is made clear when examining the
lambda and rawlambda dumps from the compiler.

It seems like the compiler type checks the source in section 2
just fine, so thinks it's ok to proceed to code generation.  Then,
when the variable isn't available, the compiler thinks something
has gone badly wrong and so emits a rather uninformative Fatal_error.

So lacking requisite knowledge of the object/type theory involved,
I must ask you all whether it makes sense to treat class definition
in the same way recursive definitions are treated (or maybe like
prototypes/forward declarations, ugh), and read in all defined
variables before code is emitted; or simply to modify the
code in section 4 (from ocaml-src/bytecomp/bytegen.ml) to say
something along the lines of "variable v not found" rather than
just Fatal_error.  The problem with the latter solution, while
it is more informative for the programmer, is that it seems like
the wrong kind of error (a fatal error rather than a typing or
'unbound' error).  Maybe I'm being too nitpicky?  Have I made
any wrong assumptions here?

Thanks for any feedback!                          -- Neil Inala


==== begin code section 1 =========
class virtual foo =
  object (_: 'a)
    method virtual make_altered_self : unit -> 'a
  end

class bar =
  object (self)
    inherit foo
    val v = 3
    method make_altered_self () = {< v = 5 >}
  end
==== end code =====================

==== begin code section 2 =========
class virtual foo =
  object (_: 'a)
    method virtual make_altered_self : unit -> 'a
  end

class bar =
  object (self)
    inherit foo
    method make_altered_self () = {< v = 5 >}
    val v = 3
  end

==== end code =====================

==== begin code section 3 =========
  try
    parse_file inputfile Parse.implementation ast_impl_magic_number
    ++ print_if ppf Clflags.dump_parsetree Printast.implementation
    ++ Typemod.type_implementation sourcefile prefixname modulename
env
    ++ Translmod.transl_implementation modulename
    ++ print_if ppf Clflags.dump_rawlambda Printlambda.lambda
    ++ Simplif.simplify_lambda
    ++ print_if ppf Clflags.dump_lambda Printlambda.lambda
    ++ Bytegen.compile_implementation modulename
    ++ print_if ppf Clflags.dump_instr Printinstr.instrlist
    ++ Emitcode.to_file oc modulename;
    Warnings.check_fatal ();
    remove_preprocessed inputfile;
    close_out oc;
  with x ->
    close_out oc;
    remove_file objfile;
    raise x

==== end code =====================

==== begin code section 4 =========
  match exp with
    Lvar id ->
      begin try
        let pos = Ident.find_same id env.ce_stack in
        Kacc(sz - pos) :: cont
      with Not_found ->
      try
        let pos = Ident.find_same id env.ce_heap in
        Kenvacc(pos) :: cont
      with Not_found ->
      try
        let ofs = Ident.find_same id env.ce_rec in
        Koffsetclosure(ofs) :: cont
      with Not_found ->
        Format.eprintf "%a@." Ident.print id;
        fatal_error ("Bytegen.comp_expr: var " ^ Ident.unique_name
id)
      end
==== end code =====================






__________________________________________________
Do You Yahoo!?
Yahoo! GeoCities - quick and easy web site hosting, just $8.95/month.
http://geocities.yahoo.com/ps/info1
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr

Re: [Caml-list] bytegen.comp_expr error when doing object copying

[Xavier Leroy]

> Perhaps this should go to caml-bugs only, but I thought discussions
> on the list might disambiguate some assumptions I'm making.  Also
> I'm not sure it's a bug.  In the code below (section 1), everything
> seems to work fine.  The code compiles with no problems.  In the
> almost-identical code section 2, the compiler emits the following:
> 
> v/64
> >> Fatal error: Bytegen.comp_expr: var v_64
> Uncaught exception: Misc.Fatal_error

This is most certainly a bug in the compiler. "Fatal errors" are,
well, just that: internal inconsistencies in the compiler that should
never happen.

We will investigate, but it would have been preferable to submit a bug
report to caml-bugs@inria.fr: these get archived automatically and are
much harder for us to forget about :-)

- Xavier Leroy
-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr