arXiv:cs/0506035v1 [] 10 Jun 2005

Fast Recompilation of Object Oriented
Modules
Jérôme Collin and Michel Dagenais
Département de génie informatique
Ecole Polytechnique de Montréal
C.P. 6079, Succ. Centre-Ville
Montréal, Québec, CANADA, H3C 3A7
michel.dagenais@polymtl.ca
March 5, 2018
Abstract
Once a program file is modified, the recompilation time should be
minimized, without sacrificing execution speed or high level object
oriented features. The recompilation time is often a problem for the
large graphical interactive distributed applications tackled by modern
OO languages. A compilation server and fast code generator were
developed and integrated with the SRC Modula-3 compiler and Linux
ELF dynamic linker. The resulting compilation and recompilation
speedups are impressive. The impact of different language features,
processor speed, and application size are discussed.

Keywords: Compiler, Code generator, Dependency analysis, Persistent
cache, Smart recompilation

1

Introduction

Recompilation speed is only one ingredient in the global picture of programming productivity. Nonetheless, its impact on programmer satisfaction is not
1

to be underestimated. Interpreters are sometimes seen as the solution for zero
recompilation time. However, the modified module needs to be parsed into
bytecode, which is not too different from machine code, especially if the link
editing phase is partially obviated by dynamic linking.
The recompilation may be divided into the following phases. The smart
recompilation phase determines the modified files and computes the minimal
set of files to recompile. The parsing and code generation phases convert the
source code files into relocatable binary files. The prelink phase computes
package wide information such as initialization order. Finally, the link phase
combines all the relocatable binary files into a library or executable program.
These phases are detailed in section 2 along with a discussion of the
impact of different language features on their complexity. This section motivates the two main extensions brought by the authors to the DEC SRC
Modula-3 compiler [1], a compilation server and fast code generator, and
reviews related work.
Section 3 details the compilation server while section 4 describes the fast
integrated code generator for Linux ELF [2]. Section 5 presents the results
obtained with the enhanced compiler, and outlines the contribution of each
extension as well as the sensitivity to different parameters. In the conclusion,
the applicability of these results to other languages such as Java [3] and C++
[4] are discussed, and avenues for further development are examined.

2

Background

The different phases involved in recompiling a package, program or library,
are detailed in this section. The work performed by typical compilers and by
the DEC SRC Modula-3 compiler, possible enhancements, and related work
are discussed at key steps.
The modification time of files comprising a package are checked to determine which ones were modified since the last compilation. These files always
need to be recompiled. In an integrated development environment, this information may be provided by the editor, if all modifications are performed
through it.
If any type checking, or data structure member offset computation, is
performed at compile time, files have dependencies upon imported files containing declarations. This is not the case for languages such as Smalltalk [5]
or LISP, which defer type checking to runtime, but applies to Java, C++
2

and Modula-3. When one of the declarations used by a file is changed, that
file needs to be recompiled too.
The use of a text level macro preprocessor, for importing declarations
from other files, makes such dependency analysis extremely difficult in C
and C++. The traditional approach embodied by makefiles is to recompile
a file whenever an included file was modified. The DEC SRC Modula-3
compiler remembers the fingerprint of each declaration used by a module,
and recompiles the module only when any of the declarations used has a
different fingerprint. This much finer grain dependency analysis, (at the
level of individual type declaration instead of complete header file), explains
in large part the smaller recompilation times typically associated with more
structured languages, as compared to C/C++.
Computing the minimal set of files needing recompilation is the smart
recompilation phase and has been studied in [6], [7], [8], and [9]. Any reduction in the number of files to recompile, due to a finer analysis, has a direct
impact on the total recompilation time.
The set of modified files, and of files potentially affected by modifications
in files on which they depend, is recompiled in the parsing and code generation phase. Compiling the individual files is often the most time consuming
step. While minimizing the number of files to recompile is important, it is
also possible to reduce the number of imported interfaces to parse, and to
speedup the code generation phase.
The DEC SRC Modula-3 compiler already has a cache for imported interface files. Each imported interface is read at most once in each recompilation.
A first extension, described in section 3, was to convert the compiler into a
compilation server. This way, an imported file may be kept in the interface
cache and need not be read and reparsed if it did not change between two
compilations.
Koehler and Horspool [10] worked on a compilation server for the C language. Most of their effort was spent analyzing the pre-processor context, to
determine if the imported file can be reused in different importers. It requires
a validation scheme rather different than the one proposed here. Onodera
proposed [11] a compilation server for a different language, COB, which has
2 kinds of interfaces, one similar to C and one similar to Modula-3.
The code generation time is a significant fraction of the total compilation
time. A fast code generator for Linux ELF, based on an existing code generator for NT in SRC Modula-3, is a second extension described in section
4. Tanenbaum et al. [12], and Fraser et al. [13] have obtained interesting
3

