Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Data-Oriented Design chapter #112

Open
doyougnu opened this issue Aug 23, 2024 · 6 comments
Open

Data-Oriented Design chapter #112

doyougnu opened this issue Aug 23, 2024 · 6 comments

Comments

@doyougnu
Copy link
Collaborator

doyougnu commented Aug 23, 2024

references:

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
Copy link
Collaborator Author

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
Copy link

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
Copy link
Collaborator

hsyl20 commented Sep 26, 2024

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
Copy link
Collaborator Author

doyougnu commented Sep 26, 2024

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
Copy link

@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
Copy link
Collaborator Author

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
Status: To do
Development

No branches or pull requests

3 participants