« August 2017 | Main | October 2017 »
Friday, September 29, 2017
Floating Point Benchmark: Prolog Language Added
I have posted an update to my trigonometry-intense floating point benchmark which adds Prolog to the list of languages in which the benchmark is implemented. A new release of the benchmark collection including Prolog is now available for downloading. Prolog is a language designed for logic programming. Working in conjunction with a database of facts and rules, one can make queries which are answered by applying the rules of formal logic. Thus, in Prolog, one often describes the answer one seeks and lets the language implementation find it rather than prescribing the steps through which the answer is obtained as one would in a conventional imperative programming language. Prolog is used in artificial intelligence and computational linguistics research, and is well-suited to the analysis of unstructured natural language. Components of IBM's Watson question answering system are written in Prolog. The first Prolog system was developed in 1972, and the language was standardised as ISO/IEC 13211-1 in 1995, with subsequent corrigenda in 2007 and 2012. Prolog is intended for problems which are nothing like that performed by the floating point benchmark, which is a typical scientific computing task involving floating point numbers and trigonometric functions. However, Prolog supports floating point numbers and trigonometric functions, and as a Turing-complete language is able to perform any computational task which can be programmed in any other such language. So, this can be considered as a case of misusing Prolog for a task for which it wasn't remotely intended, with the goal of seeing how well it expresses the algorithms and performs. The resulting program uses very little of Prolog's sophisticated pattern-matching and inference engine: the task simply doesn't require these facilities. Instead, Prolog is used as a functional programming language, employing its variables to pass arguments to and return values from functions coded as Prolog rules. The result looks somewhat odd to those accustomed to other programming languages, but one you get used to the syntax, the code is expressive and comprehensible. Pattern matching allows replacing all of the conditionals for the four cases of the transit_surface operation (marginal or paraxial ray, flat or curved surface) with four different rules selected by the arguments passed to them, as done in functional languages such as Haskell and Erlang. I originally developed this benchmark on GNU Prolog version 1.4.4, but when I went to run the benchmark for an archival run time of around five minutes, I ran into the problem that GNU Prolog does not fully implement tail call optimisation. What does this mean? Prolog, like many functional languages, does not provide control structures for iteration. Instead, iteration is accomplished by recursion. For example, here's how you might write the factorial function in C using iteration:
int factorial(int n) {
int result = 1;
int i;
for (i = 1; i <= n; i++) {
result *= i;
}
return result;
}
But Prolog has no equivalent of C's for statement, so you define
the factorial function recursively as it's usually expressed in
mathematics:
fact(N, NF) :-
fact(1, N, 1, NF).
fact(X, X, F, F) :- !.
fact(X, N, FX, F) :-
X1 is X + 1,
FX1 is FX * X1,
fact(X1, N, FX1, F).
Now, this looks a bit odd until you become accustomed to the
rather eccentric syntax of Prolog, but the key thing to take
away is that evaluation is accomplished by the four argument
definition of fact(). When the final definition of fact() calls
itself, it is the last item executed, and tail call optimisation
takes note of this and, instead of recursively calling itself,
uses the same stack frame and transforms the recursion into an
iteration. This allows recursion to an arbitrary depth without
consuming large amounts of stack memory.
Tail call optimisation is common among languages such as Lisp,
Haskell, and Prolog, but GNU Prolog does not implement it, or at
least doesn't do so in a sufficiently general manner as to
permit running benchmarks with a large number of iterations.
As a result, I moved the project from GNU Prolog to SWI-Prolog:
a mature Prolog system which properly supports tail call
optimisation. I used Linux version 7.6.0-rc2, which is a stable
and complete implementation of Prolog, using the 64-bit Ubuntu
installation package.
Development of the program was straightforward, with the only
speed bumps my coming to terms with the Prolog way of doing
things. This program constitutes an “abuse of language” almost
as extreme as the COBOL version. Prolog is intended for logic
programming where its underlying inference engine does most of
the work in resolving queries where the programmer specifies a
way to find the answer but not the details of how it is to be
evaluated. Optical design ray tracing couldn't be more
different—the computations must be evaluated procedurally, so I
ended up using Prolog as a functional programming langauge,
writing procedural code as ∧ expressions within rules, while
taking advantage of Prolog's polymorphism and pattern matching
to make the code more expressive of the problem being solved.
Since Prolog provides full support for floating point arithmetic
and trigonometric functions, there were no problems in
evaluating the expressions used in the benchmark.
After testing the benchmark in SWI-Prolog for accuracy, I ran
the Prolog benchmark for 13,725,893 iterations and obtained the
following run times in seconds for five runs:
(287.14,
286.64,
288.11,
288.15,
286.38)
These runs give a mean time of 287.284 seconds, or 20.9301
microseconds per iteration.
I then ran the C benchmark for 166,051,660 iterations, yielding
run times of:
(296.89,
296.37,
296.29,
296.76,
296.37)
seconds, with mean 296.536, for 1.7858 microseconds per
iteration.
Dividing these gives a SWI-Prolog run time of 11.7203 longer
than that of C. In other words, for this benchmark, SWI-Prolog
runs around 11.72 times slower than C.
I next wanted to compare GNU Prolog with C. Because of the lack
of tail call optimisation, I was unable to run the benchmark for
the required number of iterations to obtain an “on the record”
run of about five minutes (even when I tried tricks of nesting
iterations in calls), so I estimated its performance as follows.
I ran the benchmark on GNU Prolog with 450000 iterations, which
was the maximum I could use after setting “export
GLOBALSZ=80000000000” to create an enormous global stack. I
received the following timings in seconds:
(4.37,
4.36,
4.41,
4.33,
4.32)
of which the mean is 4.358 seconds.
Then, I ran the same benchmark under SWI-Prolog and measured:
(8.90,
8.80,
8.79,
8.99,
8.96)
for a mean of 8.888. This gives a run time ratio of GNU Prolog
to SWI-Prolog of 0.49032, and applying this to the measured
ratio of SWI-Prolog to C, we can infer a ratio of GNU Prolog to
C of 5.7467.
I do not report this as a primary benchmark for GNU Prolog
because its lack of tail call optimisation prevented it from
fulfilling the conditions of the benchmark: a run of around five
minutes. It is, however, indicative of the performance of
Prolog which can be obtained by compiling to native code, and is
included because it demonstrates that Prolog can perform within
the range of other compiled languages.
In summary, Prolog did pretty well on this job for which it
wasn't designed. The program is straightforward and readable,
and the performance in SWI-Prolog is comparable to other
languages which compile to byte code, as does this Prolog
implementation. GNU Prolog, which compiles to native machine
code, performed better than GNU Common Lisp in compiled mode,
but toward the slow end of machine code compilers (but, since
the full benchmark could not be run, the GNU Prolog results are
not archival).
This directory includes a Makefile which can build the benchmark
using either SWI-Prolog of GNU Prolog (which, of course, must be
installed on your machine). The SWI-Prolog version of the
benchmark uses that system's nonstandard three argument format/3
predicate to print its results to Prolog atoms, allowing the
program to perform its own accuracy test at the completion of
the benchmark. GNU Prolog and the ISO standard do not implement
this extension, so alternative code is used which simply prints
the output of the last iteration of the benchmark to standard
output where it is compared with the expected results with diff.
The relative performance of the various language implementations (with C taken as 1) is as follows. All language implementations of the benchmark listed below produced identical results to the last (11th) decimal place.
| Language | Relative Time |
Details |
|---|---|---|
| C | 1 | GCC 3.2.3 -O3, Linux |
| Visual Basic .NET | 0.866 | All optimisations, Windows XP |
| FORTRAN | 1.008 | GNU Fortran (g77) 3.2.3 -O3, Linux |
| Pascal | 1.027 1.077 |
Free Pascal 2.2.0 -O3, Linux GNU Pascal 2.1 (GCC 2.95.2) -O3, Linux |
| Swift | 1.054 | Swift 3.0.1, -O, Linux |
| Rust | 1.077 | Rust 0.13.0, --release, Linux |
| Java | 1.121 | Sun JDK 1.5.0_04-b05, Linux |
| Visual Basic 6 | 1.132 | All optimisations, Windows XP |
| Haskell | 1.223 | GHC 7.4.1-O2 -funbox-strict-fields, Linux |
| Scala | 1.263 | Scala 2.12.3, OpenJDK 9, Linux |
| Ada | 1.401 | GNAT/GCC 3.4.4 -O3, Linux |
| Go | 1.481 | Go version go1.1.1 linux/amd64, Linux |
| Simula | 2.099 | GNU Cim 5.1, GCC 4.8.1 -O2, Linux |
| Lua | 2.515 22.7 |
LuaJIT 2.0.3, Linux Lua 5.2.3, Linux |
| Python | 2.633 30.0 |
PyPy 2.2.1 (Python 2.7.3), Linux Python 2.7.6, Linux |
| Erlang | 3.663 9.335 |
Erlang/OTP 17, emulator 6.0, HiPE [native, {hipe, [o3]}] Byte code (BEAM), Linux |
| ALGOL 60 | 3.951 | MARST 2.7, GCC 4.8.1 -O3, Linux |
| PL/I | 5.667 | Iron Spring PL/I 0.9.9b beta, Linux |
| Lisp | 7.41 19.8 |
GNU Common Lisp 2.6.7, Compiled, Linux GNU Common Lisp 2.6.7, Interpreted |
| Smalltalk | 7.59 | GNU Smalltalk 2.3.5, Linux |
| Forth | 9.92 | Gforth 0.7.0, Linux |
| Prolog | 11.72 5.747 |
SWI-Prolog 7.6.0-rc2, Linux GNU Prolog 1.4.4, Linux, (limited iterations) |
| COBOL | 12.5 46.3 |
Micro Focus Visual COBOL 2010, Windows 7 Fixed decimal instead of computational-2 |
| Algol 68 | 15.2 | Algol 68 Genie 2.4.1 -O3, Linux |
| Perl | 23.6 | Perl v5.8.0, Linux |
| Ruby | 26.1 | Ruby 1.8.3, Linux |
| JavaScript | 27.6 39.1 46.9 |
Opera 8.0, Linux Internet Explorer 6.0.2900, Windows XP Mozilla Firefox 1.0.6, Linux |
| QBasic | 148.3 | MS-DOS QBasic 1.1, Windows XP Console |
| Mathematica | 391.6 | Mathematica 10.3.1.0, Raspberry Pi 3, Raspbian |
Posted at
20:56
Sunday, September 24, 2017
Floating Point Benchmark: PL/I Language Added
I have posted an update to my trigonometry-intense floating point benchmark which adds PL/I to the list of languages in which the benchmark is implemented. A new release of the benchmark collection including PL/I is now available for downloading. I have always had a fondness for PL/I. Sure, it was an archetypal product of IBM at the height of the supremacy of Big Blue, and overreached and never completely achieved its goals, but it was a product of the 1960s, when technological ambition imagined unifying programming languages as diverse as Fortran, COBOL, and Algol into a single language which would serve for all applications and run on platforms ranging from the most humble to what passed for supercomputers at the time. It was the choice for the development of Multics, one of the most ambitious operating system projects of all time (and, after its wave of enthusiasm broke on the shore of reality, inspired Unix), and the C language inherits much of its syntax and fundamentals from PL/I. Few people recall today, but the first version of AutoCAD shipped to customers was written in PL/I. When we were developing AutoCAD in 1982, we worked in parallel, using Digital Research's PL/I-80 (a subset of PL/I, but completely adequate for the needs of AutoCAD) on 8080/Z-80 CP/M systems and C on 8086/8088 machines. As it happened, AutoCAD-80, the PL/I version, shipped first, so the first customer who purchased AutoCAD received a version written in PL/I. The goal of PL/I was the grand unification of programming languages, which had bifurcated into a scientific thread exemplified by Fortran and variants of Algol and a commercial thread in which COBOL was dominant. The idea was that a single language, and a single implementation would serve for all, and that programmers working in a specific area could learn the subset applicable to their domain, ignoring features irrelevant to the tasks they programmed. By the standards of the time, the language feature set was ambitious. Variables could be declared in binary or decimal, fixed point or floating, with variable precision. Complex structures and arrays could be defined, including arrays of structures and structures containing arrays. A variety of storage classes were available, allowing the creation of dynamically or manually allocated storage, and access through pointers. Support for recursive procedures and reentrant code was included. The language was defined before the structured programming craze, but its control structures are adequate to permit structured programming should a programmer choose that style. Object orientation was undreamt of at the time, and support for it was added only much later. Iron Spring Software is developing a reasonably complete implementation of PL/I which runs on Linux and OS/2. It adheres to ANSI standard X3.74-1987 (ISO/IEC 6522:1992), the so-called “Subset G” of the language, but, in its present beta releases, does not support all features of the standard, The current state of the beta version is documented in the Programming Guide. With one exception (the ASIN mathematical builtin function), none of the missing features are required by the floating point benchmark, and ASIN is easily emulated by the identity (expressed in PL/I)asin(x) = atan(x, sqrt(1 − (x * x)))
implemented as a procedure in the program. The Iron Spring PL/I compiler is closed source, and will be offered for sale upon general release, but during the beta period downloads are free. The runtime libraries (much of which are written in PL/I) are open source and licensed under the GNU Lesser General Public License (LGPL). There are no restrictions or licenses required to redistribute programs compiled by the compiler and linked with its libraries. This version of the benchmark was developed using the 0.9.9b beta release of the Iron Spring PL/I compiler. Current Linux downloads are 32-bit binaries and produce 32-bit code, but work on 64-bit systems such as the one on which I tested it. It is possible that a native 64-bit version of the compiler and libraries might outperform 32-bit code run in compatibility mode, but there is no way at present to test this. The PL/I implementation of Fbench is a straightforward port derived from the Ada version of the program, using the same imperative style of programming and global variables. All floating point values are declared as FLOAT BINARY(49), which maps into IEEE double-precision (64 bit) floating point. As noted above, the missing ASIN (arc sine) builtin function was emulated by an internal procedure named l_asin to avoid conflict with the builtin on compilers which supply it. Development of the program was straightforward, and after I recalled the idioms of a language in which I hadn't written code for more than thirty years, the program basically worked the first time. Support for the PUT STRING facility allowed making the program self-check its results without any need for user interaction. To avoid nonstandard system-dependent features, the iteration count for the benchmark is compiled into the program. After I get the benchmark running and have confirmed that it produces the correct values, I then time it with an modest iteration count, then adjust the iteration count to obtain a run time of around five minutes, which minimises start-up and termination effects and accurately reflects execution speed of the heart of the benchmark. Next, I run the benchmark five times on an idle system, record the execution times, compute the mean value, and from that calculate the time in microseconds per iteration. This is then compared with the same figure from runs of the C reference implementation of the benchmark to obtain the relative speed of the language compared to C. When I first performed this process, it was immediately apparent that something had seriously gang agley. The C version of the benchmark ran at 1.7858 microseconds per iteration, while the PL/I implementation took an aching 95.1767 microseconds/iteration—fully 53 times slower! This was, in its own way, a breathtaking result. Most compiled languages come in between somewhere between the speed of C and four times slower, with all of the modern heavy-hitter languages (Fortran, Pascal, Swift, Rust, Java, Haskell, Scala, Ada, and Go) benchmarking no slower than 1.5 times the C run time. Most interpreted languages (Perl, Python, Ruby) still benchmark around twice as fast as this initial PL/I test. It was time to start digging into the details. First of all, I made sure that all of the floating point variables were properly defined and didn't, for example, declare variables as fixed decimal. When I tried this with the COBOL version of the benchmark, I indeed got a comparable execution time (46 times slower than C). But the variables were declared correctly, and examination of the assembly language listing of the code generated by the compiler confirmed that it was generating proper in-line floating-point instructions instead of some horror such as calling library routines for floating point arithmetic. Next, I instrumented the program to verify that I hadn't blundered and somehow made it execute more iterations of the inner loop than were intended. I hadn't. This was becoming quite the mystery. It was time to take a deeper look under the hood. I downloaded, built, and installed OProfile, a hardware-supported statistical profiling tool which, without support by the language (which is a good thing, because the PL/I compiler doesn't provide any) allows measurement of the frequency of instruction execution within a program run under its supervision. I ran the benchmark for five minutes under OProfile:
operf ./fbench
(because the profiling process uses restricted kernel calls, this must be done as the super-user), and then annotated the results with:
opannotate --source --assembly fbench >fbench.prof The results were flabbergasting. I was flabber-aghast to discover that in the entire five minute run, only 5.6% of the time was spent in my benchmark program: all the rest was spent in system libraries! Looking closer, one of the largest time sinks was the PL/I EXP builtin function, which was distinctly odd, since the program never calls this function. I looked at the generated assembly code and discovered, however, that if you use the normal PL/I or Fortran idiom of “x ** 2” to square a value, rather than detecting the constant integer exponent and compiling the equivalent code of “x * x”, the compiler was generating a call to the general exponential function, able to handle arbitrary floating point exponents. I rewrote the three instances in the program where the “**” operator appeared to use multiplication, and when I re-ran the benchmark it was almost ten times faster (9.4 times to be precise)! Examination of the Oprofile output from this version showed that 44% of the time was spent in the benchmark, compared to 5.6% before, with the rest divided mostly among the mathematical library builtin functions used by the program. Many of the library functions which chewed up time in the original version were consequences of the calls on EXP and melted away when it was replaced by multiplication. Further experiments showed that these library functions, most written in PL/I, were not particularly efficient: replacing the builtin ATAN function with my own implementation ported from the INTRIG version of the C benchmark sped up the benchmark by another 6%. But the goal of the benchmark is to test the compiler and its libraries as supplied by the vendor, not to rewrite the libraries to tweak the results, so I set this version aside and proceeded with timing tests. I ran the PL/I benchmark for 29,592,068 iterations and obtained the following run times in seconds for five runs (299.23, 300.59, 298.52, 300.94, 298.07). These runs give a mean time of 299.47 seconds, or 10.1209 microseconds per iteration. I then ran the C benchmark for 166,051,660 iterations, yielding run times of (296.89, 296.37, 296.29, 296.76, 296.37) seconds, with mean 296.536, for 1.7858 microseconds per iteration. Dividing these gives a PL/I run time of 5.667 longer than that of C. In other words, for this benchmark, PL/I runs around 5.7 times slower than C. This is toward the low end of compiled languages in which the benchmark has been implemented. Among those tested so far, it falls between ALGOL 60 (3.95 times C) and GNU Common Lisp (compiled, 7.41 times C), and it is more than twice as fast as Micro Focus Visual COBOL in floating point mode (12.5 times C). It should be remembered, however, that this is a beta test compiler under active development, and that optimisation is often addressed after full implementation of the language. And since the libraries are largely written in PL/I, any optimisation of compiler-generated code will improve library performance as well. The lack of optimisation of constant integer exponents which caused the initial surprise in timing tests will, one hopes, be addressed in a subsequent release of the compiler. Further, the second largest consumer of time in the benchmark, after the main program itself with 44%, was the ATAN function, with 23.6%. But the ATAN function is only used to emulate the ASIN builtin, which isn't presently implemented. If and when an ASIN function is provided, and if its implementation is more efficient (for example, using a Maclaurin series) than my emulation, a substantial increase in performance will be possible. Nothing inherent in the PL/I language limits its performance. Equivalent code, using the same native data types, should be able to run as fast as C or Fortran, and mature commercial compilers from IBM and other vendors have demonstrated this performance but at a price. The Iron Spring compiler is a promising effort to deliver a professional quality PL/I compiler for personal computers at an affordable price (and, in its present beta test incarnation, for free). The relative performance of the various language implementations (with C taken as 1) is as follows. All language implementations of the benchmark listed below produced identical results to the last (11th) decimal place.
| Language | Relative Time |
Details |
|---|---|---|
| C | 1 | GCC 3.2.3 -O3, Linux |
| Visual Basic .NET | 0.866 | All optimisations, Windows XP |
| FORTRAN | 1.008 | GNU Fortran (g77) 3.2.3 -O3, Linux |
| Pascal | 1.027 1.077 |
Free Pascal 2.2.0 -O3, Linux GNU Pascal 2.1 (GCC 2.95.2) -O3, Linux |
| Swift | 1.054 | Swift 3.0.1, -O, Linux |
| Rust | 1.077 | Rust 0.13.0, --release, Linux |
| Java | 1.121 | Sun JDK 1.5.0_04-b05, Linux |
| Visual Basic 6 | 1.132 | All optimisations, Windows XP |
| Haskell | 1.223 | GHC 7.4.1-O2 -funbox-strict-fields, Linux |
| Scala | 1.263 | Scala 2.12.3, OpenJDK 9, Linux |
| Ada | 1.401 | GNAT/GCC 3.4.4 -O3, Linux |
| Go | 1.481 | Go version go1.1.1 linux/amd64, Linux |
| Simula | 2.099 | GNU Cim 5.1, GCC 4.8.1 -O2, Linux |
| Lua | 2.515 22.7 |
LuaJIT 2.0.3, Linux Lua 5.2.3, Linux |
| Python | 2.633 30.0 |
PyPy 2.2.1 (Python 2.7.3), Linux Python 2.7.6, Linux |
| Erlang | 3.663 9.335 |
Erlang/OTP 17, emulator 6.0, HiPE [native, {hipe, [o3]}] Byte code (BEAM), Linux |
| ALGOL 60 | 3.951 | MARST 2.7, GCC 4.8.1 -O3, Linux |
| PL/I | 5.667 | Iron Spring PL/I 0.9.9b beta, Linux |
| Lisp | 7.41 19.8 |
GNU Common Lisp 2.6.7, Compiled, Linux GNU Common Lisp 2.6.7, Interpreted |
| Smalltalk | 7.59 | GNU Smalltalk 2.3.5, Linux |
| Forth | 9.92 | Gforth 0.7.0, Linux |
| COBOL | 12.5 46.3 |
Micro Focus Visual COBOL 2010, Windows 7 Fixed decimal instead of computational-2 |
| Algol 68 | 15.2 | Algol 68 Genie 2.4.1 -O3, Linux |
| Perl | 23.6 | Perl v5.8.0, Linux |
| Ruby | 26.1 | Ruby 1.8.3, Linux |
| JavaScript | 27.6 39.1 46.9 |
Opera 8.0, Linux Internet Explorer 6.0.2900, Windows XP Mozilla Firefox 1.0.6, Linux |
| QBasic | 148.3 | MS-DOS QBasic 1.1, Windows XP Console |
| Mathematica | 391.6 | Mathematica 10.3.1.0, Raspberry Pi 3, Raspbian |
Posted at
15:17
Friday, September 15, 2017
Tom Swift and His Electric Runabout updated, EPUB added
All 25 of the public domain Tom Swift novels have been posted in the Tom Swift and His Pocket Library collection. I am now returning to the earlier novels, upgrading them to use the more modern typography of those I've done in recent years. The fifth novel in the series, Tom Swift and His Electric Runabout, has now been updated. Several typographical errors in the original edition have been corrected, Unicode text entities are used for special characters such as single and double quotes and dashes, and the HTML version is now XHTML 1.0 Strict. An EPUB edition of this novel is now available which may be downloaded to compatible reader devices; the details of how to do this differ from device to device—please consult the documentation for your reader for details. Tom Swift's electric car, described in this 1910 novel, compares quite favourably with those on the market more than a century later. Top speed was one hundred miles an hour, and in chapter four Tom says of range on a battery charge, “Well, if I can make it do three hundred miles I'll be satisfied, but I'm going to try for four hundred.” But in case the battery runs down and there's no charging station nearby, Tom has a trick up his sleeve even Elon Musk can't exploit. Asked by his father, “Suppose you're not near a charging station?”, Tom replies, “…I'm going to have it fixed so I can take current from any trolley line, as well as from a regular charging station. My battery will be capable of being recharged very quickly, or, in case of need, I can take out the old cells and put in new ones.” In 1910, interurban trolley lines were ubiquitous in the eastern United States, so the intrepid motorist, seeing the charge gauge creeping down toward zero, need only divert to the nearest trolley line, hook up to the rail and overhead wire or third rail, and before long everything would be just tickey-boo. No thief, the young Swift remarks, “ ‘I'm going to pay for the current I use,’ explained the young inventor. ‘I have a meter which tells how much I take.’ ”Posted at
13:58
Tuesday, September 12, 2017
UNUM Updated to Unicode 10, HTML5
I have just posted version 2.1 of UNUM. This update, the first since 2006, updates the database of Unicode characters to Unicode version 10.0.0 (June 2017) and adds, for the first time, full support for the entire set of Chinese, Japanese, and Korean (CJK) ideographic characters, for a total of 136,755 characters in all. CJK characters are identified by their nomenclature in commonly used lexicons, and, where specified in the Unicode database, English definitions. The table of HTML named character references (the sequences like “<” you use in HTML source code when you need to represent a character which has a syntactic meaning in HTML or which can't be directly included in a file with the character encoding you're using to write it) has been updated to the list published by the World Wide Web Consortium (W3C) for HTML5. It used to be that HTML named character references were a convenient text-based shorthand so that, for example, if your keyboard or content management system didn't have a direct way to specify the Unicode character for a right single quote, you could write “’” instead of “’”, the numeric code for the character. This was handy, made the HTML easier to understand, and made perfect sense and so, of course, it had to be “improved”. Now, you can specify the same character as either “’”, “’”, or “’” as well. “Close Curly Quote”—are there also Larry and Moe quotes? Now, apparently to accommodate dim people who can't remember or be bothered to look up the standard character references which have been in use for more than a decade (and how many of them are writing HTML, anyway?), we have lost the ability to provide a unique HTML character reference for Unicode code points which have them. In other words, the mapping from code points to named character references has gone from one-to-one to one-to-many. Further, named character references have been extended from a symbolic nomenclature for Unicode code points to specify logical character definitions which are composed of multiple (all the current ones specify only two) code points which are combined to generate the character. For example, the character reference “≫̸”, which stands for the mathematical symbol “not much greater than”, is actually composed of code points U+226B (MUCH GREATER-THAN) and U+0338 (COMBINING LONG SOLIDUS OVERLAY). Previously, UNUM could assume a one-to-one mapping between HTML character references and Unicode code points, but thanks to these innovations this is no longer the case. Now, when a character is displayed, if it has more than one HTML name, they are all displayed in the HTML column, separated by commas. If the user looks up a composite character reference, all of the Unicode code points which make it up are displayed, one per line, in the order specified in the W3C specification. The addition of the CJK characters makes the code point definition table, which was already large, simply colossal. The Perl code for UNUM including this table is now almost eight megabytes. To cope with this, there is now a compressed version of UNUM in which the table is compressed with the bzip2 utility, which reduces the size of the program to less than a megabyte. This requires a modern version of Perl and a Unix-like system on which bzip2 is installed. Users who lack these prerequisites may download an uncompressed version of UNUM, which will work in almost any environment which can run Perl. UNUM Documentation and Download Page Update: Version 2.2 improves compatibility of the compressed version of the utility by automatically falling back to Perl's core IO::Uncompress::Bunzip2 module if the host system does not have bunzip2 installed. (2017-09-19 18:47 UTC)Posted at
23:35
Saturday, September 9, 2017
Floating Point Benchmark: Scala Language Added
I have posted an update to my trigonometry-intense floating point benchmark which adds Scala to the list of languages in which the benchmark is implemented. A new release of the benchmark collection including Scala is now available for downloading. Scala is a general purpose programming language originally developed at the École Polytechnique Fédérale in Lausanne, Switzerland. Scala combines the paradigm of functional programming with support for conventional object-oriented imperative programming, allowing the programmer to choose whichever style is most expressive of the algorithm being implemented. Unlike Haskell, which forces the programmer into a strict functional style, Scala contains control structures for iteration, mutable variables, and a syntax which C and Java programmers will find familiar. Scala runs on the Java virtual machine, and Scala and Java code can interoperate, which provides Scala access to all existing Java libraries. The Scala version of the benchmark was developed and tested using Scala 2.12.3 on an x86_64 machine running Xubuntu 16.04 kernel 4.4.0-93. In order to compile and run this program you must install Scala on your computer. Scala programs compile to byte code which is executed by an implementation of the Java virtual machine. I ran these tests using:openjdk version "9-internal"The Scala implementation of the floating point benchmark is written mostly in a pure functional style, but I did use mutable variables and iteration where it made the code more readable. Scala does not optimise tail recursion as aggressively as Haskell, so iteration may be more efficient in heavily-used code. At the time I developed this benchmark, a recent release of the GNU C mathematical function library had been issued which halved the mean execution speed of trigonometric functions. This made all comparisons of run time against the C reference implementation of the benchmark using the earlier, more efficient libraries, invalid. (It's said that the performance hit was done in the interest of improved accuracy, but it made no difference in the computations of the floating point benchmark, which are checked to 13 significant digits.) Consequently, I compared the execution speed of the Scala implementation against that of the Java version, then computed the speed relative to the original C version with the old libraries by multiplying the relative speed of Java vs. C and Scala vs. Java. The relative performance of the various language implementations (with C taken as 1) is as follows. All language implementations of the benchmark listed below produced identical results to the last (11th) decimal place.
OpenJDK Runtime Environment (build 9-internal+0-2016-04-14-195246.buildd.src)
OpenJDK 64-Bit Server VM (build 9-internal+0-2016-04-14-195246.buildd.src, mixed mode)
| Language | Relative Time |
Details |
|---|---|---|
| C | 1 | GCC 3.2.3 -O3, Linux |
| Visual Basic .NET | 0.866 | All optimisations, Windows XP |
| FORTRAN | 1.008 | GNU Fortran (g77) 3.2.3 -O3, Linux |
| Pascal | 1.027 1.077 |
Free Pascal 2.2.0 -O3, Linux GNU Pascal 2.1 (GCC 2.95.2) -O3, Linux |
| Swift | 1.054 | Swift 3.0.1, -O, Linux |
| Rust | 1.077 | Rust 0.13.0, --release, Linux |
| Java | 1.121 | Sun JDK 1.5.0_04-b05, Linux |
| Visual Basic 6 | 1.132 | All optimisations, Windows XP |
| Haskell | 1.223 | GHC 7.4.1-O2 -funbox-strict-fields, Linux |
| Scala | 1.263 | Scala 2.12.3, OpenJDK 9, Linux |
| Ada | 1.401 | GNAT/GCC 3.4.4 -O3, Linux |
| Go | 1.481 | Go version go1.1.1 linux/amd64, Linux |
| Simula | 2.099 | GNU Cim 5.1, GCC 4.8.1 -O2, Linux |
| Lua | 2.515 22.7 |
LuaJIT 2.0.3, Linux Lua 5.2.3, Linux |
| Python | 2.633 30.0 |
PyPy 2.2.1 (Python 2.7.3), Linux Python 2.7.6, Linux |
| Erlang | 3.663 9.335 |
Erlang/OTP 17, emulator 6.0, HiPE [native, {hipe, [o3]}] Byte code (BEAM), Linux |
| ALGOL 60 | 3.951 | MARST 2.7, GCC 4.8.1 -O3, Linux |
| Lisp | 7.41 19.8 |
GNU Common Lisp 2.6.7, Compiled, Linux GNU Common Lisp 2.6.7, Interpreted |
| Smalltalk | 7.59 | GNU Smalltalk 2.3.5, Linux |
| Forth | 9.92 | Gforth 0.7.0, Linux |
| COBOL | 12.5 46.3 |
Micro Focus Visual COBOL 2010, Windows 7 Fixed decimal instead of computational-2 |
| Algol 68 | 15.2 | Algol 68 Genie 2.4.1 -O3, Linux |
| Perl | 23.6 | Perl v5.8.0, Linux |
| Ruby | 26.1 | Ruby 1.8.3, Linux |
| JavaScript | 27.6 39.1 46.9 |
Opera 8.0, Linux Internet Explorer 6.0.2900, Windows XP Mozilla Firefox 1.0.6, Linux |
| QBasic | 148.3 | MS-DOS QBasic 1.1, Windows XP Console |
| Mathematica | 391.6 | Mathematica 10.3.1.0, Raspberry Pi 3, Raspbian |
Posted at
13:38
Wednesday, September 6, 2017
Reading List: Making Contact
- Scoles, Sarah. Making Contact. New York: Pegasus Books, 2017. ISBN 978-1-68177-441-1.
- There are few questions in our scientific inquiry into the universe and our place within it more profound than “are we alone?” As we have learned more about our world and the larger universe in which it exists, this question has become ever more fascinating. We now know that our planet, once thought the centre of the universe, is but one of what may be hundreds of billions of planets in our own galaxy, which is one of hundreds of billions of galaxies in the observable universe. Not long ago, we knew only of the planets in our own solar system, and some astronomers believed planetary systems were rare, perhaps formed by freak encounters between two stars following their orbits around the galaxy. But now, thanks to exoplanet hunters and, especially, the Kepler spacecraft, we know that it's “planets, planets, everywhere”—most stars have planets, and many stars have planets where conditions may be suitable for the origin of life. If this be the case, then when we gaze upward at the myriad stars in the heavens, might there be other eyes (or whatever sense organs they use for the optical spectrum) looking back from planets of those stars toward our Sun, wondering if they are alone? Many are the children, and adults, who have asked themselves that question when standing under a pristine sky. For the ten year old Jill Tarter, it set her on a path toward a career which has been almost coterminous with humanity's efforts to discover communications from extraterrestrial civilisations—an effort which continues today, benefitting from advances in technology unimagined when she undertook the quest. World War II had seen tremendous advancements in radio communications, in particular the short wavelengths (“microwaves”) used by radar to detect enemy aircraft and submarines. After the war, this technology provided the foundation for the new field of radio astronomy, which expanded astronomers' window on the universe from the traditional optical spectrum into wavelengths that revealed phenomena never before observed nor, indeed, imagined, and hinted at a universe which was much larger, complicated, and violent than previously envisioned. In 1959, Philip Morrison and Guiseppe Cocconi published a paper in Nature in which they calculated that using only technologies and instruments already existing on the Earth, intelligent extraterrestrials could send radio messages across the distances to the nearby stars, and that these messages could be received, detected, and decoded by terrestrial observers. This was the origin of SETI—the Search for Extraterrestrial Intelligence. In 1960, Frank Drake used a radio telescope to search for signals from two nearby star systems; he heard nothing. As they say, absence of evidence is not evidence of absence, and this is acutely the case in SETI. First of all, consider that you must first decide what kind of signal aliens might send. If it's something which can't be distinguished from natural sources, there's little hope you'll be able to tease it out of the cacophony which is the radio spectrum. So we must assume they're sending something that doesn't appear natural. But what is the variety of natural sources? There's a dozen or so Ph.D. projects just answering that question, including some surprising discoveries of natural sources nobody imagined, such as pulsars, which were sufficiently strange that when first observed they were called “LGM” sources for “Little Green Men”. On what frequency are they sending (in other words, where do we have to turn our dial to receive them, for those geezers who remember radios with dials)? The most efficient signals will be those with a very narrow frequency range, and there are billions of possible frequencies the aliens might choose. We could be pointed in the right place, at the right time, and simply be tuned to the wrong station. Then there's that question of “the right time”. It would be absurdly costly to broadcast a beacon signal in all directions at all times: that would require energy comparable to that emitted by a star (which, if you think about it, does precisely that). So it's likely that any civilisation with energy resources comparable to our own would transmit in a narrow beam to specific targets, switching among them over time. If we didn't happen to be listening when they were sending, we'd never know they were calling. If you put all of these constraints together, you come up with what's called an “observational phase space”—a multidimensional space of frequency, intensity, duration of transmission, angular extent of transmission, bandwidth, and other parameters which determine whether you'll detect the signal. And that assumes you're listening at all, which depends upon people coming up with the money to fund the effort and pursue it over the years. It's beyond daunting. The space to be searched is so large, and our ability to search it so limited, that negative results, even after decades of observation, are equivalent to walking down to the seashore, sampling a glass of ocean water, and concluding that based on the absence of fish, the ocean contained no higher life forms. But suppose you find a fish? That would change everything. Jill Tarter began her career in the mainstream of astronomy. Her Ph.D. research at the University of California, Berkeley was on brown dwarfs (bodies more massive than gas giant planets but too small to sustain the nuclear fusion reactions which cause stars to shine—a brown dwarf emits weakly in the infrared as it slowly radiates away the heat from the gravitational contraction which formed it). Her work was supported by a federal grant, which made her uncomfortable—what relevance did brown dwarfs have to those compelled to pay taxes to fund investigating them? During her Ph.D. work, she was asked by a professor in the department to help with an aged computer she'd used in an earlier project. To acquaint her with the project, the professor asked her to read the Project Cyclops report. It was a conversion experience. Project Cyclops was a NASA study conducted in 1971 on how to perform a definitive search for radio communications from intelligent extraterrestrials. Its report [18.2 Mb PDF], issued in 1972, remains the “bible” for radio SETI, although advances in technology, particularly in computing, have rendered some of its recommendations obsolete. The product of a NASA which was still conducting missions to the Moon, it was grandiose in scale, envisioning a large array of radio telescope dishes able to search for signals from stars up to 1000 light years in distance (note that this is still a tiny fraction of the stars in the galaxy, which is around 150,000 light years in diameter). The estimated budget for the project was between 6 and 10 billion dollars (multiply those numbers by around six to get present-day funny money) spent over a period of ten to fifteen years. The report cautioned that there was no guarantee of success during that period, and that the project should be viewed as a long-term endeavour with ongoing funding to operate the system and continue the search. The Cyclops report arrived at a time when NASA was downsizing and scaling back its ambitions: the final three planned lunar landing missions had been cancelled in 1970, and production of additional Saturn V launch vehicles had been terminated the previous year. The budget climate wasn't hospitable to Apollo-scale projects of any description, especially those which wouldn't support lots of civil service and contractor jobs in the districts and states of NASA's patrons in congress. Unsurprisingly, Project Cyclops simply landed on the pile of ambitious NASA studies that went nowhere. But to some who read it, it was an inspiration. Tarter thought, “This is the first time in history when we don't just have to believe or not believe. Instead of just asking the priests and philosophers, we can try to find an answer. This is an old and important question, and I have the opportunity to change how we try to answer it.” While some might consider searching the sky for “little green men” frivolous and/or absurd, to Tarter this, not the arcana of brown dwarfs, was something worthy of support, and of her time and intellectual effort, “something that could impact people's lives profoundly in a short period of time.” The project to which Tarter had been asked to contribute, Project SERENDIP (a painful acronym of Search for Extraterrestrial Radio Emissions from Nearby Developed Intelligent Populations) was extremely modest compared to Cyclops. It had no dedicated radio telescopes at all, nor even dedicated time on existing observatories. Instead, it would “piggyback” on observations made for other purposes, listening to the feed from the telescope with an instrument designed to detect the kind of narrow-band beacons envisioned by Cyclops. To cope with the problem of not knowing the frequency on which to listen, the receiver would monitor 100 channels simultaneously. Tarter's job was programming the PDP 8/S computer to monitor the receiver's output and search for candidate signals. (Project SERENDIP is still in operation today, employing hardware able to simultaneously monitor 128 million channels.) From this humble start, Tarter's career direction was set. All of her subsequent work was in SETI. It would be a roller-coaster ride all the way. In 1975, NASA had started a modest study to research (but not build) technologies for microwave SETI searches. In 1978, the program came into the sights of senator William Proxmire, who bestowed upon it his “Golden Fleece” award. The program initially survived his ridicule, but in 1982, the budget zeroed out the project. Carl Sagan personally intervened with Proxmire, and in 1983 the funding was reinstated, continuing work on a more capable spectral analyser which could be used with existing radio telescopes. Buffeted by the start-stop support from NASA and encouraged by Hewlett-Packard executive Bernard Oliver, a supporter of SETI from its inception, Tarter decided that SETI needed its own institutional home, one dedicated to the mission and able to seek its own funding independent of the whims of congressmen and bureaucrats. In 1984, the SETI Institute was incorporated in California. Initially funded by Oliver, over the years major contributions have been made by technology moguls including William Hewlett, David Packard, Paul Allen, Gordon Moore, and Nathan Myhrvold. The SETI Institute receives no government funding whatsoever, although some researchers in its employ, mostly those working on astrobiology, exoplanets, and other topics not directly related to SETI, are supported by research grants from NASA and the National Science Foundation. Fund raising was a skill which did not come naturally to Tarter, but it was mission critical, and so she mastered the art. Today, the SETI Institute is considered one of the most savvy privately-funded research institutions, both in seeking large donations and in grass-roots fundraising. By the early 1990s, it appeared the pendulum had swung once again, and NASA was back in the SETI game. In 1992, a program was funded to conduct a two-pronged effort: a targeted search of 800 nearby stars, and an all-sky survey looking for stronger beacons. Both would employ what were then state-of-the-art spectrum analysers able to monitor 15 million channels simultaneously. After just a year of observations, congress once again pulled the plug. The SETI Institute would have to go it alone. Tarter launched Project Phoenix, to continue the NASA targeted search program using the orphaned NASA spectrometer hardware and whatever telescope time could be purchased from donations to the SETI Institute. In 1995, observations resumed at the Parkes radio telescope in Australia, and subsequently a telescope at the National Radio Astronomy Observatory in Green Bank, West Virginia, and the 300 metre dish at Arecibo Observatory in Puerto Rico. The project continued through 2004. What should SETI look like in the 21st century? Much had changed since the early days in the 1960s and 1970s. Digital electronics and computers had increased in power a billionfold, not only making it possible to scan a billion channels simultaneously and automatically search for candidate signals, but to combine the signals from a large number of independent, inexpensive antennas (essentially, glorified satellite television dishes), synthesising the aperture of a huge, budget-busting radio telescope. With progress in electronics expected to continue in the coming decades, any capital investment in antenna hardware would yield an exponentially growing science harvest as the ability to analyse its output grew over time. But to take advantage of this technological revolution, SETI could no longer rely on piggyback observations, purchased telescope time, or allocations at the whim of research institutions: “SETI needs its own telescope”—one optimised for the mission and designed to benefit from advances in electronics over its lifetime. In a series of meetings from 1998 to 2000, the specifications of such an instrument were drawn up: 350 small antennas, each 6 metres in diameter, independently steerable (and thus able to be used all together, or in segments to simultaneously observe different targets), with electronics to combine the signals, providing an effective aperture of 900 metres with all dishes operating. With initial funding from Microsoft co-founder Paul Allen (and with his name on the project, the Allen Telescope Array), the project began construction in 2004. In 2007, observations began with the first 42 dishes. By that time, Paul Allen had lost interest in the project, and construction of additional dishes was placed on hold until a new benefactor could be found. In 2011, a funding crisis caused the facility to be placed in hibernation, and the observatory was sold to SRI International for US$ 1. Following a crowdfunding effort led by the SETI Institute, the observatory was re-opened later that year, and continues operations to this date. No additional dishes have been installed: current work concentrates on upgrading the electronics of the existing antennas to increase sensitivity. Jill Tarter retired as co-director of the SETI Institute in 2012, but remains active in its scientific, fundraising, and outreach programs. There has never been more work in SETI underway than at the present. In addition to observations with the Allen Telescope Array, the Breakthrough Listen project, funded at US$ 100 million over ten years by Russian billionaire Yuri Milner, is using thousands of hours of time on large radio telescopes, with a goal of observing a million nearby stars and the centres of a hundred galaxies. All data are available to the public for analysis. A new frontier, unimagined in the early days of SETI, is optical SETI. A pulsed laser, focused through a telescope of modest aperture, is able to easily outshine the Sun in a detector sensitive to its wavelength and pulse duration. In the optical spectrum, there's no need for fancy electronics to monitor a wide variety of wavelengths: all you need is a prism or diffraction grating. The SETI Institute has just successfully completed a US$ 100,000 Indiegogo campaign to crowdfund the first phase of the Laser SETI project, which has as its ultimate goal an all-sky, all-the-time search for short pulses of light which may be signals from extraterrestrials or new natural phenomena to which no existing astronomical instrument is sensitive. People often ask Jill Tarter what it's like to spend your entire career looking for something and not finding it. But she, and everybody involved in SETI, always knew the search would not be easy, nor likely to succeed in the short term. The reward for engaging in it is being involved in founding a new field of scientific inquiry and inventing and building the tools which allow exploring this new domain. The search is vast, and to date we have barely scratched the surface. About all we can rule out, after more than half a century, is a Star Trek-like universe where almost every star system is populated by aliens chattering away on the radio. Today, the SETI enterprise, entirely privately funded and minuscule by the standards of “big science”, is strongly coupled to the exponential growth in computing power and hence, roughly doubles its ability to search around every two years. The question “are we alone?” is one which has profound implications either way it is answered. If we discover one or more advanced technological civilisations (and they will almost certainly be more advanced than we—we've only had radio for a little more than a century, and there are stars and planets in the galaxy billions of years older than ours), it will mean it's possible to grow out of the daunting problems we face in the adolescence of our species and look forward to an exciting and potentially unbounded future. If, after exhaustive searches (which will take at least another fifty years of continued progress in expanding the search space), it looks like we're alone, then intelligent life is so rare that we may be its only exemplar in the galaxy and, perhaps, the universe. Then, it's up to us. Our destiny, and duty, is to ensure that this spark, lit within us, will never be extinguished.
Posted at
23:46