OPTIMIZATION
-----
7-Feb-95 message:
They put "update events" in the queue. In a long-running process,
you'll periodically query the queue to see if other more important
stuff has come in. There's a bit about regions. I think you get a
region to update, and you can start updating it, and then mark part
of the region as updated. It's probably not 100% straightforward,
as you have to put some intelligence in as to which events override
the work you're already doing.
-----
8-Feb-95 message:
Another one is the subject of optimization. I think there's a broad
set of rules that people can follow to help them optimize. Example:
"choose the right level for the optimization" - sometimes people
mutilate their code to make bubblesort work rather than just calling
qsort, or they try to optimize design and code when the easy thing
to do is throw hardware at it. There may be a coherent approach
that can be followed to systematically optimize.
-----
17-Mar-95 message:
A Pattern Language for Performance Improvement
+ Choose the right level for changes
There are many levels at which performance can be addressed: overall
system, design, code, hardware. Choose the level that is likely to
give the most bang for the buck. For example: it might be cheaper
to just upgrade the processor rather than try to squeeze 15% more
performance out of already-tuned assembly code.
+ Assess the system before and after any changes. Be wary of regressions in some areas.
It is very easy to make changes and find they actually have no effect other than to make the system more brittle. You need a defined test suite, run during the tuning process. Note that this provides an implicit model of system use, and the generality/appropriateness/robustness of the model should be assessed.
+ Multiple levels have multiplicative effects.
Suppose it is easy to code-tune and get a doubling in speed, but
more would be difficult; similarly it may be easy to double hardware
speed but not easy to go faster. But combining both would provide
a potential speedup of 4 times.
+ Profilers can measure where systems spend their time.
There are "counting" profilers that tell how many times a particular
routine or line of code is executed, and there are "timing" profilers
that tell how much time was spent in a particular routine. Note
that both sets of numbers are useful, and that there is no necessary
relationship between them.
+ Use gross characterizations of performance at first. - back of the envelope
Are the algorithms linear, quadratic, n log n, or what? Do
they break down at some volume? How quickly can real data
be processed?
+ End-to-end processing
What happens to a bit of data all the way through the system
(e.g., from when it is typed till when the editor displays
it). How many "touches" involved in processing it?
+ Focus on critical paths: typical and special cases
Some functions are central to the processing - an editor
that can't keep up feels sluggish, and so normal typing
may be a critical case. Are there ways to speed up the
critical path by making less critical things pay for it?
+ Design changes: changing the order of magnitude of algorithms
Example: use quicksort (n log n) instead of insertion sort (n^2).
+ Code changes - lots of them
Compiler switches
Inlining
Common subexpressions
Hidden calls (constructors, destructors, etc)
+ Code: expensive routines
An expensive routine can be made cheaper itself, or routines
it calls can be made cheaper, or you can arrange to call
this routine less. (Example: sine routine; lazy loading;
etc.)
+ Code: I/O vs. CPU-bound vs. operator-bound
What is code usually waiting for?
+ Assembly coding of critical routines
Costs
+ Firmware/Hardware changes
Throwing memory at it, faster processor, microcode, etc.
The goal would be a set of these, that would guide you through the
process of performance tuning. You should feel at each point that
you have direction to go.
Feel free to throw more at this.
I've got a couple articles at home on this, a book by Connie Smith,
and the book "Writing Efficient Programs" by Jon Bentley. Other
suggestions welcome.
==================================================
PATTERNS FOR PORTING
Date: Fri, 1 Sep 95 13:50:23 EDT
From: wakew (To: steve)
To: steve
Subject: Patterns for Portability
Hey -
Someone asked for "Patterns for Portability". I was thinking of
turning it around and making it "Patterns for Porting", a little
process model of how to go about porting source code.
Vague outline:
+ Deciding to port
+ Make a "golden" reference version - used for comparison against "new" versions.
+ Make a master test suite.
+ Work from the original system first.
- Turn on all warnings. FIX THE PROBLEMS.
- Try it with as many compilers as possible. Use other tools if
available: heap scramblers, garbage collectors, Purify, lint, etc.
- Don't just build - try against the test suite.
+ Identify porting differences: system call structure, integer
sizes, endian-ness, filenames, what else? Try to resolve them on
the original system. (For example, make a system-independent data
format, or make sure that the file contains an indication of what
format it expects.) Probably this has a checklist.
+ Add portability layers eg. for system calls
+ Move to the target system. Compile & build in the most similar
way possible to the original, and test (eg no optimization, all
assertions "on", etc.) Gradually move to a normal environment.
+ Establish the "build" environment, eg., multiple makefiles, config info, etc.
I don't know what else. This doesn't need to become too big.
The ideal for these patterns to form a "pattern language" is that
a pattern fixes something big but has a few side effects that
following patterns address.
On the other hand, this might be something that would be better as
a "recipe" book, and it's silly to make a pattern.
--bill
==================================================
PLOP 95 - NOTES FROM EVENT LOOP
6-Feb-95 message from Doug:
I really like your two ideas. Also, I'm still interested in the idea of
handling background tasks. Think about displaying a 10x10 grid on a 2x2
screen (for example), where each grid square takes 30 seconds to draw. You
want to draw part of a grid square, check for new events, draw a little
more, etc. However, in addition, you want to see if they've scrolled part
of the grid. They may have scrolled off part of what you had on the queue
to draw: you need to remove the need to draw that, and add the new portions.
You may need to bit blit part of a grid square and then change the queue so
that the instructions to draw reflect that the square is being drawn in a
new location.
7-Feb-95 message from Doug:
Of course, my region thing is just an example. The actual pattern would be
about doing any tasks in the background, like your database stuff, or my
relineation while users are not typing. Actually, that's a really good
example. I want to relineate line 100, and then later the whole paragraph
scrolls off the page, so I don't have to worry about it like I did before.
Hmm..I need to think some more about this.
8-Feb-95 message:
Doug had an idea of an event loop kind of thing - what to do when you have slow operations but want to provide interaction.
Date: Thu, 25 May 95 11:36:21 EDT
From: wakew (To: dwake@uhunix.uhcc.Hawaii.Edu (B. Douglas Wake))
To: dwake@uhunix.uhcc.Hawaii.Edu (B. Douglas Wake)
Subject: Re: Quick look
Pattern 4.5: Interruptible commands AKA "That changes everything!"
I just have notes on this, or the beginnings of ideas.
It will sometimes happen that a new incoming event causes a "that
changes everything!" effect. For example, a delete could occur
while inserting text.
There's a special case where we can deal with this:
Suppose a command execution has two parts: a setup and an execution phase.
I guess the setup phase must be non-destructive.
You could check at the end of the setup phase, and see if
any "compatible" events are pending. If so, abort the
command and return to the point where you merge events into
commands. Keep the original command (as it wasn't executed)
and merge the new event into it.
I'm not sure when this applies:
+ If command execution is non-trivial (so we want to avoid it)
+ But command setup must be non-trivial too (otherwise we
would have merged the event already. If the setup takes
practically no time, there won't be time for an event to
come in.)
+ Events that undo work done so far are "common" (don't know how common)
My tendency is to leave this pattern out. Do you have a sense of
what else could go into it that might make it more important?
--bill
-----------------
Date: Mon, 15 May 1995 09:18:21 -1000
X-Sender: dwake@pop-server.Hawaii.Edu
Mime-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
To: Bill Wake <wakew@jingluo.cs.vt.edu>
From: dwake@uhunix.uhcc.Hawaii.Edu (B. Douglas Wake)
Subject: Re: #4 command merging
X-Mailer: <windows Eudora Version 1.4.2b16>
>Your idea of a tick is good, that's sort of what I had in mind. The crucial
>thing is that there is a difference between queueing up the work and doing
the
>work.
A tick is the same thing as an idle, I guess. It's just that you're not
necessarily idle.
>I made up that it doesn't matter if "step 2" takes a bit long in general, if
>you can just get that "extra work" done. So "s" then "ser" is ok to take the
>full time to find s. Since these commands are sort of "cumulative", the
work to
>find s is not wasted.
Not only do I agree with this, but I think it's outside the scope. We don't
care how they handle it. But we can outline ways to handle it. But the
important thing is not whether you start handling "ser" right away but what
you do when it's "destructive," as in changing "ser" to "set."
I need to find that letter I sent you a long time ago. I had this thing
about overlapping rectangles. It's the same deal whether it's rectangles or
incremental search or whatever.
Let's look at all possible rectangle patterns:
- you can get a new, disjunct rectangle (addition)
- you can get a rectangle that combines with yours (accumulation)
- you can get a new rectangle that eliminates the one you're working on
(replacement)
Anything else?
In our example, say we're searching for records containing "bet"
addition: now we should search for records containing "bet" and "Vegas"
accumulation: now we should search for records containing "better"
replacement: instead of searching for "bet," search for "cards"
>The other thing is - I've been ignoring the problem of redraw and just
focusing
>on "doing the work".
I hope this helps. Looking at how your redraw can change can make a difference.
But it's each tickable function's job to maintain its queue or "rectangle list."
>This is sort of getting at the notion of the output queue. In "my" situation,
>typing the letter executes the command that affects the model (inserts it in
>text). But output isn't tied to commands, output is almost a separate thing
>just trying to keep up. So if new letter comes in or a delete, and it can be
>consolidated, then the command executes "atomically" and the output catches
up
>after the whole thing.
Yes, this is what we really need to figure out. So it's easy for command to
execute quickly, but output needs to figure out how to combine the rectangles.
>Can you point me to a good intro to windows progr. that discusses this? I've
>probably got enough Mac stuff, and I'm sure I can find a decent descr. of
what
>X does.
If you want to understand Windows programming, you need to look at Charles
Petzold's book. I don't remember what it's called, Inside Windows or
something. But the first couple of chapters will tell you plenty. It's
pretty standard, I think.
Of course, I don't use that paradigm anymore. I use objects that get their
members called in any order. You know, ::draw, ::keypressed, etc. It's
still happening that way, but it's invisible to me.
Doug
Categories