www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Incremental compilation with DMD

reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Short story: DMD probably needs an option to output template instances 
to all object files that need them.

Long story:

I've been trying to make incremental compilation in xfBuild reliable, 
but it turns out that it's really tricky with DMD. Consider the 
following example:

* module A instantiates template T from module C
* module B instantiates the same template T from module C (with the same 
arguments)
* compile all modules at the same time in the order: A, B, C
* now A.obj contains the instantiation of T
* remove the instantiation from the A module
* perform an incremental compilation - 'A' was changed, so only it has 
to be recompiled
* linking of A.obj, B.obj and C.obj fails because no module has the 
instantiation of T for B.obj

What happens is that the optimization in DMD to only emit templates to 
the first module that needs it creates implicit inter-module 
dependencies. I've tried tracking them by modifying DMD, but still 
wouldn't find them all - it seems that one would have to dig deep in the 
codegen, my attempts at hacking the frontend (mostly template.c) weren't 
enough.

Yet, I still managed to get some of these implicit dependencies figured 
and attempted using this extra info in xfBuild when deciding what to 
compile incrementally. I've tossed it on a project of mine with > 350 
modules and no circular imports. The result was that even a trivial 
change caused most of the project to be pulled into compilation.

When doing regular incremental compilation, all modules that import the 
modified ones must be recompiled as well. And all modules that import 
these, and so on, up to the root of the project. This is because the 
incremental build tool must assume that the modules that import module 
'A' could have code of the form 'static if (A.something) { ... } else { 
... }' or another form of it. As far as I know, it's not trivial to 
detect whether this is really the case or whether the change is isolated 
to 'A'.

When trying to cope with the implicit dependencies caused by template 
instantiations and references, one also has to recompile all modules 
that contain template references to a module/object file which gets the 
instance. In the first example, it would mean recompiling module 'B' 
whenever 'A' changes. The graph of dependencies here doesn't depend very 
much on the structure of imports in a project, but rather in the order 
that DMD decides to run semantic() on template instances.

Add up these two conservative mechanisms and it turns out that tweaking 
a simple function causes half of your project to be rebuilt. This is not 
acceptable. Even if it was feasible - getting these implicit 
dependencies is probably a matter of either hacking the backend or 
dumping object files and matching unresolved symbols with comdats. 
Neither would be very fast or portable.

Compiling modules one-at-a-time is not a solution because it's too slow.

Thus my suggestion of adding an option to DMD so it may emit template 
instances to all object files that use them. If anyone has alternative 
ideas, I'd be glad to hear them, because I'm running out of options. The 
approach I'm currently using in an experimental version of xfBuild is:

* get a fixed order of modules to be compiled determined by the order 
DMD calls semantic() on them with the root modules at the end
* when a module is modified, additionally recompile all modules that 
occur after it in the list

This quite obviously ends up compiling way too many modules, but seems 
to work reliably (except when OPTLINK decides to crash) without 
requiring full rebuilds all the time. Still, I fear there might be 
corner cases where it will fail as well. DMD sometimes places 
initializers in weird places, e.g.:

.objs\xf-nucleus-model-ILinkedKernel.obj(xf-nucleus-model-ILinkedKernel)
  Error 42: Symbol Undefined 
_D61TypeInfo_S2xf7nucleus9particles13BasicParticle13BasicParticle6__initZ

The two modules (xf.nucleus.model.ILinkedKernel and 
xf.nucleus.particles.BasicParticle) are unrelated. This error occured 
once, somewhere deep into an automated attempt to break the experimental 
xfBuild by touching random modules and performing incremental builds.


-- 
Tomasz Stachowiak
http://h3.team0xf.com/
h3/h3r3tic on #D freenode
Sep 11 2009
next sibling parent Ary Borenszweig <ary esperanto.org.ar> writes:
Tom S escribió:
 Short story: DMD probably needs an option to output template instances 
 to all object files that need them.

