OOP Is Dead, Long Live Data-oriented Design

1y ago
20 Views
2 Downloads
2.27 MB
46 Pages
Last View : 2d ago
Last Download : 2m ago
Upload by : Aliana Wahl
Transcription

OOP is dead, long liveData-oriented designStoyan Nikolov@stoyannkCppCon 2018 @stoyannk

Who am I? In the video games industry for 10 yearsSoftware Architect at Coherent LabsWorking on game development technologyLast 6.5 years working on chromiumWebKitHummingbird - in-house game UI & browser engineHigh-performance maintainable C Games using Coherent Labs technologyImages courtesy of Rare Ltd., PUBG CorporationCppCon 2018 @stoyannk2

Can a browser engine be successful withdata-oriented design?CppCon 2018 @stoyannk3

CSS Animations with chromium (OOP)DEMOCppCon 2018 @stoyannk4

CSS Animations with Hummingbird (DoD)DEMOCppCon 2018 @stoyannk5

YesCppCon 2018 @stoyannk6

Agenda Basic issue with Object-oriented programming (OOP)Basics of Data-oriented design (DoD)Problem definitionObject-oriented programming approachData-oriented design approachResults & AnalysisCppCon 2018 @stoyannk7

What is so wrong with OOP?CppCon 2018 @stoyannk8

OOP marries data with operations. .it’s not a happy marriageHeterogeneous data is brought together by a “logical” black box objectThe object is used in vastly different contextsHides state all over the placeImpact on on 2018 @stoyannk9

Data-oriented designData AField A[]Field B[]Field C[]Data CField G[]System αSystem γData BField D[]Field E[]Field F[]Data DField H[]System βLogical Entity 0Logical Entity 1Field A[0]Field D[0]Field A[1]Field D[1]Field B[0]Field E[0]Field B[1]Field E[1]Field C[0]Field F[0]Field C[1]Field F[1]CppCon 2018 @stoyannk.10

Data-oriented design - the gist Separates data from logic The logic embraces the data If we aren’t going to use a piece of information, why pack it together?Avoids “hidden state”No virtual calls Does not try to hide itLeads to functions that work on arraysReorganizes data according to it’s usage Structs and functions live independent livesData is regarded as information that has to be transformedThere is no need for themPromotes deep domain knowledgeReferences at the end for more detailCppCon 2018 @stoyannk11

The system at handCppCon 2018 @stoyannk12

What is a CSS Animation?DEMOCppCon 2018 @stoyannk13

Animation definition@keyframes example {from {left: 0px;} to {left: 100px;}}div {width: 100px;height: 100px;background-color: red;animation-name: example;animation-duration: 1s;}CppCon 2018 @stoyannk Straightforward declaration Interpolate some properties over a period oftime Apply the Animated property on the rightElementsHowever at a second glance. Different property types (i.e. a number and acolor) There is a DOM API (JavaScript) that requiresthe existence of some classes (Animation,KeyframeEffect etc.)14

Let’s try OOPCppCon 2018 @stoyannk15

The OOP way (chromium 66) chromium has 2 Animation systems Employs some classic OOP We’ll be looking at the Blink systemClosely follows the HTML5 standard and IDLRunning Animation are separate objectsStudy chromium - it’s an amazing piece of software, a lot to learn!CppCon 2018 @stoyannk16

The flow Unclear lifetime semanticsCppCon 2018 @stoyannk17

The state Hidden stateBranch mispredictionsCppCon 2018 @stoyannk18

The KeyframeEffect Cache missesCppCon 2018 @stoyannk19

Updating time and values Jumping contextsCache misses (data and instruction)Coupling between systems (animations and events)CppCon 2018 @stoyannk20

Interpolate different types of values Dynamic type erasure - data and instruction cache missesRequires testing combinations of concrete classesCppCon 2018 @stoyannk21

Apply the new value Coupling systems - Animations and Style solvingUnclear lifetime - who “owns” the ElementGuaranteed cache missesWalks up the DOM tree!CppCon 2018 @stoyannk22

leRecalcCppCon 2018 @stoyannk23

Recap We used more than 6 non-trivial classesObjects contain smart pointers to other objectsInterpolation uses abstract classes to handle different property typesCSS Animations directly reach out to other systems - coupling Calling eventsSetting the value in the DOM ElementHow is the lifetime of Elements synchronized?CppCon 2018 @stoyannk24

Let’s try data-oriented designCppCon 2018 @stoyannk25

Back to the drawing board Animation data operations Tick (Update) - 99.9% AddRemovePause Animation Tick Input Animation Tick Output Animation definitionTimeChanged propertiesNew property valuesWho owns the new valuesDesign for many animationsCppCon 2018 @stoyannk26