results with fast but less flexible non optimizing backends.
In the prelink phase, a number of application wide informations may
need to be computed, to be used by the run-time system. Non OO languages
like C had little or none such information. In Modula-3, the initialization
order of modules (based on the modules dependency graph), the run time
type information (after resolving type equivalence), the coherence of opaque
types revelations, and the structures for checking inheritance relationships in
constant time, are computed during this prelink phase. In Java, initialization
order is determined at runtime. C++ does not specify an initialization order
and only recently started to offer run time type identification.
The final step, performed by the link editor, is assembling the object code
of all the modules into the final executable. With dynamic linking, such
as in Linux ELF [2], the amount of processing required is greatly reduced.
All references internal to a module use position independent code and do
not require further link editing. Moreover, links to libraries are resolved
at execution time. Data symbols in libraries are resolved upon loading the
executable but procedure references are resolved only when needed, as the
execution proceeds.

3

Compilation Server

A compilation server reduces the recompilation time by maintaining some
information across compilations, instead of reading and reparsing the corresponding files each time. Imported interfaces represent the bulk of the
information required when compiling a file and often do not change from one
compilation to another. Thus, the purpose of the compilation server is to
maintain the interface cache across compilations.
Implementing a compilation server for C/C++ presents serious difficulties
because of the preprocessor mechanism. For instance, the #ifdef in Figure
1 can lead to two different variables in the symbol table, depending on the
value of DEBUG. Moreover, the compilation of an included .h file does not
lead to an independent object file. Instead, the object code associated with
it is part of the relocatable object files produced by the compilation of “.c”
files that include the “.h” file.
In languages with explicit interfaces such as Modula-3, the content of an
interface is not dependent on the importing file and can be reused for several
importing files, even across compilations. Some languages such as Eiffel and
4

#ifdef DEBUG
int x
#else
int y
#endif
Figure 1: #ifdef example

D
✡
✡

A

✣❏
❪❏
✡✡
✡
❏
✲

library 1

E
❏
❏✡

✡
✡

✣
✡✡

B ✛

C

library 2

❃
✚
❩
⑥
✻
✚
❩
✚
❩
✚
❩
✚
❩
❩✚

new program
or library

P

Figure 2: Dependencies among imported Modula-3 interfaces
Java extract the interface from the program file. When the program file is
recompiled, the interface is extracted. It could be stored in the interface
cache of a compilation server in the same way.
Figure 2 shows the dependencies between interfaces A to E used by a
program P. An arrow shows that a module or an interface imports another
interface. This acyclic directed graph imposes a compilation order. The interfaces at the leaves are compiled first. Each interface is compiled seperately,
i.e. it has its own associated relocatable object file. However, an interface
would normally need to be parsed again whenever it is imported. This is the
costly part of the compilation avoided with the interface cache. The parsing
result, the abstract syntax tree (AST ), is stored in the interface cache.
Between compilations, some of the interfaces in the cache may become
invalid. Indeed, if the associated source file has been modified or if a directly
5

