From: TedCashel@atlmug.org (Ted Cashel)<\/p>\n
Date: Wed Mar 31, 1999 11:10:17 PM US\/Eastern<\/p>\n
To: jeb@5forks.com<\/p>\n
Cc: ndcashel@yahoo.com<\/p>\n
Subject: Fwd: Neat story<\/p>\n
Reply-To: Ted_Cashin@atlmug.org (Ted Cashin)<\/p>\n
Attachments: There is 1 attachment<\/p>\n
(Embedded image moved to file: pic09930.jpg)<\/p>\n
jcashel@harland.net didn’t work so I am trying you here<\/p>\n
I got this from a recent Tidbits and it reminded me of your prime number program. This guy has a more complex program (albeit nearly as pointless) but has the background to have tried it on a proud line of mainframes and modern PC’s.<\/p>\n
Power Macintosh G3: The Cannonball Express<\/p>\n
——————————————<\/p>\n
by Rick Holzgrafe <\/p>\n
The Cannonball Express was the fabled train that was so fast it<\/p>\n
took three men to say “Here she comes,” “Here she is,” and “There<\/p>\n
she goes.” Computers are fast too, although unlike trains, most<\/p>\n
aren’t self-propelled. What makes a computer fast, and how much<\/p>\n
effect does software design have? How much faster are today’s<\/p>\n
computers than yesterday’s? Recently I revisited some of these<\/p>\n
questions, beginning with a trip down memory lane.<\/p>\n
\n**Back in the Stone Age** — Twenty years ago, I was teaching<\/p>\n
myself programming and had access to a DEC PDP-11\/60 minicomputer<\/p>\n
on evenings and weekends. This beast was bigger than a washing<\/p>\n
machine, and during workdays I shared it with two dozen other<\/p>\n
technicians and engineers. I found a word puzzle in a magazine and<\/p>\n
thought it would be fun to program the PDP to solve it. The puzzle<\/p>\n
was as follows.<\/p>\n
Given a phrase and a sheet of graph paper, write the phrase on the<\/p>\n
graph paper according to these rules:<\/p>\n
1. Write one letter per square on the graph paper, like filling in<\/p>\n
a crossword puzzle. Ignore case and anything that’s not one of the<\/p>\n
26 letters of the alphabet. The phrase “N. 1st Street” is thus<\/p>\n
identical to “NSTSTREET”.<\/p>\n
2. Put the first letter of the phrase in any square you like.<\/p>\n
3. After writing any letter, put the next letter of the phrase in<\/p>\n
any adjacent square. Here, “adjacent” means any of the eight<\/p>\n
neighboring squares, up, down, left, right, or diagonally. You may<\/p>\n
reuse a square if it is adjacent and already holds the letter you<\/p>\n
need; otherwise you must use a blank square. You can’t use the<\/p>\n
same square twice in a row – no “hopping in place” for double<\/p>\n
letters.<\/p>\n
The goal is to write the phrase inside a rectangle of the smallest<\/p>\n
possible area. (A subtle point: you are not trying to write in a<\/p>\n
minimal number of squares.) To score your solution, draw the<\/p>\n
smallest enclosing rectangle you can and take its area. The<\/p>\n
rectangle may enclose some blank squares; count them, too.<\/p>\n
Got it? Tongue-twisters are the most fun because they have lots of<\/p>\n
opportunities to reuse whole snaky strings of squares. The 37<\/p>\n
letters in “Peter Piper picked a peck of pickled peppers” can be<\/p>\n
packed into a 3 by 5 rectangle, like this (view this in a<\/p>\n
monospaced font):<\/p>\n
KCPER<\/p>\n LEDAS<\/code><\/p>\n In those days I knew computers were “fast” but had no idea how<\/p>\n fast. The answer turned out to be “not very.” I wrote a program to<\/p>\n solve these puzzles and called it Piper after the tongue-twister.<\/p>\n I set Piper running on a medium-length phrase on a Friday evening,<\/p>\n and came back on Monday to find it still running. It had found<\/p>\n several less-than-best solutions but hadn’t finished. Way too slow<\/p>\n – I found a better solution myself on paper in about half an hour.<\/p>\n Why did it take so long? Piper was a “brute force” program. It<\/p>\n tried every possible solution to the problem, one after another.<\/p>\n The trouble is that there are too many possible solutions. Exactly<\/p>\n how many depends on the phrase, but for any non-trivial phrase the<\/p>\n number is astronomical. I realized for the first time that “fast”<\/p>\n sometimes isn’t “fast enough.” This point may be obvious today,<\/p>\n when we all use computers and are weary of waiting for them. But<\/p>\n in 1979, that PDP-11 was only the second computer I had ever seen!<\/p>\n **What Part of Fast Don’t You Understand?** I saw that I would<\/p>\n have to make Piper faster. There are two basic ways to speed up a<\/p>\n program. Plan A is to find a better way of solving the problem,<\/p>\n but after twenty years I still haven’t thought of a better<\/p>\n solution. That leaves plan B, the classic efficiency expert’s<\/p>\n solution: eliminate unnecessary steps. For example, Piper created<\/p>\n every possible solution, then calculated the area of each. It<\/p>\n built each solution one letter at a time, so instead of taking the<\/p>\n area only for completed solutions, I changed Piper to check the<\/p>\n area after placing each letter. If placing a letter made the<\/p>\n solution-in-progress take up more space than the smallest complete<\/p>\n solution found so far, Piper could skip the rest of that solution<\/p>\n (and all other solutions that started the same way) and move right<\/p>\n on to the next one. This eliminated a huge amount of work and<\/p>\n greatly improved Piper’s speed. Finding clever ways to track the<\/p>\n area of a growing solution helped too, because it was faster than<\/p>\n calculating the area from scratch after each letter. I also found<\/p>\n a way to calculate a minimum size for the final solution quickly:<\/p>\n I couldn’t guarantee that the best solution would be that small,<\/p>\n but I could guarantee that it wouldn’t be smaller. If Piper got<\/p>\n lucky and found a solution as small as that calculated minimum, it<\/p>\n could stop immediately. Otherwise it would continue on after<\/p>\n finding the best solution, vainly seeking a still better one.<\/p>\n Eventually Piper became clever enough to finish that original<\/p>\n phrase in a reasonably short period of time. But the holy grail<\/p>\n continued to elude me: I wanted a solution for “How much wood<\/p>\n would a woodchuck chuck if a woodchuck could chuck wood?” That PDP<\/p>\n (and, perhaps, my cleverness) were not up to the task. I had run<\/p>\n out of ideas for speeding up Piper, and runs still took longer<\/p>\n than a weekend. But if I couldn’t improve Piper, I could at least<\/p>\n hope to run it on a faster computer.<\/p>\n **Big Iron** — People tend to think of processor speed as the<\/p>\n speed of a computer, but many factors affect overall performance.<\/p>\n Virtual memory lets you work on bigger data sets or on more<\/p>\n problems at a time, but it’s slow, so adding more physical RAM<\/p>\n helps by reducing your reliance on virtual memory. Faster disks<\/p>\n and I\/O buses load and save data more quickly. RAM disks and disk<\/p>\n caching replace slow disk operations with lightning-quick RAM<\/p>\n access. Instruction and data caches in special super-fast RAM<\/p>\n offer big improvements for some programs. Well-written operating<\/p>\n systems and toolboxes can outrun poorly written ones.<\/p>\n But in the end, little of this matters to Piper. Piper has always<\/p>\n used only a small amount of data, doesn’t read or write the disk<\/p>\n after it gets going, and does little I\/O of any kind. With its<\/p>\n small code and data set Piper can take good advantage of data and<\/p>\n instruction caching, but what it mostly needs is “faster hamsters”<\/p>\n – a faster processor to make the wheels turn more quickly.<\/p>\n As the years rolled on, I ran versions of Piper on my first Macs,<\/p>\n but in the middle 1980’s I worked for Apple Computer, and had<\/p>\n access to a programmer’s dream: Apple’s $15 million Cray Y-MP<\/p>\n supercomputer, one of only two dozen in the world and arguably the<\/p>\n fastest computer in existence at the time. I figured the Cray<\/p>\n would make short work of Piper. But the Cray was not well suited<\/p>\n to the problem. It could barrel through parallel-processing<\/p>\n floating-point matrix calculations like the Cannonball Express,<\/p>\n but Piper was a highly linear, non-mathematical problem. Piper<\/p>\n used only one of the Cray’s four processors and didn’t do the kind<\/p>\n of operations at which the Cray excelled. Piper wasn’t a fair test<\/p>\n of the Cray’s power, but the Cray was still the fastest machine<\/p>\n I’d ever used. The Cray succeeded where all previous machines<\/p>\n (that PDP, my Mac Plus, my Mac II) had failed. It solved<\/p>\n “woodchuck” in less than a day, taking only about 20 hours to<\/p>\n finish its run. I was awestruck – 20 hours?! I’d no idea that<\/p>\n “woodchuck” was _that_ big a problem!<\/p>\n **Young Whippersnappers** — I set Piper aside for many years, but<\/p>\n recently I began to wonder how a modern desktop box compares to<\/p>\n those old minicomputers and mainframes. I rewrote Piper from<\/p>\n memory and ran it on my new 400 MHz ice-blue Power Macintosh G3<\/p>\n with “woodchuck.” The output is below. Piper first reprints the<\/p>\n phrase, then prints solutions and elapsed times as it finds them.<\/p>\n Each solution is the best found so far, culminating in the best of<\/p>\n all. The times are in seconds from the beginning of the run; the<\/p>\n final time is the total run time. (Unfortunately, the best<\/p>\n solution for “woodchuck” is larger than Piper’s calculated<\/p>\n minimum, so Piper continued to run for a bit after finding the<\/p>\n best solution.)<\/p>\n Here are the results. Some intermediate solutions have been left<\/p>\n out for brevity, but you can see Piper finding ever smaller<\/p>\n solutions. In the end, the 57 letters in “woodchuck” are packed<\/p>\n into a 4 by 4 rectangle. Have a look at Piper’s total run time,<\/p>\n and the time needed to find its best solution:<\/p>\n How much wood would a woodchuck chuck if a woodchuck could chuck wood?<\/p>\n 0 seconds:<\/p>\n HDOAIUCOHWUHOD<\/p>\n UCOWFKHDOMCWOW<\/p>\n K WO<\/code><\/p>\n 1 seconds:<\/p>\n UCKOHWUHOD<\/p>\n OHDWOMCWOW<\/code><\/p>\n 2 seconds:<\/p>\n HWUHODKUK<\/p>\n OMCWOWAFI<\/code><\/p>\n 7 seconds:<\/p>\n OMCWOD<\/p>\n IKAUCW<\/p>\n FLDHK<\/code><\/p>\n 9 seconds:<\/p>\n OMCW<\/p>\n LUOK<\/p>\n HDOI<\/p>\n CWAF<\/code><\/p>\n 65 seconds:<\/p>\n OUC<\/p>\n IKH<\/p>\n FWC<\/p>\n ADO<\/p>\n LUO<\/code><\/p>\n 67 seconds:<\/p>\n OOCH<\/p>\n UDWK<\/p>\n LAFI<\/code><\/p>\n Total run time: 107 seconds<\/p>\n There you have it: a shade over a minute to find the best<\/p>\n solution, under two minutes to finish its run. Two minutes! So<\/p>\n much for the big iron of the 1980’s. My new G3 Mac finished<\/p>\n “woodchuck” over 600 times faster (and 5,000 times cheaper) than<\/p>\n that 15 megabuck Cray. (For a more realistic comparison, see this<\/p>\n description of UCLA’s Project Appleseed.)<\/p>\n www.apple.com\/education\/hed\/aua0101\/appleseed\/<\/a><\/p>\n If you want to check Piper’s speed on your Mac, I’ve placed the<\/p>\n code in the public domain; it’s a 40K package.<\/p>\n ftp:\/\/ftp.tidbits.com\/pub\/tidbits\/misc\/piper.hqx<\/p>\n **The Future** — What’s yet to come? 400 MHz already looks a<\/p>\n little pokey. It’s the best Apple offers today, but I’ve seen<\/p>\n claims of 550 MHz or so from third party accelerators and over-<\/p>\n clocking tricks. People are predicting 1 GHz (1,000 MHz) chips for<\/p>\n the near future. Buses are getting faster, and caches hold more<\/p>\n data in less space and are moving onto the processor chip for<\/p>\n still more speed. (Small is fast. Did you know that the speed of<\/p>\n light is a serious limiting factor in modern computer design? The<\/p>\n closer together the components are, the faster they can signal<\/p>\n each other.)<\/p>\n And like the old Cray, multi-processor desktop systems are<\/p>\n starting to appear. They gang up on a problem by having separate<\/p>\n processors work on different parts of the problem simultaneously.<\/p>\n Although I didn’t try to use the Cray’s extra processors, I’ve<\/p>\n done a little thinking lately. Piper doesn’t have to be completely<\/p>\n linear. On an eight-processor system, I bet I could come close to<\/p>\n making Piper run in one-eighth of the time of a single processor.<\/p>\n Are you ready?<\/p>\n Here she comes –<\/p>\n Here she is –<\/p>\n There she GOES!<\/p>\n","protected":false},"excerpt":{"rendered":" From: TedCashel@atlmug.org (Ted Cashel) Date: Wed Mar 31, 1999 11:10:17 PM US\/Eastern To: jeb@5forks.com Cc: ndcashel@yahoo.com Subject: Fwd: Neat story Reply-To: Ted_Cashin@atlmug.org (Ted Cashin) Attachments: There is 1 attachment (Embedded image moved to file: pic09930.jpg) jcashel@harland.net didn’t work so I … Continue reading OFIPT<\/p>\n ULD ADLU<\/p>\n DLIFADLU<\/p>\n ULCHC<\/p>\n HWUHOW<\/p>\n HWUH<\/p>\n HWM<\/p>\n HWMU<\/p>\n