The AnimationControllerAnimationControllerActive AnimationsAnimationStateTick(time)Animation OutputLeft: 50pxOpacity: 0.2AnimationStateLeft: 70pxRight: 50pxAnimationStateTop: 70pxInactive ent*Element*Element*CppCon 2018 @stoyannk27

Go flat!Note: Some read-only data gets duplicated across multiple instancesCppCon 2018 @stoyannk28

Avoid type erasurePer-property vector for every Animation type!Note: We know every needed type at compile time, the vector declarations are auto-generatedCppCon 2018 @stoyannk29

Ticking animations Iterate over all vectorsAnimationState BorderLeft AnimationState Opacity AnimationState BorderLeft AnimationState Opacity AnimationState Transform AnimationState BorderLeft AnimationState BorderLeft AnimationState Opacity AnimationState Transform Use implementation-level templates (in the .cpp file)CppCon 2018 @stoyannk30

Avoiding branches Keep lists per-boolean “flag” Separate Active and Inactive animations Similar to database tables - sometimes called that way in DoD literatureActive are currently running But can be stopped from APIInactive are finished But can start from APIAvoid “if (isActive)” !Tough to do for every bool, prioritize according to branch predictor chanceCppCon 2018 @stoyannk31

A little bit of codeCppCon 2018 @stoyannk32

Adding an API - Controlling Animations The API requires having an “Animation” object play()pause()playbackRate()But we have no “Animation” object?!An Animation is simply a handle to a bunch of data!AnimationId (unsigned int) wrapped in a JS-accessible C objectAnimationJS APICppCon 2018 @stoyannk-Play()Pause()Stop() AnimationId Id;AnimationController-Play(Id)Pause(Id)Stop(Id) 33

Implementing the DOM API cont. AnimationController implements all the data modifications“Animation” uses the AnimationId as a simple handleCppCon 2018 @stoyannk34

Analogous concepts between OOP and DoDOOPDoDblink::Animation inheriting 6 classesAnimationState templated structReferences to Keyframe dataRead-only duplicates of the Keyframe dataList of dynamically allocated InterpolationsVectors per-propertyBoolean flags for “activeness”Different tables (vectors) according to flagInherit blink::ActiveScriptWrappableAnimation interface with Id handleOutput new property value to ElementOutput to tables of new valuesMark Element hierarchy (DOM sub-trees) for stylingList of modified ElementsCppCon 2018 @stoyannk35

Key points Keep data flat Existence-based predication Reduce branchingApply the same operation on a whole tableId-based handles Maximise cache usageNo RTTIAmortized dynamic allocationsSome read-only duplication improves performance and readabilityNo pointersAllow us to rearrange internal memoryTable-based output No external dependenciesEasy to reason about the flowCppCon 2018 @stoyannk36

AnalysisCppCon 2018 @stoyannk37

Performance analysisAnimation Tick timeaverageOOPDoD6.833 ms1.116 msDoD Animations are 6.12x fasterCppCon 2018 @stoyannk38

Scalability Issues multithreading OOP chromium Animations Solutions for the OOP case Carefully re-work each data dependencyIssues multithreading DoD Animations Collections getting modified during iterationEvent delegatesMarking Nodes for re-styleMoving AnimationStates to “inactive” (table modification from multiple threads)Building list of modified Nodes (vector push back across multiple threads)Solutions in the DoD case Each task/job/thread keeps a private table of modified nodes & new inactive animsJoin merges the tablesClassic fork-joinCppCon 2018 @stoyannk39

Testability analysis The OOP case Needs mocking the main input - animation definitionsNeeds mocking at least a dozen classesNeeds building a complete mock DOM tree - to test the “needs re-style from animation logic”Combinatorial explosion of internal state and code-pathsAsserting correct state is difficult - multiple output pointsThe DoD case Needs mocking the input - animation definitionsNeeds mocking a list of Nodes, complete DOM tree is not neededAnimationController is self-containedAsserting correct state is easy - walk over the output tables and checkCppCon 2018 @stoyannk40

Modifiability analysis OOP Very tough to change base classes Very hard to reason about the consequencesData tends to “harden” Hassle to move fields around becomes too big Nonoptimal data layouts stick aroundShared object lifetime management issues Hidden and often fragile order of destructionEasy to do “quick” changesDoD Change input/output - requires change in System “before”/”after” in pipelineImplementation changes - local Can experiment with data layout Handles mitigate potential lifetime issuesCppCon 2018 @stoyannk41

Downsides of DoD Correct data separation can be hard Existence-based predication is not always feasible (or easy) OOP allows to “just add” a member, accessor, callMore discipline is needed to keep the benefits of DoDYou might have to unlearn a thing or two Think adding a bool to a class VS moving data across arraysToo many booleans is a symptom - think again about the problem“Quick” modifications can be tough Especially before you know the problem very wellThe beginning is toughThe language is not always your friendCppCon 2018 @stoyannk42

