[cpu minus startup time]     [sort] [sort]   Source Code CPU (sec) Mem (KB) Lines Code Log mlton 1.00 880 765 log bigloo 1.94 5016 60 log cmucl 3.44 10908 48 log ocaml 3.67 668 32 log icon 3.74 1512 26 log mawk 3.79 580 32 log ocamlb 4.22 808 32 log perl 4.72 1344 28 log g++ 5.18 768 54 log gcc 5.33 400 111 log smlnj 5.38 5212 767 log pike 5.48 2420 18 log lua 5.77 576 17 log python 8.88 1492 27 log rep 9.39 1180 31 log java 10.80 8892 68 log gawk 13.89 892 32 log ruby 14.31 1452 23 log tcl 30.36 1092 20 log guile 30.69 1768 44 log gforth 37.50 700 87 log erlang 58.03 2996 72 log Languages that compile to native code are in Bold Italics.

[Note: Values have been normalized to fall in the range of 0-10 for aesthetic reasons. Original value ranges are included on the X-axis. Click here for more detailed data and graphs. [Results last updated: Sun Sep 9 13:20:25 2001 CDT]

About this test

Please Note: this test is due for an overhaul, because of the variety of solutions for this test that aren't really using regular expressions. I'll probably split this into 2 tests, one that does some kind of parsing/pattern matching, and another that calls for NFA regular expressions with capture buffers.

For this test, each program should be implemented in the same way.

The purpose of this test is to extract strings that look like phone numbers from a file and print them in a standard format. For the sake of this test, we aren't interested in I/O performance, so we read the file into an array before starting, then extract the phone numbers from the array N times, and on the last iteration, we print the extracted numbers in the standard format. See the detail page for different values of N.

Each program can assume that no line will exceed 128 characters (including newline).

Input file. Output file.

The telephone number pattern we are trying to match can be described this way:

• there may be zero or one telephone numbers per line of input.
• a telephone number may start at the beginning of the line or be preceeded by a non-digit, (which may be preceeded by anything).
• it begins with a 3-digit area code that looks like this (DDD) or DDD (where D is [0-9]).
• the area code is followed by one space,
• which is followed by the 3 digits of the exchange: DDD
• the exchange is followed by a space or hyphen [ -]
• which is followed by the last 4 digits: DDDD
• which can be followed by end of line or a non-digit (which may be followed by anything).

For the C program I wasn't going to implement my own regular expressions from scratch, I use the Perl Compatible Regular Expressions (PCRE) library.

The C++ program uses Bill Lear's PCRE library for C++.

Markus Mottl helped me use his PCRE library for Ocaml.

The Java program uses a 3rd party, mostly-Perl5-compatible regexp library, called ORO. Apparently this package, once available from oroinc.com (defunct), is now maintained by the Apache Jakarta project.

Bigloo's regular grammar facility is very powerful. I wish all languages offered this feature. I think it shows that while it's nice to be able to do complex pattern matching, it is really more important how easily you can do something with the matched data.

I have been a little sloppy in this test specification, and some languages don't implement the same exact pattern matching. I'll try to fix this soon by adding more test strings to the input to take care of some of the sloppy cases.

Observations

Erlang's regular expression support is minimal, it doesn't support captures (backreferences), and strings are represented as linked lists, so it doesn't do very well on this test.