Category Archives: Rant

But the question is: will it recur? Part 1: fibonacci(40)

16 Replies

A rant, maybe a bad rant due to babbling about philosophical reasons, made me wonder how the programming languages stack up against this stuff: recursion. Or should I say the runtimes, since the programming language itself is nothing but a bunch of text. I know that the algorithm itself is bad, but that’s the whole point. I know that fibonacci(0) yields a wrong result, but for the sake of lazyness, I kept the original algorithm.

The source code of all the tests is available here in order to make the tests to be reproducible. There wasn’t a high number of runs, particularly for the rutimes that take more than the next ice age. But the results are pretty consistent for specific runtimes. The relevant systems specs are: Ubuntu 10.04 amd64 (up to date), Q9400 CPU.

Now, less talk, more results.

JavaScript (node.js/V8)

node -v: v0.4.12
time node fib.js
node fib.js 6.40s user 0.02s system 99% cpu 6.423 total
node fib.js 6.39s user 0.02s system 99% cpu 6.410 total

It may seem slow, but for a language with dynamic typing, it puts the rest from the same category to shame. Or most of them. Bear with me.

PHP

php -v: PHP 5.3.8 (cli)
time php fib.php
php fib.php 77.57s user 0.06s system 99% cpu 1:17.66 total
php fib.php 78.05s user 0.07s system 99% cpu 1:18.18 total

Compared to the V8 runtime, PHP seems to take an eternity. It happens that PHP isn’t bad at recursion because it uses the stack, but because the lack of speed of the runtime. But we’re not even halfway there. Stay tuned. PHP isn’t the only thing that sucks at recursion.

C

gcc -v: gcc version 4.4.3 (Ubuntu 4.4.3-4ubuntu5)
make fib
time ./fib
./fib 2.84s user 0.00s system 100% cpu 2.840 total
./fib 2.84s user 0.00s system 100% cpu 2.835 total

It wasn’t a surprise that C came up to this result. Which makes the V8 result even more interesting.

Edit:
Forgot about the compiler optimization. Caught by Jabbles on HN.

gcc -O4 fib.c -o fib
time ./fib
./fib 0.65s user 0.01s system 100% cpu 0.657 total
gcc -O3 fib.c -o fib
time ./fib
./fib 0.66s user 0.00s system 100% cpu 0.657 total
gcc -O2 fib.c -o fib
time ./fib
./fib 1.54s user 0.00s system 100% cpu 1.535 total
gcc -O1 fib.c -o fib
time ./fib
./fib 0.00s user 0.00s system 0% cpu 0.001 total
time ./fib
165580141
./fib 2.06s user 0.00s system 99% cpu 2.060 total

For some reason, the O1 flag hates this code. Printing fibonacci(40) yields a result closer to the result without any O flag. This brings it past the Java result, but only for O3+.
/End Edit.

Lua

lua -v: Lua 5.1.4
time lua fib.lua
lua fib.lua 28.02s user 0.03s system 99% cpu 28.081 total
lua fib.lua 28.86s user 0.02s system 99% cpu 28.883 total

./luajit -v: LuaJIT 2.0.0-beta8
time ./luajit fib.lua
./luajit fib.lua 10.59s user 0.00s system 99% cpu 10.591 total
./luajit fib.lua 10.58s user 0.01s system 99% cpu 10.610 total

Tested both of the implementations that I know of. I guess this article isn’t that funny for the generations of Lua coders that laugh about V8 in somebody’s face. Don’t get me wrong, I like Lua due to its simplicity, but in the speed realm, I still need to do some tests to verify some of those claims that sometimes appear to be overly inflated.

Edit:

With the following Lua script:

local function fibonacci(n)
	if n < 2 then
		return 1
	else
		return fibonacci(n - 2) + fibonacci(n - 1)
	end
end
fibonacci(40)

the results are getting better:

time lua fib.lua
lua fib.lua 24.17s user 0.08s system 99% cpu 24.281 total
lua fib.lua 24.24s user 0.01s system 99% cpu 24.307 total