or indirectly imported interface is invalid, the interface is declared invalid. In
the last case, the fine grain dependency analysis is used to determine if any
declaration actually used by the interface has changed. If not, the interface
is still valid. Otherwise, the interface is removed from the cache and will
need to be read and parsed again.
Thus, the validation algorithm is to recursively visit each imported interface in the graph to see if its associated source file has been modified or
if imported declarations have changed. A time stamp is used to mark each
valid interface as valid for this recompilation. When the same interface appears in the import graph of another file, the time stamp indicates that it
has already been checked as valid. The existing implementation of DEC SRC
Modula-3 did not have a validation phase since the interface cache was not
kept across compilations. Any interface in the cache was necessarily parsed
in the current compilation and therefore still valid.
A further optimization is added for interfaces imported from separate libraries (packages). Indeed, each package has an associated file containing the
information used by the smart recompilation system. Any modification to an
interface in a library, and subsequent recompilation, changes the modification
time of the associated file. Thus, the modification time of library interfaces is
checked only if the associated file has changed. Many libraries being seldom
changed, this simple optimization avoids a large number of file modification
time checks. The generic interfaces (the equivalent of the templates in C++)
are not put in the cache because they don’t have a corresponding AST. Their
instanciations, however, are eligible to be cached.
Figures 3 and 4 show the general structure of the compiler before and
after being transformed into a server. Libraries are represented as ovals
and programs as rectangles. Import relationships are indicated by arrows.
Programs executing other programs are shown with dashed lines.
Packages m3front and m3back are the frontend and the backend respectively. M3linker is the smart recompilation system. Package m3 contains
the main procedure of the compiler. M3quake is a simple interpreter that
parses the m3makefiles and passes parameters to the compiler (m3 ). M3build
initiates the m3quake interpreter in the appropriate directory, inserts the
platform and package dependent definitions, and sends the m3makefile to
m3quake. The connections to the two available code generators, and to the
linker, were left out for simplicity.
The existing compiler involved several processes which were merged in a
single executable program calling upon several libraries. Packages m3 and
6

m3build

✲

✎

☞

m3quake ✌
✍

✲

m3

✟◗
✟✟ ✄❆ ◗
✟✟ ☞ ✄ ❆ ◗◗
✙
✟
✎
✄
❆
◗
s
◗
☞
✎
m3linker ✌✄
❆
✍
m3back
✄
❆
✌
☞✍
✎ ✄✎
❆
✁
m3front
✍ ❳❳ ✌❆ ✁
❳❳ ❆ ✁
③
❳
❆❯✁☛
✎❳
☞

“driver”

m3middle ✌

✍

Figure 3: Structure of the SRC Modula-3 compiler
m3quake were converted to libraries. M3build acted as the remaining program and, instead of exiting after a recompilation, awaited further commands
from clients using network objects [14], as shown in Figure 5.
Each client request consists in a package name and location, build options
if any, and a network output stream to receive the error messages. The same
compilation server can process requests for different packages. Simultaneous
recompilation requests are serialized.
A small program, m3client, acts as a client that passes compilation requests to the server. It replaces the compilation command normally entered
from the command line or through the editor menus.
There is currently no mechanism or strategy to remove interfaces from the
cache (e.g. least recently used). This is not a problem for a few users working
on a few packages. However, if the compilation server executes for weeks and
new packages are constantly being added, the memory growth is likely to
become a problem. Deciding on an efficient strategy may require some study
but would be a minor implementation effort. The problem of multi-user
access control has not been addressed either. Sharing a compilation server
would bring interesting benefits only in very specific environments.
An alternative to maintaining the parsed interfaces in memory in a server
process across compilations, is to store on disk pre-parsed versions of the
interfaces. This would be faster than having no compilation server, if writing
these pre-parsed interfaces is much quicker than the time saved by not having
to re-parse the interfaces. However, this is slower than keeping the parsed
interfaces already in memory, provided that enough memory is available.
7

m3client
qq
qq

m3server

✎
☞
✲ m3quake
✍
✌

✎
☞
✲
m3
✍ ✟
✌
✟ ✄◗
❆ ◗
✟
✟
✄ ❆ ◗
✟ ☞✄
✙
✟
✎
❆ ◗
◗
s
◗
✎
☞
m3linker
❆
✍
✌✄
m3back
❆ ✍
✌
✎ ✄✎✄
☞
❆
✁
m3front
✍ ❳❳ ✌❆ ✁
❳❳❳❆ ✁
❆❯ ✁☛
③
✎ ❳
☞

m3middle ✌

✍

Figure 4: Structure of the modified SRC Modula-3 compiler

4

Fast Code Generation

