はてなブックマーク

Editor’s note: For this blog entry I welcome my friend and colleague Gerben Stavenga as a guest author. Recently Andrei Alexandrescu published an interesting post about optimizing QuickSort using the Lomuto partition scheme. The essence of that post is that for many situations the performance of QuickSort is completely dominated by branch mispredicts and that a big speed up can be achieved by writ

One of the most interesting design challenges in a programming language interpreter or VM is what kind of memory management API to offer to native extensions. This issue is more or less invisible unless you’re writing a native extension. When you are simply writing a program in Ruby, Python, Lua, etc., you don’t usually care how the memory management is implemented. You only care is that you can c

My first adventures in parsing theory came when I was doing an independent study of programming languages in college. When I got to the part about algorithms such as LL, LR, and their many variations (Strong-LL, SLR, LALR, etc), I was fascinated. I felt like I was peering at some deep and powerful incantations, the significance of which I could not yet appreciate, but I was sure that someday terms

Author’s note: this article used to be called “What Every Computer Programmer Should Know About Floating Point, part 1”. Some people noted that this was perhaps too similar to the name of the existing article “What Every Computer Scientist Should Know About Floating Point”. Since I have a bunch of other articles called “X Demystified”, I thought I’d rename this one to remove confusion. The subject

In my last blog entry LL and LR Parsing Demystified, we explored LL and LR parsers from a black-box perspective. We arrived at a model for these parsers where both their input and output were streams of tokens, with the parser inserting rules as appropriate according to Polish and Reverse Polish notation. In future articles I want to focus in even closer on the details of LL and LR algorithms, but

Many programmers are aware that C++ templates are Turing-complete, and this was proved in the 2003 paper C++ Templates are Turing Complete. However, there is an even stronger result that many people are not aware of. The C++ FQA has a section showing that parsing C++ is undecidable, but many people have misinterpreted the full implications of this (understandable, since the FQA is discussing sever

This is a demonstration of how simple and enjoyable small JITs (just-in-time compilers) can be. The word “JIT” tends to invoke an image of deepest wizardry, something that only teams of the most hard-core compiler guys would ever dream of creating. It makes you think of the JVM or .NET, very large runtimes with hundreds of thousands of lines of code. You never see “Hello, World!” sized programs fo

Floating-point math has a reputation for being very unpredictable and hard to understand. I think that a major reason for this is that floating-point values are hard to inspect. Take the following program: #include <stdio.h> int main() { double x = 0.1; printf("%f\n", x); } Here is the output I get on my system: 0.100000 You might be tempted to think that the variable x is indeed equal to the valu