Earlier quoted context omitted.
Notably, that graph starts at 25 which seems misleading.
Eh it was clearly labeled, and I pretty quickly gleaned that it was like 5 microseconds faster
Given that the chart goes to 80, it was misleading labeling.
Always Bump Downwards (2019)
11–20 of 74 posts
Re: Always Bump Downwards (2019)
#12In the "bump up" version you could remove both the checked_add branches and replace them with a single check at the end, making the amount of branches the same.
Quick example: https://godbolt.org/z/rdv4qnrs8.
*edited to update the example, realized I messed up the comparison logic.
Re: Always Bump Downwards (2019)
#13Earlier quoted context omitted.
I don't think Rust is the issue here. The same integer overflow can occur in any language and should be checked. Integer overflow and underflow is one of the most common security bugs after memory access errors. It is more that bump allocators are so efficient that a relatively inexpensive overflow check can be a significant fraction of their runtime.
It's not integer overflow but pointer overflow. If you're doing small bump allocations and you're anywhere near pointer overflow, it means you're way out of bounds already; the bump allocations you already made were wrong. You need to check whether the allocation increment is out of the zone from which you're allocating, and you need that no matter which direction you go. If the requests are small, you will hit the e…
Or you just add ALIGNMENT-1 and then mask. So if alignment is 16 then you add 15.
Re: Always Bump Downwards (2019)
#14Since the title is less than perfectly perspicuous: It's about "bump allocators", where you allocate memory just by incrementing/decrementing a pointer (and don't free it until you're ready to free up all the memory all at once). These can either allocate "upwards", starting at low addresses and giving you memory at higher addresses for successive allocations, or "downwards", going the other way. The claim being made…
Incidentally, you can choose to bump in both directions. It's more complicated (you need to keep track of which end you allocated each data structure on), but in exchange, the allocator becomes sufficient for many more use cases.
Given a choice, the OP implies that you should position small-but-numerous allocations next to the top, and larger infrequent allocations next to the bottom.
Re: Always Bump Downwards (2019)
#15Earlier quoted context omitted.
It's not integer overflow but pointer overflow. If you're doing small bump allocations and you're anywhere near pointer overflow, it means you're way out of bounds already; the bump allocations you already made were wrong. You need to check whether the allocation increment is out of the zone from which you're allocating, and you need that no matter which direction you go. If the requests are small, you will hit the e…
Or you just add ALIGNMENT-1 and then mask. So if alignment is 16 then you add 15.
Oh right; that's how I've always done it, just forgot. Right. Still, it's an extra addition compared to just masking down.
Re: Always Bump Downwards (2019)
#16Since the title is less than perfectly perspicuous: It's about "bump allocators", where you allocate memory just by incrementing/decrementing a pointer (and don't free it until you're ready to free up all the memory all at once). These can either allocate "upwards", starting at low addresses and giving you memory at higher addresses for successive allocations, or "downwards", going the other way. The claim being made…
Incidentally, you can choose to bump in both directions. It's more complicated (you need to keep track of which end you allocated each data structure on), but in exchange, the allocator becomes sufficient for many more use cases. Given a choice, the OP implies that you should position small-but-numerous allocations next to the top, and larger infrequent allocations next to the bottom.
This sounds like it would make the alloc logic much more complicated and branch-y, defeating the purpose of bumping down anyway, unless your implying some compile-time way to do this.
Re: Always Bump Downwards (2019)
#17Earlier quoted context omitted.
I don't think Rust is the issue here. The same integer overflow can occur in any language and should be checked. Integer overflow and underflow is one of the most common security bugs after memory access errors. It is more that bump allocators are so efficient that a relatively inexpensive overflow check can be a significant fraction of their runtime.
It's not integer overflow but pointer overflow. If you're doing small bump allocations and you're anywhere near pointer overflow, it means you're way out of bounds already; the bump allocations you already made were wrong. You need to check whether the allocation increment is out of the zone from which you're allocating, and you need that no matter which direction you go. If the requests are small, you will hit the e…
I would definitely be in favor of an even faster `SmallBump` variant which assumes that the allocations are small w.r.t. usize::MAX for some additional speed.
I also wouldn't mind the a default "fast" bump allocator library to do all tricks it can without sacrificing safety.
Re: Always Bump Downwards (2019)
#18Earlier quoted context omitted.
I think the lesson is "safety comes at a cost. If you bump downwards you can avoid those safety checks" I don't think the lesson is "let's just write unsafe code"
Caller asks for a 500 megabyte downward bump allocation in a 32 bit system. Do you check for underflow or not?
You check to make sure the size requested is less than or equal to current pointer - chunk start and fail if it is bigger.
Let's face facts, the allocator, even with this additional check, is still going to be blazing fast compared to malloc() or whatever. If you're allocating so much that the handful of extra instructions is going to be a significant slowdown, maybe structure your allocations differently?
Re: Always Bump Downwards (2019)
#19So lesson is don’t use safe Rust code when writing something like a memory allocator where an overflow check is deemed by the author to be too slow? Update: >To handle both these cases, we will use checked addition and return a null pointer if either addition overflows. Here is the new Rust source code: I’m still filling this under “Author made arbitrary decision and result is arbitrary solution is slower as a result…
No, the lesson is to work with the safety mechanisms to accomplish both fast and safe result. If I'm writing code in language A, I don't choose to throw out one of the foundational aspects of that language on the grounds that it's merely inconvenient.
Re: Always Bump Downwards (2019)
#20Earlier quoted context omitted.
Incidentally, you can choose to bump in both directions. It's more complicated (you need to keep track of which end you allocated each data structure on), but in exchange, the allocator becomes sufficient for many more use cases. Given a choice, the OP implies that you should position small-but-numerous allocations next to the top, and larger infrequent allocations next to the bottom.
This sounds like it would make the alloc logic much more complicated and branch-y, defeating the purpose of bumping down anyway, unless your implying some compile-time way to do this.
No, the idea is that you manually make some allocations downward from the top and some allocations upward from the bottom. The bumping code is as simple as in the unidirectional case.
The tricky part is choosing in a way that puts you noticeably ahead of the unidirectional allocator re: what problems you can solve, without putting excessive mental load on yourself. I've found a pattern of "long-lived allocations on one end, short-lived allocations on the other" to work well here (which, yes, doesn't always coincide with the numerous vs. infrequent axis mentioned in my previous comment).