Portable, retargetable, optimizing compilers such as gcc are built in several
layers and construct abstract syntax trees, an intermediate language representation, and an assembly language file at different stages during the compilation. Furthermore, the interface between the Modula-3 frontend, written
in Modula-3, and the gcc based backend introduces another intermediate
representation.
While the gcc based backend is retained to benefit from its optimizing
capabilities and wide range of supported platforms, an integrated code generator may be used on some platforms for faster compilation during the edit
compile debug cycle. The code generator is fed by the frontend with simple
virtual machine instructions and generates object code directly. It cannot
perform sophisticated optimizations or target multiple platforms.
An existing code generator for NT under Intel 386 was used as a base.
It was modified to support Linux ELF object files [2], and to produce position independent code and debugging information. Position independent
code allows efficient dynamic linking, another important ingredient for fast
recompilation. Debugging information generation increases slightly the code
generation time but is almost essential for adequately supporting the edit
compile debug cycle.
Figure 6 a) shows a simple Modula-3 procedure returning the sum of two
8

INTERFACE M3Server;
IMPORT NetObj, Thread, Wr, Pathname, TextList;
EXCEPTION
Error (TEXT);
TYPE
T = NetObj.T OBJECT METHODS
compile(init dir:Pathname.T;options:TextList.T;writer:Wr.T)
RAISES NetObj.Error, Thread.Alerted, Error;
END;
END M3Server.
Figure 5: Network object interface to the compilation server
values received as arguments. In b), the sequence of methods calls issued
by the Modula-3 frontend, and implemented by the code generator object,
is illustrated. The methods supported by the code generation object are
sometimes called the intermediate language. The arguments for the methods
were omitted in the example. In c), the machine code produced by the
backend is presented in the AT&T assembly language format for Intel 386
Architecture.
At the beginning of a procedure, the method begin procedure is called
by the frontend, and the 6 first machine instructions are generated. This
saves on the stack and initializes the registers used for setting up a new
frame according to the calling convention. Figure 7 shows the structure of
the stack frame constructed with these instructions. The ebp register (base
register) is used to reference other values in the stack frame by specifying
a 4 byte offset in an indexed address mode. The stack frame also includes
the arguments to the procedure, the return address of the calling procedure,
the value of ebp for the previous stack frame, local variables, and some saved
register values.
Thereafter, the machine instructions corresponding to the body of the
Modula-3 procedure are generated. The load method is called twice by the
frontend, once for each operand. No machine code is generated for this. Instead, the operands are pushed on the operand stack in the data structures
maintained by the code generator. The call of the method add by the frontend generates the code for adding the operands previously pushed on the
stack. On the i386, at least one operand of add must be in a register. Thus,
9

PROCEDURE Add(i, j: INTEGER): INTEGER =
BEGIN
RETURN i + j;
END Add;
(a)
begin procedure(...)

pushl %ebp
movl %esp,%ebp
pushl %ebx
pushl %esi
pushl %edi

load(...)
load(...)
add(...)

movl 0x8(%ebp),%edx
addl 0xc(%ebp),%edx
movl %edx,%eax
popl %edi
popl %esi
popl %ebx
leave
ret

exit proc(...)
end procedure(...)

(c)

(b)

Figure 6: Compilation of a simple procedure.
one variable must be moved from its position in the stack frame in memory to
a register (here edx ). The other operand can be addressed directly in memory by instruction add. The result of the addition must be returned to the
calling procedure in register eax, as specified in the calling convention. Thus,
the value in edx is moved to eax when method exit procedure is called by the
frontend. The call to method end procedure generates the code required to
remove the stack frame and restore affected registers.
Several optimizations to the generated code would be possible. For example, the use of register edx could be avoided by using eax instead. This would
obviate the need to transfer the return value to eax in the end. Registers
ebx, esi and edi were needlessly saved and restored on the stack even if they
were not used during the body of the procedure. Even though the fast code
generator does not perform such optimizations, the generated code is still
more efficient than the naive code produced by gcc without optimization, as
10

C(%ebp)
8(%ebp)
4(%ebp)
0(%ebp)
-4(%ebp)
-8(%ebp)
-C(%ebp)
-10(%ebp)

high addresses
argument 1 (j)
argument 0 (i)
return address
previous ebp
temporary variable
ebx
esi
edi
low addresses
Figure 7: Stack frame

