Re: Looking for a smart linker for GNAT/DOS

Re: Looking for a smart linker for GNAT/DOS

[Samuel Tardieu]

>>>>> "Gautier" == Gautier  <Gautier.DeMontmollin@maths.unine.ch> writes:

Gautier> Is there an alternative linker for GNAT/DOS, a bit smarter
Gautier> than the ``official'' one - i.e. which would add into the
Gautier> .exe only the really used procedures of a package ?

AFAIK no.

Gautier> It could avoid the explosion of executables' sizes (47k for a
Gautier> ``null'' programme, 97k for a ``hello world'',...)

Well, this has nothing to do with an "explosion", this is a rather
fixed overhead (depending on the packages you need). Sure, if you only 
write "null" or "hello world" programs, this overhead is significant,
but as soon as you start working on real projects, then this becomes
insignificant.

  Sam
--
Samuel Tardieu -- sam@ada.eu.org

Re: Looking for a smart linker for GNAT/DOS

[Gautier]

Samuel Tardieu <sam@ada.eu.org>:
> Gautier> It could avoid the explosion of executables' sizes (47k for a
> Gautier> ``null'' programme, 97k for a ``hello world'',...)
> 
> Well, this has nothing to do with an "explosion", this is a rather
> fixed overhead (depending on the packages you need). Sure, if you only 
> write "null" or "hello world" programs, this overhead is significant,
> but as soon as you start working on real projects, then this becomes
> insignificant.

