Archive for January 10, 2014

Friday, January 10, 2014

Why GNU grep Is Fast

Mike Haertel:

Moreover, GNU grep AVOIDS BREAKING THE INPUT INTO LINES. Looking for newlines would slow grep down by a factor of several times, because to find the newlines it would have to look at every byte!

So instead of using line-oriented input, GNU grep reads raw data into a large buffer, searches the buffer using Boyer-Moore, and only when it finds a match does it go and look for the bounding newlines. (Certain command line options like -n disable this optimization.)

“Doom” 20th Anniversary Stories

Wil Shipley:

The way I got into the software business (besides learning to code) was to use every piece of software I could find and send the developers tons and tons of notes and bug reports. It turns out developers liked this, and it gained me a lot of opportunities. One of them was porting Doom and Quake to NEXTSTEP.


Don’t take this to mean [Carmack’s] code was spaghetti—it was actually some of the easiest-to-understand code I’ve ever worked with. It has an almost indescribable quality of “obviousness.” Like, you know when a really good teacher explains something, it seems obvious? That’s what his code was like.


We did some other ports for free as well, because back when OS X was new it wasn’t at all clear that the Cocoa layer would win out over the Carbon layer. (Most people thought not.) It had been my life’s mission (since 1987) to make sure that NEXTSTEP technology got into the mainstream, and OS X was our last and only hope. We knew games were crucial for a platform‘s wide adoption (c.f. iOS), and Steve didn’t like games, so it was up to us.

Why MacPaint’s Original Canvas was 416 Pixels Wide

Bill Scott (via John Gruber):

The key to this really fast render operation was the use of the Motorola 68k’s MOVEM command. MOVEM stands for Move Multiple. It can take a range of registers and move bits from an address into the M68k registers or do the reverse.