Hi Tom, What you describe here is very interesting and useful. I think of adding an incremental builder to Descent in some point in the future and I'll probably encounter the same problem. So I vote++ to emmiting template instances in every obj that uses them.
Sep 11 2009
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Fri, 11 Sep 2009 07:47:11 -0400, Tom S  
<h3r3tic remove.mat.uni.torun.pl> wrote:
 Short story: DMD probably needs an option to output template instances  
 to all object files that need them.

 Long story:

 I've been trying to make incremental compilation in xfBuild reliable,  
 but it turns out that it's really tricky with DMD. Consider the  
 following example:

 * module A instantiates template T from module C
 * module B instantiates the same template T from module C (with the same  
 arguments)
 * compile all modules at the same time in the order: A, B, C
 * now A.obj contains the instantiation of T
 * remove the instantiation from the A module
 * perform an incremental compilation - 'A' was changed, so only it has  
 to be recompiled
 * linking of A.obj, B.obj and C.obj fails because no module has the  
 instantiation of T for B.obj

 What happens is that the optimization in DMD to only emit templates to  
 the first module that needs it creates implicit inter-module  
 dependencies. I've tried tracking them by modifying DMD, but still  
 wouldn't find them all - it seems that one would have to dig deep in the  
 codegen, my attempts at hacking the frontend (mostly template.c) weren't  
 enough.

 Yet, I still managed to get some of these implicit dependencies figured  
 and attempted using this extra info in xfBuild when deciding what to  
 compile incrementally. I've tossed it on a project of mine with > 350  
 modules and no circular imports. The result was that even a trivial  
 change caused most of the project to be pulled into compilation.

 When doing regular incremental compilation, all modules that import the  
 modified ones must be recompiled as well. And all modules that import  
 these, and so on, up to the root of the project. This is because the  
 incremental build tool must assume that the modules that import module  
 'A' could have code of the form 'static if (A.something) { ... } else {  
 ... }' or another form of it. As far as I know, it's not trivial to  
 detect whether this is really the case or whether the change is isolated  
 to 'A'.

 When trying to cope with the implicit dependencies caused by template  
 instantiations and references, one also has to recompile all modules  
 that contain template references to a module/object file which gets the  
 instance. In the first example, it would mean recompiling module 'B'  
 whenever 'A' changes. The graph of dependencies here doesn't depend very  
 much on the structure of imports in a project, but rather in the order  
 that DMD decides to run semantic() on template instances.

 Add up these two conservative mechanisms and it turns out that tweaking  
 a simple function causes half of your project to be rebuilt. This is not  
 acceptable. Even if it was feasible - getting these implicit  
 dependencies is probably a matter of either hacking the backend or  
 dumping object files and matching unresolved symbols with comdats.  
 Neither would be very fast or portable.

 Compiling modules one-at-a-time is not a solution because it's too slow.

 Thus my suggestion of adding an option to DMD so it may emit template  
 instances to all object files that use them. If anyone has alternative  
 ideas, I'd be glad to hear them, because I'm running out of options. The  
 approach I'm currently using in an experimental version of xfBuild is:

 * get a fixed order of modules to be compiled determined by the order  
 DMD calls semantic() on them with the root modules at the end
 * when a module is modified, additionally recompile all modules that  
 occur after it in the list

 This quite obviously ends up compiling way too many modules, but seems  
 to work reliably (except when OPTLINK decides to crash) without  
 requiring full rebuilds all the time. Still, I fear there might be  
 corner cases where it will fail as well. DMD sometimes places  
 initializers in weird places, e.g.:

 .objs\xf-nucleus-model-ILinkedKernel.obj(xf-nucleus-model-ILinkedKernel)
   Error 42: Symbol Undefined  
 _D61TypeInfo_S2xf7nucleus9particles13BasicParticle13BasicParticle6__initZ

 The two modules (xf.nucleus.model.ILinkedKernel and  
 xf.nucleus.particles.BasicParticle) are unrelated. This error occured  
 once, somewhere deep into an automated attempt to break the experimental  
 xfBuild by touching random modules and performing incremental builds.

On the other hand, one-at-a-time builds can be done in parallel if you have multi-cores. Of course, still not a net win on my system, so vote++
Sep 11 2009
prev sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
Tom S wrote:
 Thus my suggestion of adding an option to DMD so it may emit template 
 instances to all object files that use them. If anyone has alternative 
 ideas, I'd be glad to hear them, because I'm running out of options.

Try compiling with -lib, which will put each template instance into its own obj file.
Sep 11 2009
parent reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Walter Bright wrote:
 Tom S wrote:
 Thus my suggestion of adding an option to DMD so it may emit template 
 instances to all object files that use them. If anyone has alternative 
 ideas, I'd be glad to hear them, because I'm running out of options.

Try compiling with -lib, which will put each template instance into its own obj file.

