Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Efficient and Thread-Safe Objects for Dynamical...

Benoit Daloze
November 03, 2016

Efficient and Thread-Safe Objects for Dynamically-Typed Languages

We present a thread-safe object model for dynamic languages, such as Ruby, Python, JavaScript, ..., which occurs no overhead on single-threaded peak performance and very small overhead for parallel benchmarks.

Benoit Daloze

November 03, 2016
Tweet

More Decks by Benoit Daloze

Other Decks in Research

Transcript

  1. Introduction We are in the multi-core era, but: Dynamic languages

    have poor support for parallel execution (e.g.: Ruby, Python, JavaScript, . . . ) Object models are not thread-safe or inefficient Allow adding or removing fields at run time 2 / 35
  2. How is this executed? @field @field = value . .

    . when done concurrently on the same object? 3 / 35
  3. A simple class class Foo def a @a end def

    a=(v) @a = v end def b @b end def b=(v) @b = v end end 4 / 35
  4. What could go wrong? obj = Foo.new Thread.new { obj.a

    = "a" } Thread.new { obj.b = "b" obj.fields # => [:a, :b] OK obj.b # => "b" OK } 5 / 35
  5. What could go wrong? obj = Foo.new Thread.new { obj.a

    = "a" } Thread.new { obj.b = "b" obj.fields # => [:a] ?? obj.b # => nil ?? } 6 / 35
  6. What could go wrong? obj = Foo.new Thread.new { obj.a

    = "a" } Thread.new { obj.b = "b" obj.fields # => [:b] OK obj.b # => "a" ?? } 7 / 35
  7. The Truffle Object Storage Model Based on maps from the

    SELF programming language An Efficient Implementation of SELF, a Dynamically-Typed Object-Oriented Language Based on Prototypes. C. Chambers, D. Ungar & E. Lee., 1991. 10 / 35
  8. The Truffle Object Storage Model An Object Storage Model for

    the Truffle Language Implementation Framework A. Wöß, C. Wirth, D. Bonetta, C. Seaton, C. Humer & H. Mössenböck, 2014. 11 / 35
  9. The Truffle Object Storage Model An Object Storage Model for

    the Truffle Language Implementation Framework A. Wöß, C. Wirth, D. Bonetta, C. Seaton, C. Humer & H. Mössenböck, 2014. 12 / 35
  10. Defining a new field Grow the object storage (allocate, copy,

    update pointer) obj.storage = copy(obj.storage, size+1) and write the value: obj.storage[size-1] = value Update the Shape pointer: obj.shape = newShape Two reference fields cannot be read and written atomically, unless using synchronization! 18 / 35
  11. Can we just synchronize field updates? Writing to a field

    and loop 0 50 100 150 200 250 300 30 290 Median time per 10M writes (ms) Unsafe Synchronized 19 / 35
  12. Synchronize only on shared objects writes Choices: Synchronize only on

    shared objects writes Unsynchronized reads on shared objects Motivation: Reads are more frequent than writes on shared objects 28× more frequent in concurrent DaCapo benchmarks! A Black-box Approach to Understanding Concurrency in DaCapo. T. Kalibera, M. Mole, R. Jones, and J. Vitek, 2012. 23 / 35
  13. One Solution: synchronize on shared objects Lost Field Definitions and

    Updates Synchronize writes, but only on shared objects Local objects need no synchronization Out-Of-Thin-Air Values Different storage locations for each field: A storage location of an object is only ever used for one field 24 / 35
  14. Tracking the set of shared objects All globally-reachable objects are

    initially shared, transitively Write to shared object =⇒ share value, transitively # Share 1 Array, 1 Object, 1 Hash and 1 String shared_obj.field = [Object.new, { "a" => 1 }] 25 / 35
  15. Sharing: writing to a field of a shared object void

    share(DynamicObject object) { if (!isShared(obj.shape)) { object.shape = sharedShape(obj.shape); for (location : obj.getObjectLocations()) { share(location.get(obj)); // recursive call } } } void writeBarrier(DynamicObject sharedObject, Object value) if (value instanceof DynamicObject) { share(value); } synchronized (sharedObject) { location.set(sharedObject, value); } } 26 / 35
  16. Optimized Sharing for a Rectangle and two Points Compiled with

    Truffle: Self-optimizing AST interpreters. T. Würthinger, A. Wöß, L. Stadler, G. Duboscq, D. Simon & C. Wimmer, 2012. 28 / 35
  17. Optimized Sharing result after Partial Evaluation void shareRectangle(DynamicObject rect) {

    if (rect.shape == localRectangleShape) { rect.shape = sharedRectangleShape; } else { /* Deoptimize */ } DynamicObject tl = rect.object1; if (tl.shape == localPointShape) { tl.shape = sharedPointShape; } else { /* Deoptimize */ } DynamicObject br = rect.object2; if (br.shape == localPointShape) { br.shape = sharedPointShape; } else { /* Deoptimize */ } } 29 / 35
  18. Performance: Are we fast yet? q q q q MRI

    2.3 JRuby 9.0.4 Node.js JRuby+Truffle Java 1.8.0u66 1 5 10 25 50 75 Cross-Language Compiler Benchmarking: Are We Fast Yet? S. Marr, B. Daloze, H. Mössenböck, 2016. 31 / 35
  19. Impact on Sequential Performance Peak performance, normalized to Unsafe, lower

    is better q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0.0 0.5 1.0 1.5 2.0 2.5 Bounce DeltaBlue JSON List NBody Richards Towers Unsafe Safe All Shared All Shared synchronizes on all object writes. All object-related benchmarks from Cross-Language Compiler Benchmarking: Are We Fast Yet? S. Marr, B. Daloze, H. Mössenböck, 2016. 32 / 35
  20. Performance for Parallel Actor Benchmarks q q q q q

    q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q 0.0 0.5 1.0 1.5 2.0 2.5 APSP RadixSort Trapezoidal Runtime normalized to Unsafe (lower is better) Scala Akka Unsafe Safe No Deep Sharing Benchmarks from Savina – An Actor Benchmark Suite. S. Imam & V. Sarkar, 2014. 33 / 35
  21. Conclusion Concurrently growing objects need synchronization to not lose updates

    or new fields Distinguish local/shared objects reduces overhead Only synchronize on shared object writes Needs a write barrier (can be specialized) Thread-safe objects in dynamic languages Zero cost on sequential peak performance Low overhead on parallel code 34 / 35