Program Specialization E-Book

Renaud Marlet

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 989

Veröffentlichungsjahr: 2013

Beschreibung

This book presents the principles and techniques of program specialization — a general method to make programs faster (and possibly smaller) when some inputs can be known in advance. As an illustration, it describes the architecture of Tempo, an offline program specializer for C that can also specialize code at runtime, and provides figures for concrete applications in various domains. Technical details address issues related to program analysis precision, value reification, incomplete program specialization, strategies to exploit specialized program, incremental specialization, and data specialization. The book, that targets both researchers and software engineers, also opens scientific and industrial perspectives.

Leseprobe

Contents

Chapter 1 Main Principles of Program Specialization

1.1. Specialized program

1.2. Specializing to improve performance

1.3. Automatic specialization

1.4. Main applications of specialization

1.5. Specialization times

1.6. Financial viability of specialization

Chapter 2 Specialization Techniques

2.1. Transforming specialization programs

2.2. Termination of specialization

2.3. Correctness of specialization

2.4. Other forms of specialization

Chapter 3 Offline Specialization

3.1. Main principles of offline specialization

3.2. Compared advantages of offline specialization

3.3. Main components of binding-time analysis

3.4. When static inputs become dynamic

Chapter 4 A Specializer for C: Tempo

4.1. History

4.2. Disruptive technologies

4.3. Architecture

4.4. Engineering economics

4.5. Beyond Tempo

4.6. Other specializers for the C language

Chapter 5 Applications of Specialization

5.1. Applications in operating systems and networks

5.2. Applications to numerical computation

5.3. Applications to compilation using an interpreter

5.4. Applications to the optimization of software architectures

5.5. Specialization as a software engineering tool

Chapter 6 Precision of Program Analysis

6.1. Choosing the precision of an analysis

6.2. Sensitivity to (control) flow

6.3. Sensitivity to speculative evaluation

6.4. Sensitivity to data structure components

6.5. Sensitivity to data structure instances

6.6. Sensitivity to use (of memory locations)

6.7. Sensitivity to use of literal constants

6.8. Intraprocedural versus interprocedural analysis

6.9. Sensitivity to the context (of function call)

6.10. Sensitivity to the return value

6.11. Other precision forms

6.12. Precision of the existing C specializers

Chapter 7 Reification: From a Value to a Term

7.1. Different types of reification

7.2. Constraints of lifting

7.3. Lifting of immutable data

7.4. Lifting of a non-shared mutable piece of data

7.5. Reification of a shared mutable piece of data

7.6. Reification of a reference

7.7. Physical data sharing between execution times

7.8. Reification and binding time

Chapter 8 Specialization of Incomplete Programs

8.1. Constraints on the code to be specialized

8.2. Specialization module and language module

8.3. Revision of the expression of specialization

8.4. Calling context of a function to be specialized

8.5. Effect of external function calls

8.6. Abstract modeling languages

8.7. Concrete modeling

Chapter 9 Exploitation of Specialization

9.1. Means of exploiting specialization

9.2. Invariant execution context

9.3. Optimistic specialization

9.4. Selection by necessity of a specialized function

9.5. Selection by anticipation of a specialized function

Chapter 10 Incremental Runtime Specialization

10.1. Data availability staging

10.2. Models for incremental specialization

10.3. Binding-time analyses for incremental specialization

10.4. Implementation

10.5. Compared advantages of iterated specialization

10.6. Related works

10.7. Improving incremental runtime specialization

Chapter 11 Data Specialization

11.1. Program specialization and loop unrolling

11.2. General concept of data specialization

11.3. Caching and binding time

11.4. Structuring the cache

11.5. The question of control in data specialization

11.6. Reconstructions of control

11.7. Program specialization versus data specialization

11.8. Experimental results

Chapter 12 Scientific Perspectives

12.1. Improving the specialized code

12.2. Complexity of the process of specialization

12.3. Simplifying the process of specialization

12.4. Integration into a software engineering process

Chapter 13 Conclusion: From Prototype to Product

13.1. The race for performance

13.2. A different viewpoint

13.3. Difficulties for investing in software engineering

13.4. Niche uses

13.5. Developing a specialization platform

Appendix: Basic Facts about Languages and Programs

A.1. Programming languages

A.2. Semantics

A.3. Program equivalence

A.4. Execution

A.5. Program performance

A.6. Program analysis

A.7. Program transformation

Bibliography

Index

First published 2013 in Great Britain and the United States by ISTE Ltd and John Wiley & Sons, Inc.

Apart from any fair dealing for the purposes of research or private study, or criticism or review, as permitted under the Copyright, Designs and Patents Act 1988, this publication may only be reproduced, stored or transmitted, in any form or by any means, with the prior permission in writing of the publishers, or in the case of reprographic reproduction in accordance with the terms and licenses issued by the CLA. Enquiries concerning reproduction outside these terms should be sent to the publishers at the undermentioned address:

ISTE Ltd

27-37 St George’s Road

London SW19 4EU

UK

www.iste.co.uk

John Wiley & Sons, Inc.

111 River Street

Hoboken, NJ 07030

USA

www.wiley.com

© ISTE Ltd 2013

The rights of Renaud Marlet to be identified as the author of this work have been asserted by him in accordance with the Copyright, Designs and Patents Act 1988.

