Boyer-Moore is one of the examples that made me realize clearly that on the larger scale of programmer competence I'm nobody special. Some algorithms show such out-of-the-box thinking that it blows your mind.
The most interesting thing is that most pattern matching algorithms up to then got slower with longer match strings, but Boyer-Moore actually got faster!
To quote Majikthise: "Bloody hell, now that is what I call thinking."...
The most interesting thing is that most pattern matching algorithms up to then got slower with longer match strings, but Boyer-Moore actually got faster!
Another interesting bit of trivia: In the first chapter of my thesis I present a string matching algorithm with almost exactly the same asymptotic running time as BM -- but where BM performs exact matching using no precomputed index, my algorithm performs matching with mismatches using an index.
With an index, of course, exact matching is O(log N) time -- in a peculiar way, the "cost" of inexact matching is one index worth of efficiency.
[EDIT: On second thought, this last comment meaningful at all? I'm not sure, but it's almost 4AM so I'm not going to figure it out now.]
One thing to remember, is that almost all of the unix utility programs were developed for computers that had FAR less horsepower than even a modest desktop PC of today. In the early days, literally every byte of RAM was precious as was every CPU instruction. So in that sense, necessity was the mother of invention, and developers were accustomed to working with that mindset.
Most of UNIX's utilities were written with high regard for their memory use. When GNU decided to clone them all, they actually outlined that their developers were forbidden to even review UNIX sourcecode. Convention stated that they all try to write the programs with speed in mind, and now we have these discussions.
I don't think you should optimize for space or speed at each others expense without figuring out if the trade-off is worth it.
Space and speed will always be conflicting goals during optimizations (unless you're very lucky), and for practical use the sweet spot is usually somewhere in between the two extremes.
To blindly optimize for speed will result in very wasteful behaviour when it comes to memory usage, to blindly optimize for space will result in terrible performance.
Smart software realizes when the space is available and free for the taking and will use it to find an increase in speed, it will also realize when space is at a premium and economize on it's usage.
On another note, accessing all that memory costs cycles and is almost certainly going to trash your cache, chances are that if you manage to reduce your memory footprint eventually you'll find that instead of losing speed you're gaining speed.
Open Office started up with a blank word processor document uses 83 Megs of RAM, something tells me that could be a whole lot less without sacrificing functionality or speed.
I agree completely that one should not optimize for one area without taking in account the penalties incurred on the other areas. I hope I didn't give that impression.
One of the more major reasons of GNU developing the habit of writing utilities that were significantly different in their implementation was to make sure no UNIX/BSD code could leak in, since at the time the project was underway, BSD was stuck in that whole USL vs BSDi suit, and BSD's code was tentatively deemed 'non-free'.
One also needs to account for the time period these utilities were written, and for what computer system they were originally written for. Both memory and speed were expensive. Writing these utilities probably required much more thought to the smaller details than one would think about today when writing say a word processor, even though one could benefit by doing so.
Having lots of memory can serve as a poor-man's SSD. At least on a Linux system files are read from the disk and left in memory until that memory is needed for something else. This can increase responsiveness by reducing the need to go to disk for frequently used filesystem data.
The stable version of Chrome leaks memory like crazy on Linux. I was frequently using over 1gb according to about:memory and have seen it use up to 3gb. 6.0.495.0 dev seems to be better about it.
Adobe After effects is a good example of a fairly standard app that will happily chew through 8-12 gigs of ram when working on moderately complicated videos.
I also know people who work with fluid dynamics and the new workstations they bought for work have 48 gigs of RAM.
Think about what Adobe After effects is doing, though: non-linear video editing. A bit more than a decade ago, you couldn't do that outside of Hollywood. A bit more than two decades ago, and even Hollywood couldn't do it - everyone still used celluloid.
I'm not sure that either video editing or fluid dynamics count as bloatware in my book, because the problems are inherently complex. Word processing, however...
I did non-linear video editing on my PC in the late 90s. There were certainly some limitations since the AVI format was stupid (used a signed integer for an index limiting you to 2GB file size), but my machine then was a 133MHz pentium with probably 32 or 64MB of RAM. Granted I was only working with half-height VHS (640x240), but it worked.
I haven't tried a lot of video editing software today (since I no longer pirate software like I used to), but what I have used is not huge progress from what I did in the late 90s. The only big step is that you can work with compressed streams directly, which is nice, but expected since even a modest machine today is expected to be able to decompress the latest MPEG spec in realtime.
What are you putting in those tabs? I frequently have 50+ tabs open in Chrome and rarely get to more than about 1GB total. Sometimes some long running web apps will leak enough (Gmail, I'm looking at you...) to bring a single tab up in the 100-200MB+ range, but that's rare.
Thanks, I didn't know that algorithm and your comment made me look it up.
For anyone else who skimmed the article and doesn't know the algorithm, check it out at http://en.wikipedia.org/wiki/Boyer-Moore. It's a very quick read to get the basic idea, and it's as good as jacquesm cracks it up to be.
Actually I posted this article yesterday
http://news.ycombinator.com/item?id=1624402 but I went unnoticed. The
author was working on search feature for his Hex editor and tried to
outperform GNU grep by using Boyer-Moore. After multiple attempts, he
finally discovered the hard way all the tricks used by Mike Heartel to
make GNU grep run faster than his implementation.
I read that one years ago thanks for the repost. I missed it on the submissions, they go by so fast now. I think we're too late to bring it up though, it would need quite a large number of upvotes to come back after dropping down this far.
They're about the same amount of trippiness. Boyer-Moore makes the same kind of jump table, except Boyer-Moore starts comparing at the end of the search string.
BM is my favourite algorithm, but I haven't seen any others that are as elegant and powerful. What are the other examples you're thinking of?
(BM is especially cute because the basic idea is so simple: do it backwards. Quicksort is very clever. Arithmetic coding is mindbendingly cool, but the algorithm isn't simple enough - for this old brain anyway.)
Levenshtein, DCTs, Wavelets, Phong shading, flood fill and so on. There are so many really insightful algorithms.
But BM stands out for me because it is taking the opposite approach where that was entirely non-obvious in spite of lots of people having looked at that problem for a very long time (and plenty of those people were anything but stupid).
For the record, I've written an operating system (multi-tasking, multi-user, message passing) a window manager to go with it, a bunch of applications to go with the window manager and a whole pile of commercial software besides that.
And in spite of all that I think I can make the above statement in confidence, that algorithm has something very unique and it exhibits a level of thinking that goes beyond the ordinary world of programming.
> I'd say thinking up Boyer-Moore is nothing special. It's just a logical progression of ideas. If you think about the problem long enough, you would come up with the same solution, or maybe even a better one.
What's stopping you?
I'm sure we'd love to see the Palish algorithm that beats MB by a significant margin and that does not build upon it.
A complete side-note, but it's hard to figure out where else to put this.
HN should not allow you to delete a post once it has a child comment. I find that people sometimes delete entire stacks of comments that have children (as in this case) when they don't seem to like how the argument is going. (This is not super-common, but it happens often enough that I've noticed it.) It's enormously frustrating for readers - not to mention childish on the part of the deleters.
Now, as for the rest of you kids, get off my lawn.
It seems to be something that has been 'figured out' and is now spreading. I'll theorize that it has to do with people that are afraid of the down-mod mob to avoid their karma taking a hit after posting something silly or they're afraid of being found in a decade by a google search from some prospective employer.
I could restore the deleted bits (without naming the author) if that's desired?
There are people that are simply better at this stuff than I am, I'm not going to belittle my own work by paying homage to theirs. That does not mean that I can't improve relative to where I am today though, and I strive very hard to do so. Maybe one day I will be that good.
It's the difference between arrogance and objectivity.
I'm more than happy creating the stuff I do, every now and then I come up with something that is new (at least, new to me, see http://news.ycombinator.com/item?id=1353259), but that does not mean that I'm going to see this as anything other than the stroke of genius that it was.
If it really was that easy we could all improve on every major algorithm out there just by staring at it long enough and that's exactly why BM is so neat, it wasn't just a simple incremental improvement on someone else's code.
So, I challenge you, come up with an improvement on the status quo prior to BM that does not use the principles as exposed in BM and that performs on par or better, and that are not part of the current literature.
I'll tip you $250 if you manage to do that, that should be easy money for you. And I'm good for the cash.
You will probably get a nice wikipedia entry to boot.
Why would being objective about someone elses achievements relative to your own discourage anybody? That's a motivation to try harder not to give up, after all, it shows you what is possible.
Just like hearing Jehudi Menuhin play should not cause you to burn your violin but to practice.
I'm not putting algorithms on a pedestal, I'm putting that particular example of all the algorithms available up as the one that I ran in to which taught me that I (still!) have a lot to learn.
jacquesm seems like an accomplished guy. I believe he created internet video feeds. I just bookmarked his HN comment feed along with tptacek because it's a great way to find the good technical threads on HN.
When jacquesm is in awe of some developer, I find it inspirational, to think: hey, he's a mortal, maybe I can be that good too one day.
Comments
Boyer-Moore is one of the examples that made me realize clearly that on the larger scale of programmer competence I'm nobody special. Some algorithms show such out-of-the-box thinking that it blows your mind.
The most interesting thing is that most pattern matching algorithms up to then got slower with longer match strings, but Boyer-Moore actually got faster!
To quote Majikthise: "Bloody hell, now that is what I call thinking."...
The most interesting thing is that most pattern matching algorithms up to then got slower with longer match strings, but Boyer-Moore actually got faster!
Another interesting bit of trivia: In the first chapter of my thesis I present a string matching algorithm with almost exactly the same asymptotic running time as BM -- but where BM performs exact matching using no precomputed index, my algorithm performs matching with mismatches using an index.
With an index, of course, exact matching is O(log N) time -- in a peculiar way, the "cost" of inexact matching is one index worth of efficiency.
[EDIT: On second thought, this last comment meaningful at all? I'm not sure, but it's almost 4AM so I'm not going to figure it out now.]
Is your thesis online?
I'd like to read that.
Is your thesis online?
Yes, http://www.daemonology.net/papers/thesis.pdf
I'd like to read that.
I recommend skipping the proofs. They're not very informative and the calculus gets rather tedious.
I liked this: from your thesis:
"If a mathematician is a machine for turning coffee into theorems, a computer scientist is a machine for converting caffeine into algorithms."
Thank you!
> I recommend skipping the proofs. They're not very informative and the calculus gets rather tedious.
And besides that is well over my head anyway, but I should be able to follow your main line of reasoning.
Colin, that is a well-written thesis I have read in a long time! Great work!
One thing to remember, is that almost all of the unix utility programs were developed for computers that had FAR less horsepower than even a modest desktop PC of today. In the early days, literally every byte of RAM was precious as was every CPU instruction. So in that sense, necessity was the mother of invention, and developers were accustomed to working with that mindset.
> every byte of RAM was precious as was every CPU instruction.
What I wouldn't give to infuse that sense in to present day programmers. (writing this on a box with 12G ram, pretty much maxed out).
Most of UNIX's utilities were written with high regard for their memory use. When GNU decided to clone them all, they actually outlined that their developers were forbidden to even review UNIX sourcecode. Convention stated that they all try to write the programs with speed in mind, and now we have these discussions.
http://www.gnu.org/prep/standards/html_node/Reading-Non_002d...
I don't think you should optimize for space or speed at each others expense without figuring out if the trade-off is worth it.
Space and speed will always be conflicting goals during optimizations (unless you're very lucky), and for practical use the sweet spot is usually somewhere in between the two extremes.
To blindly optimize for speed will result in very wasteful behaviour when it comes to memory usage, to blindly optimize for space will result in terrible performance.
Smart software realizes when the space is available and free for the taking and will use it to find an increase in speed, it will also realize when space is at a premium and economize on it's usage.
On another note, accessing all that memory costs cycles and is almost certainly going to trash your cache, chances are that if you manage to reduce your memory footprint eventually you'll find that instead of losing speed you're gaining speed.
Open Office started up with a blank word processor document uses 83 Megs of RAM, something tells me that could be a whole lot less without sacrificing functionality or speed.
I agree completely that one should not optimize for one area without taking in account the penalties incurred on the other areas. I hope I didn't give that impression.
One of the more major reasons of GNU developing the habit of writing utilities that were significantly different in their implementation was to make sure no UNIX/BSD code could leak in, since at the time the project was underway, BSD was stuck in that whole USL vs BSDi suit, and BSD's code was tentatively deemed 'non-free'.
One also needs to account for the time period these utilities were written, and for what computer system they were originally written for. Both memory and speed were expensive. Writing these utilities probably required much more thought to the smaller details than one would think about today when writing say a word processor, even though one could benefit by doing so.
> writing this on a box with 12G ram, pretty much maxed out
Serious question: what are you using 12G of RAM on? My workstation is pretty modest (core 2 duo, 4G RAM) and I'm rarely able to utilize more than 1G.
Having lots of memory can serve as a poor-man's SSD. At least on a Linux system files are read from the disk and left in memory until that memory is needed for something else. This can increase responsiveness by reducing the need to go to disk for frequently used filesystem data.
More info: http://www.linuxatemyram.com/index.html
The price of SSDs has come down sufficiently that you probably could say that having lots of memory is a stupid way to emulate having an SSD ;)
But the speed of RAM is still at least one order of magnitude faster than the SSD so there is still an advantage even with a faster fixed disk.
IDE, OpenOffice, Browser, email client, shell and window manager. That's it. The big ones are the first three and X windows.
I run exactly those apps on a computer with 2 gigs of RAM and never really had any problems.
We are probably doing different things with our applications.
Out of curiosity, how do you manage to make an IDE, Open Office and a browser eat through 12 gigs of RAM?
The stable version of Chrome leaks memory like crazy on Linux. I was frequently using over 1gb according to about:memory and have seen it use up to 3gb. 6.0.495.0 dev seems to be better about it.
It's really not that hard. One fair sized project and a bunch of browsers with tabs. It surprises me very much how much RAM that gobbles up.
I'm not even testing stuff with VMs right now, as soon as I get in to that I have to shut down the IDE at a minimum or I'll hit the swap.
a java ide?
Yep. Unfortunately.
Adobe After effects is a good example of a fairly standard app that will happily chew through 8-12 gigs of ram when working on moderately complicated videos.
I also know people who work with fluid dynamics and the new workstations they bought for work have 48 gigs of RAM.
Think about what Adobe After effects is doing, though: non-linear video editing. A bit more than a decade ago, you couldn't do that outside of Hollywood. A bit more than two decades ago, and even Hollywood couldn't do it - everyone still used celluloid.
I'm not sure that either video editing or fluid dynamics count as bloatware in my book, because the problems are inherently complex. Word processing, however...
I did non-linear video editing on my PC in the late 90s. There were certainly some limitations since the AVI format was stupid (used a signed integer for an index limiting you to 2GB file size), but my machine then was a 133MHz pentium with probably 32 or 64MB of RAM. Granted I was only working with half-height VHS (640x240), but it worked.
I haven't tried a lot of video editing software today (since I no longer pirate software like I used to), but what I have used is not huge progress from what I did in the late 90s. The only big step is that you can work with compressed streams directly, which is nice, but expected since even a modest machine today is expected to be able to decompress the latest MPEG spec in realtime.
Chrome uses some absolutely amazing 4-500MBs per tab. Had this box had less than 12GBs, I would rather be using the Firefox 4 betas.
What are you putting in those tabs? I frequently have 50+ tabs open in Chrome and rarely get to more than about 1GB total. Sometimes some long running web apps will leak enough (Gmail, I'm looking at you...) to bring a single tab up in the 100-200MB+ range, but that's rare.
Regular newspapers, facebook, reddit, hacker news, xkcd and dilbert.
That's about it.
Thanks, I didn't know that algorithm and your comment made me look it up.
For anyone else who skimmed the article and doesn't know the algorithm, check it out at http://en.wikipedia.org/wiki/Boyer-Moore. It's a very quick read to get the basic idea, and it's as good as jacquesm cracks it up to be.
Actually I posted this article yesterday http://news.ycombinator.com/item?id=1624402 but I went unnoticed. The author was working on search feature for his Hex editor and tried to outperform GNU grep by using Boyer-Moore. After multiple attempts, he finally discovered the hard way all the tricks used by Mike Heartel to make GNU grep run faster than his implementation.
I read that one years ago thanks for the repost. I missed it on the submissions, they go by so fast now. I think we're too late to bring it up though, it would need quite a large number of upvotes to come back after dropping down this far.
If you think Boyer-Moore is trippy, try to understand the partial match lookup table creation algorithm in Knuth-Morris-Pratt: http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pr...
They're about the same amount of trippiness. Boyer-Moore makes the same kind of jump table, except Boyer-Moore starts comparing at the end of the search string.
linked from that wikipedia page, an applet showing them side-by-side, you will need java, and you have to supply your own test strings.
http://www.ics.uci.edu/~goodrich/dsa/11strings/demos/pattern...
Thanks for the recommendation! If anyone else isn't familiar, there is an exceptionally good Wikipedia entry:
http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_sear...
BM is my favourite algorithm, but I haven't seen any others that are as elegant and powerful. What are the other examples you're thinking of?
(BM is especially cute because the basic idea is so simple: do it backwards. Quicksort is very clever. Arithmetic coding is mindbendingly cool, but the algorithm isn't simple enough - for this old brain anyway.)
Levenshtein, DCTs, Wavelets, Phong shading, flood fill and so on. There are so many really insightful algorithms.
But BM stands out for me because it is taking the opposite approach where that was entirely non-obvious in spite of lots of people having looked at that problem for a very long time (and plenty of those people were anything but stupid).
[deleted]
For the record, I've written an operating system (multi-tasking, multi-user, message passing) a window manager to go with it, a bunch of applications to go with the window manager and a whole pile of commercial software besides that.
And in spite of all that I think I can make the above statement in confidence, that algorithm has something very unique and it exhibits a level of thinking that goes beyond the ordinary world of programming.
> I'd say thinking up Boyer-Moore is nothing special. It's just a logical progression of ideas. If you think about the problem long enough, you would come up with the same solution, or maybe even a better one.
What's stopping you?
I'm sure we'd love to see the Palish algorithm that beats MB by a significant margin and that does not build upon it.
A complete side-note, but it's hard to figure out where else to put this.
HN should not allow you to delete a post once it has a child comment. I find that people sometimes delete entire stacks of comments that have children (as in this case) when they don't seem to like how the argument is going. (This is not super-common, but it happens often enough that I've noticed it.) It's enormously frustrating for readers - not to mention childish on the part of the deleters.
Now, as for the rest of you kids, get off my lawn.
It happened again, above.
It seems to be something that has been 'figured out' and is now spreading. I'll theorize that it has to do with people that are afraid of the down-mod mob to avoid their karma taking a hit after posting something silly or they're afraid of being found in a decade by a google search from some prospective employer.
I could restore the deleted bits (without naming the author) if that's desired?
Maybe a retract button instead of delete would be a fair compromise? The comment still appears but the karma is frozen and cannot be downvoted further
Not a bad idea. Add an optional 'reason' field for the mea culpa as well.
pre-sets:
- put foot in mouth
- drunk in charge of keyboard
- 4 am
- the cat did it
- sincerely regret writing that
[deleted]
Whoever talked about losing hope?
There are people that are simply better at this stuff than I am, I'm not going to belittle my own work by paying homage to theirs. That does not mean that I can't improve relative to where I am today though, and I strive very hard to do so. Maybe one day I will be that good.
It's the difference between arrogance and objectivity.
I'm more than happy creating the stuff I do, every now and then I come up with something that is new (at least, new to me, see http://news.ycombinator.com/item?id=1353259), but that does not mean that I'm going to see this as anything other than the stroke of genius that it was.
If it really was that easy we could all improve on every major algorithm out there just by staring at it long enough and that's exactly why BM is so neat, it wasn't just a simple incremental improvement on someone else's code.
So, I challenge you, come up with an improvement on the status quo prior to BM that does not use the principles as exposed in BM and that performs on par or better, and that are not part of the current literature.
I'll tip you $250 if you manage to do that, that should be easy money for you. And I'm good for the cash.
You will probably get a nice wikipedia entry to boot.
[deleted]
Why would being objective about someone elses achievements relative to your own discourage anybody? That's a motivation to try harder not to give up, after all, it shows you what is possible.
Just like hearing Jehudi Menuhin play should not cause you to burn your violin but to practice.
I'm not putting algorithms on a pedestal, I'm putting that particular example of all the algorithms available up as the one that I ran in to which taught me that I (still!) have a lot to learn.
jacquesm seems like an accomplished guy. I believe he created internet video feeds. I just bookmarked his HN comment feed along with tptacek because it's a great way to find the good technical threads on HN.
When jacquesm is in awe of some developer, I find it inspirational, to think: hey, he's a mortal, maybe I can be that good too one day.