Mantis Bug Tracker

View Issue Details Jump to Notes ] Issue History ] Print ]
IDProjectCategoryView StatusDate SubmittedLast Update
0007643OCamltools (ocaml{lex,yacc,dep,debug,...})public2017-09-28 01:382017-10-19 14:39
ReporterChriChri 
Assigned Tooctachron 
PrioritynormalSeverityminorReproducibilityalways
StatusresolvedResolutionfixed 
PlatformOSOS Version
Product Version4.05.0 
Target Version4.06.0 +dev/beta1/beta2/rc1Fixed in Version4.07.0+dev/beta2/rc1/rc2 
Summary0007643: ocamldep loops
Descriptionocamldep 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.
TagsNo tags attached.
Attached Files? file icon foo.ml [^] (183,871 bytes) 2017-09-28 01:38 [Show Content]

- Relationships

-  Notes
(0018375)
ChriChri (reporter)
2017-09-28 01:43

I confirm: the pb is due to the nested includes on got away when I fixed my generator.
(0018378)
gasche (administrator)
2017-09-28 10:15
edited on: 2017-09-28 10:16

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.

(0018379)
octachron (developer)
2017-09-28 10:48

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.
(0018381)
gasche (administrator)
2017-09-28 11:24

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.
(0018384)
octachron (developer)
2017-09-28 13:50

A fix is available at https://github.com/ocaml/ocaml/pull/1377 [^] .
ChriChri, would you like to be cited for the bug report? And if yes, under which identity?.
(0018385)
ChriChri (reporter)
2017-09-28 13:53
edited on: 2017-09-30 20:32

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

(0018589)
gasche (administrator)
2017-10-19 14:39

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

- Issue History
Date Modified Username Field Change
2017-09-28 01:38 ChriChri New Issue
2017-09-28 01:38 ChriChri File Added: foo.ml
2017-09-28 01:43 ChriChri Note Added: 0018375
2017-09-28 10:15 gasche Note Added: 0018378
2017-09-28 10:16 gasche Note Edited: 0018378 View Revisions
2017-09-28 10:48 octachron Note Added: 0018379
2017-09-28 11:24 gasche Note Added: 0018381
2017-09-28 13:47 octachron Assigned To => octachron
2017-09-28 13:47 octachron Severity major => minor
2017-09-28 13:47 octachron Status new => assigned
2017-09-28 13:50 octachron Note Added: 0018384
2017-09-28 13:53 ChriChri Note Added: 0018385
2017-09-30 20:32 ChriChri Note Edited: 0018385 View Revisions
2017-10-02 13:57 doligez Target Version => 4.06.0 +dev/beta1/beta2/rc1
2017-10-19 14:39 gasche Note Added: 0018589
2017-10-19 14:39 gasche Status assigned => resolved
2017-10-19 14:39 gasche Fixed in Version => 4.07.0+dev/beta2/rc1/rc2
2017-10-19 14:39 gasche Resolution open => fixed


Copyright © 2000 - 2011 MantisBT Group
Powered by Mantis Bugtracker