Runtime Tags Aren't Necessary
Report ID: TR-142-88Author: Appel, Andrew W.
Date: 1988-03-00
Pages: 10
Download Formats: |PDF|
Abstract:
Many modern programming environments use tag bits at runtime to distinguish objects of different types. This is particularly common in systems with garbage collection, since the garbarge collector must be able to distinguish pointers from non-pointers, and to learn the length of records pointed to. The use of tag bits leads to inefficiency. They take up memory (though generally not too much); but more important, tag bits must be stripped off of data before arithmetic operations are performed, and re-attached to the data when it is stored into memory. This takes either extra instructions at runtime, or special tag-handling hardware, or both. This paper shows how the use of tag bits, record descriptor words, explicit type parameters, and the like can be avoided in languages (like ML) with static polymorphic typechecking. Though a form of tag will still be required for user-defined variant records, all other type information can be encoded once - in the program - rather than replicated many times in the data. This can lead to savings both in space and time.