[with LuaJIT v2.0.0-beta8 GIT HEAD]
time ./luajit fib.lua
./luajit fib.lua 2.02s user 0.00s system 99% cpu 2.026 total
./luajit fib.lua 2.02s user 0.00s system 99% cpu 2.023 total

Now, some of the Lua chops can have a lulz about V8. This project is getting more interesting, especially for pairing LuaJIT with luafcgid. I forgot about the local keyword since my Lua experience is limited to basic testing. Nice comeback!

/End Edit.

Python

python -V: Python 2.6.5
time python fib.py
python fib.py 59.42s user 0.02s system 99% cpu 59.494 total
python fib.py 59.27s user 0.05s system 99% cpu 59.375 total

./configure
make -j 4
./python -V: Python 2.7.2
time ./python fib.py
./python fib.py 61.29s user 0.03s system 99% cpu 1:01.35 total
./python fib.py 61.38s user 0.06s system 99% cpu 1:01.48 total

./configure
make -j 4
./python -V: Python 3.2.2
./python fib.py 71.23s user 0.08s system 99% cpu 1:11.33 total
./python fib.py 70.31s user 0.06s system 99% cpu 1:10.39 total

./pypy -V
Python 2.7.1 (d8ac7d23d3ec, Aug 17 2011, 11:51:19)
[PyPy 1.6.0 with GCC 4.4.3]
./pypy fib.py 4.61s user 0.07s system 99% cpu 4.708 total
./pypy fib.py 4.81s user 0.01s system 99% cpu 4.853 total

Happens to have 2.6.5 around because Ubuntu says so. But in order to make the potential trolls to STFU about not using the latest versions, I made some fresh builds of 2.7.2 and 3.2.2. It gets even suckier with recent versions. In fact, the CPython runtime is struggling to catch up the PHP runtime on the slowness realm. The only Python runtime that is actually very impressive about the recursion stuff is PyPy. Which brings me to the first statement: the language is just a bunch of text. The runtime is the piece that sucks or does not suck. PyPy proves that with talented people shepherding the project, the language of the runtime implementation is quite irrelevant. This is the first implementation of a JIT that passes V8 as well.

Ruby

ruby -v: ruby 1.8.7 (2010-01-10 patchlevel 249) [x86_64-linux]
time ruby fib.rb
ruby fib.rb 233.40s user 66.94s system 99% cpu 5:00.55 total
ruby fib.rb 231.75s user 68.08s system 99% cpu 4:59.99 total

./configure
make -j 4
./miniruby -v: ruby 1.9.3dev (2011-09-23 revision 33323) [x86_64-linux]
time ./miniruby fib.rb
./miniruby fib.rb 36.05s user 0.01s system 99% cpu 36.073 total
./miniruby fib.rb 35.92s user 0.04s system 99% cpu 35.978 total

Everytime a Ruby fan says that “thou shalt not care about the runtime speed” makes me laugh so hard up to the point of bursting into tears. Seriously, I couldn’t imagine that MRI sucks that hard at recursion. I barely had the patience to even run this code. KRI washes part of the shame though while it scores closely to the Lua implementation. If you’re asking why I used the miniruby binary, the reason is that the ruby binary complained about not having rubygems.rb. I am bad at figuring out what’s missing from a Ruby stack. But it made the fib.rb work.

Perl

perl -v: This is perl, v5.10.1 (*) built for x86_64-linux-gnu-thread-multi
time perl fib.pl
perl fib.pl 125.60s user 0.17s system 99% cpu 2:05.92 total
perl fib.pl 124.06s user 0.10s system 99% cpu 2:04.20 total

./Configure [accepted all defaults, specifically built without threading]
make
./perl -v: This is perl 5, version 14, subversion 2 (v5.14.2) built for x86_64-linux
./perl fib.pl 100.12s user 0.09s system 99% cpu 1:40.29 total
./perl fib.pl 100.38s user 0.05s system 99% cpu 1:40.63 total

