To: patterns@cs.uiuc.edu Subject: Where's the beef? Patterns to chew on (first in a series) Reply-To: Don Dwiggins Date: Tue, 6 Dec 94 10:19:53 PST From: dwig@markv.com Ralph Johnson writes (in patterns-discussion): > If you want to make your > patterns good, get as much feedback as you can. Get people to use > them. Post them to the patterns list several times. Find a few people > who are interested in your patterns and talk a lot with them. > Lots of people make comments on this list about the patterns they are > writing, but few people post their patterns. Your patterns will never > reach their potential if you don't get lots of feedback on them. > -Ralph And Robert Martin adds: > I, for one, would love to see more patterns posted on this list. > Otherwise, "Where's the beef?" OK, you've convinced me. I have some nascent patterns, in state all the way from raw to quarter-baked (do you bake beef?); I was planning to put a little more solitary work on them before exposing them, but Ralph and Robert are right. The best use of this list is to get the ideas out early, and bring them to completion together. Some of these patterns embody tradeoffs between alternative approaches; I've written them as single patterns, since the alternatives need to be considered together, and the solution is essentially the choice of alternative. I've used the Gang of Four template as a guide, but haven't followed it exactly. Following is the first one; I'll post others in subsequent messages: ---- Lazy vs. Eager Processing Intent ------ Create processing artifacts at the right time for the situation Motivation ---------- Eager processing creates artifacts as soon as possible, even if they're not needed at the moment. Lazy processing only creates artifacts when they're called for; in particular, a compound object may be created piecemeal, and unused parts may never be created. Eager processing exploits parallelism to create artifacts ahead of need, so they're instantly available when called for; on the other hand, it uses cycles that may be wasted if the artifacts aren't in fact ever used. Lazy processing saves cycles by not creating more than is needed; in fact, where the artifact is potentially infinite (e.g. the list of all primes), it may be the only way to go. On the other hand, it could slow things down when clients have to wait while an artifact is created. Applicability ------------- When an object is going to be needed at some point, and will take considerable time to access or create, consider a) whether the entire object will likely be needed and b) whether it's possible and useful to create it ahead of the need. Solution -------- {TBD, but should include the following:} Consider mixing the two: compute parts of an artifact ahead of time, others only on demand. Consequences ------------ {TBD} Implementation -------------- {TBD; discuss techniques such as closures and continuations for lazy processing, parallelism for eager processing} Related patterns ---------------- Strong vs. Weak Methods: extra knowledge can avoid waste associated with "overeager" processing, and delays caused by "too lazy" processing. Examples of use --------------- {Need real examples, references} Eager: traversing long list stored on persistent storage, chunked 100 elements per "block". When passing 80th element, fork process/thread to load next block. Lazy: random number generator provides list of numbers one at a time. Eager: parallel garbage collection: grab the junk as soon as it shows up. Lazy: partial garbage collection: only collect enough to satisfy the current request. Don Dwiggins "Solvitur Ambulando" Mark V Systems, Inc. dwig@markv.com Date: Tue, 6 Dec 94 13:53:03 PST From: dwampl@atl.com (Dean Wampler (dwampl@atl.com)) To: patterns@cs.uiuc.edu Cc: dwig@markv.com Subject: Re: Where's the beef? Patterns to chew on (first in a series) > Reply-To: Don Dwiggins > ... > > OK, you've convinced me. I have some nascent patterns, in state all the > way from raw to quarter-baked (do you bake beef?); I was planning to put a > little more solitary work on them before exposing them, but Ralph and Robert > are right. The best use of this list is to get the ideas out early, and > bring them to completion together. > ... > > Lazy vs. Eager Processing > This is an issue that I've also been thinking about lately. Another (cute) name that occurred to me is "Just In Time Processing". However, this name could be slightly misleading because JIT usually implies that you start a process of known duration "just in time" for it to be finished when a dependent process is scheduled to start. How many software "processes" are so well quantified? Not many, unfortunately. Usually, "lazy" processing in software implies a low-priority background process, or one process waiting for another to finish some task (see below). > Intent > ------ > Create processing artifacts at the right time for the situation > > Motivation > ---------- > Eager processing creates artifacts as soon as possible, even if they're > not needed at the moment. Lazy processing only creates artifacts when > they're called for; in particular, a compound object may be created > piecemeal, and unused parts may never be created. > > Eager processing exploits parallelism to create artifacts ahead of need, so > they're instantly available when called for; on the other hand, it uses > cycles that may be wasted if the artifacts aren't in fact ever used. > > Lazy processing saves cycles by not creating more than is needed; in fact, > where the artifact is potentially infinite (e.g. the list of all primes), it > may be the only way to go. On the other hand, it could slow things down > when clients have to wait while an artifact is created. > Another use for lazy processing is to postpone slow or low-priority processing so that higher priority processing can be completed sooner. For example, system start-up times should be minimal, so that it is available for use as soon as possible. The system can be brought up to a "usable" state more quickly using lazy processing to postpone slow or low-priority processes. > Applicability > ------------- > When an object is going to be needed at some point, and will take > considerable time to access or create, consider a) whether the entire object > will likely be needed and b) whether it's possible and useful to create it > ahead of the need. c) Can parts of the object (process) be created (completed) later? > > Solution > -------- > {TBD, but should include the following:} > > Consider mixing the two: compute parts of an artifact ahead of time, others > only on demand. Or, compute parts now, and others "in the background" so that they will be ready when needed later. > > Consequences > ------------ > {TBD} Increase in complexity. Risk of having some processing "wait" for lazy evaluation to complete. > > Implementation > -------------- > {TBD; discuss techniques such as closures and continuations for lazy > processing, parallelism for eager processing} > Split the process into high- and low-priority sections. Do the high-priority sections immediately in a high-priority "task". Do the low-priority sections in a parallel, low-priority task or do them on demand in the high-priority task. If multitasking is used, then communication primitives (semaphores, messages, etc.) must be used to indicate if and when the lazy processes are finished. > Related patterns > ---------------- > Strong vs. Weak Methods: extra knowledge can avoid waste associated with > "overeager" processing, and delays caused by "too lazy" processing. > > Examples of use > --------------- > {Need real examples, references} > > Eager: traversing long list stored on persistent storage, chunked 100 > elements per "block". When passing 80th element, fork process/thread to > load next block. > > Lazy: random number generator provides list of numbers one at a time. > > Eager: parallel garbage collection: grab the junk as soon as it shows up. > > Lazy: partial garbage collection: only collect enough to satisfy the current > request. > Eager: Some system state transitions can take a long time to perform (e.g., constructing and presenting a complex UIF dialog, switching to a different processing "mode", etc.). If the next likely transitions can be predicted in advance, then eager processing can be used to "preprocess" some of these transitions (build the dialog but don't display it, initialize support "subsystems" for the new processing "mode"). If and when the state transition is actually made, the transition time will be reduced, since much of the work will have already been done. Combining Eager and Lazy Processing: System initialization ("bootup"). Users of a machine want it to boot as quickly as possible. The user interface should be presented as quickly as possible. Often, the user will have some simple steps to do at the beginning (such as typing in some data), which do not require the full machine. While the user is doing these steps, the machine can complete its initialization in the background (such as booting and testing hardware, establishing network connections, etc.). Coordination mechanisms are used to prevent the UIF from starting any action involving uninitialized subsystems. > > Don Dwiggins "Solvitur Ambulando" > Mark V Systems, Inc. > dwig@markv.com > Dean +-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-+ | Dean Wampler, Ph.D. email: dwampl@atl.com | | Advanced Technology Laboratories | | MS: 264 office: (206) 487-7871 | | 22100 Bothell Highway S.E. fax: (206) 486-5220 | | Bothell, WA 98041-3003 | |-----------------------------------------------------------------| | "I feel your pain...." =:O] | +-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-+ Date: Wed, 7 Dec 1994 00:14:21 +0001 (EST) From: Michael Trachtman Subject: Re: Where's the beef? Patterns to chew on (first in a series) To: dwig@markv.com Cc: patterns@cs.uiuc.edu On Tue, 6 Dec 1994 dwig@markv.com wrote: > Lazy processing saves cycles by not creating more than is needed; in fact, > where the artifact is potentially infinite (e.g. the list of all primes), it > may be the only way to go. On the other hand, it could slow things down > when clients have to wait while an artifact is created. > Cost 1: Lazy processing has the additional disadvantage, that you often have to add extra "flags" to track which parts of the "partially constructed" object have been constructed and which have not. Cost 2: In addition, it has the additional cost, that whenever you access part of a "lazily constructed" object, you first have to check whether the part you want has been constructed yet or not. These two considerations suggest Rules Of Thumb (ROT) that can help in deciding whether to use "lazy" or "eager" processing. ROT 1: If all or most of the parts of an object are eventually going to be accessed, then you may as well do an "eager" construction. In this way you save cost 1 and cost 2, without really incurring the cost of constructing things that you will never use. ROT 2: If some part of an object will (typically, on average) be accessed many times, that that part of the object should be constructed eagerly. This will save cost 1 and cost 2 for that part of the object. On average, the cost of the eager construction will not be wasted. How often constitutes: "Typically", or "on average" and "many times", depends on the ratio of the cost of computing that part of the object with Cost1 and Cost 2 above. Roughly let: avg = avg_times( object_part_will_be_accessed) // This is the avg number of times that // this part of the object will be accessed // during its life. prob = probability that the object part will be accessed. construction_cost = the cost of constructing that part of the object. // This cost is also incurred if using the lazy // approach, the object is ultimately accessed, // and thereby constructed. total_lazy_cost = prob * construction_cost + avg * cost2 + cost1. total_eager_cost = construction_cost. which gives us: cost_difference = total_eager_cost - total_lazy_cost = (1 - prob) construction_cost - avg * cost2 - cost1. If cost_difference < 0, then use the eager approach, otherwise use the lazy approach. Note 1: cost1 is only incurred once per object. Note 2: the values of these "costs" is not only "runtime". It includes a combination of: "runtime", "programmer time", and "memory cost". How to evaluate these on a uniform scale is up to the judgement of the person applying this heuristic. From: "Carlini, Giuliano" To: "'patterns@cs.uiuc.edu.'" Subject: Where's the beef? Patterns to chew on (first in a series) Date: Wed, 07 Dec 94 14:17:00 PST >> Lazy processing saves cycles by not creating more than is needed; in fact, >> where the artifact is potentially infinite (e.g. the list of all primes), it >> may be the only way to go. On the other hand, it could slow things down >> when clients have to wait while an artifact is created. >> >Cost 1: Lazy processing has the additional disadvantage, that you often have >to add extra "flags" to track which parts of the "partially constructed" >object have been constructed and which have not. > >Cost 2: In addition, it has the additional cost, that whenever you access part >of a "lazily constructed" object, you first have to check whether the >part you want has been constructed yet or not. Both of these costs can be minimized through the use of "Futures". I've read several papers on this from various conferences, but don't have any references handy that I can cite. I believe that several have apeared in past OOPSLA proceedings. I believe that futures may be similar to "proxies", but am not sure (while I've skimmed it, I have yet to read the GOF book). A future is an object which "stands in" for another which may not exist yet. It provides the same interface as the object it represents, and so may be passed around just as if it were the real thing. However, if one of its methods is called, it will block the executing thread until the real object becomes available. From then on, all methods are just passed on to the real object. To also nicely accomodates lazy vs. eager processing, and minimizing delays. When an "eager" future is created, it immediately starts the process of constructing the real object. This can be done in a new thread, so that the "future" object constructor can return almost immediately. This can reduce the time required to bring up an interactive system so that it is available to the user. When a lazy future is created, it does nothing about creating the real object. Only when one of it's methods is called does it do so. This can cause a delay for interactive applications, especially if constructing the real object requires a long time; for example, to access the network. A hybrid "sluggish" future might be useful in these cases. When constructed, it will immediately start the creation of the "real" object. Any "futures" in the real object will be constructed lazely. When a method of the sluggish future is called, it will tell the real object to start the construction of any of it's future components. Thus, the futures will always try to stay just a little ahead of their clients. This may minimize the both the creation of objects that will be never used, and the delays waiting for needed objects to be created. g Date: Wed, 07 Dec 1994 17:46:38 -0800 To: , From: pope@qds.com (Alan L. Pope) Subject: Futures References At 02:17 PM 12/7/94 PST, Carlini, Giuliano wrote: > >Both of these costs can be minimized through the use of "Futures". I've read >several >papers on this from various conferences, but don't have any references handy >that >I can cite. I believe that several have apeared in past OOPSLA proceedings. Here are a couple of references that I have (the first of these lists is from a note from Bruce Delagi--Sun Microsystems--to myself): > From my perspective, the foundation work for futures is found in > Friedman and Wise..."An Indeterminate Constructor for Applicative > Programming" 7th Annual Symposium on Principals of Programming > Languages 1980, pages 245-250...which I think points back even further > to some notes by McCarthy a decade or more previously. > > And then there is the ever popular Lieberman..."Thinking about lots of > things without getting confused" AI Memo 626, MIT, May 1981....actually > a good tutorial as I remember it. > > A useful introduction to all of this and how it can be used can be > gained from the discussion about "streams" in Abelson and Sussman with > Sussman ...Structure and Interpretation of Computer Programs, section > 3.4, pages 242-292 in the 1985 edition. > > [The elements of a "stream" as used above are generally considered as > computed on demand but they could also be constructed eagerly and so > can be thought of as data structures which contain promises for > computation...whether eagerly or lazily evaluated.] You can get papers from BBN on their implementation of Cronus: BBN (Cronus) Cronus is an object-oriented distributed computing environment that has been under development for several years at BBN. It uses a proprietary ORB-like object architecture. A proprietary RPC is used for communication. The RPC uses futures for asynchronous invocations. C and CLOS language interfaces are available. Alan L. Pope Quantitative Data Systems, Inc. 9500 Toledo Way Irvine, Ca 92718