Data-Oriented Design chapter

[doyougnu]

references:

• Mike Acton's talk: https://youtu.be/rX0ItVEVjHc?si=77prqtc6hA8_Hopy
• Andrew Kelley's practical talk: https://youtu.be/IroPQ150F6c?si=TUZYXcb2AOXxKg-h
• Handles are the better pointers post: https://floooh.github.io/2018/06/17/handles-vs-pointers.html
• the DoD book

The chapter should provide a practical manual to doing DoD in Haskell. Many of the DoD techniques should readily apply. Some won't though, for example we cannot always remove pointers by using Int that index into an array because the arrays we have in haskell have boxed elements (and are therefore still pointed to). But that does not mean the technique is not useful, for example we still might have better temporal locality with the array. Will need to micro-benchmark that but I'm not holding my breathe.

[doyougnu]

A good example will be errors as values vs errors as exceptions with respect to the L1 data cache. With errors as values the hot loop of your code is larger because you have to pass and check the errors as values. Note that ideally this kind of checking would never occur in a hot loop but sometimes its unavoidable. This takes up precious cycles and cache space, whereas exceptions are stored in the exception table which is stored externally to your hot code. So when an exception occurs you get a long jump but your hot loop is smaller and your allocating less because you are not using errors as values. So the tradeoff is that the exceptional case becomes slower (because of the long jump) but the normal case is significantly faster because of better caching, and spatial locality.

[eyeinsky]

Is this known to be applicable to Haskell as well, or is this generally so for other languages? And by "errors as values" I assume you mean ExceptT errorType IO a?

[hsyl20]

So when an exception occurs you get a long jump but your hot loop is smaller and your allocating less because you are not using errors as values. So the tradeoff is that the exceptional case becomes slower (because of the long jump) but the normal case is significantly faster because of better caching, and spatial locality.

Maybe, maybe not. In Haskell you have to allocate your exception value that is passed to the exception handlers (and it's not a single long-jump, but a traversal of the haskell stack until a matching handler is found). While if your function returns a value such as Bool or Int to indicate error cases, it may not allocate anything (Bool datacons are static closures, Int also has some static closures and may also be passed unboxed if strictly used). I wouldn't start by this for a chapter about Haskell/DOD ;-)

[doyougnu]

Of course, but the idea is to at least nail this down for Haskell and explain the machinery that one needs to understand to even answer the question just as @hsyl20 has above. A major goal of HoH is to demystify and so whether error as values are slow or not is an open question. I wanted to write down that example because its a useful test case to check with perf or cachegrind.

[eyeinsky]

@doyougnu I wasn't contesting to what to put in the book :), was just reading what you wrote and wondering if it applies to haskell, or whether it's a summary of the youtube videos.

[doyougnu]

was just reading what you wrote and wondering if it applies to haskell

Ah gotcha, I also am wondering if it applies to Haskell :) the more I think about it the more I'm convinced that that particular claim is not really data-oriented design. But it made me curious to try to empirically observe its impact. In anycase, I really appreciate the engagement! A lot of times I feel like I'm writing into the void and I never really expect anyone to be reading these issues.