Thanks for the suggestion. Unfortunately it's a no-go since -lib seems to have the same issue that compiling without -op does - if you have multiple modules with the same name (but different packages), one will overwrite the other in the lib. On the other hand, I was able to hack DMD a bit and use -multiobj since your suggestion gave me an idea :) Basically, the approach would be to compile the project with -multiobj and move the generated objects to a local (per project) directory, renaming them so no conflicts arise. The next step is to determine all public and comdat symbols in all of these object files - this might be done via a specialized program, however I've used Burton Radons' exelib to optimally run libunres.exe from DMC. The exports are saved to some sort of a database (a dumb structured file is ok). The following is done on the initial build - so the next time we have some object files in a directory and a map of all their exported symbols. In an incremental step, we'll compile the modified modules, but don't move their object files immediately over to the special directory. We'll instead scan their public and comdat symbols and figure out which object files they replace from our already compiled set. For each symbol in the newly compiled objects, find which object in the original set defined it, then mark it. For all marked files, add them to a library ( I call it junk.lib ), then remove the source object. Finally, move the newly compiled objects to the special object directory. The junk.lib will be used if the newly compiled object files missed any shared symbols that were in the old objects and that would be generated, had more modules be passed to the compiler. In other words, it contains symbols that the naive incremental compilation will lose. When linking, all object files from the directory are passed explicitly to the compiler and symbols are pulled eagerly from them, however junk.lib will be queried only if a symbol cannot be found in the set of objects in the special directory. I've put up a proof-of-concept implementation at http://h3.team0xf.com/increBuild.7z . It requires a slightly patched DMD (well, hacked actually), so it prints out the names of all objects it generates. Basically, uncomment the `printf("writing '%s'\n", fname);` in glue.c at line 133 and add `printf("writing '%s'\n", m->objfile->name->str);` after `m->genobjfile(global.params.multiobj);` in mars.c. I'm compiling the build tool with a recent (SVN-ish) version of Tango and DMD 1.047. As for my own impressions of this idea, its biggest drawback probably is that the multitude of object files created via -multiobj strains the filesystem. Even when running on a ramdrive, my WinXP-based system took a good fraction of a second to move a few hundred object files to their destination directory. This can probably be improved on, as -multiobj seems to produce some empty object files (at least according to libunres and ddlinfo). It might also be possible to use specialized storage for object files by patching up dmd and hooking OPTLINK's calls to CreateFile. I'm not sure about Linux, but perhaps something based on FUSE might work. These last options are probably long shots, so I'm still quite curious how DMD might perform with outputting template instantiations into each object file that uses them. -- Tomasz Stachowiak http://h3.team0xf.com/ h3/h3r3tic on #D freenode
Sep 12 2009
next sibling parent Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Tom S wrote:
 Walter Bright wrote:
 Tom S wrote:
 Thus my suggestion of adding an option to DMD so it may emit template 
 instances to all object files that use them. If anyone has 
 alternative ideas, I'd be glad to hear them, because I'm running out 
 of options.

Try compiling with -lib, which will put each template instance into its own obj file.

Thanks for the suggestion. Unfortunately it's a no-go since -lib seems to have the same issue that compiling without -op does - if you have multiple modules with the same name (but different packages), one will overwrite the other in the lib.

To clarify, this is not the only issue with -lib. The libs would either have to be expanded into objects or static ctors would not run. And why extract them if -multiobj already generates them extracted? -- Tomasz Stachowiak http://h3.team0xf.com/ h3/h3r3tic on #D freenode
Sep 12 2009
prev sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
Tom S wrote:
 As for my own impressions of this idea, its biggest drawback probably is 
 that the multitude of object files created via -multiobj strains the 
 filesystem.

Sure, but -multiobj and -lib generate exactly the same object files, it's just that -lib puts them all into a library so it doesn't strain the file system. Extracting the obj files from the lib is pretty simple, you can see the libomf.c for the format.
Sep 12 2009
parent reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Walter Bright wrote:
 Tom S wrote:
 As for my own impressions of this idea, its biggest drawback probably 
 is that the multitude of object files created via -multiobj strains 
 the filesystem.

Sure, but -multiobj and -lib generate exactly the same object files, it's just that -lib puts them all into a library so it doesn't strain the file system. Extracting the obj files from the lib is pretty simple, you can see the libomf.c for the format.

You're right, I'm sorry. I must've overlooked something in the lib dumps and assumed one module overwrites the other. So with -lib, it should be possible to only extract the object files that contain static constructors and the main function and keep the rest packed up. Does that sound about right? By the way, using -lib causes DMD to eat a LOT of memory compared to the 'normal' mode - in one of my projects, it eats up easily > 1.2GB and dies. This could be a downside to this approach. I haven't tested whether it's the same with -multiobj Would it be hard to add an option to DMD to control template emission? Apparently GDC has -femit-templates, so it's doable ;) LDC outputs instantiations to all objects. -- Tomasz Stachowiak http://h3.team0xf.com/ h3/h3r3tic on #D freenode
Sep 12 2009
parent reply Walter Bright <newshound1 digitalmars.com> writes:
Tom S wrote:
 Walter Bright wrote:
 Tom S wrote:
 As for my own impressions of this idea, its biggest drawback probably 
 is that the multitude of object files created via -multiobj strains 
 the filesystem.

Sure, but -multiobj and -lib generate exactly the same object files, it's just that -lib puts them all into a library so it doesn't strain the file system. Extracting the obj files from the lib is pretty simple, you can see the libomf.c for the format.

You're right, I'm sorry. I must've overlooked something in the lib dumps and assumed one module overwrites the other. So with -lib, it should be possible to only extract the object files that contain static constructors and the main function and keep the rest packed up. Does that sound about right?

