(defn pmap [f xs] (let [futs (map (fn [x] (fork (f x))) xs)] (map (fn [fut] (join fut)) futs)))
pmapimplements a parallel
map. First, we fork a new future for each element in the list, which computes
(f x)in parallel. Next, all results are joined and returned.
(def checking (ref 150)) (def savings (ref 500)) (defn transfer [from to amount] (atomic (ref-set from (- @from amount)) (ref-set to (+ @to amount)))) (transfer checking savings 100)
In this example,
savingsare two bank accounts stored in transactional variables (
atomicencapsulates a transaction that transfers $100 from the checking to the savings account.
Transactions + Futures
(def my-accounts [(ref 150) (ref 500) (ref 30)]) (defn add-interest [accounts pct] (atomic (pmap (fn [acc] (ref-set acc (* @acc pct))) accounts))) (add-interest my-accounts 1.01)
This example adds 1% interest to each of my bank accounts. We use the
pmapfunction of the first example to do this in parallel. Chocola guarantees that this does what you expect.
(def interface (behavior [id accounts] [:print-accounts] (println "Customer " id " has: " accounts) [:add-account account] (become :same id (cons account accounts)))) (def my-actor (spawn interface 1 )) (send my-actor :add-account 500) (send my-actor :print-accounts) ; => Customer 1 has: 
This example uses actors.
behaviordefines the interface of an actor. This consists of the actor’s internal state (here an
idand list of
accounts) and its reaction to messages: a list of patterns and the code to execute. An actor can read its internal state and the data passed in the message (extracted using pattern matching). It can modify its behavior and internal state using
become(here the interface stays the same but the state changes).
The example spawns one actor and sends two messages, to add a bank account and print all accounts.
Actors + Transactions + Futures
(def interface (behavior [id accounts] [:transfer from to amount] (transfer from to amount) [:add-interest] (add-interest accounts 1.01)) (def checking (ref 150)) (def savings (ref 500)) (def my-accounts [checking savings]) (def my-actor (spawn interface 1 my-accounts)) (send my-actor :add-interest)
In this example, all three concurrency models are combined. We create one actor and send it a message to calculate the interest. In the actor, a transaction is started, and in this transaction, several futures are created. This demonstrates Chocola’s ability to freely use and combine whichever concurrency model suits the problem.
We have implemented Chocola as an extension of Clojure. It can be downloaded on GitHub.
It can easily be included in existing Clojure projects that use Leiningen: by injecting Chocola in the project's
project.clj, Clojure will be patched on start up with Chocola's modifications. This is decribed in more detail in the README file.
Chocola is released under the Eclipse Public License (same as Clojure).
You can find a complete description of Chocola in my PhD thesis. It describes the motivation behind Chocola, the semantics of each of its parts, a formalization of its semantics, some details on its implementation, and the benchmark applications we used to evaluate it.
We also published about (the ideas behind) Chocola at academic conferences, in the following papers:
Chocola: Integrating Futures, Actors, and TransactionsAt AGERE (at SPLASH), November 2018
This paper presents Chocola. It builds upon our previous work to unify futures, actors, and transactions in one framework. We first describe the guarantees of each separate model. Next, for each pairwise combination, we study which guarantees are broken in a naive combination and describe how these can be maintained in our modified semantics. Finally, we unify these modified semantics in Chocola. We also present its implementation in Clojure.Download paper
Transactional Tasks: Parallelism in Software TransactionsAt ECOOP, July 2016
This paper studies the combination of futures and transactions. It introduces transactional futures: a construct that allows futures to be created in a transaction. They make it possible to exploit the parallelism inside a transaction, while providing safe access to the state of their encapsulating transaction. Transactional futures maintain serializability and do not introduce non-determinism. We also demonstrate that introducing transactional futures can improve performance.Download paper
Transactional Actors: Communication in TransactionsAt SEPS (at SPLASH), October 2017
This paper the combination of combination of actors and transactions, resulting in transactional actors. By using transactions in an actor, memory can be shared safely between actors. By using the actor model in a transaction, transactions can communicate. Hence, transactional actors combine transactions and actors while maintaining their properties.Download paper
Towards Composable Concurrency AbstractionsAt PLACES (at ETAPS), April 2014
This paper is a case study of the combinations of the six concurrency models supported by Clojure. We study all pairwise combinations of these models, noting which ones compose without issues and which don’t. This motivated the creation of Chocola.Download paper
We have used Chocola to create three example applications. These are applications from STAMP, a benchmark suite of applications that use transactions (paper). We modified these applications to show that better performance can be achieved by combining transactions with either futures or actors.
vacation2 is a simulated reservation system for hotels, flights, and rental cars. It uses actors to process several customers in parallel, and transactions to manage the shared data (hotels, flights, and car reservations).GitHub repository
The Labyrinth application simulates the placement of electrical wires between transistors on a computer chip. This is a bit like searching for paths through a “labyrinth”, but the electrical wires between the transistors should not overlap. Several threads search for paths at the same time, and write their result to transactional memory. Using transactions ensures paths do not overlap. However, inside each transaction there’ a search algorithm that can also be parallelized. We use futures in the transaction to improve the performance of this application.GitHub repository
The Bayes benchmark implements an algorithm that learns the structure of a “Bayesian network”. This network is a graph, in which a node can be accessed by multiple threads. Hence, each node is stored as a transactional variable, and modifications to the graph occur in a transaction. Sometimes, this requires expensive computations, which can be parallelized using futures. Thus, this application benefits from better performance by combining futures and transactions.GitHub repository