seen in section 5.
The code generator structure is designed around four major objects, as
shown in Figure 8. The main object is M3x86 which implements code generation for procedure calls and returns, and produces the global variables section. It also coordinates the code generation performed by the other objects.
Stackx86 implements the operand stack, performs the register allocation and
generates the code to move operands between the stack and the registers.
Detailed machine instructions layouts, including addressing modes, are obtained through the Codex86 object. Everything is formatted into an ELF
binary file, with debugging information, by M3ObjFile. The relationships
between these objects are represented by arrows in Figure 8.

5

Results

The test set used for the performance evaluation is described in Table 1.
It contains programs and libraries of different sizes, and importing different
types of libraries. Large graphical applications such as webscape, postcard,
and ps2html tend to use large libraries, and involve numerous imported interfaces. Webvbt is one of the libraries used by webscape, and columns is a
smaller graphical application. Netobjd is a small program involving network
objects, and m3browser is a module/type browser with a web server interface. M3tohtml is a small program converting Modula-3 modules to html,
and m3front is a library implementing the Modula-3 compiler frontend.
For each package are shown the source code size, number of lines, number
of non blank lines, number of directly and indirectly imported interfaces, and
11

M3front

✏✏PPP
P
✏✏
q
P
✮
✏

modified GCC ❄ M3BackWindows
M3x86 -procedure management
(call, ret)
-management of variables and
❄ the initialized data
Stackx86 -operand stack management
-register allocation
❄ ❄
Codex86 -address mode of the
machine instructions
❄ ❄
M3ObjFile -binary file production
-debugger support
M3BackLinux
Figure 8: Structure of the code generator.
the memory consumed by the interface cache to represent the AST. All tests
were performed on a 75MHz Intel Pentium with 32MB of main memory and
running Linux 2.0. All times are in elapsed seconds on a single user machine,
and thus account for input/output delays.
The performance of both the integrated backend and the compilation
server were evaluated and compared to the original DEC SRC Modula-3
compiler version 3.6. The compilation times for the original compiler are in
Table 2.
Detailed measures were obtained for the various compilation phases using
the compiler built-in timers. Column M3⇒I.L is the time required to translate Modula-3 code into intermediate language, which is performed by the
frontend. I.L.⇒ass. is the time needed by the gcc based backend (m3cgc1)
to convert the intermediate language into assembly, and ass.⇒reloc. is the
time taken by the assembler to produce a relocatable binary file.
Table 3 presents the results for the compiler with the integrated backend
instead of the gcc based backend. The fast code generator goes directly from
the code generating method calls to the relocatable binary file, as indicated
by M3⇒reloc. Since the code generation is performed at the same time as
parsing, the time required for each phase is not available separately.
12

package
compiled
columns
netobjd
webscape
m3browser
webvbt
m3tohtml
m3front
postcard
ps2html

size
lines lines* interf.
47.17K 1553 1306
6
3.87K
151
128
1
11.72K
374
347
0
210.58K 7005 6312
12
194.76K 6254 5364
21
83.08K 3035 2656
8
1.367M 45827 39789
175
341.81K 10418 9575
12
315.85K 13468 9197
30

modules
7
2
1
13
20
9
171
11
30

imported
interfaces
30
27
69
67
120
35
38
161
111

memory
required
2.26M
1.12M
2.96M
1.93M
3.63M
1.26M
3.06M
3.93M
3.57M

Table 1: Packages used to evaluate the performance

package
compiled
columns
netobjd
webscape
m3browser
webvbt
m3tohtml
m3front
postcard
ps2html

smart
recomp.
1.19
0.78
3.48
1.04
4.80
0.79
1.62
2.79
3.43

Time (in seconds)
M3 ⇒ I.L. ⇒ ass. ⇒
I.L.
ass.
reloc. linking
4.21
8.65
4.44
0.85
0.87
1.50
0.85
0.43
2.56
4.06
1.51
1.50
10.08
36.09
11.88
1.11
14.17
37.52
16.83
0.97
4.00
16.49
6.39
0.85
69,56 220.36 108.03
5.84
22.38
55.34
16.43
4.16
28.24
84.38
27.34
6.02

other total
0.32 19.66
0.32
4.75
0.91 14.02
0.81 61.01
2.03 76.32
0.61 29.13
17.32 422.73
0.74 101.84
1.48 150.89