All the .lib file is, is: [header] [all the object files concatenated together and aligned] [dictionary and index] Linux .a libraries are the same idea, just a different format for the header, dictionary and index. The obj files are unmodified in the library. You can extract them based on whatever criteria you need.
 By the way, using -lib causes DMD to eat a LOT of memory compared to the 
 'normal' mode - in one of my projects, it eats up easily > 1.2GB and 
 dies. This could be a downside to this approach. I haven't tested 
 whether it's the same with -multiobj

Hmm. I build Phobos with -lib, and haven't experienced any problems, but it's possible as dmd doesn't ever discard any memory.
 Would it be hard to add an option to DMD to control template emission? 
 Apparently GDC has -femit-templates, so it's doable ;) LDC outputs 
 instantiations to all objects.

I've found the LDC approach to be generally a poor one (having much experience with it for C++, where there is no choice). It generates huge object files and there are often linker problems trying to remove the duplicates. I really got tired of "COMDAT" problems with linkers, and no, it wasn't just with Optlink. Having each template instantiation in its own obj file works out great, eliminating all those problems. I don't really understand why the -lib approach is not working for your needs.
Sep 12 2009
parent reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Walter Bright wrote:
 I don't really understand why the -lib approach is not working for your 
 needs.

I'm not sure what you mean by "the -lib approach". Just how do you exactly apply it to incremental compilation? If my project has a few hundred modules and I change just one line in one function, I don't want to rebuild it with -lib all again. I thought you were referring to the proof-of-concept incremental build tool I posted yesterday which used -multiobj, as it should be possible to optimize it using -lib... I just haven't tried that yet. -- Tomasz Stachowiak http://h3.team0xf.com/ h3/h3r3tic on #D freenode
Sep 12 2009
parent reply Walter Bright <newshound1 digitalmars.com> writes:
Tom S wrote:
 Walter Bright wrote:
 I don't really understand why the -lib approach is not working for 
 your needs.

I'm not sure what you mean by "the -lib approach". Just how do you exactly apply it to incremental compilation? If my project has a few hundred modules and I change just one line in one function, I don't want to rebuild it with -lib all again. I thought you were referring to the proof-of-concept incremental build tool I posted yesterday which used -multiobj, as it should be possible to optimize it using -lib... I just haven't tried that yet.

You only have to build one source file with -lib, not all of them.
Sep 12 2009
parent reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Walter Bright wrote:
 Tom S wrote:
 Walter Bright wrote:
 I don't really understand why the -lib approach is not working for 
 your needs.

I'm not sure what you mean by "the -lib approach". Just how do you exactly apply it to incremental compilation? If my project has a few hundred modules and I change just one line in one function, I don't want to rebuild it with -lib all again. I thought you were referring to the proof-of-concept incremental build tool I posted yesterday which used -multiobj, as it should be possible to optimize it using -lib... I just haven't tried that yet.

You only have to build one source file with -lib, not all of them.

So you mean compiling each file separately? That's only an option if we turn to the C/C++ way of doing projects - using .di files just like C headers - *everywhere*. Only then can changes in .d files be localized to just one module and compiled quickly. Java and C# do without header files because (to my knowledge) they have no means of changing what's compiled based on the contents of an imported module (basically they lack metaprogramming). So we could give up and do it the C/C++ way with lots of duplicated code in headers (C++ is better here with allowing you to only implement methods of a class in the .cpp file instead of rewriting the complete class and filling in member functions, like the .d/.di approach would force) or we might have an incremental build tool that doesn't suck. This is the picture as I see it: * I need to rebuild all modules that import the changed modules, because some code in them might evaluate differently (static ifs on the imported modules, for instance - I explained that in my first post in this topic). * I need to compile them all at once, because compiling each of them in succession yields massively long compile times. * With your suggestion of using -lib, I assumed that you were suggesting building all these modules at once into a lib and then figuring out what to do with their object files one by one. * Some object files need to be extracted because otherwise module ctors won't be linked into the executable. * As this is incremental compilation, there will be object files from the previous build, some of which should not be linked, because that would cause multiple definition errors. * The obsoleted object files can't be simply removed, since they might contain comdat symbols needed by some objects outside of the newly compiled set (I gave an example in my first post, but can provide actual D code that illustrates this issue). Thus they have to be moved into a lib and only pulled into linking on demand. That's how my experimental build tool maps to the "-lib approach". -- Tomasz Stachowiak http://h3.team0xf.com/ h3/h3r3tic on #D freenode
Sep 13 2009
parent reply Walter Bright <newshound1 digitalmars.com> writes:
Tom S wrote:
 Walter Bright wrote:
 Tom S wrote:
 Walter Bright wrote:
 I don't really understand why the -lib approach is not working for 
 your needs.

I'm not sure what you mean by "the -lib approach". Just how do you exactly apply it to incremental compilation? If my project has a few hundred modules and I change just one line in one function, I don't want to rebuild it with -lib all again. I thought you were referring to the proof-of-concept incremental build tool I posted yesterday which used -multiobj, as it should be possible to optimize it using -lib... I just haven't tried that yet.