At first I didn’t want to bother with Perl, but then I remembered the legions of Perl fans ranting about the PHP recursion. I know that this is an inflammatory statement, but next time, people, please keep up with the facts. I guess you aren’t that smug now.

D

gdc -v: gcc version 4.3.4 (Ubuntu 1:1.046-4.3.4-3ubuntu1)
gdc -o fib fib.c (same source as the C binary)
time ./fib
./fib 2.82s user 0.00s system 100% cpu 2.817 total
./fib 2.82s user 0.00s system 100% cpu 2.814 total

Predictable results from a language from the same family as C/C++. Slightly faster binary that the C version (although the same source code), but I guess most people won’t notice.

Java

javac -version: gcj-4.4 (Ubuntu 4.4.3-1ubuntu4.1) 4.4.3
java -version
java version “1.6.0_20”
OpenJDK Runtime Environment (IcedTea6 1.9.9) (6b20-1.9.9-0ubuntu1~10.04.2)
OpenJDK 64-Bit Server VM (build 19.0-b09, mixed mode)
javac fib.java
time java fib
java fib 0.86s user 0.02s system 99% cpu 0.882 total
java fib 0.86s user 0.02s system 100% cpu 0.872 total

I admit that sometimes I use to tell this joke: knock! knock!; who’s there?; [very long pause]; Java. I guess that now is a good time to swallow my own words. Not only that Java puts the other JIT implementations to shame, the rest of the VMs to shame, it also obliterates the statically compiled C and D binaries at their own favorite game aka the runtime speed. My first reaction was: WTF, there’s got to be a mistake! Printing some junk to STDIO confirmed the same results between C and Java. Newbie warning: this is my first Java application. No, really! Don’t bash me for the lack of understanding of the usage of the static keyword. I don’t understand if it actually helps the runtime. I managed to put together the code by reading how to write a simple HelloWorldApp. Experienced Java chops may explain it though.

Why sometimes I hate RFCs

Leave a Reply

Every time when there’s a debate about the format of something that floats around the Internets, people go to RFCs in order to figure out who’s right and who’s wrong. Which may be a great thing in theory. In practice, the rocket scientists that wrote those papers might squeeze a lot of confusion into a single page of text, as the G-WAN manual states.

Today’s case was a debate about the Expires header timestamps as defined by the HTTP/1.1 specs (RFC 2616). If you read the 14.21 section regarding the Expires header, you can see the following statement:

The format is an absolute date and time as defined by HTTP-date in section 3.3.1; it MUST be in RFC 1123 date format:

Expires = “Expires” “:” HTTP-date

I made a newb mistake in thinking that the RFC 1123 dates are legal Expires timestamps. Actually, by proof reading 3.3.1 of RFC 2616 you may deduce the following: the dates in use by the HTTP/1.1 protocol are not the dates into the RFC 1123 format, but the actual format is a subset of RFC 1123. The debate started around the GMT specification which in the HTTP/1.1 contexts is actually UTC, but it must be specified as GMT anyway. Even more, +0000 which is valid timezone specifier as defined by RFC 1123 is not valid for Expires timestamps. Although some caches accept +0000 as valid timezone specifier for the HTTP timestamps, some of them don’t.

It isn’t that the RFCs are broken per se, but the language they use can be very confusing sometimes.

How to fix nginx and PHP/FastCGI PATH_INFO issue

3 Replies

You may be disappointed by this statement: you don’t. nginx has something in it that’s broken by design, while the author didn’t bother at least to reply my email, explaining the situation. I can demonstrate this by using some comparisons.

Apache (+mod_php5) knows the difference between a script and a PATH_INFO input request that ends in .php. It would be ridiculous not to do so since the PHP runtime is part of the webserver itself. Didn’t bother to try various Apache + mod_fcgid configurations since most of the time Apache simply wastes my own time. lighttpd binds the FastCGI proxying to the file extension. This is the part where nginx fails: it tries to use a one-size-fits-all configuration logic that actually doesn’t fits all the usage modes. The FastCGI pass is done into a location (not file / file extension!) directive that doesn’t tell anything about the nature of the input. Let’s take a look at this example:

