3 ms·
This is not only a dated paper (a decade and a half old), but it relies on assumptions that do not necessarily hold in practice. If you test actual allocation
by rbehrends 7y ago
This is not only a dated paper (a decade and a half old), but it relies on assumptions that do not necessarily hold in practice.
If you test actual allocation performance on actual current day hardware, you may end up with completely different results, e.g.:
https://github.com/rbehrends/btree-alloc https://github.com/rbehrends/btree-alloc
- eru 7y agoThat's a very fresh repo. I wonder how GHC would fare. I guess I should contribute.
- rbehrends 7y agoThanks, but I do not plan to extend this project to other languages. I put it together a while ago as an illustration that conventional wisdom regarding GC cost is not what many people think. If I were to expand it, I'd look at other allocation patterns rather than more languages; I've already good a fairly good cross-section of garbage collectors and malloc() implementations, so I don't really need any more.
- eru 7y agoFair enough. Well, too late, I just hacked together a Haskell version based on the OCaml version. It's naive code, but 16 times faster (0.235s vs 3.818s). So I expect some GHC specific optimizations are kicking in. Eg GHC is probably smart enough never to construct the whole tree at once. Whether that counts as the kind of static analysis static of object lifetimes someones else in this thread talked about or not, I don't know. Update: I think it's just common subexpression elimination kicking in..