The skip from 47k to 97k with the usage of Text_IO is insignificant
for a real project because you will use the greatest part of Text_IO.
But, in a real project, you will (maybe) also use much bigger 
and specialized packages whom you use only 10% - e.g., a graphics package
with tons of gadgets, curves, bars (I'm making an improved clone
of Turbo Pascal's Graph, there the problem appears well...).
So, the difference between the full packages sizes and the used part of them
will *increase* with greater projects - this is why the <<explosion>> term
is appropriated.
I'm thinking about the LAPACK library in FORTRAN, too: in many real projects,
only a few from the thousends LAPACK routines are used.
A GNAT/DOS implementation of it would produce executables of >20 megas
(and certainly just wouldn't run on most machines),
although they should be of a few hundreds of K if linked by a good linker!

G.

Re: Looking for a smart linker for GNAT/DOS

[Gautier]

> <<...
> It could avoid the explosion of executables' sizes
> (47k for a ``null'' programme, 97k for a ``hello world'',...)>>

dewar@merv.cs.nyu.edu (Robert Dewar) writes:
 
> Are you sure you are stripping the executables? I find only 24K for
> a null program on OS/2, and that is without a shared library (it would
> of course be MUCH smaller if I used a shared library).
> 
> In any case, I don't think there is much in the way of unused code in
> these programs -- what makes you think there is? GNAT only loads library
> units that are used.

Oh? Not every package found on the HD is linked ? ;-)

>                      There is a certain fundamental overhead of stuff
> that is needed to e.g. setup handling of standard exceptions.
> 
> But I think your 47K sounds like it still has some debugging stuff left in

The 47k programme is compiled without debug option (-g) 
and the exe is stripped. The fact that the DOS version has 47k and the OS/2,
24K, seems normal since with the DOS version all I/O and file handling must
be made through the DPMI interface.

This 47k basis is not annoying but the fact that 100% of each new added
package is linked although a part of it (maybe a few tenth for a graphics
package, a few thousends for a numerics package like LAPACK) is really used.

Here is a test package to illustrate it:

-------------------------------------------------------------------------------
--  Package to test the linker's smartness (unused procedures detection)
--  See P_TstLnk test procedure

package TestLink is
  procedure A; procedure B; procedure C; procedure D;
end;

with Text_IO; use Text_IO;
package body TestLink is
  procedure A is begin Put("Adalbert"); end;   
  procedure B is begin Put("Berthold"); end;
  procedure C is begin Put("Clothilde"); end;
  procedure D is 
    procedure E is begin Put("Ernest"); end;
    procedure F is begin Put("Fabien"); end;
  begin Put("Dagobert"); E; end;
end;

-- Only "Berthold", "Dagobert", "Ernest" strings should appear in P_TSTLNK.EXE
-- "Adalbert", "Clothilde", "Fabien" should not appear.

with TestLink; use TestLink; procedure P_TstLnk is begin B; D; end;
------------------------------------------------------------------------------- 

A Turbo Pascal equivalent of it will have only the used procedures in the .exe

G.

Re: Looking for a smart linker for GNAT/DOS

[Robert Dewar]

<<This 47k basis is not annoying but the fact that 100% of each new added
package is linked although a part of it (maybe a few tenth for a graphics
package, a few thousends for a numerics package like LAPACK) is really used.>>

Of course, that is certainly so -- it is, as you note, a linker issue. But
what I was saying was that this is not the reason for the base sizes that
you quote. 

It is certainly the case that in large programs, the elimination of unused
subprograms would save a lot of code.

We are currently developing a tool that will in fact operate at the front end
level and allow complete elimination of unused subprograms. This will be
useful on systems where the linker is not smart enough, which unfortunately
is the great majority of systems (both Unix and DOS have traditions of very
simple stupid linkers -- as far as I know, only AIX among standard Unix
impementations has a linker that eliminates unused subprograms.

Re: Looking for a smart linker for GNAT/DOS

[Gautier]

dewar@merv.cs.nyu.edu (Robert Dewar) writes:

(...)
> It is certainly the case that in large programs, the elimination of unused
> subprograms would save a lot of code.
> 
> We are currently developing a tool that will in fact operate at the front end
> level and allow complete elimination of unused subprograms.

Wow! Will it be integrated into GNAT (gnatmake) ? 

>                                                             This will be
> useful on systems where the linker is not smart enough, which unfortunately
> is the great majority of systems (both Unix and DOS have traditions of very
> simple stupid linkers -- as far as I know, only AIX among standard Unix
> impementations has a linker that eliminates unused subprograms.

and Turbo Pascal linker among 16 bit DOS linkers...

G.

Re: Looking for a smart linker for GNAT/DOS

[Robert Dewar]

Gautier said

<<The skip from 47k to 97k with the usage of Text_IO is insignificant
for a real project because you will use the greatest part of Text_IO.
But, in a real project, you will (maybe) also use much bigger
and specialized packages whom you use only 10% - e.g., a graphics package
with tons of gadgets, curves, bars (I'm making an improved clone
of Turbo Pascal's Graph, there the problem appears well...).
So, the difference between the full packages sizes and the used part of them
will *increase* with greater projects - this is why the <<explosion>> term
is appropriated.>>

   That's certainly right, we just found your examples in your original
   message to be unconvincing, and not terribly relevant, because in
   fact a smart linker would not reduce much in either of the two cases
   you mentioned if anything.

   One thing that can help is the systematic use of DLL's or whatever
   shared libraries are called on your machine. Since only what you
   actually use is loaded into physical memory, and since your image
   then does not contain the code, the problem is largely alleviated.

   Note for example that the DLL that comes with Cygwin is pretty big,
   several megabytes, since it contains huge amounts of functionality.
   But a program using this DLL pays neither in disk space for the EXE
   nor in working set size in physical memory.

   By the way, we are now designing and implementing a new tool that
   will automate the building of such DLL's and that will help.

   P.S. GNAT already does something about Text_IO. In GNAT, packages
   like Integer_IO, Float_IO etc are implemented as child units (which
   is how they should have been defined in the first place if we were
   not constrained by Ada 83 compatibility), so they are only loaded
   if needed. This implementation is transparent to a user (interested
   people may enjoy looking at the routine Text_IO_Kludge in rtsfind
   in the GNAT sources to see how this is done :-)

I'm thinking about the LAPACK library in FORTRAN, too: in many real projects,
only a few from the thousends LAPACK routines are used.
A GNAT/DOS implementation of it would produce executables of >20 megas
(and certainly just wouldn't run on most machines),
although they should be of a few hundreds of K if linked by a good linker!

   You are confusing virtual and physical memory here. Just because an
   EXE is large does not mean that you needs lots of physical memory in
   your working set to run the program, so you are probably quite wrong
   about it not running on most machines.

   Nevertheless, even in these days of 6 cents/megabyte disk, we really
   do not want 20 meg executables around (for one thing there are still
   old fashioned systems that do initially load the whole exe file instead
   of mapping it), and for another, even at that price, 20 megs/program
   adds up!

   There are two solutions (besides a smart linker). The first is to
   structure the interface as a set of separate Ada 95 child units,
   rather than one monolithic spec. After all the original Fortran
   routines are separate units, and a Fortran program using LAPACK
   works fine even without a smart linker.

   The second is to put the interface in a DLL, as described above.
   These days, that is getting to be a more and more attractive
   solution, and it may well be that this is the way to go, since
   it is more convenient for the Ada programmer than splitting the
   interface into separate units.

   This is not to say that a smart linker would not be useful, just that
   with modern systems, the need for smart linkers is less than it used
   to be, which makes it even less likely that you will find such beasts
   around.

   Certainly we have decided that we cannot count on smart linkers for
   elimination of unused subprograms, which is why we have decided on
   a source based approach to solve this problem. Basically our approach
   works as follows:

     There is a configuration pragma which declares that a certain 
     subprogram is unused. In the presence of the pragma, the compiler
     (a) stubs out the subprogram, and (b) makes sure it is not called.

     These configuration pragmas can be gathered together in gnat.adc
     as usual, so no actual source changes are required.

     There is an ASIS based tool that scans a set of units to determine
     the set of unused subprograms and builds the necessary file of
     configuration pragmas.

Robert Dewar
Ada Core Technologies

Re: Looking for a smart linker for GNAT/DOS

[Fergus Henderson]

dewar@merv.cs.nyu.edu (Robert Dewar) writes:

>   Note for example that the DLL that comes with Cygwin is pretty big,
>   several megabytes, since it contains huge amounts of functionality.

Nope, the DLL that comes with Cygwin is several megabytes only because
it contains huge amounts of *debugging information*.  I haven't built
a version of cygwin.dll without debugging information myself, but
I've heard that without debugging info it is less than half a megabyte
(somewhere between 300 and 400k, if I remember correctly.)

--
Fergus Henderson <fjh@cs.mu.oz.au>   |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>   |  of excellence is a lethal habit"
PGP: finger fjh@128.250.37.3         |     -- the last words of T. S. Garp.

Re: Looking for a smart linker for GNAT/DOS

[Robert Dewar]

G. asks

Wow! Will it be integrated into GNAT (gnatmake) ?

  Yes, it will be integrated into gnatmake or some higher level harness

and Turbo Pascal linker among 16 bit DOS linkers...

  I was talking about general purpose linkers. You will find quite a few
  special purpose language specific linkers that can do this. For example,
  many of the old Alsys compilers have specialized binder/linker software
  that eliminated unused subprograms.

  The trouble with doing it generally is that most object formats are not
  well set up to accomdate this processing at link time.

Re: Looking for a smart linker for GNAT/DOS

[Geert Bosch]

Robert Dewar (dewar@merv.cs.nyu.edu) wrote:
      One thing that can help is the systematic use of DLL's or
      whatever shared libraries are called on your machine. Since
      only what you actually use is loaded into physical memory,
      and since your image then does not contain the code, the
      problem is largely alleviated.

Actually, this only increases the importance of smart linkers or 
compilers. In the example below I will assume a system with 4 kB
VM pages loaded on demand.

Consider a program using a library of 50 subprograms of 500 bytes
in size on average. When the program uses only 6 of the subprograms
in the package, chances are that these 6 subprograms are all in
different VM pages, so using these 6 subprograms will cause nearly
the entire library to be loaded.

When statically linking in only the functions that are actually
used, they all fit in a single VM page reducing the working set
and improving locality of reference. Since compilers know a lot
about the calling graph of a library or program they should
arrange the code in such a way that VM pages are used in a smart
way. 

Regards,
   Geert

Re: Looking for a smart linker for GNAT/DOS

[Gautier]

> I'm thinking about the LAPACK library in FORTRAN, too: in many real projects,
> only a few from the thousends LAPACK routines are used.
> A GNAT/DOS implementation of it would produce executables of >20 megas
> (and certainly just wouldn't run on most machines),
> although they should be of a few hundreds of K if linked by a good linker!
> 
>    You are confusing virtual and physical memory here. Just because an
>    EXE is large does not mean that you needs lots of physical memory in
>    your working set to run the program, so you are probably quite wrong
>    about it not running on most machines.

I meant running at a reasonable speed, too. If your computation takes
100 days instead of 1 because of waste of memory (=> need of virtual
memory), oooch!

(...)
>    There are two solutions (besides a smart linker). The first is to
>    structure the interface as a set of separate Ada 95 child units,
>    rather than one monolithic spec. After all the original Fortran
>    routines are separate units, and a Fortran program using LAPACK
>    works fine even without a smart linker.

That's true, but if you have to mention explicitly all the part
of LAPACK you are using, you won't convince any Fortran programmer to
change... (Do you know Modula-2, where the ``importation'' part is
as long as the programmes themselves ?)

> 
>    The second is to put the interface in a DLL, as described above.
>    These days, that is getting to be a more and more attractive
>    solution, and it may well be that this is the way to go, since
>    it is more convenient for the Ada programmer than splitting the
>    interface into separate units.

Good idea if no better solution.

> 
>    This is not to say that a smart linker would not be useful, just that
>    with modern systems, the need for smart linkers is less than it used
>    to be, which makes it even less likely that you will find such beasts
>    around.

Alas...
       
G.

Re: Looking for a smart linker for GNAT/DOS

[Robert Dewar]

Fergus said

<<Nope, the DLL that comes with Cygwin is several megabytes only because
it contains huge amounts of *debugging information*.  I haven't built
a version of cygwin.dll without debugging information myself, but
I've heard that without debugging info it is less than half a megabyte
(somewhere between 300 and 400k, if I remember correctly.)
>>

But for most people, the ability to debug calls into the DLL does
constitute useful functionality. 

Look, it is only disk space we are talking about here, nothing else! Disk
space now costs as low as 6 cents/megabyte (that's the new 6.4 meg
IDE drive which costs $350 list) 

How can one get concerned over less than 25 cents of disk space.

Well that's not quite fair, notebooks are more limited, but even there,
2 gig disks are getting pretty standard, and 3 gig disks are now available.

Re: Looking for a smart linker for GNAT/DOS

[Gautier]

> Look, it is only disk space we are talking about here, nothing else! 
                          
- Are RAM space and speed not indirectly concerned by the size of
  actually loaded blocks of EXE's or DLL's ?

> Disk
> space now costs as low as 6 cents/megabyte (that's the new 6.4 meg
> IDE drive which costs $350 list) 
> 
> How can one get concerned over less than 25 cents of disk space.
> 
> Well that's not quite fair, notebooks are more limited, but even there,
> 2 gig disks are getting pretty standard, and 3 gig disks are now available.

- The cost of disk space is secondary, the important is that you
  should put more files on disks with more space. It's not the case with
  such a ``Microsoft'' philosophy that the programs should grow in the
  same proportion as the available disk space (and be as slower as
  the processor is faster): there is no progress at all !

- The HD space grows, but the diskette space doesn't !

G.

Re: Looking for a smart linker for GNAT/DOS

[Mats Weber]

>    P.S. GNAT already does something about Text_IO. In GNAT, packages
>    like Integer_IO, Float_IO etc are implemented as child units (which
>    is how they should have been defined in the first place if we were
>    not constrained by Ada 83 compatibility), so they are only loaded
>    if needed. This implementation is transparent to a user (interested
>    people may enjoy looking at the routine Text_IO_Kludge in rtsfind
>    in the GNAT sources to see how this is done :-)

The subpackages in Text_IO are all generic, and GNAT implements generics
via macro expansion, so I don't see what this wins in exe size when
these generics are not instantiated. Or am I missing something ?

>    Certainly we have decided that we cannot count on smart linkers for
>    elimination of unused subprograms, which is why we have decided on
>    a source based approach to solve this problem. Basically our approach
>    works as follows:
> 
>      There is a configuration pragma which declares that a certain
>      subprogram is unused. In the presence of the pragma, the compiler
>      (a) stubs out the subprogram, and (b) makes sure it is not called.

One of the situations where I would like dead code elimination in the
linker or compiler is in generic instances. It often happens that a
generic unit (e.g. AVL trees with set operations, iterators, etc.) is
instantiated very often with only a small subset of its operations being
used (e.g. Insert, Member and Remove) and all the other stuff is unused.
The compilers/linkers I have used so far do not eliminate this kind of
dead code. (I know I can split the generic using generic children, but
the code exists (Ada 83) and I don't want to do this).

Even if the new GNAT pragma approach seems to make this possible (if I
understand it correctly, and assuming that the pragma is allowed for
subprograms created via generic instantiation), the process will be
manual. Is there any chance of having this done automatically ?

Re: Looking for a smart linker for GNAT/DOS

[Robert Dewar]

Geert says

<<Consider a program using a library of 50 subprograms of 500 bytes
in size on average. When the program uses only 6 of the subprograms
in the package, chances are that these 6 subprograms are all in
different VM pages, so using these 6 subprograms will cause nearly
the entire library to be loaded.>>

Yes, true on your small scale example, but here we have only 25K
of code (that's about a dime's worth of memory at current prices).
For the more typical case, where you have huge specs with thousands
of routines, or at least hundreds, the advantage of a DLL over
unsmart linking can be huge.

You are not likely to achieve smart linking on typical Unix systems.
the infrastructure is just not there (e.g. appropriate format object
modules with separate control sections for separate routines).

Re: Looking for a smart linker for GNAT/DOS

[Robert Dewar]

Gautier says

<<- Are RAM space and speed not indirectly concerned by the size of
  actually loaded blocks of EXE's or DLL's ?
>>

no, if you don't load part of an EXE file into memory, you don't load it.
Now of course there are some systems which do not provide this kind of
mapping (though nearly all do for DLL's in effect). Certainly debugging
informatoin does NOT get loaded in any system I know of. So do not assume
that EXE size is related to working set requirements!

<<- The HD space grows, but the diskette space doesn't!
>>

Well if you still mess with diskettes (I barely use them any more), then
you certainly will be struggling these days, though pretty soon, there
should be diskettes with 100x capacity -- I hardly find it convincing that
we should restrict the functionality of modern software to accomdoate
obsolete technology!

After all, old software does not go bad, if you are happy with yesterdays
smaller software that fits on diskettes, by all means use it (I think you
can even get an RR Ada 83 compiler that will run from diskettes).

Re: Looking for a smart linker for GNAT/DOS

[Robert Dewar]

Mats Weber says

<<The subpackages in Text_IO are all generic, and GNAT implements generics
via macro expansion, so I don't see what this wins in exe size when
these generics are not instantiated. Or am I missing something ?
>>

Yes, you are missing something. Only a tiny part of these packages is
generic. All sorts of basic support code (e.g. basic conversion code)
is likely to be loaded anyway in typical text_io implementations. For
example, Float_IO uses some basic floationg-point conversion routines,
that are not loaded in GNAT if you do not instantiate Float_IO.

<<One of the situations where I would like dead code elimination in the
linker or compiler is in generic instances. It often happens that a
generic unit (e.g. AVL trees with set operations, iterators, etc.) is
instantiated very often with only a small subset of its operations being
used (e.g. Insert, Member and Remove) and all the other stuff is unused.
The compilers/linkers I have used so far do not eliminate this kind of
dead code. (I know I can split the generic using generic children, but
the code exists (Ada 83) and I don't want to do this).

>>

Right in Ada you would use generic children to achieve this reliably without
depending on your implementation to eliminate unused code, but that's not
possible in Ada 83. Obviously we cannot figure out solutions for existing
Ada 83 technology here :-)

<<Even if the new GNAT pragma approach seems to make this possible (if I
understand it correctly, and assuming that the pragma is allowed for
subprograms created via generic instantiation), the process will be
manual. Is there any chance of having this done automatically ?
>>

You do not understand it correctly, and I don't quite understand where
your incorrect understanding came from -- I guess I was not clear. There
will indeed be an automatic tool that generates the necessary directives
for the compialtion process. This in fact will be one of the first
ASIS-based tools for GNAT (a whole suite of such tools is in the planning
stages, now that ASIS is becoming a reality for GNAT).

Re: Looking for a smart linker for GNAT/DOS

[Gautier]

> <<- Are RAM space and speed not indirectly concerned by the size of
>   actually loaded blocks of EXE's or DLL's ?
>>>
> no, if you don't load part of an EXE file into memory, you don't load it.

But when many blocks are alternatively loaded and unloaded during execution,
there can be much time lost...

> Now of course there are some systems which do not provide this kind of
> mapping (though nearly all do for DLL's in effect). Certainly debugging
> informatoin does NOT get loaded in any system I know of.

Fortunately...

>                                                          So do not assume
> that EXE size is related to working set requirements!
> 
> <<- The HD space grows, but the diskette space doesn't!
>>>
> 
> Well if you still mess with diskettes (I barely use them any more), then
> you certainly will be struggling these days, though pretty soon, there
> should be diskettes with 100x capacity

No problem, the EXE's, the PowerPoint & Acrobat stuff will be 100x bigger too,
for exactly the same content!

>                                        -- I hardly find it convincing that
> we should restrict the functionality of modern software to accomdoate
> obsolete technology!

I don't think that ability to move of a fat person is restricted when he
becomes less fat...

> 
> After all, old software does not go bad, if you are happy with yesterdays
> smaller software that fits on diskettes, by all means use it (I think you
> can even get an RR Ada 83 compiler that will run from diskettes).

But not an Ada 95 one... I'm still unhappy:  B-(

G.
 

Re: Looking for a smart linker for GNAT/DOS

[Robert Dewar]

Gautier is unhappy that there is no Ada 95 compiler running from diskettes.

Sorry, I have zero sympathy here -- why would anyone try to run any
compiler from diskettes these days -- a complete waste of time as I
see it -- and I would have been willing to make that statement ten years

ago (the original Realia COBOL could run off disketttes, but I don't think
there was a single user who found this interesting).

The idea that the much larger software components of today have no more
functoinality thatn the small ones of yesterday seems completely at ood with
the facts to me!

Re: Looking for a smart linker for GNAT/DOS

[Geert Bosch]

Gautier (Gautier.DeMontmollin@maths.unine.ch) wrote:

   But not an Ada 95 one... I'm still unhappy:  B-(

The OS/2 version of GNAT is distributed in 8 floppy-sized
files, 3 of which contain the actual compiler and runtime
library. (The rest is for development utilities, debugger
etc.) The compiler itself fits on a single floppy.

Regards,
   Geert

Re: Looking for a smart linker for GNAT/DOS

[Larry Kilgallen]

In article <5jac72$atr$1@gonzo.sun3.iaf.nl>, geert@gonzo.sun3.iaf.nl (Geert Bosch) writes:
> Robert Dewar (dewar@merv.cs.nyu.edu) wrote:
>       One thing that can help is the systematic use of DLL's or
>       whatever shared libraries are called on your machine. Since
>       only what you actually use is loaded into physical memory,
>       and since your image then does not contain the code, the
>       problem is largely alleviated.
> 
> Actually, this only increases the importance of smart linkers or 
> compilers. In the example below I will assume a system with 4 kB
> VM pages loaded on demand.
> 
> Consider a program using a library of 50 subprograms of 500 bytes
> in size on average. When the program uses only 6 of the subprograms
> in the package, chances are that these 6 subprograms are all in
> different VM pages, so using these 6 subprograms will cause nearly
> the entire library to be loaded.

But shared libraries are not just for a single program, they are for
multiple programs.  So  although the set of people using your program
on a given machine may only use 6 subprograms, those using other programs
at the same time which use the same shared library will be using different
subprograms.  They may even have preloaded the six you need by accident !

Obviously all of this depends on OS capability.

(Contrary to the thread topic, I believe the discussion indicates we
are talking about more than just single-user DOS systems.)

Larry Kilgallen

Re: Looking for a smart linker for GNAT/DOS

[Gautier]

> The OS/2 version of GNAT is distributed in 8 floppy-sized
> files, 3 of which contain the actual compiler and runtime
> library. (The rest is for development utilities, debugger
> etc.) The compiler itself fits on a single floppy.

The floppy question obviously doesn't concern the compiler, but
the produced executables! 

In an example above in this discussion, there were a non smartly
linked scientific program using a few of the thousends of LAPACK
routines. Imagine you want to distribute or sell a set of programs
of that sort. Even compressed, the executables will take tens of
diskettes and occupy too many megas in the destination HD.

G.