Immutable data types in concurrent programming on basis of Clojure language
Name
Kristjan Kelt
Abstract
Concurrent programming tries to solve the problems where there is a need to share different resources between different threads. In most simplest case it is about sharing the processor time but modern multi-core processors do add a new dimension where the access to the shared memory becomes the most essential problem.
It is concluded in this work that the concurrent programming in Java inherits most of its problems from the direct incorporation of the shared memory model. Because it is possible in Java to access shared memory without properly applied mutual exclusion, it can produce hard to detect software bugs. Moreover Java lock based mutual exclusion can introduce additional hard to detect problems. Most notoriously the program can contain a possible deadlock when lock acquisition is not correctly ordered. It is difficult to compose separate thread safe atomic operations into a new atomic operation using locks because an additional complex synchronization is required when combining multiple method calls.
The main focus of this work is on the innovations provided by the Clojure language. It is concluded in this work that a new Lisp inspired functional language Clojure that is implemented on top of the Java platform introduces a more limited ruleset for the data sharing between different threads. Most importantly all data sharing operations must be expressed explicitly. This approach can arguably reduces the set of possible programming errors.
Clojure offers two methods for the data sharing. It can be accomplished asynchronously with the agents or synchronously with either software transactional memory (STM) for operations that require updating multiple values in one atomic operations or with simpler atomic updates when only one values is shared.
Clojure STM provides syntactically simple method for combining multiple separate atomic operations into new atomic operation by simply wrapping given operations into a new transaction. Clojure STM can reduce programming errors further by using runtime verification to check that no updates are performed outside of the transaction.
It was concluded that regardless of the above Clojure does not free the programmer from correctly identifying set of the operations that should be executed atomically.
Clojure method of the concurrent programming relies heavily on the immutable data structures. Immutability lets it regard complex data structures as simple values whose state does not change outside of the control of the reference holder. Therefore it is important for Clojure to provide rich set of different data structures that follow these principles.
One of such data structures in Clojure is Persistent Vector from Clojure collections library. The internal working principles of this data type were explored. In summary it is a bit mapped trie with the high branching factor that allows possibility of the deferred additions into the end of the vector by collecting the new elements into a tail buffer before pushing them into the trie as a whole. Persistent Vector can share a bulk of its internal structure with the previous versions making it effective immutable data structure.
The actual performance of the Persistent Vector was evaluated. The findings show that it can provide addition and iteration operation performance compared to the Java collections ArrayList. The update by index performs two orders of magnitude slower than analogue operation on ArrayList. The performance difference of lookup by index operation was not conclusively determined due probably JIT induced difficulty to measure ArrayList index lookups reliably. Performed measurements still allow to speculate that the performance difference of the index lookup operation between Persistent Vector and ArrayList is similar to the performance difference of the update by index operation.
Few additional performance enchantments were evaluated and it was concluded that it would be possible to improve the addition operation performance around two times when additional thread confined flag is used to allow further sharing of the tail buffer between different versions.
It can be argued that relatively good addition and iterating performance would allow to use Persistent Vector to solve a set of useful problems. For example the Persistent Vector can be used to load a list of the records from the database to be iterated over to build a web page based on that data.
Due hardness of the proper performance testing of the parallel operations such tests were not included into this work. It can be suggested that testing the performance of sharing persistent vector between multiple threads is needed.
It was concluded in summary that Clojure shows that it is possible to make concurrent programming relatively safer when a set of design principles are changed. It can be argued that difficulty of concurrent programming in Java does not improve unless its memory access principles are considerably reevaluated.
Graduation Thesis language
English
Graduation Thesis type
Bachelor - Computer Science
Supervisor(s)
Oleg Batrashev
Defence year
2013