You only have to build one source file with -lib, not all of them.

So you mean compiling each file separately?

Yes. Or a subset of the files.
 That's only an option if we 
 turn to the C/C++ way of doing projects - using .di files just like C 
 headers - *everywhere*. Only then can changes in .d files be localized 
 to just one module and compiled quickly. Java and C# do without header 
 files because (to my knowledge) they have no means of changing what's 
 compiled based on the contents of an imported module (basically they 
 lack metaprogramming).
 
 So we could give up and do it the C/C++ way with lots of duplicated code 
 in headers (C++ is better here with allowing you to only implement 
 methods of a class in the .cpp file instead of rewriting the complete 
 class and filling in member functions, like the .d/.di approach would 
 force) or we might have an incremental build tool that doesn't suck.
 
 This is the picture as I see it:
 
 * I need to rebuild all modules that import the changed modules, because 
 some code in them might evaluate differently (static ifs on the imported 
 modules, for instance - I explained that in my first post in this topic).
 
 * I need to compile them all at once, because compiling each of them in 
 succession yields massively long compile times.
 
 * With your suggestion of using -lib, I assumed that you were suggesting 
 building all these modules at once into a lib and then figuring out what 
 to do with their object files one by one.
 
 * Some object files need to be extracted because otherwise module ctors 
 won't be linked into the executable.
 
 * As this is incremental compilation, there will be object files from 
 the previous build, some of which should not be linked, because that 
 would cause multiple definition errors.
 
 * The obsoleted object files can't be simply removed, since they might 
 contain comdat symbols needed by some objects outside of the newly 
 compiled set (I gave an example in my first post, but can provide actual 
 D code that illustrates this issue). Thus they have to be moved into a 
 lib and only pulled into linking on demand.
 
 That's how my experimental build tool maps to the "-lib approach".

What you can try is creating a database that is basically a lib (call it A.lib) of all the modules compiled with -lib. Then recompile all modules that depend on changed modules in one command, also with -lib, call it B.lib. Then for all the obj's in B, replace the corresponding ones in A.
Sep 13 2009
next sibling parent reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Walter Bright wrote:
 What you can try is creating a database that is basically a lib (call it 
 A.lib) of all the modules compiled with -lib. Then recompile all modules 
 that depend on changed modules in one command, also with -lib, call it 
 B.lib. Then for all the obj's in B, replace the corresponding ones in A.

That's what I'm getting at :) -- Tomasz Stachowiak http://h3.team0xf.com/ h3/h3r3tic on #D freenode
Sep 13 2009
parent reply Walter Bright <newshound1 digitalmars.com> writes:
Tom S wrote:
 Walter Bright wrote:
 What you can try is creating a database that is basically a lib (call 
 it A.lib) of all the modules compiled with -lib. Then recompile all 
 modules that depend on changed modules in one command, also with -lib, 
 call it B.lib. Then for all the obj's in B, replace the corresponding 
 ones in A.

That's what I'm getting at :)

With this approach, you could wind up with some 'dead' obj files in A.lib, but aside from a bit of bloat in the lib file, they'll never wind up in the executable.
Sep 13 2009
parent reply Don <nospam nospam.com> writes:
Walter Bright wrote:
 Tom S wrote:
 Walter Bright wrote:
 What you can try is creating a database that is basically a lib (call 
 it A.lib) of all the modules compiled with -lib. Then recompile all 
 modules that depend on changed modules in one command, also with 
 -lib, call it B.lib. Then for all the obj's in B, replace the 
 corresponding ones in A.

That's what I'm getting at :)

With this approach, you could wind up with some 'dead' obj files in A.lib, but aside from a bit of bloat in the lib file, they'll never wind up in the executable.

I'm feeling horribly guilty for having asked for module-level static if(). I have a dreadful suspicion that it might have been a profoundly bad idea.
Sep 13 2009
parent Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Don wrote:
 Walter Bright wrote:
 Tom S wrote:
 Walter Bright wrote:
 What you can try is creating a database that is basically a lib 
 (call it A.lib) of all the modules compiled with -lib. Then 
 recompile all modules that depend on changed modules in one command, 
 also with -lib, call it B.lib. Then for all the obj's in B, replace 
 the corresponding ones in A.

That's what I'm getting at :)

With this approach, you could wind up with some 'dead' obj files in A.lib, but aside from a bit of bloat in the lib file, they'll never wind up in the executable.

I'm feeling horribly guilty for having asked for module-level static if(). I have a dreadful suspicion that it might have been a profoundly bad idea.

