CMSC 838Y Paper Reviews

Skip down to paper 0: Michael Franz. Dynamic linking of software components. IEEE Computer, 30(3):74-81, March 1997. [ .pdf ]


Reviews for paper 0

Review from Yuan Yuan <yuanyuan@cs> at Sun Feb 9 11:47:09 EST 2003:


Paper: Dynamic Linking of Software Components

With the ability of using computing resources efficiently without duplicate 
functionality, dynamic linking became a key technique to construct highly 
flexible systems. This paper addressed five strategies to implement this 
technique. I like to summarize first three of them here.
ź	Runtime table lookup: to link client module with library module, linker 
replaces the symbolic reference in client’s link table with its procedure’s 
memory position. Ad: modules can be freely relocated. Disad: indirect calls 
incur runtime overhead.
ź	Loadtime code modification: linker updates the object code directly at load 
time by maintaining lists for each external calls. Ad: after loading process, 
no further overhead.
ź	Runtime modification: Replace external reference in its first usage. Ad: 
minimize the work of the linker. Disad: cache missing lows down the 
performance.

This paper gives us a clear view of dynamic linking from the concept, 
importance to the detailed implementation approaches. By comparing those 
“lightweight” approaches, author points out most current systems support 
Load-Time code modification because it does not incur runtime overhead and 
cache invalidation entailed by other approaches. Also its speed is coming close 
to traditional loader.

The paper is valuable since it provides us a way to get first touch with 
dynamic linking. But this paper is only a summary paper. All the strategies 
mentioned here are only concepts without concrete framework and detailed 
consideration, like how to solve security, efficiency problem. 

Review from plamba@wam.umd.edu at Mon Feb 10 10:22:00 EST 2003:

Michael Franz's paper gives the brief description of the five different 
techniques of the dynamic linking .He also points out the importance of Modular 
systems. His explanation on the need of Modular application and Modular 
operating system where there is abstract layer between the application and 
operating system modules is well appreciated. According to him the modules can 
be defined as client and library modules. Modules are separated till the time 
of linking. This paper gives the convincible reasons for the use of 
Fingerprints to verify nothing imported from the library has been changed since 
client has changed. To enable Linking object file needs two directories naming 
Entry table (explaining the exported features) and Link Table (explaining which 
imported features). 

Author builds the description for the first three techniques for the linking on 
the concept of Entry table and Link Table. According to me the author is able 
to explain the concepts of Run Time Table Look Up, Load Time Code Modification, 
Run Time code modification and Load Time code generation. He leaves the Full 
Load Time Compilation unexplained and open to discussion

According to me one of the most effective methods of the dynamic linking is 
Load time code generation since I/O overheads are the main factor for 
influencing load time ands in dynamic code generation object files need to be 
read only once.


Review from Nikhil Swamy <nswamy@cs> at Mon Feb 10 15:01:51 EST 2003:

In this paper Michael Franz provides an overview of a variety of approaches to 
the dynamic linking of object modules. The exposition makes a smooth transition 
from a high-level perspective on the concepts related to linking into some of 
the specifics associated with some of the techniques described. While the 
description of these techniques is by no means detailed the reader is left with 
an intuitive understanding of the procedures and perhaps even an inkling of 
some of the intricacies of the implementation of such methods.

It is curious however that the paper devotes considerable space to the growing 
disparity between I/O and CPU performance. It appears to me that this issue is 
somewhat extraneous to the problem of dynamic linking. While certainly such a 
gap in the current technology may be exploited, it should hardly be phrased as 
a prime motivating factor for future work into this field - for instance, 
nanotechnology might well result in a rapid closing of this gap. 

In conclusion, as a novice, this paper provided an approachable survey of some 
of the issues related to dynamic linking.

Review from Bryan Payne <bdpayne@cs> at Mon Feb 10 17:34:40 EST 2003:

