Type Analysis and Data Structure Selection
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.
J. Cai et al., "Type Analysis and Data Structure Selection," Constructing Programs from Specifications: Proceedings of the IFIP TC2/WG 2.1 Working Conference on Constructing Programs from Specifications, North-Holland, Jan 1991.
IFIP TC2/WG 2.1 Working Conference on Constructing Programs from Specifications, Pacific Grove, CA, USA, 13-16 May, 1991
Mathematics and Statistics
Article - Conference proceedings
© 1991 North-Holland, All rights reserved.