No need to feel guilty. This problem actually manifests itself in many other cases than just static if, e.g. changing an alias in the modified module, adding some fields to a struct or methods to a class. Basically anything that would bite us if we had C/C++ projects solely in .h files (except multiple definition errors). I've prepared some examples (.d and .bat files) of these at http://h3.team0xf.com/dependencyFail.7z (-version is used instead of literally changing the code). I have no idea how Java or C# deal with these. Could be smart linking or some sort of static analysis. As for the 'dead' obj files, one could run a 'garbage collection' step from time to time ;) -- Tomasz Stachowiak http://h3.team0xf.com/ h3/h3r3tic on #D freenode
Sep 13 2009
prev sibling parent reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Walter Bright wrote:
 What you can try is creating a database that is basically a lib (call it 
 A.lib) of all the modules compiled with -lib. Then recompile all modules 
 that depend on changed modules in one command, also with -lib, call it 
 B.lib. Then for all the obj's in B, replace the corresponding ones in A.

OK, there we go: http://h3.team0xf.com/increBuild2.7z // I hope it's fine to include LIBUNRES here. It's just for convenience. This is the second incarnation of that incremental build tool experiment. This time it uses -lib instead of -multiobj, as suggested by Walter. The algorithm works as follows: * compile modules to a .lib file * extract objects with static ctors or the __Dmain function (remove them from the lib) * find out which old object files should be replaced * any objects whose any symbols were re-generated in this compilation pass * pack up the obsoleted object files into a 'junk' library * prepend the 'junk' library to the /library chain/ * prepend the newly compiled library to the /library chain/ * link the executable by passing the cached object files and the whole library chain to the linker It doesn't use the simple approach of having just one 'junk'/'A.lib' library and appending objects to it, because that's pretty slow due to the librarian having to re-generate the dictionary at each such operation. So instead it keeps a chain of all libraries generated in this process and passes them to the linker in the right order. This will waste more space than the naive approach, but should be faster. The archive contains the source code and a compiled binary (DMD-Win only for now... Sorry, folks) as well as a little test in the test/ directory. It shows how naive incremental compilation fails (break.bat) and how this tool works (work.bat). The tool can be used with the latest Mercurial revision of xfBuild ( http://bitbucket.org/h3r3tic/xfbuild/ ) by passing "+cincreBuild" to it. The support is a massive hack though, so expect some strangeness. I was able to run it on the 'Test1' demo of my Hybrid GUI ( http://team0xf.com:1024/hybrid/file/c841d95675ca/Test1.d ) and a simple/dumb ray tracer based on OMG ( http://team0xf.com:1024/omg/file/5199ed783490/Tracer.d ). In incremental compilation it's not noticeably slower than the naive approach, however DMD consumes more memory in the -lib mode and the executables produced by this approach are larger for some reason. For instance, with Hybrid, Test1.exe has about 20MB with increBuild, compared to about 5MB with the traditional approach. Perhaps there's some simple way to remove this bloat, as compressed with UPX even with the fastest compression method the executables differ by just a few kilobytes. When building my second largest project, DMD eats up about 1.2GB of memory and dies (even without -g). Luckily, xfBuild allows me to set the limit of modules to be compiled at a time, so when I cap it to 200, it compiled... but didn't link :( Somewhere in the process a library is created that confuses OPTLINK as well as "lib -l". There's one symbol in it that neither of these are unable to see and it results in an undefined reference when linking. The symbol is clearly there when using a lib dumping tool from DDL or "libunres -d -c". I've dropped the lib at http://h3.team0xf.com/strangeLib.7z . The symbol in question is compressed and this newsgroup probably won't chew the non-ansi chars well, but it can be found via a regex "D2xf3omg4core.*ctFromRealVee0P0Z". One thing slowing this tool down is the need to call the librarian multiple times. DMD -lib will sometimes generate multiple objects with the same name and you can only extract them (when using the librarian) by running lib -x multiple times. DMD should probably be patched up to include fully qualified module names in objects instead of just the last name (foo.Mod and bar.Mod both yield Mod.obj in the library), as -op doesn't seem to help here. Another idea that will map well onto any incremental builder would be to write a tool that will find the differences between modules and tell whether e.g. they're limited to function bodies. Then an incremental builder could assume that it doesn't have to recompile any dependencies, just this one modified file. Unfortunately, this assumption doesn't always hold - functions could be used via CTFE to generate code, thus the changes escape. Personally I'm of the opinion that functions should be explicitly marked for CTFE, and this is just another reason for such. I'm using a patched DMD with added pragma(ctfe) which instructs the compiler not to run any codegen or generate debug info functions/aggregates marked as such. This trick alone can slim an executable down by a good megabyte, which sometimes is a life-saver with OPTLINK. I've been hearing that other people put their CTFE stuff into .di files, but this approach doesn't cover all cases of codegen via CTFE and string mixins. I'm afraid I won't be doing any other prototypes shortly - I really need to focus on my master's thesis :P But then, I don't really know how this tool can be improved without hacking the compiler or writing custom OMF processing. -- Tomasz Stachowiak http://h3.team0xf.com/ h3/h3r3tic on #D freenode
Sep 15 2009
next sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
Tom S wrote:
 Personally I'm of the opinion that functions should 
 be explicitly marked for CTFE, and this is just another reason for such. 
 I'm using a patched DMD with added pragma(ctfe) which instructs the 
 compiler not to run any codegen or generate debug info 
 functions/aggregates marked as such. This trick alone can slim an 
 executable down by a good megabyte, which sometimes is a life-saver with 
 OPTLINK.