Table 2: Compilation with the gcc based code generator

13

package
compiled
columns
netobjd
webscape
m3browser
webvbt
m3tohtml
m3front
postcard
ps2html

smart
recomp.
1.16
0.77
3.98
0.97
4.52
0.94
2.45
3.07
3.62

Time (in seconds)
M3 ⇒
reloc. linking other total
6.46
0.85
0.61
9.08
1.24
0.43
0.39
2.83
2.93
1.69
1.14
9.74
14.91
0.85
0.46 17.19
21.60
1.01
2.02 29.15
5.83
1.06
0.39
8.22
95.54
8.05
16.88 122.92
31.75
8.51
1.09 44.42
35.73
4.77
1.28 45.40

Table 3: Compilation with the integrated backend
The compilation time reduction is significant for all packages. When the
compilation time is larger than 20 seconds with the gcc based backend, the
total compilation time may be cut in half with the integrated backend. Other
tests [15] demonstrate that the production of position independent code does
not significantly affect the compilation time. However, the generation of
debugging information increases the total compilation time by 10-30%.
To evaluate the quality of the generated code, a program was compiled
with the gcc based backend without optimization and with full optimization
(-O2), and with the fast code generator. The execution time for the version
compiled with the fast code generator was 6% faster than without optimization and 9% slower than with optimization. The memory footprint of the
program compiled with the fast code generator is 18% smaller than without
optimization and 14% larger than with optimization.
These results are consistent with those reported by Tanenbaum and al.
[12], where they obtained a speedup between 2 and 3 by using a simplified
backend. Their backend however still retained the ability to interface to
different frontends and targets.
The compilation server was evaluated both under a full recompilation and
in a typical situation where only a few files were modified. For the first case,
the executable and all object files were removed before recompiling. This is
14

package
compiled
columns
netobjd
webscape
m3browser
webvbt
m3tohtml
m3front
postcard
ps2html

smart
recomp.
0.63
0.46
3.00
0.63
4.46
0.41
1.39
2.48
3.12

Time (in seconds)
M3 ⇒ I.L. ⇒ ass. ⇒
I.L.
ass.
reloc. linking
1.96
9.04
4.45
0.86
0.28
1.52
1.09
0.44
1.58
4.06
1.55
1.71
8.90
37.19
12.24
1.55
12.04
39.80
17.41
1.29
3.29
16.40
6.90
0.86
77.84 235.90 121.02 34.70
21.67
57.73
18.35
7.32
24.73
89.48
30.44
11.54

other total
0.26 17.20
0.25
4.04
0.65 12.55
0.40 60.91
2.31 77.31
0.37 28.23
31.18 502.03
0.72 108.27
1.59 160.90

Table 4: Full recompilation of the packages with AST’s in the cache
shown in Table 4.
The savings brought by maintaining the interface cache across two compilations are smaller than originally anticipated. Only small gains are obtained
for the small packages. Since the SRC Modula-3 compiler already contains
an interface cache, the time to parse the interfaces is relatively small as compared to the code generation time, and a small fraction of the time is saved
by caching the interfaces across compilations.
More disturbing is the slight degradation obtained for some of the larger
packages. Removing the network objects communication between the client
and server did not change the results. The explanation lies in the increased
memory footprint of the compilation server. With 32 MB, there is some competition for physical memory between buffered files (e.g. libraries, object files
and the generated executable), and executing programs (e.g. the compiler
and linker). Indeed, when the same tests were repeated on a computer with
twice as much physical memory, a slight improvement was measured instead
of a degradation.
In a full recompilation, the existing interface cache brings most of the
benefits, and the code generation phase largely dominates because all modules need to be recompiled. Therefore, the savings brought by the server are
minor as compared to the total compilation time and may even turn into
15

compiler
used
standard
with m3cgc1
server
with m3cgc1
standard
with integrated
server
with integrated

smart
recomp.

Time (in seconds)
M3 ⇒ I.L. ⇒ ass. ⇒
I.L.
ass.
reloc. linking

other total

0.73

0.97

2.73

0.86

0.42

0.22

5.93

0.76

0.62

2.73

0.84

0.42

0.15

5.52

0.74

1.84

0.42

