I sometimes feel bad that I'm not more of an "algorythms developer", that I don't read all(any) research papers, that I don't remember what RedBlack Trees are, that other than minimal attention to using decent basic structures and reasonable bigO operaions (e.g hashes, don't pop of front of array in loop) when I sit down and code I invariably brute force it.
OTOH, I encounter the "computers are fast" phenomenon 9 out of ten times.
I'm on the other side of your situation. These days, nine out of ten times I'm looking at papers, algorithms, lots of paper with big-O and cache nitpicking, brainstorming with others trying to make those 20 Gbps turn to 60..
Speed is a direct product of simplicity, and for me simple is elegant. I also think speed is important enough for me to feel strongly about cutting down a "feature" or two, to just make the damned thing not take all night to solve your sudoku..
Well I think it's a combination of two things. Most days when I'm writing a web app or some other high level program I kind of chuck data about without thinking about it.
When I put on my kernel dev hat or when I was working on SQL Server I spent all day making sure other me could throw data around haphazardly and not get stuck on a course-grained kernel lock or only hit 1/8 of the pipelines.
Sometimes it's just too much to handle all at once, even if you know what you're doing in both domains.
I'm not sure if you're being sarcastic or not, but I'm on the same page. I try to focus on clarity and elegance in my code, and only worry about speed if it turns out to be slow.
But I sure as heck grumble when my computer is slow. "You've got, like, 800 hojillion cycles a second!" I say to it. "How hard is opening a program?!"
I/O is one of my biggest daily pains. Spend some time in Process Explorer on Windows and you can see just how much disk-based I/O the average app is doing. Anti-virus software makes the bad problem worse. It's just like pouring sugar in a gastank. Why isn't more software designed to take advantage, where appropriate, of large amounts of RAM?
Sometimes I wonder if the OS can put very heavily used files from the FS into RAM. Some software just sucks and keeps pulling the same files over and over...
... and the plus side is, if an application needs the RAM, no harm done, just dump the file from RAM and read it from disk.
Or Unix's mmap, which predates Vista by a couple decades. (It was designed around the time of 4.2BSD, i.e., 1983* .) I'd be shocked if Windows hasn't had a similar mechanism for years, as well.
* _The Design and Implementation of the 4.4BSD Operating System_, McKusick et al., p. 29-30.
mmap is not SuperFetch; and memory mapping has been in NT since it started.
What SuperFetch does is collect statistics about files hit by processes when they start up, so it can proactively cache bits of those files, to the point that it can cache files read by processes before those processes are ever started, assuming they are either commonly started or started on a schedule.
That's very weird. I can launch VS 2010 in < 3 seconds cold on my system. Maybe its a VM thing? VS might always think its launching for the very first time ever on that machine, so it has a lot of heavy duty, one time only things, but on a VM, it does this every time you boot the VM?
A long time ago I was working on a data conversion project that involved taking what was essentially a 10 dimensional data set and reordering it. The easiest way to achieve this was to load everything into a ten dimensional array and read it out in another order, but I was sure this would take too long. So I spent some time trying to get a sparse array implementation working until I finally sat down and worked out that the entire 10 dimension data structure would require 63 megabytes of RAM (not giga, this was a long time ago.) The Sparc server in the next room had 64 megs of RAM. It was a simple algorithm with quick results and I moved on to the next problem. I think that was the last time I really really cared about performance. I'd spent the previous 15 years getting closer and closer to the hardware, caring about every register and every byte. I've spent the 15 years since then on the slow slide to letting the computer worry about everything. I currently live in Python land and love every minute of it. I hear that string concatenation is slow but honestly, it's never been an issue for me. Computers really are fast.
Another: I solved the 8-queens problem for a magazine contest using a BASIC program (!)
Instead of modelling the board with an 8X8 array, I used the digits 1-8 representing the height of the queen (row #), and the 8 digits in a string as the heights for each column. I permuted the digits - n! time to execute which was never going to finish.
So, prune! as it swapped digits left to right in a Grey-code-like sequence, test the digits to the left for diagonals (|row#A - row#B| == |A-B|) and don't bother to recurse if its already failing.
Every few minutes - out popped a solution, and it finished in under 25 minutes.
Nowadays, that would take imperceptible time to execute.
Something I like thinking about: Your computer can (probably) perform a few dozen arithmetic operations or a few stores/reads in the time light leaving your monitor takes to reach your eye balls.
Around '94 I used a close to the top of the range (at least in CPU power) DEC Alpha workstation - which I used for running Lisp programs.
One of the other research teams in the department were working on some kind of custom chip for some specialized application and they wanted to show how much better it was than even the best commodity CPU so they gave me a chunk of completely unoptimized vanilla C to compile and run as a benchmark.
Turns out the Alpha was way faster than their chip - which I don't think they were too happy about!
Light travels about 1 foot/nanosecond, so the travel time from monitor to eyeball is 1 or 2 nanoseconds, which might be 2 or 3 clock cycles. So I think at most 3 operations per CPU.
There's 2 to 3 feet between me and my screen, my cpu has 2 cores, and modern CPUs can perform many simple arithmetic operations per clock cycle, per core. Not to mention what's happening in my GPU.
Let's take a concrete example. A Core-i7 980X Extreme Edition, the latest and greatest from Intel, can execute a maximum of four instructions in a clock cycle. (The numbers on actual code are probably a little over 1 instruction per cycle, which is really pretty good.) It runs at 3.33 GHz and has 6 cores. That's a theoretical maximum of about 43.336 = 79 instructions per nanosecond, on all cores combined. Assuming I didn't make some dumb arithmetic mistake.
Of course, in real code you'll be lucky to get anywhere near that.
Regarding double precision calculations (I can't compare random instructions) at the time OP mentions the PC FPU made something of the order of KFLOPS. Even assuming 100 KFLOPS (it was less), one current graphical card can be up to 5 million times faster than the PC of that time in some scientific calculations, that is, the gamer of today has under his desk the computing power of 5 million first PC computers.
i7 can do 2 double precision adds per clock per core, that would give 36 GFLOPS on 6 cores (assuming 3 GHz clock), and at the same time ATI Radeon 5870 GPU can do 500 GFLOPS in double precision, that's 500 floating point calculations in one nanosecond.
To cross the 0.5 meter distance the light takes around 1.6 ns, which means that during that time the CPU is able to do almost 60 FPU additions and the GPU around 800 FPU additions. Impressive.
CPUs are fast but the ratio of latency of random access vs. maximum bandwidth is getting worse.
In nanoseconds, approximately:
10^7 Disk seek
10^4 2KB over 1Gbps
10^2 RAM uncached reference
10^1 L2/L3 cache reference
10^0 L1 cache reference
That's why systems don't feel fast lately. In particular for big data or bloated software that can't fit well within the caches or shared systems doing a lot of frequent switches (VMs in particular.)
Many classic assumptions for algorithms are outdated. Like avoiding full sequential scans. Those are fast for simple operations.
SSD's have become viable in terms of $/GB to justify them in a server room these days. I'd highly recommend moving to them (for your boot drive/VMs at least). It will make a world of difference. $400 may seem like a lot to spend for 160GB of storage, but knocking off two orders of magnitude off your seek time quickly becomes worth it when you're running four VMs off it at once.
I didn't think SSDs were that important until I read this and was like, "Oh, I should get one." Which I haven't done yet -- soon, though. When AppleCare on my iMac expires.
I loved the punchline to the story. Someone decides to write an algorithm to compute a few tables, works a while on an algorithm to compute them efficiently, in the end gives up and brute-forces it very inefficiently, then discovers that it takes only 2 seconds to run.
And the punchline: there's an article on Wikipedia with all of the values pre-computed!
No need to brute-force. It's pretty easy to just eliminate possibilities:
The largest number must be larger than 7, else the largest possible sum of the three numbers is 21.
If the largest number is 8, then the other two must sum to 15, which is not possible since they must both be 7 or less.
So the largest number is 9, and the other two numbers sum to 14. The possibilities for those other two, with the smallest first are (5 and 9), (6 and 8), or (7 and 7). Clearly (5 and 9) would duplicate the original 9 (5+9+9), and (7 and 7) would duplicate the 7.
Definitely makes you think about opportunity cost in terms of CS: spend time writing an efficient algorithm or just bust out the ole brute force. Surprisingly, brute force works really well with the excess performance we all have sitting around...
...until you have several hundred users hitting your server running that brute force algorithm. Sigh.
Most developers like to imagine they're going to have somewhere between 100 and 10,000 concurrent requests on their webserver shortly after launch, so they have to write really efficient algorithms. The reality is usually considerably less demanding. In most cases, its usually just cheaper to throw hardware at it. Of course, in some rare cases, algorithm efficiency is crucially important, but this is pretty rare.
As much as everyone would like to think they are working on something in the same class as google, facebook, etc, very few projects are comparable. You're better off shipping early, and dealing with scalability when it becomes a problem.
One thing I beat on my development staff about is that computers are fast, stupid fast. As in billions of operations per second fast. With rare exception, if I do an operation on something in memory, it shouldn't take any more than 1/2 a second for it to happen. This extends to UI interactions, selecting a few thousand items in a list shouldn't take 4 seconds a disk swap.
There are times though, when they have to go back and revisit something where they just "let the computer handle it" and whatever libraries they happened to be using do the work, and go back and rewrite a bunch of stuff to be performant from scratch. When that happens, there usually is some pretty large speedup, on the order of hundreds of percent.
I was going to point out that this extra part of Killer Soduku reminded me of Kakuro, but I see that's mentioned in the first line of the Wikipedia entry he links to:
It's true that computers are really fast. I solve Project Euler puzzles on a pretty old PC, using Python which is an interpreted language, and it's amazing how much "brute force" I can get away with. Test all permutations of the digits 1-9 for primality? Easy.
53 comments
[ 3.0 ms ] story [ 102 ms ] threadAnd with a bit of optimization, it would be even quicker.
OTOH, I encounter the "computers are fast" phenomenon 9 out of ten times.
Speed is a direct product of simplicity, and for me simple is elegant. I also think speed is important enough for me to feel strongly about cutting down a "feature" or two, to just make the damned thing not take all night to solve your sudoku..
When I put on my kernel dev hat or when I was working on SQL Server I spent all day making sure other me could throw data around haphazardly and not get stuck on a course-grained kernel lock or only hit 1/8 of the pipelines.
Sometimes it's just too much to handle all at once, even if you know what you're doing in both domains.
But why then it is so annoying that Visual Studio starts longer than my whole custom linux system in VM on the same computer...
But I sure as heck grumble when my computer is slow. "You've got, like, 800 hojillion cycles a second!" I say to it. "How hard is opening a program?!"
Is that hypocritical?
Disclaimer: I am using custom gnu/linux built entirely form sources.
Varnish dev says second-guessing VM is so 1975: http://news.ycombinator.com/item?id=1554656 OR http://news.ycombinator.com/item?id=1760811
Redis dev says second-guessing VM is elite (and not doing so is so 2006): http://news.ycombinator.com/item?id=1760540
... and the plus side is, if an application needs the RAM, no harm done, just dump the file from RAM and read it from disk.
* _The Design and Implementation of the 4.4BSD Operating System_, McKusick et al., p. 29-30.
What SuperFetch does is collect statistics about files hit by processes when they start up, so it can proactively cache bits of those files, to the point that it can cache files read by processes before those processes are ever started, assuming they are either commonly started or started on a schedule.
So, prune! as it swapped digits left to right in a Grey-code-like sequence, test the digits to the left for diagonals (|row#A - row#B| == |A-B|) and don't bother to recurse if its already failing.
Every few minutes - out popped a solution, and it finished in under 25 minutes.
Nowadays, that would take imperceptible time to execute.
edit: not to mention GPUs
We need 64 transputers to run this in real time, 1 year of PCB layout later = hey we can do this in 16 transputers and a Sparc.
Cue another year of redesign - now it would only take 4 transputers and a Sparc5.
Then a sales guy turns up promising to put the 16 transputers into an FPGA card.
Just before that works we get an i860 board for the Sparc.
Then finally we can do it in software on a Pentium...
One of the other research teams in the department were working on some kind of custom chip for some specialized application and they wanted to show how much better it was than even the best commodity CPU so they gave me a chunk of completely unoptimized vanilla C to compile and run as a benchmark.
Turns out the Alpha was way faster than their chip - which I don't think they were too happy about!
Light travels about 1 foot/nanosecond, so the travel time from monitor to eyeball is 1 or 2 nanoseconds, which might be 2 or 3 clock cycles. So I think at most 3 operations per CPU.
Of course, in real code you'll be lucky to get anywhere near that.
i7 can do 2 double precision adds per clock per core, that would give 36 GFLOPS on 6 cores (assuming 3 GHz clock), and at the same time ATI Radeon 5870 GPU can do 500 GFLOPS in double precision, that's 500 floating point calculations in one nanosecond.
To cross the 0.5 meter distance the light takes around 1.6 ns, which means that during that time the CPU is able to do almost 60 FPU additions and the GPU around 800 FPU additions. Impressive.
1998: "if" too slow; use "case".
2002: "case" too slow; use Boolean algebra.
2006: Boolean algebra too slow, use arrays & pointers.
2010: Who wrote this shit and what does it do? Rewritten to use "if".
In nanoseconds, approximately:
That's why systems don't feel fast lately. In particular for big data or bloated software that can't fit well within the caches or shared systems doing a lot of frequent switches (VMs in particular.)Many classic assumptions for algorithms are outdated. Like avoiding full sequential scans. Those are fast for simple operations.
http://www.anandtech.com/show/3734/seagates-momentus-xt-revi...
I didn't think SSDs were that important until I read this and was like, "Oh, I should get one." Which I haven't done yet -- soon, though. When AppleCare on my iMac expires.
And the punchline: there's an article on Wikipedia with all of the values pre-computed!
- Billy Zelsnack
I'm kidding, obviously, but this is a very common phenomenon. Developers optimize their algorithms based on real-world performance instead of theory.
I wonder what impact this has on the world, would the cost of computing be dramatically lower (making computers more accessible) if we didn't do this?
The largest number must be larger than 7, else the largest possible sum of the three numbers is 21.
If the largest number is 8, then the other two must sum to 15, which is not possible since they must both be 7 or less.
So the largest number is 9, and the other two numbers sum to 14. The possibilities for those other two, with the smallest first are (5 and 9), (6 and 8), or (7 and 7). Clearly (5 and 9) would duplicate the original 9 (5+9+9), and (7 and 7) would duplicate the 7.
So the only possible solution is 6+8+9.
...until you have several hundred users hitting your server running that brute force algorithm. Sigh.
As much as everyone would like to think they are working on something in the same class as google, facebook, etc, very few projects are comparable. You're better off shipping early, and dealing with scalability when it becomes a problem.
There are times though, when they have to go back and revisit something where they just "let the computer handle it" and whatever libraries they happened to be using do the work, and go back and rewrite a bunch of stuff to be performant from scratch. When that happens, there usually is some pretty large speedup, on the order of hundreds of percent.
http://en.wikipedia.org/wiki/Kakuro