ftp.umcs.maine.edu/2015-02-07.ftp.umcs.maine.edu.tar/ftp.umcs.maine.edu/pub/WISR/wisr6/proceedings/ascii/thomas.ascii

Text File | 1993-10-19 | 18KB | 380 lines

                A  Scalable  Approach  to  Software  Libraries



               Jeff Thomas, Don Batory, Vivek Singhal, and Marty Sirkin



                                Department of Computer Sciences

                                The University of Texas at Austin

                                          Austin, Texas 78712

                                       Tel:  [phone]

                   Email: fjthomas,batory,singhal,[e-mail]



                                                  Abstract


    Software libraries offer a convenient and accessible means to achieve the benefits of reuse. The
components of these libraries are written by hand, and each represents a unique combination of
features that distinguishes it from other components. Unfortunately, as the number of features
grows, the size of these libraries grows exponentially, making themunscalable.
    Predator is a research project to develop abstractions and tools to provide the benefits of
software libraries without incurring the scalability disadvantages just mentioned. Our approach
relies on a careful analysis of an application domain to arrive at appropriate high-level abstrac-
tions,  standardized  (i.e.,  plug-compatible)  interfaces,  and  layered  decompositions.  Predator
provides  language  extensions  for  implementing  components, and  compilers  to  automatically
convert component compositions into efficient programs.


Keywords: Predator, GenVoca, domain analysis, containers, software libraries, software reuse,
compositional reuse, generative reuse, feature combinatorics.


Workshop Goals: feedback on our work; exposure to other important work in software reuse.


Working  Groups:  reuse  process  models;  reuse terminology  standards;  domain  analysis  /
engineering; design guidelines for reuse-general, Ada, and C++; reuse and OO methods; tools
and environments.



                                                 Thomas- 1


1      Introduction



Domain-specific software libraries are becoming an increasingly common means of rapidly building
software  systems.  Such  libraries  offer  numerous  software  components  that implement  different
algorithms  from  a  given  problem  domain.  For  example, consider  the  domain  of  data  structure
algorithms  (i.e., containers  of  objects).   Examples  include  linked  lists,  arrays,  trees, and  hash
tables.  Because eachof these structures could be implemented using a variety of algorithms, the
domain of data structures is clearly quite large. The FSF's libg++ class library [1] and the C++
Booch Components [2] are examples of data structure software libraries.


Although software libraries offer a simple and effective means of attaining the benefits of reuse,
they also expose a basic obstacle that limits the long-term success of software libraries as a reuse
paradigm. The Booch Components offers numerous implementations for each basic data structure;
for example, it provides 3  3  2 = 18 varieties of deques (double-ended queues)! A developer can
choose a deque's algorithm for concurrency control (sequential, guarded, synchronized), memory
allocation (bounded, unbounded, dynamic), and priority (ordered, unordered). Each of these fea-
ture selections is mutually independent; consequently,  the implementor of the component library
must laboriously enumerate every permutation of feature selections.


As the number of available features increases, the size of component libraries grows exponentially.
For  example, suppose  a  new  feature  were  added  which  let  a  library  user  choose  if  the  elements
of  a  deque  should  be  stored  in  persistent  memory  or  transient memory;  the  number  of  deque
components would then double from eighteen to thirty-six.  It is apparent that as domain-specific
software libraries achieve broader use, they will need to support an even broader range of features,
thus aggravating this problem of feature combinatorics.


Feature combinatorics is a serious problem.  Consider the following disadvantages for the library
implementor:



    fflLibrary growth can be explosive.


    fflLibrary maintenance is complicated by the large number of components.


    fflCode repetition is a nightmare that inheritance alone cannot solve.



And the following disadvantages for the library user:



    fflIf the library implementor is unable/unwilling to supply components that enumerate every
       permutation of features, then it is likely that some application will eventually need a particular
       combination of features which isn't implemented by any component.


    fflSearching for the appropriate component is difficult when the size of the library is large.



This  problem  of  feature  combinatorics  is  not  unique  to  data  structures.  Twenty-five  years  ago,
McIlroy  [3]  postulated  that  a  well-stocked  library  of  sine  routines  would  likely contain  as  many
as 300 components, supporting different degrees of precision, granularity, range, and robustness.
Krueger  recognized  that  the  problem  of  feature  combinatorics  is,  unfortunately,  inherent  to  all
libraries [4].  Clearly, we must find a means of populating libraries of software components which is
scalable with respect to the number of features offered by the library.



                                                        Thomas- 2


2      Predator



The Predator system is based on the idea that data structures should be mechanically generated
from libraries of primitive components, where each component implements precisely one feature.
Users specify the set of features that they want,and Predator synthesizes the target data structure.
This approach eliminates the implementation and maintenance problems of feature combinatorics,
and is scalable by just adding new primitives to the Predator library.