0.24

3.24

0.64

1.36

0.42

0.20

2.62

Table 5: Recompilation of postcard after modifications to 2 files
a degradation if memory is short. The picture improves however when the
compilation server is combined with the fast code generator. Indeed, the
2.46s reduction for columns represents 12.5% of 19.66s but amount to 27.1%
of 9.08s. These savings only involve the smart recompilation and frontend
parsing phase, and are independent of the code generation time.
The tests presented in Tables 5 and 6 are more typical of the edit compile
debug cycle. They consist in recompiling a large graphical application, postcard, after 2 files, and 4 files, are modified. Four different cases are covered:
existing compiler and code generator, fast code generator, compilation server,
compilation server with fast code generator. For these tests, the computer
used had the same characteristics except a Pentium Pro 180MHz processor
and 64MB of RAM.
These tests clearly demonstrate that the compilation server and fast
code generator contribute independently to the recompilation time reduction. Their combined effect in that case amounts to a reduction from 9.77s
to 3.22s. This is especially impressive considering that the Modula-3 compiler
is already much more efficient than most C/C++ compilers, because of the
interface cache and fine grain dependency analysis allowed by the structured
interface mechanism.

16

compiler
used
standard
with m3cgc1
server
with m3cgc1
standard
with integrated
server
with integrated

smart
recomp.

Time (in seconds)
M3 ⇒ I.L. ⇒ ass. ⇒
I.L.
ass.
reloc. linking

other total

0.75

1.89

4.83

1.68

0.42

0.20

9.77

0.44

1.09

4.85

1.68

0.43

0.17

8.66

0.73

2.66

0.43

0.27

4.09

0.51

2.05

0.42

0.24

3.22

Table 6: Recompilation of postcard after modifications to 4 files

6

Conclusion

A fast recompilation system for a modular, compiled, object oriented language was presented. It benefits from the existing interface cache and fine
grain dependency analysis, and was extended with a persistent interface
cache, fast code generator, and Linux ELF dynamic libraries support. The
resulting recompilation time reduction is impressive. For a large graphical
application, recompiling after a few files were modified took 3.22s instead of
9.77s.
In the coming years, faster processors, larger main memory and more
complex programs may be expected. The average size of each file, and the
number of files modified between compilations are not expected to change
significantly however. The net effect would be a gradual reduction of the file
parsing and code generation time, which currently dominates the recompilation time at 2.05s out of 3.22s. The smart recompilation and linking time
accounts for much of the remaining time (.92s out of 1.17s). These may
be adversely affected by the increasing programs complexity and eventually
dominate the recompilation time.
Increases in programs complexity are likely to change more the number
of libraries imported by each program rather than the size of each program
file or library. The smart recompilation system could accordingly be further
optimized in several ways. More information about each imported library
17

could be cached, as applications importing more libraries have much larger
times for the smart recompilation phase. A tighter integration between the
program editor and the compilation server could allow the smart recompilation to perform most of its work incrementally. When a file is opened and
modified, the compiler could pre-compute which files are affected, and need
to be recompiled or dependency checked. When a file is saved, the recompilation of that file and affected files may proceed. Thus, when the last file is
saved, only that last file, and the files affected, would need recompilation.
The final recompilation steps, prelinking and linking, involve the complete
program and may therefore become the dominant step as program complexity
increases. Interestingly, the Linux ELF linker is surprisingly efficient for
dynamically linked libraries. Only a small fraction of each library needs to
be read by the linker. Yet, because of the lazy procedure linking algorithm
used in ELF, the program startup penalty imposed by dynamic linking is
small. As may be seen from the results, the linking time is mostly affected
by the package size rather than by the number of imported libraries.
Linking is an I/O intensive process, and the availability of free RAM for
the I/O buffer cache strongly impacts the elapsed time. This was apparent for large programs where the compilation server actually degraded the
performance because of the competition for memory. Assuming sufficient
physical memory, it may be possible to reduce the linking time by dynamically loading each object file as it is being recompiled. This would remove
the linking step which reads all object files from disk, merges the files into an
executable, and writes the executable to disk, before loading the executable.
The prelinking step, listed as other, currently uses a small fraction of the
overall recompilation time. It checks the coherency of opaque types revelations, determines the modules initialization order, and generates the run time
type identification data structures. The processing time is proportional to
the total number of modules in the final program. With increasing program
complexities, this may in the long term become an important factor.
In C++, run time type identification is a recent addition and is likely to
bring different problems. Indeed, a declaration appearing in a .h file may
be included and compiled several times. The prelinker must ideally remove
duplicate virtual methods tables and run time type information. The Java
language does not specify a static initialization order nor does it have opaque
types to check. The prelinker step is thus mostly avoided. However, since a
class must be initialized at its first active use, many tests must be inserted at
run time to initialize classes when they are used, if it is the first time. Thus,
18

