Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

ocamldep loops #7643

Closed
vicuna opened this issue Sep 27, 2017 · 7 comments
Closed

ocamldep loops #7643

vicuna opened this issue Sep 27, 2017 · 7 comments
Assignees
Milestone

Comments

@vicuna
Copy link

vicuna commented Sep 27, 2017

Original bug ID: 7643
Reporter: ChriChri
Assigned to: @Octachron
Status: resolved (set by @gasche on 2017-10-19T12:39:07Z)
Resolution: fixed
Priority: normal
Severity: minor
Version: 4.05.0
Target version: 4.06.0 +dev/beta1/beta2/rc1
Fixed in version: 4.07.0+dev/beta2/rc1/rc2
Category: tools (ocaml{lex,yacc,dep,debug,...})
Monitored by: ChriChri

Bug description

ocamldep loops on the attached file (clearly this file is exposing a
pb with my code generator that I am solving, but ocamldep should not loop)

May be it does not loop, but run for too long ... I killed after 1mn

Note: the memory is not growing.

File attachments

@vicuna
Copy link
Author

vicuna commented Sep 27, 2017

Comment author: ChriChri

I confirm: the pb is due to the nested includes on got away when I fixed my generator.

@vicuna
Copy link
Author

vicuna commented Sep 28, 2017

Comment author: @gasche

This issue falls under the general rule: "Weird-looking generated code is not given first-class support within the compiler distribution, fixes for compiler blowup are not prioritized and will only be merged if they preserve readability/maintainability of the compiler codebase".

Of course we cannot know whether a readable fix exist without understanding the issue, and the idea that there may exist an algorithmic bug within ocamldep made me curious, so I wrote this reproduction script:

generate.ml:

let rec generate = function
| 0 -> ()
| i ->
let open Printf in
printf "let _ = Foo.x\n";
printf "include struct\n";
generate (i - 1);
printf "end\n"

let () = match int_of_string Sys.argv.(1) with
| n -> generate n
| exception _ ->
prerr_endline "please provide an integer as command-line argument";
exit 2

The command (ocaml generate.ml 24) produces a file that ocamldep.opt takes 3 seconds on. Increasing the argument increases computation time quickly, but for smaller argument values (below 20) the processing is still instantaneous.

I would like to understand what's so bad with this code (there is only one external dependency, Foo, and the included modules export no names, so no data-structure should grow too big), and using this as an excuse to play with memory profilers.

@vicuna
Copy link
Author

vicuna commented Sep 28, 2017

Comment author: @Octachron

I have played a bit with spacetime on a similar code generator, and the memory profile and allocation rate are flat. Contrarily, for 24 nested include, the add_struct_item somehow ends up being called more than 61M times when there is only 48 structure item in the code.

@vicuna
Copy link
Author

vicuna commented Sep 28, 2017

Comment author: @gasche

Well, add_module_binding calls both:

  • add_module,
    which calls add_structure in the Pmod_structure case,
    which calls add_structure_binding on the structure items
  • and add_structure_binding on the structure items (in the Pmod_structure case)

So there is an duplication of calls here which leads to an exponential blowup.

@vicuna
Copy link
Author

vicuna commented Sep 28, 2017

Comment author: @Octachron

A fix is available at #1377 .
ChriChri, would you like to be cited for the bug report? And if yes, under which identity?.

@vicuna
Copy link
Author

vicuna commented Sep 28, 2017

Comment author: ChriChri

Yes I don't mind being cited as Christophe Raffalli.
Thanks for the fix!

@vicuna
Copy link
Author

vicuna commented Oct 19, 2017

Comment author: @gasche

Florian's fix was merged in trunk (future 4.07).

@vicuna vicuna closed this as completed Oct 19, 2017
@vicuna vicuna added the tools label Mar 14, 2019
@vicuna vicuna added this to the 4.06.0 milestone Mar 14, 2019
@vicuna vicuna added the bug label Mar 20, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants