| home / programming / optimize / speedup / chap10 / 2 |   [next] |
|
|
|
[The following is a continuation of our series of excerpts from Chapter 10 of the New Riders title, Speed Up Your Site: Web Site Optimization.]
Okay, you've switched to a better algorithm and revamped your data structure. You've refactored your code and minimized DOM interaction, but speed is still an issue. It is time to tune your code by tweaking loops and expressions to speed up hot spots. In his classic book, Writing Efficient Programs (Prentice Hall, 1982), Jon Bentley revealed 27 optimization guidelines for writing efficient programs. These code-tuning rules are actually low-level refactorings that fall into five categories: space for time and vice versa, loops, logic, expressions, and procedures. In this section, I touch on some highlights.
Many of the optimization techniques you can read about in Bentley's book and elsewhere trade space (more code) for time (more speed). You can add more code to your scripts to achieve higher speed by "defactoring" hot spots to run faster. By augmenting objects to store additional data or making it more easily accessible, you can reduce the time required for common operations.
In JavaScript, however, any additional speed should be balanced against any additional program size. Optimize hot spots, not your entire program. You can compensate for this tradeoff by packing and compressing your scripts.
Douglas Bagnall employed data structure augmentation in the miniscule 5K chess game that he created for the 2002 5K contest (http://www.the5k.org/). Bagnall used augmented data structures and binary arithmetic to make his game fast and small. The board consists of a 120-element array, containing numbers representing either pieces, empty squares, or "off-the-board" squares. The off-the-board squares speed up the testing of the sides—preventing bishops, etc., from wrapping from one edge to the other while they're moving, without expensive positional tests.
Each element in his 120-item linear array contains a single number that represents the status of each square. So instead of this:
board=[16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,2,3,4,5,6,2,3,4,5,16,....]He did this:
bstring="ggggggggggggggggggggg23456432gg11111111gg0000 ... g";
for (z=0;z<120;z++){
board[z]=parseInt(bstring.charAt(z),35);
}This base-35 value represents the squares on the board (parseInt
using a radix of 35). As alpha "g" corresponds to 16 (the 5th
bit; that is, bit 4), Bagnall says he actually could have used base-17
instead of 35. Perhaps this will leave room for future enhancements.
Each position on the board is encoded like this:
bit 4 (16): 0 = on board, 1 = off board.
bit 3 (8): 0 = white, 1 = black.
bits 0-2(7): 0 = empty, non-zero = the piece type:
1 - pawn
2 - rook
3 - knight
4 - bishop
5 - queen
6 - kingSo to test the color of a piece, movingPiece, you'd use
the following:
ourCol=movingPiece & 8; // what color is it? 8=black, 0=white
movingPiece &= 7; // now we have the color info, dump it.
if(movingPiece > 1){ // If it is not a pawn.Bagnall also checks that the piece exists (because the preceding code
will return white for an empty square), so he checks that movingPiece
is non-empty. To see his code and the game in action, visit the following
sites:
http://halo.gen.nz/chess/main-branch/ (the actual code)
| home / programming / optimize / speedup / chap10 / 2 | [next] |
From Speed Up Your Site: Web Site Optimization, Chapter 10.
Copyright 2003. Reproduced by permission of New Riders.
Legal Notices, Licensing, Reprints, Permissions, Privacy Policy.
Advertise | Newsletters | Shopping | E-mail Offers | Freelance Jobs 
Created: January 15, 2003
Revised: January 15, 2003
URL: http://webreference.com/programming/optimize/speedup/chap10/2/
