« September 2014 | Main | November 2014 »

Sunday, October 26, 2014

Floating Point Benchmark: Rust Language Added

I have posted an update to my trigonometry-intense floating point benchmark which adds Rust to the list of languages in which the benchmark is implemented. A new release of the benchmark collection including Rust is now available for downloading.

Rust is a systems programming language currently under development. It attempts to provide performance comparable to low-level programming languages such as C and C++ while avoiding common causes of crashes and security problems such as subscript and pointer errors, dangling pointers, memory leaks, and multi-thread race conditions. It is a compiled language with extensive compile-time checking which detects many errors which cause run-time errors in other languages, and has a reference-counted memory management architecture which avoids the overhead of garbage collection and provides critical section locking in multi-thread programs.

As a language actively under development, Rust is a moving target and any program developed for it may require modification as the language and run-time libraries evolve. This program was developed on version 0.13.0, and I encountered no problems with the language or libraries. Rust supports multiple programming paradigms: I chose to implement this program in a functional style with no mutable variables.

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
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
Free Pascal 2.2.0 -O3, Linux
GNU Pascal 2.1 (GCC 2.95.2) -O3, 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
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
LuaJIT 2.0.3, Linux
Lua 5.2.3, Linux
Python 2.633
PyPy 2.2.1 (Python 2.7.3), Linux
Python 2.7.6, Linux
Erlang 3.663
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
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
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
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