If you are compiling files with -lib, and nobody calls those CTFE functions at runtime, then they should never be linked in. (Virtual functions are always linked in, as they have a reference to them even if they are never called.) Executables built this way shouldn't have dead functions in them.
Sep 17 2009
parent reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Walter Bright wrote:
 Tom S wrote:
 Personally I'm of the opinion that functions should be explicitly 
 marked for CTFE, and this is just another reason for such. I'm using a 
 patched DMD with added pragma(ctfe) which instructs the compiler not 
 to run any codegen or generate debug info functions/aggregates marked 
 as such. This trick alone can slim an executable down by a good 
 megabyte, which sometimes is a life-saver with OPTLINK.

If you are compiling files with -lib, and nobody calls those CTFE functions at runtime, then they should never be linked in. (Virtual functions are always linked in, as they have a reference to them even if they are never called.) Executables built this way shouldn't have dead functions in them.

It could be debug info, because with -g something definitely is linked in whether it's -lib or not (except with -lib there's way more of it). With ctfe-mixin-based metaprogramming, you also end up with string literals that don't seem to get optimized away by the linker. -- Tomasz Stachowiak http://h3.team0xf.com/ h3/h3r3tic on #D freenode
Sep 17 2009
parent reply Walter Bright <newshound1 digitalmars.com> writes:
Tom S wrote:
 Walter Bright wrote:
 Tom S wrote:
 Personally I'm of the opinion that functions should be explicitly 
 marked for CTFE, and this is just another reason for such. I'm using 
 a patched DMD with added pragma(ctfe) which instructs the compiler 
 not to run any codegen or generate debug info functions/aggregates 
 marked as such. This trick alone can slim an executable down by a 
 good megabyte, which sometimes is a life-saver with OPTLINK.

If you are compiling files with -lib, and nobody calls those CTFE functions at runtime, then they should never be linked in. (Virtual functions are always linked in, as they have a reference to them even if they are never called.) Executables built this way shouldn't have dead functions in them.

It could be debug info, because with -g something definitely is linked in whether it's -lib or not (except with -lib there's way more of it).

The linker doesn't pull in obj modules based on symbolic debug info. You can find out what is pulling in a particular module by deleting it from the library, linking, and seeing what undefined symbol message the linker produces.
 With ctfe-mixin-based metaprogramming, you also end up with string 
 literals that don't seem to get optimized away by the linker.

The linker has no idea what a string literal is, or what any other literals are, either. It doesn't know what a type is. It doesn't know what language the source code was. It only knows about symbols, sections, and bytes of binary data. The object module format offers no way to mark a piece of data as a string literal. I do think it is possible, though, for the compiler to do a better job of not putting unneeded literals into the obj file.
Sep 17 2009
parent reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Walter Bright wrote:
 Tom S wrote:
 Walter Bright wrote:
 Tom S wrote:
 Personally I'm of the opinion that functions should be explicitly 
 marked for CTFE, and this is just another reason for such. I'm using 
 a patched DMD with added pragma(ctfe) which instructs the compiler 
 not to run any codegen or generate debug info functions/aggregates 
 marked as such. This trick alone can slim an executable down by a 
 good megabyte, which sometimes is a life-saver with OPTLINK.

If you are compiling files with -lib, and nobody calls those CTFE functions at runtime, then they should never be linked in. (Virtual functions are always linked in, as they have a reference to them even if they are never called.) Executables built this way shouldn't have dead functions in them.

It could be debug info, because with -g something definitely is linked in whether it's -lib or not (except with -lib there's way more of it).

The linker doesn't pull in obj modules based on symbolic debug info.

I wasn't implying that.
 You 
 can find out what is pulling in a particular module by deleting it from 
 the library, linking, and seeing what undefined symbol message the 
 linker produces.

I tested it on a single-module program before posting. Basically void main() {} and a single unused function void fooBar {}. With -g, something with the function's mangled name ended up in the executable. Without -g, the linker was able to remove the function (I ran a diff on a compiled file with the function removed altogether from source).
 With ctfe-mixin-based metaprogramming, you also end up with string 
 literals that don't seem to get optimized away by the linker.

The linker has no idea what a string literal is, or what any other literals are, either. It doesn't know what a type is. It doesn't know what language the source code was. It only knows about symbols, sections, and bytes of binary data. The object module format offers no way to mark a piece of data as a string literal.

I wasn't implying that either and I'm well aware of it :S I thought it would be easier for everyone to understand than any blurbing about LEDATA/LED386 and static data segments.
 I do think it is possible, though, for the compiler to do a better job 
 of not putting unneeded literals into the obj file.

