Tag: algorithm

Against PCRE

This is a tale of 2 approaches to regular expression matching. 1 of them is in widespread use in the standard interpreters for many languages, including Perl. The other is used only in a few places, notably most implementations of awk and grep. The 2 approaches have wildly different performance characteristics:

Thompson NFA graph
death to PCRE

Donald Knuth Interview

You are one of the fathers of the open-source revolution, even if you aren’t widely heralded as such. You previously have stated that you released TeX as open source because of the problem of proprietary implementations at the time, and to invite corrections to the code—both of which are key drivers for open-source projects today. Have you been surprised by the success of open source since that time? Donald Knuth: The success of open source code is perhaps the only thing in the computer field that hasn’t surprised me during the past several decades. But it still hasn’t reached its full potential; I believe that open-source programs will begin to be completely dominant as the economy moves more and more from products towards services, and as more and more volunteers arise to improve the code.

interesting as always

Regarding The Art of Computer Programming, it’s such a fascinating project. As I was researching I realized that you started it before either of my parents were even born. When you’re considering a project of that scope, how do you go about outlining and organizing and planning?

Well the best thing is to be a very bad estimator of how much time it’s going to take. At one point I thought I would have it done before my son was born; he was born in 1965. If I had known how much work it was going to be, I would have been pretty stupid to have started because here we are almost 60 years later and I’m basically a little more than half done.

Synthesis Kernel

This dissertation shows that operating systems can provide fundamental services an order of magnitude more efficiently than traditional implementations. It describes the implementation of a new operating system kernel, Synthesis, that achieves this level of performance.

The Synthesis kernel combines several new techniques to provide high performance without sacrificing the expressive power or security of the system. The new ideas include:
Run-time code synthesis – a systematic way of creating executable machine code at runtime to optimize frequently-used kernel routines – queues, buffers, context switchers, interrupt handlers, and system call dispatchers – for specific situations, greatly reducing their execution time.
Fine-grain scheduling – a new process-scheduling technique based on the idea of feedback that performs frequent scheduling actions and policy adjustments (at submillisecond intervals) resulting in an adaptive, self-tuning system that can support real-time data streams.
Lock-free optimistic synchronization is shown to be a practical, efficient alternative to lock-based synchronization methods for the implementation of multiprocessor operating system kernels.
An extensible kernel design that provides for simple expansion to support new kernel services and hardware devices while allowing a tight coupling between the kernel and the applications, blurring the distinction between user and kernel services.The result is a significant performance improvement over traditional operating system implementations in addition to providing new services.

Mind-expanding in a lisp way

News Analysis

TextMap is a search engine for entities: the important (and not so important) people, places, and things in the news. Our news analysis system automatically identifies and monitors these entities, and identifies meaningful relationships between them. TextMap analyzes both the temporal and geographical distribution of news entities. We literally monitor the state-of-the-world through our analysis of 1000 domestic and international news sources every day.

shows promise, but they have about a factor of 1000 fewer machines than they need.

Soul of The Sims

This is the prototype for the soul of The Sims, which Will Wright wrote on January 23, 1997. I had just started working at the Maxis Core Technology Group on “Project X” aka “Dollhouse”, and Will Wright brought this code in one morning, to demonstrate his design for the motives, feedback loop and failure conditions of the simulated people. While going through old papers, I ran across this print-out that I had saved, so I scanned it and cleaned the images up, and got permission from Will to publish it. This code is a interesting example of game design, programming and prototyping techniques. The Sims code has certainly changed a lot since Will wrote this original prototype code. For example, there is no longer any “stress” motive. And the game doesn’t store motives in global variables, of course. My hope is that this code will give you a glimpse of how Will Wright designs games, and what was going on in his head at the time!

Attacking Noise in Chat

And then I had an idea — what if you were only allowed to say sentences that had never been said before, ever? A bot with access to the full channel logs could kick you out when you repeated something that had already been said. There would be no “all your base are belong to us”, no “lol”, no “asl”, no “there are no girls on the internet”. No “I know rite”, no “hi everyone”, no “morning sucks.” Just thoughtful, full sentences.

you can never utter the same line twice, ever. works beautifully in a constrained environment like IRC. but would be extremely useful for blogs / comments / mails