cs450a03@uc780.umd.edu (04/19/91)
This is a continuation of my last post: vauge ruminations about how to implement J efficiently. Problem: building a list of length n from n scalar operations is O(n squared), rather than O(n) LISP people would laugh, and say you need cons cells. That might actually be a way to go: have catenate build an internal structure specially optimized for catenate, then the first time something besides catenate operates on that object, a post processing stage kicks in and produces a flat list for use by whatever this new function is. There would be a tradeoff there--for some things this could really waste time. Also note that this is similar to using APL's indexed assignment assignment to build arrays, although indexed assignment takes advantage of being able to estimate storage requirements ahead of time. Most likely, the people at ISI and IPS have already gone over this issue a number of times, and already have some favored solutions. Any comments from over there? Raul Rockwell
rbe@yrloc.ipsa.reuter.COM (Robert Bernecky) (04/21/91)
In article <19APR91.08155946@uc780.umd.edu> cs450a03@uc780.umd.edu writes: > >Problem: building a list of length n from n scalar operations is O(n >squared), rather than O(n) > >There would be a tradeoff there--for some things this could really >waste time. Also note that this is similar to using APL's indexed >assignment assignment to build arrays, although indexed assignment >takes advantage of being able to estimate storage requirements ahead >of time. The way that I originally implemented function rank at I.P. Sharp, way back in the dark ages around 1980 or so, was as follows: Build an array of pointers the size of the frame. Call the function to which rank applied once per element in that frame, building an array of the cell contents for each call. This went through all the primitive function conformability checking, storage management, etc. for each call. Pricey, but general, it worked, and was easier than modifying 300 thousand lines of assembler code. When all the cells had been processed, COPY all those cell results (which had been attached to the above array, ala BOX), to a NEW array, which held the logically flattened result. The special casing for catenate and other verbs I mentioned in my previous message consisted largely of removing the above sort of silliness, and placing a new outer loop around the primitive's loops, after conformability checks had been done. Both of these techniques were chosen because of the huge amount of code which not only made assumptions about data structures, but also made assumptions about space "near" data structures. FOr example: "I know I can set the rank and type of the result at the same time, because I KNOW they are adjacent cells in the same word", and "I KNOW I can index off the end of this array when storing into it, because storage management ensures that I have about 32 bytes of slop off the end of ANY just-allocated array". The last one was a killer. Still is. These sorts of assumptions are nasty because they do NOT exist in visbibly in the code -- they just lurk there, waiting to strike at the unwary. These are the sorts of coding tricks which can kill. But I digress. The way we got around it allocated storage once, and built the cell results in situ. (Situ is located near Cleveland, somewhere). Robert Bernecky rbe@yrloc.ipsa.reuter.com bernecky@itrchq.itrc.on.ca Snake Island Research Inc (416) 368-6944 FAX: (416) 360-4694 18 Fifth Street, Ward's Island Toronto, Ontario M5J 2B9 Canada
hui@yrloc.ipsa.reuter.COM (Roger Hui) (04/22/91)
Bob Bernecky writes: >But I digress. The way we got around it allocated storage once, and >built the cell results in situ. (Situ is located near Cleveland, somewhere). Bob, I gather that by "located near Cleveland", you mean it borders on the eerie ...