the savings in the prelink phase are offset by the run time overhead.
The fast code generator is now part of the freely redistributable Polytechnique Montreal Modula-3 distribution, originally found at http://m3.polymtl.ca/m3/pkg
but now hosted at http://www.elegosoft.com/pm3/, and received enthusiastic feedback from users around the world. The compilation server is available
separately at http://www.professeurs.polymtl.ca/michel.dagenais/pkg/m3server.tar.gz.

Acknowledgments
The financial support of the National Sciences and Engineering Research
Council of Canada, as a scholarship to the first author, while he was a master’s student at Ecole Polytechnique de Montreal, and an operating grant to
the second author, is gratefully acknowledged. This work would not have
been possible without the excellent environment provided by the DEC SRC
Modula-3 compiler. Bill Kalsow, Allan Heydon, and Greg Nelson contributed
to this project through numerous technical discussions.

References
[1] G. Nelson, Systems Programming with Modula-3. Innovative Technologie
Series, Englewood Cliffs, NJ: Prentice Hall, 1991.
[2] U. S. Laboratories, System V Application Binary Interface– Intel386
Architecture Processor Supplement. Unix Press, 1993.
[3] J. Gosling, B. Joy, and G. Steele, The Java Language Specification.
Reading, Massachusetts: Addison Wesley, 1996.
[4] B. Stroustrup, The C++ Programming Language.
Addison-Wesley Publishing Company, 1992.

Reading, MA:

[5] A. Goldberg and D. Robson, Smalltalk-80: The Language and its Implementation. Reading, Massachusetts: Addison Wesley, 1983.
[6] W. F. Tichy, “Smart recompilation,” ACM Transactions on Programming Languages and Systems, vol. 8, pp. pages 273–291, July 1986.

19

[7] R. Adams, W. Tichy, and A. Weinert, “The cost of selective recompilation and environment processing,” ACM Transactions on Software
Engineering and Methodology, vol. 3, pp. pages 3–28, January 1994.
[8] M. A. Linton and R. W. Quong, “A macroscopic profile of program
compilation and linking,” IEEE Transactions on Software Engineering,
vol. 15, pp. pages 427–436, April 1989.
[9] J. Gutknecht, “Separate compilation in Modula-2: An approach to efficient symbol files,” IEEE Software, vol. 3, pp. pages 29–38, November
1986.
[10] B. Koehler and N. Horspool, “CCC: A Caching Compiler for C,” paratre
dans: Software–Practice and Experience, January 1997.
[11] T. Onodera, “Reducing compilation time by a compilation server,”
Software–Practice and Experience, vol. 23, pp. pages 477–485, May 1993.
[12] A. S. Tanenbaum, M. F. Kaashoek, K. G. Langendoen, and C. J. Jacobs,
“The design of very fast portable compilers,” SIGPLAN Notices, vol. 24,
pp. pages 125–131, November 1989.
[13] C. W. Fraser and R. R. Henry, “Hard-coding bottom-up code generation tables to save time and space,” Software–Practice and Experience,
vol. 21, pp. pages 1–12, January 1991.
[14] A. Birrell, G. Nelson, S. Owicki, and E. Wobber, “Network Objects–
Report 115,” Systems Research Center Digital Equipment Corporation
130 Lytton Avenue Palo Alto, Californie, U.S.A., 94301, February 1994.
ftp://gatekeeper.dec.com/pub/DEC/SRC/research-reports/SRC115.ps.Z.
[15] J. Collin, “Compilation par serveur persistant et génération rapide de
code,” Master’s thesis, Ecole Polytechnique de Montréal, January 1997.

20