This paper took a little while to get into.  I found that the first couple of 
techniques discussed (runtime table lookup & load-time code modification) were 
not very interesting.  However, the last three techniques provided some 
interesting ideas to think about.

In particular, the discussion about leveraging the current trend of computers 
to have faster processors and slower I/O was quite interesting.  Clearly, 
today's computer systems exhibit an even greater disparity between processor 
and I/O speed than they did in 1997.  However, today's operating systems do not 
use load time code generation (as far as I know).  This leads me to believe 
that either the author's commentary in this section is incorrect or missing 
some larger point (or that the industry just decided to stick with a lesser 
solution...it wouldn't be the first time that happened either!).

While the paper provided and brief overview of each of the techniques, it 
didn't present any shocking or novel information in my opinion.  In fact, at 
the end of the paper, the author mentions that Java uses a system similar to 
the techniques discussed in the paper.  However, the author argues that the 
paper's techniques are better than those in Java.  The argument seems sound, 
but with such things I find it much easier to believe numbers from real world 
performance testing.

As a final note, the end of the paper mentioned that "the technologies chosen 
for linking components will play a pivotal role in the system's long-term 
commercial success".  Clearly, a lot has changed in the operating system market 
since 1997.

Review from Polyvios Pratikakis <polyvios@cs> at Tue Feb 11 05:07:55 EST 2003:

This article presents the concept of dynamic linking. It begins by describing 
the history of linking since the very beginning, when programs were written in 
machine language. The concept of developing a program by linking independent 
modules is introduced, and various linking mechanisms that have been used so 
far are described. The notion of loading a program is separated from linking, 
and new ideas on dynamic linking and loading (load time 
code-generation/compilation) are briefly presented.
This is not a formal paper, but rather an article published in a 
introductory-level magazine. As such, it succeeds in presenting what linking 
is, the past and the future of research in that field, and gives links for 
further reading. It does not expand on technical terms, nor present something 
new specifically. It is an introductory level article that offers background 
information, and points to further, more technical and in-detail, papers.

Review from Piyush Bhagat <piyushb@glue.umd.edu> at Tue Feb 11 09:47:33 EST 2003:

The paper Dynamic Linking Of Software Components by Michael Franz is basically 
about the dynamic linking of modular systems. The paper says that a combination 
of dynamic linking and extensible software systems makes dynamic linking even 
more powerful. The paper provides a very interesting concept of Fingerprints. A 
fingerprint is a hash function computed from the interface of the library. 
Because of the property of the hash function the probability of two libraries 
having same hash function is very less. Now an object which imports a library 
interface with a certain fingerprint can be linked to any library with the same 
fingerprint irrespective of the machine the library was compiled.
                                      The paper finally gives five linking 
schemes. The Runtime code modification, Load-time code modification, Runtime 
table lookup, Load-time code generation and full load-time compilation. Out of 
these mechanisms full load-time is still in developing stage as has got several 
problems. Runtime code modification and Load-time code generation are good 
concepts and can be implemented (they are already implemented in some languages 
like java). Out of the two Load-time code generation has got some I/O overhead 
but that can be compensated by additional computational power, which is growing 
at a very high pace now a days. Runtime code modification has got no overheads. 
So I personally feel that these two concepts would be increasingly used in 
programming languages in the future.      
   

Review from Nathaniel Waisbrot <waisbrot@cs> at Wed Feb 12 22:03:15 EST 2003:

	Franz describes five methods of dynamically linking modules.  In runtime table 
lookup, each module keeps a table of external symbols, and the linker fills in 
the table with the appropriate addresses at load-time.  In load-time code 
modification, the linker traverses the module, replacing external symbol 
references with their address.  Runtime code modification does the same thing 
as load-time code modification, but the external references are each resolved 
as needed, rather than being resolved when the module loads.  Finally, Franz 
describes load-time code generation and load-time compilation.  Load-time 
compilation is simply taking the source files for a module and compiling them 
directly into memory.  Load-time code generation is Franz's own project.  He 
compiles code to an intermediate, machine-independent file.  This intermediate 
file is significantly smaller than a complete binary, but it can be compiled to 
an executable form quickly.
	Moving the final compilation step to load time is a fascinating idea, because 
it's a dramatic demonstration of how software engineering practices can change 
in the face of the growing cost of I/O.  In fact, while Franz's slim binaries 
are a nice project, I'm surprised that he dismisses full load-time compilation 
so easily.  Following the trend he observes, programs should have as small a 
footprint on disk as possible, and his slim binaries are not as slim as 
compressed source code could be.
	As far as dynamic linking goes, the load-time compilation schemes aren't 
really very exciting, since they're essentially just doing static linking at 
load time.  The Java just-in-time compiler's lazy compilation sounds more fun.

Review from Brian K at Thu Feb 13 08:22:21 EST 2003:

The intro to the paper is a review of the history of linker and loader 
divisions of work and strategies, which I think we've mostly seen in other 
papers[levine].  

The goal finally discussed is load time code generation.  The benefit is 
supposed to be cross platform support from source-free distributions without 
needing the user to understand program compilation.  Franz asserts that this is 
now practical do to the massive speedup in processor speed relative to IO 
speed.  He does his testing with a 'slim binary' format- which I would liken to 
JIT of Java bytecode.  He asserts that the reduced IO time reading the smaller 
slim binary format can offset the addition time required to compile it to 
system specific code(similar to video cards using image compression).  

I found his example unconvincing- the loading of a vt100 emulator, mail/news 
program, finger, ftp, gopher, and a 'web browser', which take twice as long to 
load- 2.1 seconds vs 1.1 second precompiled- in total 603K.  I wonder what kind 
of web browser he's using in 603K.  In any case he asserts that while 1 second 
may be significant to an interactive user, "users normally don't start all of 
these applications at the same time".  To that I ask, why on earth did he 
select this example for measurement at all?  

He gives times for standard and dynamic compilation, but he never actually 
discusses savings from IO so it is not clear that anything was saved here.  For 
disk IO there is typically a high seek overhead followed by fairly efficient 
streaming read, so with his small example the slim binary and the object file 
might both be read in almost exactly the same time.

He also doesn't deal with the fact that cross platform programs typically must 
be designed that way - ie. avoiding OS specific linking.  Cross platform 
generation will also only be practical for fast machines, which reduces that 
number of applicable platforms anyway(ie. I wouldn't want this on my Palm).

Review from Prashant lamba<plamba@wam.umd.edu> at Thu Feb 13 11:56:30 EST 2003:

Michael Franz's paper gives the brief description of the five different 
techniques of the dynamic linking .He also points out the importance of Modular 
systems. His explanation on the need of Modular application and Modular 
operating system in which  there is abstract layer between the application and 
operating system modules is well appreciated. According to him the modules can 
be defined as client and library modules. Modules are separated till the time 
of linking. This paper gives the convincible reasons for the use of 
Fingerprints to verify nothing imported from the library has been changed since 
client has changed. To enable Linking object file needs two directories naming 
Entry table (explaining the exported features) and Link Table (explaining which 
imported features).  

Author builds the description for the first three techniques for the linking on 
the concept of Entry table and Link Table. According to me the author is able 
to explain the concepts of Run Time Table Look Up, Load Time Code Modification, 
Run Time code modification and Load Time code generation. He leaves the Full 
Load Time Compilation unexplained and open to discussion 

According to me one of the most effective methods of the dynamic linking is 
Load time code generation since I/O overheads are the main factor for 
influencing load time ands in dynamic code generation object files need to be 
read only once

Review from Mujtaba Ali <mujtaba@bitsmart.com> at Thu Feb 13 12:15:07 EST 2003:

In general, this article was captivating and fun to read.  I was wondering how 
the rest of a system would know that a new module had been ?introduced?, and 
the mention of callback mechanisms cleared up that confusion (similar to how 
observers register with a subject in the Observer pattern.)  The note on 
separate compilation versus independent compilation was also quite nice, as I 
previously thought the two were one and the same.  Franz also very effectively 
built later examples upon previous ones to demonstrate the first three dynamic 
linking strategies.   It?s also nice to see someone discuss desktop/interactive 
systems as these are easier for me to relate to.  I understand the author?s 
theory on why load-time code generation should work, but I still don?t find 
myself convinced that load-time code generation is currently feasible in 
practice, especially for interactive systems.  I agree that full load time 
compilation is not a good solution; if you need to generate an intermediate 
representation anyways (called ?compressed source code? in the article), then 
you might as well just go with ?slim binaries?.

However, there are a couple things I didn?t like about the article, or the 
author?s viewpoint in general.  Sometimes, Franz mentioned details I believe 
were not suited for this article.  For example, the discussion of module 
timestamps/fingeprints and the mention of compound documents at the end of the 
article.  Additionally, I don?t believe the leap from runtime code modification 
to load time code generation is a natural one, as Franz believes.  Furthermore, 
the author seems comfortable to take advantage of an increase in processing 
power, yet he seems awfully concerned about storage space, even though storage 
capacities have also sky rocketed in the last few years.  Lastly, I am always 
skeptical of people that overly embrace Moore?s Law.  Yes, computers are 
faster, but overall, my interactive experience today is just as ?slow? as it 
was 7 years ago.  I would argue that any increase in computing power is matched 
by an equal increase in bloat by the software community.

Review from James Rose <rosejr@cs> at Thu Feb 13 12:20:05 EST 2003:


	Like the Wadler paper, this paper provides a general overview
of an idea, rather than presenting new results, and thus I will use
the same two criteria, clarity and interest, in evaluating it.  This
paper has two related, but distinct themes: first, the illustration of
various linking schemes commonly used today; second, the idea that the
disparity between CPU and I/O performance allows more work to be done
at load time with minimal impact on performance.  
	The presentation of first theme is clear, and it serves as a
good introduction and segue into the second, though it is not strictly
necessary.  The second theme is interesting because it suggests a
rather simple solution to the problem of portability.  The idea of
slim binaries is not new, however; Microsoft implemented a similar
system which it called "p-code" in the early nineties.  Visual Basic
programs compiled to p-code, and C programs could use it as well,
though few did.  What makes this point interesting is the way it
analyzes performance from the standpoint of an interactive user,
taking into account the entire system architecture.  


Review from Jeff Odom <jodom@cs.umd.edu> at Thu Feb 13 12:23:06 EST 2003:

This paper's goal was to introduce the various techniques that have been used 
to perform dynamic linking of executables.  The paper itself was fairly 
high-level, and although it attempted to be impartial to most of the 
techniques, there seemed to be a bias towards load-time compilation.   
Surprisingly, the techniques listed in this paper have not been greatly 
expanded upon - the only technique that comes to mind is Microsoft's .NET 
linking strategy, which expands upon the fingerprinting notion by adding 
public-key signing - even though this paper was published over 5 years ago.

There were several areas that went lacking in this article.  For instance, it 
attempts to rank efficiency of various linking techniques without providing any 
real quantitative data.  In fact, there is only one page that has any numerical 
comparisons of techniques (page 79) and there only one experiment has been run. 
 Additionally, the utility of the chart on that page is questionable - how 
representative of CPU and IO speeds is it?  Also, the notion  of Java’s 
Just-In-Time compiling, even in 1997, probably deserved more than a 
one-paragraph mention, and should probably have been mentioned earlier in the 
section “Load-time code generation” instead of, or perhaps before, the author’s 
own code generation project (again it seemed some bias had crept in).


Generated: Thu Mar 6 15:39:24 EST 2003 by mwh


mwh@cs.umd.edu