In program generation systems like Predator, careful designand implementation of components is
critical.  The interfaces of components shouldreflect the basic abstractions of the domain.  Such
interfaces might be identified using domain modeling techniques.  In Predator,component interfaces
actually  were  deliberately  designed  to  ensure  that  they  would  be  suitable  for  building  complex
data structures.  Good component designs result from interfaces that p ossess the following three
properties [5, 6 ]:



    1. High-level  abstractions.  It  is  well-known  that  using  high-level  abstractions  makes  pro-
       grams easier to write and debug. It is essential for component interfaces to hide the complex
       details of their encapsulated data structures; not doing so would make components difficult
       to use and virtually impossible to combine.


    2. Standardized  interfaces.  A  key feature of software component/software generator tech-
       nologies is the ability to interchange different data structure implementations to address ap-
       plication performance requirements. Note that plug-compatible interfaces are already present
       to some extent in existing component libraries (such as Booch Components and libg++). In
       fact,  all  basic  data  structures  (lists,  trees,  arrays,  etc.)  could  even  be  viewed  as  different
       implementations of the same container abstraction (that is, all of these data structuresserve
       as containers for collections of objects).


    3. Layered  designs.  Experience  has  shown  that  many  software  systems  have  hierarchical
       designs.  The layering of abstractions (and their implementations)provides a powerful way
       to design, build, and understand complex software.  Layering is an important technique for
       managing  complexity.  By  partitioning  a  system  into  layers, system  design  can  be  greatly
       simplified.



High-level  abstractions, standardized  interfaces, and  layered  designs  characterize  our  implemen-
tation of Predator.  Each data structure feature is encapsulated in a separate component.  This
collection of components_which is inherently open-ended_defines the Predator library.  Target
data  structures_those  that  would  be  requested  by  Predator  users_are  specified  as  hierarchical
compositions of library components.


Predator provides language extensions to support the specification and composition of primitive
components, and compilers to convert them into efficient executable code.  The Predator compil-
ers use advanced optimizations such asinlining and partial evaluation.  Currently, there are two
compilers (P1 [7 ] and P2 [8 ]), both providing language extensions to ANSI C.1


P1 demonstrated that our approach was promising. It was used to generate the data structures
for the OPS5/LEAPS system, a compiler for OPS5 rules [10 ]. OPS5/LEAPS was chosen because
___________________________________________________1
     We are also developing a third Predator compiler (P++ [9]) that will provide domain-independent language
extensions to C++. We envision that P++ will be the ultimate platform on which to base future Predator research.



                                                        Thomas- 3

               _________________________________________________________________________________________________
               _                                       _Unordered _      Unordered _     Sorted  _   Binary _
               __Component_library_______________________linked_list___________array_______array_________tree____

               _ Booch Components 2.0-beta  _                    320  _           360 _      398  _      481  _
               _ libg++ 2.4                        _             336  _           386 _      474  _      336  _
               _ P1                                   _          281  _           281 _      287  _      285  _
               __P2______________________________________________308______________310________316_________310____



                    Figure 1:  Code size (in words) of dictionary benchmark programs.


               _________________________________________________________________________________________________
               _                                       _Unordered _      Unordered _     Sorted  _   Binary _
               __Component_library_______________________linked_list___________array_______array_________tree____

               _ Booch Components 2.0-beta  _                   70.9  _          54.6 _     11.1  _     15.4  _
               _ libg++ 2.4                        _            41.9  _          34.3 _       5.4 _       4.1 _
               _ P1                                   _         40.2  _          33.3 _       6.3 _       3.0 _
               __P2_____________________________________________39.9_____________33.1_________5.9_________2.9___



                Figure 2: Execution time (in seconds) of dictionary benchmark programs.



it demands high-performance and complex data structures. Preliminary experiments have shown
that using P1 to generate OPS5/LEAPS code results in improved programmer productivity and
executable code performance relative to hand written code. In the largest example attempted so
far, P1 generated almost 7000 lines of C code whose performance was 20-30% better than that of
OPS5/LEAPS. Reports on these experiments are forthcoming.


P2 is a follow-on project to P1. It supports domain-specific extensions to ANSI C and provides a
more modular and maintainable architecture than P1. P2 is a system that we plan to distribute.


In  order  to  further  verify  the  productivity  and  executable  co de  p erformance  advantages  of  our
approach, we used a simple benchmark2  totest programs using the Booch Components and libg++
container classes against P1 and P2 generated container co de.


Three observations regarding productivity were immediately apparent:



    fflThe size of the P1 and P2 programs were the same or smaller than corresponding implemen-
       tations for the Booch C++ Components and libg++ (see Figure 1). The reason is that both
       P1 and P2 offer high-level container abstractions that make programs compact and quicker
       to write.


    fflIt was trivial to alter container implementations in P1 and P2 programs. In general, only a
___________________________________________________2
     Since we know of no commonly-used benchmark suites that can evaluate container libraries in terms of program-
