Software Ghemawat describe how Google uses Map-Reduce to express large-scale distributed computations.3 Imperative and the languages can judiciously add functional style extensions and thereby benefit from those features.This is important Concurrency because the industry can't just start over.To preserve the huge investment in the world's current software,it is Revolution essential to incrementally add support for concurrency, while preserving software developers'expertise and train- ing in imperative languages. programmer specifies step-by-step changes to variables BETTER ABSTRACTIONS and data structures.Fine-grained control constructs (e.g., Most of today's languages offer explicit programming at for loops),low-level data manipulations,and shared the level of threads and locks.These abstractions are low- mutable object instances make programs in these lan- level and difficult to reason about systematically.Because guages difficult to analyze and automatically parallelize. these constructs are a poor basis for building abstractions, The common belief is that functional languages,such they encourage multithreaded programming with its as Scheme,ML,or Haskell,could eliminate this difficulty problems of arbitrary blocking and reentrancy. because they are naturally suited to concurrency.Pro- Higher-level abstractions allow programmers to grams written in these languages manipulate immutable express tasks with inherent concurrency,which a runtime object instances,which pose no concurrency hazards. system can then combine and schedule to fit the hard- Moreover,without side effects,programs seem to have ware on the actual machine.This will enable applications fewer constraints on execution order. that perform better on newer hardware.In addition,for In practice,however,functional languages are not mainstream development,programmers will value the necessarily conducive to concurrency.The parallelism illusion of sequential execution within a task. exposed in functional programs is typically at the level Two basic examples of higher-level abstractions are of procedure calls,which is impractically fine-grained for asynchronous calls and futures.An asynchronous call is a conventional parallel processors.Moreover,most func- function or method call that is nonblocking.The caller tional languages allow some side effects to mutable state, continues executing and,conceptually,a message is sent and code that uses these features is difficult to parallelize to a task,or fork,to execute operation independently. automatically. A future is a mechanism for returning a result from an These languages reintroduce mutable state for reasons asynchronous call;it is a placeholder for the value that of expressibility and efficiency.In a purely functional lan- has not yet materialized. guage,aggregate data structures,such as arrays or trees, Another example of a higher-level abstraction is an are updated by producing a copy containing a modified active object,which conceptually runs on its own thread value.This technique is semantically attractive but can be so that creating 1,000 such objects conceptually cre- terrible for performance (linear algorithms easily become ates 1,000 potential threads of execution.An active quadratic).In addition,functional updates do nothing to object behaves as a monitor,in that only one method discourage the writing of a strictly sequential algorithm, of the object executes at a given time,but it requires no in which each operation waits until the previous opera- traditional locking.Rather,method calls from outside tion updates the program's state. an active object are asynchronous messages,marshaled, The real contribution of functional languages to queued,and pumped by the object.Active objects have concurrency comes in the higher-level programming many designs,from specialized actor languages to COM style commonly employed in these languages,in which single-threaded apartments callable from traditional C operations such as map or map-reduce apply computa- code,and many design variables. tions to all elements of an aggregate data structure.These Other higher-level abstractions are needed,such as higher-level operations are rich sources of concurrency. protocols to describe and check asynchronous message This style of programming,fortunately,is not inherently exchange.Together they should bring together a consis- tied to functional languages,but is valuable in imperative tent programming model that can express typical applica- programs. tion concurrency requirements across all of the major For example,Google Fellows Jeffrey Dean and Sanjay granularity levels. 60 September 2005 QUEUE rants:feedback@acmqueue.com60 September 2005 QUEUE rants: feedback@acmqueue.com programmer specifies step-by-step changes to variables and data structures. Fine-grained control constructs (e.g., for loops), low-level data manipulations, and shared mutable object instances make programs in these lan￾guages difficult to analyze and automatically parallelize. The common belief is that functional languages, such as Scheme, ML, or Haskell, could eliminate this difficulty because they are naturally suited to concurrency. Pro￾grams written in these languages manipulate immutable object instances, which pose no concurrency hazards. Moreover, without side effects, programs seem to have fewer constraints on execution order. In practice, however, functional languages are not necessarily conducive to concurrency. The parallelism exposed in functional programs is typically at the level of procedure calls, which is impractically fine-grained for conventional parallel processors. Moreover, most func￾tional languages allow some side effects to mutable state, and code that uses these features is difficult to parallelize automatically. These languages reintroduce mutable state for reasons of expressibility and efficiency. In a purely functional lan￾guage, aggregate data structures, such as arrays or trees, are updated by producing a copy containing a modified value. This technique is semantically attractive but can be terrible for performance (linear algorithms easily become quadratic). In addition, functional updates do nothing to discourage the writing of a strictly sequential algorithm, in which each operation waits until the previous opera￾tion updates the program’s state. The real contribution of functional languages to concurrency comes in the higher-level programming style commonly employed in these languages, in which operations such as map or map-reduce apply computa￾tions to all elements of an aggregate data structure. These higher-level operations are rich sources of concurrency. This style of programming, fortunately, is not inherently tied to functional languages, but is valuable in imperative programs. For example, Google Fellows Jeffrey Dean and Sanjay Ghemawat describe how Google uses Map-Reduce to express large-scale distributed computations.3 Imperative languages can judiciously add functional style extensions and thereby benefit from those features. This is important because the industry can’t just start over. To preserve the huge investment in the world’s current software, it is essential to incrementally add support for concurrency, while preserving software developers’ expertise and train￾ing in imperative languages. BETTER ABSTRACTIONS Most of today’s languages offer explicit programming at the level of threads and locks. These abstractions are low￾level and difficult to reason about systematically. Because these constructs are a poor basis for building abstractions, they encourage multithreaded programming with its problems of arbitrary blocking and reentrancy. Higher-level abstractions allow programmers to express tasks with inherent concurrency, which a runtime system can then combine and schedule to fit the hard￾ware on the actual machine. This will enable applications that perform better on newer hardware. In addition, for mainstream development, programmers will value the illusion of sequential execution within a task. Two basic examples of higher-level abstractions are asynchronous calls and futures. An asynchronous call is a function or method call that is nonblocking. The caller continues executing and, conceptually, a message is sent to a task, or fork, to execute operation independently. A future is a mechanism for returning a result from an asynchronous call; it is a placeholder for the value that has not yet materialized. Another example of a higher-level abstraction is an active object, which conceptually runs on its own thread so that creating 1,000 such objects conceptually cre￾ates 1,000 potential threads of execution. An active object behaves as a monitor, in that only one method of the object executes at a given time, but it requires no traditional locking. Rather, method calls from outside an active object are asynchronous messages, marshaled, queued, and pumped by the object. Active objects have many designs, from specialized actor languages to COM single-threaded apartments callable from traditional C code, and many design variables. Other higher-level abstractions are needed, such as protocols to describe and check asynchronous message exchange. Together they should bring together a consis￾tent programming model that can express typical applica￾tion concurrency requirements across all of the major granularity levels. Software and the Concurrency Revolution