That would be nice and perhaps might make OPTLINK crash less. -- Tomasz Stachowiak http://h3.team0xf.com/ h3/h3r3tic on #D freenode
Sep 17 2009
parent reply Walter Bright <newshound1 digitalmars.com> writes:
Tom S wrote:
 I tested it on a single-module program before posting. Basically void 
 main() {} and a single unused function void fooBar {}. With -g, 
 something with the function's mangled name ended up in the executable. 
 Without -g, the linker was able to remove the function (I ran a diff on 
 a compiled file with the function removed altogether from source).

The best way to determine what is linked in to an executable is to generate a map file with -L/map, and examine it. It will list all the symbols in it. Also, if you specify a .obj file directly to the linker, it will put all of the symbols and data in that .obj file into the executable. The linker does NOT remove functions. What it DOES do is pull obj files out of a library to resolve unresolved symbols from other obj files already linked in. In other words, it's an additive process, not a subtractive one.
Sep 18 2009
parent Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Walter Bright wrote:
 Also, if you specify a .obj file directly to the linker, it will put all 
 of the symbols and data in that .obj file into the executable. The 
 linker does NOT remove functions.
 
 What it DOES do is pull obj files out of a library to resolve unresolved 
 symbols from other obj files already linked in.
 
 In other words, it's an additive process, not a subtractive one.

Tests seem to indicate otherwise. By the way, the linker in gcc can also remove unused sections (--gc-sections, which works best with -ffunction-sections). ----
cat foo.d

} version (WithFoo) { void foo() { } }
dmd foo.d -c -of1.obj

dmd foo.d -version=WithFoo -c -of2.obj

diff 1.obj 2.obj

lib -l 1.obj   1>NUL  && cat 1.lst

Publics by name module __Dmain 1 _D3foo12__ModuleInfoZ 1 Publics by module 1 __Dmain _D3foo12__ModuleInfoZ
lib -l 2.obj   1>NUL  && cat 2.lst

Publics by name module __Dmain 2 _D3foo12__ModuleInfoZ 2 _D3foo3fooFZv 2 Publics by module 2 __Dmain _D3foo12__ModuleInfoZ _D3foo3fooFZv
dmd -L/M 1.obj -of1.exe

dmd -L/M 2.obj -of2.exe

diff 1.exe 2.exe

diff 1.map 2.map


---- -- Tomasz Stachowiak http://h3.team0xf.com/ h3/h3r3tic on #D freenode
Sep 18 2009
prev sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
Tom S wrote:
 When building my second largest project, DMD eats up about 1.2GB of 
 memory and dies (even without -g). Luckily, xfBuild allows me to set the 
 limit of modules to be compiled at a time, so when I cap it to 200, it 
 compiled... but didn't link :( Somewhere in the process a library is 
 created that confuses OPTLINK as well as "lib -l". There's one symbol in 
 it that neither of these are unable to see and it results in an 
 undefined reference when linking. The symbol is clearly there when using 
 a lib dumping tool from DDL or "libunres -d -c". I've dropped the lib at 
 http://h3.team0xf.com/strangeLib.7z . The symbol in question is 
 compressed and this newsgroup probably won't chew the non-ansi chars 
 well, but it can be found via a regex "D2xf3omg4core.*ctFromRealVee0P0Z".

Please post to bugzilla.
 One thing slowing this tool down is the need to call the librarian 
 multiple times. DMD -lib will sometimes generate multiple objects with 
 the same name

Please post to bugzilla.
Sep 17 2009
parent Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Walter Bright wrote:
 Tom S wrote:
 When building my second largest project, DMD eats up about 1.2GB of 
 memory and dies (even without -g). Luckily, xfBuild allows me to set 
 the limit of modules to be compiled at a time, so when I cap it to 
 200, it compiled... but didn't link :( Somewhere in the process a 
 library is created that confuses OPTLINK as well as "lib -l". There's 
 one symbol in it that neither of these are unable to see and it 
 results in an undefined reference when linking. The symbol is clearly 
 there when using a lib dumping tool from DDL or "libunres -d -c". I've 
 dropped the lib at http://h3.team0xf.com/strangeLib.7z . The symbol in 
 question is compressed and this newsgroup probably won't chew the 
 non-ansi chars well, but it can be found via a regex 
 "D2xf3omg4core.*ctFromRealVee0P0Z".

Please post to bugzilla.

http://d.puremagic.com/issues/show_bug.cgi?id=3327
 One thing slowing this tool down is the need to call the librarian 
 multiple times. DMD -lib will sometimes generate multiple objects with 
 the same name

Please post to bugzilla.

http://d.puremagic.com/issues/show_bug.cgi?id=3328 -- Tomasz Stachowiak http://h3.team0xf.com/ h3/h3r3tic on #D freenode
Sep 17 2009