Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Always Bump Downwards (2019)

fitzgeraldnick.com

Post reply on HN
Print view View original

61–70 of 74 posts

Re: Always Bump Downwards (2019)

#61

Post by loeg »

rictic wrote: post #52
loeg wrote: post #44

Earlier quoted context omitted.

The API should restrict callers from providing bogus values at all.

How would the API do that without more overhead than the check that GP is suggesting?

For some uses it might be reasonable to restrict the size input to compile-time constants, which can be verified at compile time. Or you could have a newtype with a checked safe constructor and an unchecked unsafe constructor, which allows bypassing the overhead when you know the sizes are reasonable. On 64-bit systems, it is reasonable in many domains to restrict allocation size to u32. There are lots of possible ways to approach this without falling back to "tolerate any usize input."

Re: Always Bump Downwards (2019)

#62

Post by loeg »

sltkr wrote: post #53
loeg wrote: post #43

Earlier quoted context omitted.

I think it would be pretty reasonable to have an input type for that parameter that isn't a full usize and is instead some more restricted type that can only represent smaller values. The alignment parameter could be, like, u8, or maybe u16.

This still doesn't solve the overflow problem. It's also too limiting: with u8 you can't ask for page-aligned data, and with u16 not for hugepage-aligned data. Granted, those aren't exactly prime use cases for a bump allocator, but it seems like poor design to limit the API unnecessarily.

It fully solves the overflow problem. You don't need page-aligned data in a bump allocator.

Re: Always Bump Downwards (2019)

#63

Post by loeg »

saagarjha wrote: post #55
loeg wrote: post #34

Earlier quoted context omitted.

The straightforward answer is: don't tolerate ridiculous alignments.

You'd need to check for that, though.

No, just restrict the domain of the alignment input to like, u8. Maybe u16. Either way, it is easy to ensure your bump allocation space is far enough away from SIZE_MAX.

Re: Always Bump Downwards (2019)

#64

Post by asalahli »

conradludgate wrote: post #60
asalahli wrote: post #51

The rust code for rounding down is given as let new_ptr = new_ptr & !(align - 1); But I don't see rdx decremented before being negated and AND'ed with rax, in the assembly. What am I missing?

It's being converted into `-align` which is equivalent under twos compliment

I don't follow. Are you saying `new_ptr & -align` is equivalent to `new_ptr & !(align - 1)`?

Edit: I get it now. My brain was interpreting NEG as NOT for some reason.

Re: Always Bump Downwards (2019)

#65

Post by zeusk »

pizlonator wrote: post #48
titzer wrote: post #45

Earlier quoted context omitted.

In most situations, the allocation size is a constant and bumping upwards can be done without an overflow check because the region cannot be close enough to the upper part of memory to wrap around. I'm surprised that there was no discussion of memory system performance. There are tons of OS-level and hardware prefetcher optimizations for forward-marching pointer references and zero-page allocation.

You can bump upwards without an overflow check even if the size is variable. I’ve seen multiple ways to do it. And I’ve lost days of my life to coming up with pointlessly amusing variants that get there in weird ways. Yeah I’m also amused that they didn’t get into the fact that downward bump is just not what the HW expects you to do. You’d need a real benchmark to see that effect. And, it’s an open question whether t…

> fact that downward bump is just not what the HW expects you to do.

Where do you get this fact from? ARM and x86 have a descending stack (<= ARMv7 supported stack growing in either direction).

Re: Always Bump Downwards (2019)

#66

Post by tel »

lowbloodsugar wrote: post #37
tel wrote: post #17

Earlier quoted context omitted.

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.

And maybe the heap has fixed alignment so you have one that only needs 4 and one that needs 16. Indeed maybe you grow from top and bottom depending. And maybe this is all a giant premature optimization - including the panic about up vs down. My previous career was console video games and maybe this kind of handwringing isn’t required for whatever the fuck this is.

Eh, sure it is. Until it isn't. I'm not using this libraries, but I'm glad they exist.

Re: Always Bump Downwards (2019)

#67

Post by pizlonator »

zeusk wrote: post #65
pizlonator wrote: post #48

Earlier quoted context omitted.

You can bump upwards without an overflow check even if the size is variable. I’ve seen multiple ways to do it. And I’ve lost days of my life to coming up with pointlessly amusing variants that get there in weird ways. Yeah I’m also amused that they didn’t get into the fact that downward bump is just not what the HW expects you to do. You’d need a real benchmark to see that effect. And, it’s an open question whether t…

> fact that downward bump is just not what the HW expects you to do. Where do you get this fact from? ARM and x86 have a descending stack (<= ARMv7 supported stack growing in either direction).

What does downward stack have to do with the cpu predicting that you’ll most likely scan memory in the forward direction?

Re: Always Bump Downwards (2019)

#68

Post by zeusk »

pizlonator wrote: post #67
zeusk wrote: post #65

Earlier quoted context omitted.

> fact that downward bump is just not what the HW expects you to do. Where do you get this fact from? ARM and x86 have a descending stack (<= ARMv7 supported stack growing in either direction).

What does downward stack have to do with the cpu predicting that you’ll most likely scan memory in the forward direction?

Your stack is entirely data, why do you think a CPU couldn't predict access patterns on stack?

Prefetchers can predict negative offset/decrements since 1980s

Re: Always Bump Downwards (2019)

#69

Post by pizlonator »

zeusk wrote: post #68
pizlonator wrote: post #67

Earlier quoted context omitted.

What does downward stack have to do with the cpu predicting that you’ll most likely scan memory in the forward direction?

Your stack is entirely data, why do you think a CPU couldn't predict access patterns on stack? Prefetchers can predict negative offset/decrements since 1980s

Because stacks aren’t unbounded. You grow and shrink them. Therefore, regardless of which direction it grows in, it also shrinks in the opposite direction with the same likelihood.

Re: Always Bump Downwards (2019)

#70

Post by wrsh07 »

kazinator wrote: post #9
pavon wrote: post #6

Earlier 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…

Since we're both thinking about this...

Is rust warning you about pointer overflow? My understanding is that rust is complaining about integer overflow but perhaps that's insufficient?

(I don't actually know which solution is better/worse from perf perspective besides author's post)

Post reply on HN