Type Analysis and Data Structure Selection

Editor(s)

Moller, B.

Abstract

Schwartzet al.described an optimization to implement built-in ab-stract types such as sets and maps with e cient data structures. Theirtransformation rests on the discovery of nite universal sets, called bases,to be used for avoiding data replication and for creating aggregate datastructures that implement associative access by simpler cursor or pointeraccess. The SETL implementation used global analysis similar to classicaldata ow for typings and for set inclusion and membership relationshipsto determine bases. However, the optimized data structures selected bythis optmization did not include a primitive linked list or array, and alloptimized data structures retained some degree of hashing. Hence, thisheuristic approach only resulted in an expected improvement in perfor-mance over default implementations. The analysis was complicated bySETL's imperative style, weak typing, and low level control structures.The implemented optimizer was large (about 20,000 lines of SETL sourcecode) and only partially operational.

Meeting Name

IFIP TC2/WG 2.1 Working Conference on Constructing Programs from Specifications, Pacific Grove, CA, USA, 13-16 May, 1991

Department(s)

Mathematics and Statistics

Document Type

Article - Conference proceedings

Document Version

Citation

File Type

text

Language(s)

English

Rights

© 1991 North-Holland, All rights reserved.

Publication Date

01 Jan 1991

This document is currently not available here.

Share

 
COinS