DATA-ORIENTED DESIGN The hardware will thank you.


Follow Data-oriented Design on Google+

Read articles on CellPerformance

Data-Oriented Design book - online beta

FIRST PREV : PAGE 0 : NEXT LAST

Deep Pipes and looking for instruction dependency 01/06/2017:22:01:05

I came across this article on writing a really really fast json parser here

There are a few links in there that take you on a great tour of optimisations if you can spare the time to follow them, including a lovely post about 50% improvement in speed in SQLITE.

Scott Meyers - CPU Caches and Why You care 28/02/2017:09:43:42

I was recently shown a video by Scott Meyers on CPU caches, and the first ten minutes alone seems to be a reasonable push for understanding that DOD affects all langauges, not just C++ or C.

Link to the video https://vimeo.com/97337258 here for your viewing pleasure

Syntactic sugar to simplify SoA 10/09/2015:12:03:50

Manipulating data in structure of arrays format can be unweildy for some, but this post talks about making things easier for you using some simple templating to replace the manual side of iteration through the arrays.

Read here C++ encapsulation for Data-Oriented Design: performance and learn about keeping your DOD SoA approach tidier.

x86 architecture as an abstraction 26/03/2015:10:53:02

It has become more obvious to people involved in optimisation that the x86 architecture is a difficult platform to understand at the core. This is partially because of the multitude of different CPUs out there that support the instruction set, each with their different timings, but also because of this latest breed of extraordinarily out of order CPUs. Knowing what's actually going to happen in an i7 has become a near impossible task.

Read Robert Graham's post on x86 is a high-level language and try to see why it's so very difficult to grok the flow of data in these chips, and also how it's very difficult to guess what will be the best performing algorithm without doing a lot of real world tests.

Why is GNU grep so fast? 06/03/2015:15:06:44

Nice read on why grep is quick. Some simple stuff, some awesome algorithm usage, and generally the kind of thing that you might want to keep in your head for if you come across a searching pattern that is similar to grep in any way.

http://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html

The perils of alignment - or how to fully utilise the cache 18/02/2015:11:23:50

A really interesting article with real world data on the potential cache misuses issues of large, 2^ aligned structures. This is another reason to be ware of keeping data in large structures rather than separate arrays. It doesn't happen much by accident, but it's the kind of thing that gets done on purpose because there were reasons in GPUs to keep things aligned, and the cargo cult goes deep with these kinds of knowledge.
How Misaligning Data Can Increase Performance 12x by Reducing Cache Misses

A Data-Oriented Hash table 12/01/2015:19:40:10

I was skeptical at first, but the author appears to have tested his efforts with real hardware, which of course is a core tenet of DOD. Also this is not a post about a new invention, but a set of results from tests where the author replaces a hash table with alternatives. It's interesting to look at the different timings, but remember to test your code and not just follow blindly, as you may have overhead somewhere else that makes the slowest in these tests, suddenly the fastest.

data-oriented-hash-table

Unit tests, and why they don't work. 30/08/2014:10:55:40

Chose a paradigm that allows for the simplest, least complex, most provably correct code.

http://www.rbcs-us.com/documents/Segue.pdf

Optimising by fitness function 07/08/2014:09:59:32

Here's another example of premature optimisation:

Swap data for energy, and the demand oriented approach to fulfilment changes the function used to determine fitness. With energy, the demand over time was well known, but ignored by thousands of people installing expensive hardware.

Solar panels facing the wrong way

What ORMs have taught me: just learn SQL 05/08/2014:10:49:08

What ORMs have taught me

The Mature Optimization Handbook 21/11/2013:09:57:40