mer productivity and performance, we we devised our own benchmark. Our benchmark spell-checks a document
(the 1600 word Declaration of Independence) against a dictionary of 25,000 words.  The main activities involved
are inserting randomly ordered words of the dictionary into one container, inserting words of the target document
into another container while eliminating duplicates,and printing those words of the document container that do not
appear in the dictionary container.
   We used the Booch Components, libg++, P1, and P2 to implement this benchmark using four different container
implementations: unordered linked lists, unordered arrays, sorted arrays, and binary trees. The benchmarks were
executed on a SPARCstation 1+ with24 MB of memory, running SunOS 4.1.2. The Booch Components code was
compiled with Sun C++ 3.0.1 -O4, libg++ with G++ 2.4.5 -O2, and P1 and P2 with GCC 2.4.5 -O2.


                                                        Thomas- 4


       few lines of declarations needed to be changed; no executable lines were modified.


    fflPrograms that used the Booch C++ Component and libg++ libraries required more extensive
       modifications  when  container  implementations  were  altered.  Different  data  structures  had
       either different interfaces or different names for semantically equivalent functions.



Also  observe  that  the  performance  of  P1  and  P2  code  is  comparable  to the  p erformance  of  the
other programs (see Figure 2).



3      Conclusion



Software  libraries  have  been  a  successful  means  of  achieving  component  reuse.   The  paradigm
of  populating  a  library  with  components,  however,  is  potentially  very  brittle.   When  libraries
contain components that each encapsulate several features, this is a symptom of a library that is
unscalable_the number of combinations of features(and hence components) is exponential.  This
is the case for libraries of data structures.


We  believe  a  practical  alternative  to  unscalable  libraries  is  to  rebuild  these  libraries  to  contain
components that encapsulate individual features. The library should be accompanied by a generator
(or compiler) that will take a simple user-written specification of thefeatures of the target software,
and will assemble that software automatically. We are showing that performance and productivity
need  not  be  sacrificed  by  taking  a  generative  approach.   We  believe  software  generators  will  be
important tools in the advancement of software reuse.



References



  [1] D. Lea, "libg++, the GNU C++ library," in Proceedings of the USENIX C++ Conference,
      1988.


  [2] G. Booch, Software Components with Ada.  Benjamin/Cummings, 1987.


  [3] M. McIlroy, "Mass produced software components,"  in Proceedings of NATO Conference  on
      Software Engineering, pp. 88-98, 1969.


  [4] C. W. Krueger, "Software reuse," ACM Computing Surveys, June 1992.


  [5] D. Batory, V. Singhal, and M. Sirkin, "Implementing a domain model for data structures,"
      International Journal of Software Engineering and Know ledge Engineering, vol. 2, pp. 375-402,
      September 1992.


  [6] D. Batory and S. O'Malley, "The design and implementation of hierarchical software system
      with  reusable  components," ACM  Transactions  on  Software  Engineering  and  Methodology,
      October 1992.


  [7] M. Sirkin, D. Batory, and V. Singhal, "Software components in a data structure precompiler,"
      in Proceedings of the 15th International Conference on Software Engineering, May 1993.


  [8] D. Batory, V. Singhal, M. Sirkin, and J. Thomas, "Scalable software libraries," in Proceedings
      of  the  ACM  SIGSOFT  '93:  Symposium  on  the Foundations  of  Software  Engineering, (Los
      Angeles, California), December 7-10 1993.


                                                        Thomas- 5


  [9] V.  Singhal  and  D.  Batory,  "P++: a  language  for  software  system  generators,"  Tech.  Rep.
      TR-93-16, Department of Computer Sciences, The University of Texas at Austin, 1993.


[10]  D. A. Brant and D. P. Miranker, "Index support for rule activation," in Proceedings of 1993
      ACM SIGMOD, May 1993.



4      Biography



Jeff Thomas is a graduate student in the Department of Computer Sciences at the University
of  Texas, Austin.   He  received  his  B.S.  and  M.Eng.   from  Cornell  University  in  1989  and  1992
respectively. His research interests include software engineering, databases, operating systems, and
artificial intelligence.


Don Batory is an Associate Professor in the Department of Computer Sciences at The University
of Texas, Austin. He received his Ph.D. from the University of Toronto in 1980, he was Associate
Editor of the IEEE Database Engineering Newsletter from 1981-84 and was Associate Editor of
ACM Transactions on Database Systems from 1986-1991.  He is currently a member of the ACM
Software Systems Award Committee,and his research interests are in extensible and object-oriented
database management systems and large scale reuse.


Vivek Singhal is a doctoral candidate in the Department of Computer Sciences at the Univer-
sity  of  Texas, Austin.  He  received  his  S.B.  from  the  Massachusetts  Institute  of  Technology  in
1990. His research interests include reuse systems, domain modeling, and object-oriented database
management systems.


Marty Sirkin is a staff programmer at IBM Austin and a doctoral candidate at the University of
Washington. He received his M.S. from the University of Washington in 1988, and his B.S. from the
California Institute of Technology in 1984.  His research interests include reuse systems, distributed
database management algorithms, and ease-of-use issues in user interface design.



                                                        Thomas- 6