What to keep from OOP? Sometimes we have no choice Simple structs with simple methods are perfectly finePolymorphism & Interfaces have to be kept under control Third-party librariesIDL requirementsClient-facing APIsComponent high-level interfaceIMO more convenient than C function pointer structsRemember - C has great facilities for static polymorphism Can be done through templates. or simply include the right “impl” according to platform/build optionsCppCon 2018 @stoyannk43

Changes in C to better support DoD Allow new memory layout schemes for object arrays Structure Of Arrays (SOA) / Array Of Structures (AOS)Components layout, preserving classic C object access semantics Kinda doable now, but requires a lot of custom code We do it to awesome effect, but sooooo toughAlas tough to get in coreRanges look really excitingRelax requirements for unordered map/unordered set (or define new ones) Internal linked list does too many allocations & potential cache missesStandard hashmap/set with open addressingCppCon 2018 @stoyannk44

Object-oriented programming is not a silverbullet.neither is data-oriented design.use your best judgement, please.CppCon 2018 @stoyannk45

References “Data-Oriented Design and C ”, Mike Acton, CppCon 2014“Pitfalls of Object Oriented Programming”, Tony Albrecht“Introduction to Data-Oriented Design”, Daniel Collin“Data-Oriented Design”, Richard Fabian“Data-Oriented Design (Or Why You Might Be Shooting Yourself in The FootWith OOP)”, Noel Llopis“OOP ! classes, but may DOD”, roathe.com“Data Oriented Design Resources”, Daniele Bartolinihttps://stoyannk.wordpress.com/CppCon 2018 @stoyannk46

“Data-Oriented Design and C ”, Mike Acton, CppCon 2014 “Pitfalls of Object Oriented Programming”, Tony Albrecht “Introduction to Data-Oriented Design”, Daniel Collin “Data-Oriented Design”, Richard Fabian “Data-Oriented Design (Or Why You Might

Related Documents:

Some OOP features can be implemented in C or other procedural programming languages, but not enforced by these languages OOP languages: OOP concepts are embeded in and enforced by the languages. OOP Concepts 29 OOP languages vary in degrees of object-oriented Pure: Smalltalk, Eiffel, Ruby, JADE. Original OO plus some procedural features .

Floor Joist Spans 35 – 47 Floor Joist Bridging and Bracing Requirements 35 Joist Bridging Detail 35 10 psf Dead Load and 20 psf Live Load 36 – 37 10 psf Dead Load and 30 psf Live Load 38 – 39 10 psf Dead Load and 40 psf Live Load 40 – 41 10 psf Dead Load and 50 psf Live Load 42 – 43 15 psf Dead Load and 125 psf Live Load 44 – 45

Jan 11, 2020 · 3rd edition (1999) OOP need to check ask 1725 MechWarrior's Guide to the Clans 3rd edition (1999) OOP need to check 10975 Classic BattleTech Companion 3rd edition (1999) OOP 35008 A Guide to Covert Ops 3rd edition (1999) OOP BattleTech by Catalyst 14

9/5/22 Compsci 201, Fall 2022, OOP 3. Recapping some Java Themes 9/5/22 Compsci 201, Fall 2022, OOP 4. Comments on Java Style Code blocks: Opening {ends first line of if, for, while, or method . Aside: Python uses objects too 9/5/22 Compsci 201, Fall 2022, OOP 15 Split is a methodwe are calling on this String object, not a

OOP IntroductionType & SubtypeInheritanceOverloading and OverridingTemplateDynamic BindingOO-language ImplementationSummary OOP (Object Oriented Programming) So far the languages that we encountered treat data and computation separately. In OOP, the data and computation are combined into an "object". 1/55

OOP expenditure, the proportion of OOP . payments to total expenses per visit ("OOP share") for all facilities was higher for outpatient care (99 percent) than for inpatient care (80 percent). Interestingly, the OOP share for inpatient care was close to the same whether the patient attended a public or a private facility, 79 percent for private

1 1: oop 2 2 Examples 2 2 OOP 2 Intoduction 2 OOP 2 Java 3 C 3 3 Java 3 C 3 3 3 4 5 6 2: 7 Examples 7 7 7 8 3: 9 Examples 9 9 4: 10 Examples 10 10 5: 11

3 books about Dead Sea Scrolls, such as The Meaning of the Dead Sea Scrolls by A. Powell Davies, The Dead Sea Scrolls Deceptions by Richard Leigh and Michael Baigent, Jesus and the Riddle of the Dead Sea Scrolls by Barbara Thiering, The Teacher of Righteousness and the Dead Sea Scrolls by Bette Stockbauer and some Dead Sea Scrolls-related works by Kenneth Von Pfettenbach.