A lovely book on optimisation by Carlos Bueno (from facebook's performance team).

Find the book available for free download here

Data-Oriented design parallel project 13/11/2013:08:44:59

As reference material for the book, a github project has been started to show the development of a game in both the Object-Oriented and Data-Oriented approaches.

Expect slow updates right now as it only has one developer and they are in full time employment at a startup so spare time is scarce. However, if you wish to follow along, the project is hosted here on github for all to see.

In addition to the parallel game development, submissions from other developers would be appreciated, specifically any demo code that provides ways to build timings for the performance oriented points of the book. For example, any code that could be used to directly show the impact of bad pipelining, bad cache alignment, or even the effects of write combining. The only rule will be that it has to be simple, and able to run on many platforms. Single platform statistics aren't much use unless they are targetting current trending hardware like ARM based CPUs.

Data-Oriented design book 23/06/2013:20:32:14

Update: the book is now in live public beta. Check the right bar now for the link .
Time to see if there is an audience for the book.
If Richard Fabian gets more than 100 people commenting on his post then he has promised to upload and publish his work in progress book on Data-Oriented design to this very website.
If this happens, we will be replacing the signup link with the link to the full book which will be updated as it progresses towards a printable version.

Data-Parallel Decompression of Triangle Mesh Toplogy 31/05/2013:12:10:53

A lovely example of how continually looking at the data from one step to the next resulted in a drastic reduction in space usage while still maintaining a data-parallel solution to the problem of mesh decompression.
link

Component-architecture and Entity-systems development 04/03/2013:16:09:23

Even people with big brains have reservations about components, so to finish off the section on component oriented design in the upcoming data-oriented design book, I'd really like some negative experiences so they can be solved in a troubleshooting like section.

I've noticed that there are some points where people get things a bit wrong in implementing components, and it causes things to tie together badly. Once they've started coupling things together, they don't see any benefit to components, and it becomes a bad example and part of their opinion on components. This negative experience spreads around by word of mouth, and that's just as bad as gossip.

There are probably some guidelines or guiding principles that can be distilled from these negative experiences that might help when trying to ensure people don't get lost. Troubleshooting is a good match as there are likely a number of similar negative experiences that can all be solved in a similar way.

For example, in my experience the thing that trips people up most is expecting components to talk to each other for some reason, like they are objects that can message each other in some two directional way. But in practice, I've found that's not necessary.

So I think we need some examples of cases where it might seem like components don't work, or are inefficient, and follow them with how you diagnose what's wrong with those assumptions.

If you've had any bad experiences with components, they're probably going to be more beneficial than positive ones, as helping people out of messes is a lot more positive than just announcing how cool something is.

send any experiences to support@dataorienteddesign.com

Server downgrade 14/11/2012:21:06:13

Server is now a raspberry pi. Should be enough for the kind of traffic I see here, but if anyone has a job getting through then send an e-mail to support

Intrusive Linked Lists 10/09/2012:10:36:09

...again

but this time there's an interesting statement that needs to be investigated. In the section titled Why intrusive lists are better, there is an argument:

When traversing objects stored on an intrusive linked list, it only takes one pointer indirection to get to the object, compared to two pointer indirections for std::list. This causes less memory-cache thrashing so your program runs faster — particularly on modern processors which have huge delays for memory stalls.

Right

Think about it a bit more and you realise that this must in fact be false. Where are the pointers to the elements? They are in the middle of the structures being traversed. They're not somewhere all together, huddled up on cachelines, they're split apart by at least the size of the object they are linking. This means you save one indirection, but potentially at the cost of many loads from separate areas of memory which will cane your memory bandwidth.

Apart from that minor snaffet, the article is sound, but when you come across a false statement like that it does make you question the authenticity of the rest of the article. Foremost in your mind when you do any performance related work must be profiling. If the author had done profiling he might have learned that this was the case and been able to improve on the design further, or at least realise that there was a trade-off and with that knowledge be better armed.

http://www.codeofhonor.com/blog/avoiding-game-crashes-related-to-linked-lists?utm_source=rss&utm_medium=rss&utm_campaign=avoiding-game-crashes-related-to-linked-lists

Keep your types separated from the functions that operate on them 6/09/2012:00:53:34

Keeping your nouns separate from your verbs can be handy, and in this case it's being used to decrease coupling in the physical layout of code.
http://www.altdevblogaday.com/2012/09/03/a-new-way-of-organizing-header-files/

Memory Access Patterns Are Important 8/08/2012:21:36:18

"In high-performance computing it is often said that the cost of a cache-miss is the largest performance penalty for an algorithm."
http://mechanical-sympathy.blogspot.co.uk/2012/08/memory-access-patterns-are-important.html

interesting algorithm of the week 8/08/2012:21:25:57

Burrows Wheeler transform presented with an interactive demonstration of how it works.
http://blog.avadis-ngs.com/2012/04/elegant-exact-string-match-using-bwt-2/

Booleans as parameters can be seen as a code-smell 23/07/2012:10:57:26

Boolean parameters are usually used to control code flow inside a function from without. With no further information it should be a simple case of deduction that this is an unnecessary waste of time in almost all cases. If the code flow is meant to be controlled from without, then why not introduce two different functions. If there are multiple boolean switches of code flow, then it's probably true that the callee does too much.

Booleans as arguments are an alternative to having a function do what it says it does. The Ronseal-rule, a very good rule, forbids this.
http://ernstsson.net/post/27787949222/boolean-parameter-elimination

Reconsider the layout of your data 23/07/2012:08:37:15

If you put your data into classes, then you're limited to the basic structures available, namely fields as constants in your classes. Runtime changes to the structure of a class are very difficult to achieve with C++ without invoking arcane and hard to debug techniques. With blobs, or a simpler access pattern such as a free function to get a variable, then you can reimagine the data structures in new ways.
http://simblob.blogspot.co.uk/2012/07/playing-with-dot-operator.html

MVC is dead... 04/07/2012:12:41:12

Sometimes, reinterpretation can bring old ideas back to be fully realised. The MVC pattern is one of the good design patterns because it promoted separation of state from interpretation and action. MOVE is maybe a more clear interpretation of what MVC aims to provide.
http://cirw.in/blog/time-to-move-on

An example of how branch prediction affects your code 28/06/2012:12:52:55

This is a really good example of how understanding the shape of your data can help you make good decisions about your code.
http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array

Reducing distance data travels by moving the CPU near the memory 18/06/2012:21:25:26

If you're trying to reduce the amount of energy used getting data to your CPUs, then maybe this idea will work out better for efficient data movement.

Whether you're talking about high performance computers, enterprise servers, or mobile devices, the two biggest impediments to application performance in computing today are the memory wall and the power wall. Venray Technology is aiming to knock down those walls with a unique approach that puts CPU cores and DRAM on the same die. The company has been in semi-stealth mode since it inception seven years ago, but is now trying to get the word out about its technology as it searches for a commercial buyer.

http://www.hpcwire.com/hpcwire/2012-01-17/designer_of_microprocessor-memory_chip_aims_to_topple_memory_and_power_walls.html