This is a very impressive performance for a language whose specification continues to be refined and with a compiler under active development. There are few applications where an 8% speed penalty compared to C/C++ will make much of a difference (note, of course, that many systems programming applications do things very different that this floating-point intensive benchmark, and that relative performance measured by this program may not be indicative of what you'll experience on very different tasks such as text processing, management of large data structures, or parallel computation).

Posted at 00:31 Permalink

Saturday, October 18, 2014

Reading List: The Great Influenza

Barry, John M. The Great Influenza. New York: Penguin, [2004] 2005. ISBN 978-0-14-303649-4.
In the year 1800, the practice of medicine had changed little from that in antiquity. The rapid progress in other sciences in the 18th century had had little impact on medicine, which one historian called “the withered arm of science”. This began to change as the 19th century progressed. Researchers, mostly in Europe and especially in Germany, began to lay the foundations for a scientific approach to medicine and public health, understanding the causes of disease and searching for means of prevention and cure. The invention of new instruments for medical examination, anesthesia, and antiseptic procedures began to transform the practice of medicine and surgery.

All of these advances were slow to arrive in the United States. As late as 1900 only one medical school in the U.S. required applicants to have a college degree, and only 20% of schools required a high school diploma. More than a hundred U.S. medical schools accepted any applicant who could pay, and many graduated doctors who had never seen a patient or done any laboratory work in science. In the 1870s, only 10% of the professors at Harvard's medical school had a Ph.D.

In 1873, Johns Hopkins died, leaving his estate of US$ 3.5 million to found a university and hospital. The trustees embarked on an ambitious plan to build a medical school to be the peer of those in Germany, and began to aggressively recruit European professors and Americans who had studied in Europe to build a world class institution. By the outbreak of World War I in Europe, American medical research and education, still concentrated in just a few centres of excellence, had reached the standard set by Germany. It was about to face its greatest challenge.

With the entry of the United States into World War I in April of 1917, millions of young men conscripted for service were packed into overcrowded camps for training and preparation for transport to Europe. These camps, thrown together on short notice, often had only rudimentary sanitation and shelter, with many troops living in tent cities. Large number of doctors and especially nurses were recruited into the Army, and by the start of 1918 many were already serving in France. Doctors remaining in private practice in the U.S. were often older men, trained before the revolution in medical education and ignorant of modern knowledge of diseases and the means of treating them.

In all American wars before World War I, more men died from disease than combat. In the Civil War, two men died from disease for every death on the battlefield. Army Surgeon General William Gorgas vowed that this would not be the case in the current conflict. He was acutely aware that the overcrowded camps, frequent transfers of soldiers among far-flung bases, crowded and unsanitary troop transport ships, and unspeakable conditions in the trenches were a tinderbox just waiting for the spark of an infectious disease to ignite it. But the demand for new troops for the front in France caused his cautions to be overruled, and still more men were packed into the camps.

Early in 1918, a doctor in rural Haskell County, Kansas began to treat patients with a disease he diagnosed as influenza. But this was nothing like the seasonal influenza with which he was familiar. In typical outbreaks of influenza, the people at greatest risk are the very young (whose immune systems have not been previously exposed to the virus) and the very old, who lack the physical resilience to withstand the assault by the disease. Most deaths are among these groups, leading to a “bathtub curve” of mortality. This outbreak was different: the young and elderly were largely spared, while those in the prime of life were struck down, with many dying quickly of symptoms which resembled pneumonia. Slowly the outbreak receded, and by mid-March things were returning to normal. (The location and mechanism where the disease originated remain controversial to this day and we may never know for sure. After weighing competing theories, the author believes the Kansas origin most likely, but other origins have their proponents.)

That would have been the end of it, had not soldiers from Camp Funston, the second largest Army camp in the U.S., with 56,000 troops, visited their families in Haskell County while on leave. They returned to camp carrying the disease. The spark had landed in the tinderbox. The disease spread outward as troop trains travelled between camps. Often a train would leave carrying healthy troops (infected but not yet symptomatic) and arrive with up to half the company sick and highly infectious to those at the destination. Before long the disease arrived via troop ships at camps and at the front in France.

This was just the first wave. The spring influenza was unusual in the age group it hit most severely, but was not particularly more deadly than typical annual outbreaks. Then in the fall a new form of the disease returned in a much more virulent form. It is theorised that under the chaotic conditions of wartime a mutant form of the virus had emerged and rapidly spread among the troops and then passed into the civilian population. The outbreak rapidly spread around the globe, and few regions escaped. It was particularly devastating to aboriginal populations in remote regions like the Arctic and Pacific islands who had not developed any immunity to influenza.

The pathogen in the second wave could kill directly within a day by destroying the lining of the lung and effectively suffocating the patient. The disease was so virulent and aggressive that some medical researchers doubted it was influenza at all and suspected some new kind of plague. Even those who recovered from the disease had much of their immunity and defences against respiratory infection so impaired that some people who felt well enough to return to work would quickly come down with a secondary infection of bacterial pneumonia which could kill them.

All of the resources of the new scientific medicine were thrown into the battle with the disease, with little or no impact upon its progression. The cause of influenza was not known at the time: some thought it was a bacterial disease while others suspected a virus. Further adding to the confusion is that influenza patients often had a secondary infection of bacterial pneumonia, and the organism which causes that disease was mis-identified as the pathogen responsible for influenza. Heroic efforts were made, but the state of medical science in 1918 was simply not up to the challenge posed by influenza.

A century later, influenza continues to defeat every attempt to prevent or cure it, and another global pandemic remains a distinct possibility. Supportive treatment in the developed world and the availability of antibiotics to prevent secondary infection by pneumonia will reduce the death toll, but a mass outbreak of the virus on the scale of 1918 would quickly swamp all available medical facilities and bring society to the brink as it did then. Even regular influenza kills between a quarter and a half million people a year. The emergence of a killer strain like that of 1918 could increase this number by a factor of ten or twenty.

Influenza is such a formidable opponent due to its structure. It is an RNA virus which, unusually for a virus, has not a single strand of genetic material but seven or eight separate strands of RNA. Some researchers argue that in an organism infected with two or more variants of the virus these strands can mix to form new mutants, allowing the virus to mutate much faster than other viruses with a single strand of genetic material (this is controversial). The virus particle is surrounded by proteins called hemagglutinin (HA) and neuraminidase (NA). HA allows the virus to break into a target cell, while NA allows viruses replicated within the cell to escape to infect others.

What makes creating a vaccine for influenza so difficult is that these HA and NA proteins are what the body's immune system uses to identify the virus as an invader and kill it. But HA and NA come in a number of variants, and a specific strain of influenza may contain one from column H and one from column N, creating a large number of possibilities. For example, H1N2 is endemic in birds, pigs, and humans. H5N1 caused the bird flu outbreak in 2004, and H1N1 was responsible for the 1918 pandemic. It gets worse. As a child, when you are first exposed to influenza, your immune system will produce antibodies which identify and target the variant to which you were first exposed. If you were infected with and recovered from, say, H3N2, you'll be pretty well protected against it. But if, subsequently, you encounter H1N1, your immune system will recognise it sufficiently to crank out antibodies, but they will be coded to attack H3N2, not the H1N1 you're battling, against which they're useless. Influenza is thus a chameleon, constantly changing its colours to hide from the immune system.

Strains of influenza tend to come in waves, with one HxNy variant dominating for some number of years, then shifting to another. Developers of vaccines must play a guessing game about which you're likely to encounter in a given year. This explains why the 1918 pandemic particularly hit healthy adults. Over the decades preceding the 1918 outbreak, the primary variant had shifted from H1N1, then decades of another variant, and then after 1900 H1N1 came back to the fore. Consequently, when the deadly strain of H1N1 appeared in the fall of 1918, the immune systems of both young and elderly people were ready for it and protected them, but those in between had immune systems which, when confronted with H1N1, produced antibodies for the other variant, leaving them vulnerable.

With no medical defence against or cure for influenza even today, the only effective response in the case of an outbreak of a killer strain is public health measures such as isolation and quarantine. Influenza is airborne and highly infectious: the gauze face masks you see in pictures from 1918 were almost completely ineffective. The government response to the outbreak in 1918 could hardly have been worse. After creating military camps which were nothing less than a culture medium containing those in the most vulnerable age range packed in close proximity, once the disease broke out and reports began to arrive that this was something new and extremely lethal, the troop trains and ships continued to run due to orders from the top that more and more men had to be fed into the meat grinder that was the Western Front. This inoculated camp after camp. Then, when the disease jumped into the civilian population and began to devastate cities adjacent to military facilities such as Boston and Philadelphia, the press censors of Wilson's proto-fascist war machine decided that honest reporting of the extent and severity of the disease or measures aimed at slowing its spread would impact “morale” and war production, so newspapers were ordered to either ignore it or print useless happy talk which only accelerated the epidemic. The result was that in the hardest-hit cities, residents confronted with the reality before their eyes giving to lie to the propaganda they were hearing from authorities retreated into fear and withdrawal, allowing neighbours to starve rather than risk infection by bringing them food.

As was known in antiquity, the only defence against an infectious disease with no known medical intervention is quarantine. In Western Samoa, the disease arrived in September 1918 on a German steamer. By the time the disease ran its course, 22% of the population of the islands was dead. Just a few kilometres across the ocean in American Samoa, authorities imposed a rigid quarantine and not a single person died of influenza.

We will never know the worldwide extent of the 1918 pandemic. Many of the hardest-hit areas, such as China and India, did not have the infrastructure to collect epidemiological data and what they had collapsed under the impact of the crisis. Estimates are that on the order of 500 million people worldwide were infected and that between 50 and 100 million died: three to five percent of the world's population.

Researchers do not know why the 1918 second wave pathogen was so lethal. The genome has been sequenced and nothing jumps out from it as an obvious cause. Understanding its virulence may require recreating the monster and experimenting with it in animal models. Obviously, this is not something which should be undertaken without serious deliberation beforehand and extreme precautions, but it may be the only way to gain the knowledge needed to treat those infected should a similar wild strain emerge in the future. (It is possible this work may have been done but not published because it could provide a roadmap for malefactors bent on creating a synthetic plague. If this be the case, we'll probably never know about it.)

Although medicine has made enormous strides in the last century, influenza, which defeated the world's best minds in 1918, remains a risk, and in a world with global air travel moving millions between dense population centres, an outbreak today would be even harder to contain. Let us hope that in that dire circumstance authorities will have the wisdom and courage to take the kind of dramatic action which can make the difference between a regional tragedy and a global cataclysm.

Posted at 21:34 Permalink

Friday, October 3, 2014

Reading List: The Box

Levinson, Marc. The Box. Princeton: Princeton University Press, [2006] 2008. ISBN 978-0-691-13640-0.
When we think of developments in science and technology which reshape the world economy, we often concentrate upon those which build on fundamental breakthroughs in our understanding of the world we live in, or technologies which employ them to do things never imagined. Examples of these are electricity and magnetism, which gave us the telegraph, electric power, the telephone, and wireless communication. Semiconductor technology, the foundation of the computer and Internet revolutions, is grounded in quantum mechanics, elaborated only in the early 20th century. The global positioning satellites which you use to get directions when you're driving or walking wouldn't work if they did not compensate for the effects of special and general relativity upon the rate at which clocks tick in moving objects and those in gravitational fields.

But sometimes a revolutionary technology doesn't require a scientific breakthrough, nor a complicated manufacturing process to build, but just the realisation that people have been looking at a problem all wrong, or have been earnestly toiling away trying to solve some problem other than the one which people are ready to pay vast sums of money to have solved, once the solution is placed on the market.

The cargo shipping container may be, physically, the one of the least impressive technological achievements of the 20th century, right up there with the inanimate carbon rod, as it required no special materials, fabrication technologies, or design tools which did not exist a century before, and yet its widespread adoption in the latter half of the 20th century was fundamental to the restructuring of the global economy which we now call “globalisation”, and changed assumptions about the relationship between capital, natural resources, labour, and markets which had existed since the start of the industrial revolution.

Ever since the start of ocean commerce, ships handled cargo in much the same way. The cargo was brought to the dock (often after waiting for an extended period in a dockside warehouse for the ship to arrive), then stevedores (or longshoremen, or dockers) would load the cargo into nets, or onto pallets hoisted by nets into the hold of the ship, where other stevedores would unload it and stow the individual items, which might consist of items as varied as bags of coffee beans, boxes containing manufactured goods, barrels of wine or oil, and preserved food items such as salted fish or meat. These individual items were stored based upon the expertise of the gangs working the ship to make the most of the irregular space of the ship's cargo hold, and if the ship was to call upon multiple ports, in an order so cargo could be unloaded with minimal shifting of that bound for subsequent destinations on the voyage. Upon arrival at a port, this process was reversed to offload cargo bound there, and then the loading began again. It was not unusual for a cargo ship to spend 6 days or more in each port, unloading and loading, before the next leg on its voyage.

Shipping is both capital- and labour-intensive. The ship has to be financed and incurs largely fixed maintenance costs, and the crew must be paid regardless of whether they're at sea or waiting in port for cargo to be unloaded and loaded. This means that what engineers call the “duty cycle” of the ship is critical to its cost of operation and, consequently, what the shipowner must charge shippers to make a profit. A ship operating coastal routes in the U.S., say between New York and a port in the Gulf, could easily spend half its time in ports, running up costs but generating no revenue. This model of ocean transport, called break bulk cargo, prevailed from the age of sail until the 1970s.

Under the break bulk model, ocean transport was very expensive. Further, with cargos sitting in warehouses waiting for ships to arrive on erratic schedules, delivery times were not just long but also unpredictable. Goods shipped from a factory in the U.S. midwest to a destination in Europe would routinely take three months to arrive end to end, with an uncertainty measured in weeks, accounting for trucking, railroads, and ocean shipping involved in getting them to their destination. This meant that any importation of time-sensitive goods required keeping a large local inventory to compensate for unpredictable delivery times, and paying the substantial shipping cost included in their price. Economists, going back to Ricardo, often modelled shipping as free, but it was nothing of the kind, and was often the dominant factor in the location and structure of firms.

When shipping is expensive, firms have an advantage in being located in proximity to both their raw materials (or component suppliers) and customers. Detroit became the Motor City in large part because its bulk inputs: iron ore and coal, could be transported at low cost from mines to factories by ships plying the Great Lakes. Industries dependent on imports and exports would tend to cluster around major ports, since otherwise the cost of transporting their inputs and outputs overland from the nearest port would be prohibitive. And many companies simply concentrated on their local market, where transportation costs were not a major consideration in their cost structure. In 1964, when break bulk shipping was the norm, 40% of exports from Britain originated within 25 miles of their port of export, and two thirds of all imports were delivered to destinations a similar distance from their port of arrival.

But all of this was based upon the cost structure of break bulk ocean cargo shipping, and a similarly archaic way of handling rail and truck cargo. A manufacturing plant in Iowa might pack its goods destined for a customer in Belgium into boxes which were loaded onto a truck, driven to a terminal in Chicago where they were unloaded and reloaded into a boxcar, then sent by train to New Jersey, where they were unloaded and put onto a small ship to take them to the port of New York, where after sitting in a warehouse they'd be put onto a ship bound for a port in Germany. After arrival, they'd be transported by train, then trucked to the destination. Three months or so later, plus or minus a few, the cargo would arrive—at least that which wasn't stolen en route.

These long delays, and the uncertainty in delivery times, required those engaging in international commerce to maintain large inventories, which further increased the cost of doing business overseas. Many firms opted for vertical integration in their own local region.

Malcom McLean started his trucking company in 1934 with one truck and one driver, himself. What he lacked in capital (he often struggled to pay bridge tolls when delivering to New York), he made up in ambition, and by 1945, his company operated 162 trucks. He was a relentless cost-cutter, and from his own experience waiting for hours on New York docks for his cargo to be unloaded onto ships, in 1953 asked why shippers couldn't simply put the entire truck trailer on a ship rather than unload its cargo into the ship's hold, then unload it piece by piece at the destination harbour and load it back onto another truck. War surplus Liberty ships were available for almost nothing, and they could carry cargo between the U.S. northeast and south at a fraction of the cost of trucks, especially in the era before expressways.

McLean immediately found himself in a tangled web of regulatory and union constraints. Shipping, trucking, and railroads were all considered completely different businesses, each of which had accreted its own, often bizarre, government regulation and union work rules. The rate a carrier could charge for hauling a ton of cargo from point A to point B depended not upon its mass or volume, but what it was, with radically different rates for say, coal as opposed to manufactured goods. McLean's genius was in seeing past all of this obstructionist clutter and realising that what the customer—the shipper—wanted was not to purchase trucking, railroad, and shipping services, but rather delivery of the shipment, however accomplished, at a specified time and cost.

The regulatory mess made it almost impossible for a trucking company to own ships, so McLean created a legal structure which would allow his company to acquire a shipping line which had fallen on hard times. He then proceeded to convert a ship to carry containers, which would not be opened from the time they were loaded on trucks at the shipper's location until they arrived at the destination, and could be transferred between trucks and ships rapidly. Working out the details of the construction of the containers, setting their size, and shepherding all of this through a regulatory gauntlet which had never heard of such concepts was daunting, but the potential payoff was enormous. Loading break bulk cargo onto a ship the size of McLean's first container vessel cost US$ 5.83 per ton. Loading freight in containers cost US$ 0.16 per ton. This reduction in cost, passed on to the shipper, made containerised freight compelling, and sparked a transformation in the global economy.

Consider Barbie. Her body is manufactured in China, using machines from Japan and Europe and moulds designed in the U.S. Her hair comes from Japan, the plastic for her body from Taiwan, dyed with U.S. pigments, and her clothes are produced in other factories in China. The final product is shipped worldwide. There are no large inventories anywhere in the supply chain: every step depends upon reliable delivery of containers of intermediate products. Managers setting up such a supply chain no longer care whether the products are transported by truck, rail, or sea, and since transportation costs for containers are so small compared to the value of their contents (and trade barriers such as customs duties have fallen), the location of suppliers and factories is based almost entirely upon cost, with proximity to resources and customers almost irrelevant. We think of the Internet as having abolished distance, but the humble ocean cargo container has done so for things as much as the Internet has for data.

This is a thoroughly researched and fascinating look at how the seemingly most humble technological innovation can have enormous consequences, and also how the greatest barriers to restructuring economies may be sclerotic government and government-enabled (union) structures which preserve obsolete models long after they have become destructive of prosperity. It also demonstrates how those who try to freeze innovation into a model fixed in the past will be bypassed by those willing to embrace a more efficient way of doing business. The container ports which handle most of the world's cargo are, for the most part, not the largest ports of the break bulk era. They are those which, unencumbered by history, were able to build the infrastructure required to shift containers at a rapid rate.

The Kindle edition has some flaws. In numerous places, spaces appear within words which don't belong there (perhaps words hyphenated across lines in the print edition and not re-joined?) and the index is just a list of searchable terms, not linked to references in the text.

Posted at 23:46 Permalink