Library of Congress Cataloging-in-Publication Data

Marlet, Renaud.

Program specialization / Renaud Marlet.

p. cm.

Includes bibliographical references and index.

ISBN 978-1-84821-399-9

1. Program transformation (Computer programming) I. Title.

QA76.6M35946 2012

005.1--dc23

2012006563

British Library Cataloguing-in-Publication Data

A CIP record for this book is available from the British Library

ISBN: 978-1-84821-399-9

Chapter 1

Main Principles of Program Specialization

Who was it that said, “Let us lean heavily on principles; they will always give way in the end”?

— Edouard Herriot Notes & Maxims

A program specialization is a type of optimizing program transformation. To simplify this, we can take the following example: if we have a program, on the one hand, and a context for its execution, on the other (i.e. a partial knowledge of the data that will be input into the program at run time), we seek to create a new program, whose behavior is identical to that of the original program (same effects, same results), but which performs better because it is specialized to that particular execution context. In a broad context, program specialization denotes an area of computer science that brings together analytical and program transformation techniques to automatically create specialized programs.

In this chapter, we examine the main principles of program specialization. We build a cohesive framework to be used in the following chapters, which essentially discuss and develop offline specialization techniques for the C language, but whose scope is, in fact, broader than this, with the arguments being transposed or extended to C++ and Java.

Here, we focus on the motives and the stakes involved in program specialization, while attempting to maintain a fairly broad, general view. For more information about particular language cases, especially as regards binding times, the reader is referred to the publications and reference works cited in the text.

Organization of this chapter

– Section 1.1 precisely defines what a specialized program is, in terms of precomputations and semantic equivalence to the original program.

– Section 1.2 explains the advantages of specialization from the point of view of performance (in time and space).

– Section 1.3, without detailing the techniques involved in program specialization, constructs the general framework of an automated specialization process, and examines the pros and cons of this.

– Section 1.4 describes the main applications of program specialization: compiling with an interpreter (and more generally getting rid of layers of interpretation), changing an interpreter into a compiler, and creating a compiler generator.

– Section 1.5 distinguishes two specialization times (compile time and runtime) and examines the uses to which the resulting specialized programs could be put (as a specialization server and a specialization cache).

– Section 1.6, finally, discusses questions relating to whether or not specialization is profitable, particularly in terms of time and space saved.

1.1. Specialized program

In this section, we define the most commonplace concepts associated with program specialization, with the question of automatic production of a specialized program being dealt with in subsequent sections.

1.1.1. Program specialization

[1.1]

The pins program is also known as a specialized program. In certain ways, it is equivalent to the program p for the input values in that make up the partial input ins – equivalent, in the sense that it produces the same output – that is, it has the same effects and provides the same results:

[1.2]

If we are only interested in the input in that forms part of the partial input ins, then the specialized program pins can, in a manner of speaking, be “substituted” for program p. Strictly speaking, the input channels of pins are included in those of p, and the programs p and pins are only indirectly comparable from a semantic point of view (see section 1.1.6). The above definitions are represented diagrammatically in Figure 1.1.

Figure 1.1.Generic program and specialized program

On the other hand, program p has more input channels than pins – it can operate in more execution contexts. That is why, by contrast to the specialized program pins, p is referred to as a generic program.

NOTE 1.1. – This definition is purely semantic – it does not imply any link between the generic and the specialized programs other than the inclusion of identical input to yield identical output. In practice, a specialized program does not simply materialize, but rather it is obtained by transforming a generic program (see section 1.3). Also, as so often happens with nominalizations of verbs, the term “specialization” denotes both the action (of transforming a generic program p into a specialized program pins) and the result of that action (a specialized program pins). However, in this section, we discuss only the actual nature of the specialized code.

The known partial input ins to which the program is specialized is termed static input. The additional partial input ind is called dynamic input. This terminology illustrates the fact that, for a specialized program pins, the static input ins is fixed, whereas the dynamic input ind can still vary, as it remains unknown up until the moment of execution. The input values of ins are called specializing values.

According to this definition, in is not restricted to just the input that is compatible with p, nor is ind restricted just to the input that is compatible with pins (see section A.2.9). In particular, the semantic terms may be equal to a defined error in output, err. Consequently, if the partial input ins is incompatible with p, then pins is a program whose execution systematically produces an output with a definite error err. Also, remember that here we assume a program to be complete and not to interact with external objects (see section A.2.10), hypotheses that will be raised in Chapter 8.

We do not have to specialize all of a program; we can specialize only a portion of it – in practice, one or more subprograms (see section 9.1). However, to avoid ambiguity, hereafter we will not speak of specializing subprograms, but of specializing programs. Similarly, we will use the term specialized program to refer to a program–one of whose subprograms is specialized. When we use a subprogram accompanied by the functions it calls upon (to an arbitrary call depth), we call this the specialization point of entry.

In sections 3.3.3 and 6.6, we will look at a variant of this definition of specialization in which an input insd to the program may be considered to be both static and dynamic. The idea is that it serves simultaneously to generate the specialized code pins, insd and execute it . Notably, this variant enables us to look at cases where a piece of information cannot easily be integrated into a program’s code.

Examples of specialization