1 XEROX COMMON LISP DESIGN DOCUMENT 1 XEROX COMMON LISP DESIGN DOCUMENT CMLARRAY 1 XEROX COMMON LISP 1 NEW CMLARRAY 6 Ron Fischer, Larry Masinter and Gwan Santosa 14 Feb 86 While there is an existing implementation of Common Lisp arrays it has severe performance problems. It would be desireable to make almost all use of arrays within the Xerox Lisp system handled by one carefully optimized set of array functions. This would include such currently diverse structures as bitmaps. An interesting point which this brings up is the use of block transfer operations on generice arrays, which would primarily require hooks into the reference counting mechanisms. The severe performance problems in the current implementation have kept it from becoming this universal array manager. This design outlines a redesign of the data structures in the current array implementation to allow a microcode assist which will improve performance. 2 Issues 1 1) Performance is low for AREF and SETF of it. 2) Conversion of existing Xerox Lisp code to use the new and more highly optimized array facilities. 2 Decisions 1 1) Microcode assist to reduce the overhead of argument type checking and array element type dispatching. 2) Identification of existing array functionality within the system and simulation of them with 2 Design overview 1 The new array scheme can be simply separated into 4 tasks: data structure redesign, array index calculation opcode, array reference and set opcodes, block transfer opcodes, compatability package to convert old uses of existing array code. Data structures 1 The data structures in the new design will need to be completely consist across different types of arrays so that the microcode can easily determine whether it is to punt to a UFN, for higher dimensional or error cases, or to quickly calculate indices and retrieve elements one its own. In order to accomplish this all arrays have a "header" which generally describes the array; its element type and points to its storage and some indexing information. The indexing information is also referred to as a rank block, which moderates the interpretation of raw indices into array positions. This interpretation is needed because, under the Common Lisp description, two arrays may share the same storage but index into it differently. As an example, position zero for one array may be the beginning of the storage block, or for another array that shares the same storage, position zero may actually be somewhere in the middle of the storage block. The array header, and its separate rank block, allows these different "views" of the same storage space to exist. Rank blocks are a variable length data object which contain a number indicating the actual rank, or dimensionality, of the array. For each dimension in the array there will exist a triple of raw 32 bit numbers. These are: 0) an offset for position zero of the current dimension 1) the current maximum index of this dimension 2) the maximum length of this dimension The distinction between the latter two numbers in the triple is a bit fine. Index calculator 1 It is useful to proivde this as a separate opcode because read, modify, write, operations (such as incrementing an element of an array) will only need to calculate this index once. The opcode returns an offset in element units (not in words or any other implementation specific units), based on the indices provided for a one, two or higher dimensional array. The microcode will only handle only the one and two dimensional cases. Reference and set opcodes 1 Using an offset and the element type information in the array data structure, retrieves the appropriate element from the array's storage block. The microcode will handle all reference cases. Block transfer opcodes 1 The design of this area is unsettled (comments follow). Block transfer operations. To complete them we would need to identify the types of operations to be performed. I believe there is a distinction between simple block copy operations and combination operations like the current BLT, which is really like a vector AND, OR, NOR, etc. There is an orthogonality between the logical vector ops of BLT and more general vector ops like matrix or vector multiplication. 2 >>Part<< 1 >>replicate this whole section for each part. This blank should contain a description of algorithms & structures for this part<< Dependancies 1 >>part needs support from what outside of this design?<< Performance points 1 >>compiler / evaluator<< >>optimizer macros<< >>microcode<< Environment support 1 >>environmental impact (tools needed, etc.)<< Tasks 1 >>tasks this part breaks down into<< Testing issues 1 >>potential edges in algorithms and structures<< 2 Phasing and TIming 1 >>If the implementation is phased describe how and why here.<< >>Summarize by phases, parts and tasks: time estimate, dependancies and resources.<< 2 Appendix 1 >>glossaries, references, etc.<< >>SYMBOL(FOO &OPTIONAL BAZ)<< [>>def class<<] >>fn, var, const, type, etc. description<<  /øøT/ø øT.ÌÌøø/ÌÌøøT)øT)ø2T(ÌÌø )ÌÌøT)ÌÌøTBøø PAGEHEADING VERSOHEADBøø PAGEHEADING RECTOHEADAøø PAGEHEADINGFOOTINGVAøø PAGEHEADINGFOOTINGRMODERN MODERN  HELVETICA MODERNMODERNMODERN  TIMESROMAN   HRULE.GETFNMODERN  "  HRULE.GETFNMODERN  "   HRULE.GETFNMODERN    HRULE.GETFNMODERN   HRULE.GETFNMODERN7b˜ HRULE.GETFNMODERN HRULE.GETFNMODERN/f HRULE.GETFNMODERN  HRULE.GETFNMODERNib HRULE.GETFNMODERN HRULE.GETFNMODERNï HRULE.GETFNMODERN Ù #do9/(L HRULE.GETFNMODERN µû HRULE.GETFNMODERN À HRULE.GETFNMODERN 8 HRULE.GETFNMODERN  HRULE.GETFNMODERN‚  HRULE.GETFNMODERN 9 HRULE.GETFNMODERN  HRULE.GETFNMODERN . HRULE.GETFNMODERN % HRULE.GETFNMODERN 1 HRULE.GETFNMODERN HRULE.GETFNMODERN?U HRULE.GETFNMODERN  HRULE.GETFNMODERN!*ÏÄzº