/directory.php/file.php/pathinfo.php

Except nginx, both Apache and lighttpd won’t create a mess out of a path like this. A location directive is a little big vague and no amount of regex will ever fix this. Of course, you can fix it for every single damn virtual host, but then again, can you spell boilerplate? Having different configurations for every virtual host, when clearly for other web servers this isn’t a bundled “feature”, is not fun from the system administration point of view. Usually I generate the virtual host configuration from a bash script I wrote myself. I have configuration templates for all of the applications I administer, thus is all about flags and options, unlike manually writing configuration files. Working around nginx’s inabilities to tell which stuff is which could only mean that I have to write a whole bunch of configuration boilerplate for each type of application. Doesn’t sound like one-size-fits-all anymore. Is that fun? Let me rephrase that: that’s not fun. In case AWS disappears into a black hole, I can recreate everything from scratch in a matter of minutes onto a complete new hosting service while changing Cotendo origins is a child’s play.

Here are a bunch of proposed solutions for something that can turn out into a remote exploit. I’ve being using for quite a while the same solution as provided by one of the people commenting the article:

if (-f $request_filename)
{
    fastcgi_pass php_upstream;
}

Usually because this is more readable than try_files. I usually tend to understand code blocks better.

Of course, a proper PHP script won’t save any uploaded junk to a public accessible location, but what sysadmin trust his coders anyway? I usually don’t. That doesn’t mean that they don’t do a good job, but mistakes happen. I can’t made every living thing to be as paranoid about security as I am. This exploitable situation happens when people validate their upload via the $_FILES array. I have news flash for you: the MIME type defined by the $_FILES array is defined by the browser. The browser does a lousy job at providing a proper MIME. It matches a specific MIME based onto the file extension. PHP file with JPEG extension, anyone? fileinfo would be the proper alternative. PHP should deal with this junk by design, but that’s a whole other joke about the design of PHP.

Getting back to PATH_INFO. The juicy part is that basically you can extract the PATH_INFO from an input path by using fastcgi_split_path_info, but that directive uses … regex. Which brings us to the above statement: no amount of regex will ever fix this crap. Let’s take a look at $request_filename by throwing a custom debug logging configuration that places some stuff into the access_log. Guess what, the $request_filename for the above example is … /directory.php/file.php/pathinfo.php while it’s pretty clear that the actual request filename is /directory.php/file.php. Which is the other broken-by-design thing that nginx features. Q: What damn server side variable would ever lie to your face that a $request_filename is not exactly a file? A: duh!

This doesn’t mean that you should throw nginx and PHP-FPM away and go back crying to Apache. Just simply avoid the PATH_INFO junk. However, even by using my proposed configuration directive aka check if $request_filename is actually a file before doing the FastCGI pass, you can still use fastcgi_split_path_info for a limited amount of work. fastcgi_split_path_info can replace the need for doing URL rewrites by simply using:

if (!-e $request_filename)
{
    rewrite ^ /index.php last;
}

This works for a lot of stull like WordPress, Drupal, or Zend Framework. It works for certain stuff, except the stuff containing .php somewhere. I might want to use /%postname%.php as permalink structure in WordPress. Guess what … with a properly configured nginx (cough!) + the above rewrite rule replacement simply can’t. You have to go back to:

if (!-e $request_filename)
{
    rewrite ^/(.*)$ /index.php?q=$1 last;
}

Which is exactly what I did. For all my apps. Happens to be more deterministic by nature, while I tend to sleep better when I can predict the request pipeline, no matter which is the input junk.

I guess I could give Hiawatha a run which seems to be lightweight enough to support PHP with a threaded architecture. PHP is process based, doing blocking I/O by design, therefore the web server is rarely the actual bottleneck.