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

41–50 of 74 posts

Re: Always Bump Downwards (2019)

#41

Post by Conscat »

dev_dwarf wrote: post #21
chrchang523 wrote: post #20

Earlier quoted context omitted.

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

Ok, I get it now. It would add an extra ptr to the struct, but wouldn't be significant overhead. I do wonder what benefit there is for you over just having two separate allocators, one for long term and one for short term. I imagine there could be benefits in very memory constrained scenarios.

A double ended stack allocator is not an uncommon primitive in video games.

Re: Always Bump Downwards (2019)

#42

Post by sltkr »

loeg wrote: post #35
sltkr wrote: post #26

Earlier quoted context omitted.

That version is unsafe: what if size == 0xfff..fff and alignment is needed? You will end up with ptr edit : code moved to a toplevel comment

No allocator can be expected to allocate usize::MAX, so it doesn't really matter.

It matters because if the allocator cannot allocate a given amount, it should reliably return NULL to iform the caller that the allocation failed, not return a random invalid pointer that's not usable, which will lead to undefined behavior.

Re: Always Bump Downwards (2019)

#43

Post by loeg »

dev_dwarf wrote: post #38
loeg wrote: post #35

Earlier quoted context omitted.

No allocator can be expected to allocate usize::MAX, so it doesn't really matter.

Agreed. The question really is if you should demand the user to enforce that constraint on the size they pass to you, or if the function itself should signal an error in that case.

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.

Re: Always Bump Downwards (2019)

#44

Post by loeg »

sltkr wrote: post #42
loeg wrote: post #35

Earlier quoted context omitted.

No allocator can be expected to allocate usize::MAX, so it doesn't really matter.

It matters because if the allocator cannot allocate a given amount, it should reliably return NULL to iform the caller that the allocation failed, not return a random invalid pointer that's not usable, which will lead to undefined behavior.

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

Re: Always Bump Downwards (2019)

#45

Post by titzer »

pizlonator wrote: post #25

It’s possible to write many other bump algorithms, including ones that bump upwards but generate much much better code than OP’s forward upward bump. In particular, no overflow checks are needed if you write it carefully enough. My favorite is one where I only use subtraction but the direction of allocation is in the positive direction (I subtract a `remaining` counter, and the returned address is `end - remaining`).…

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.

Re: Always Bump Downwards (2019)

#46

Post by dev_dwarf »

loeg wrote: post #43
dev_dwarf wrote: post #38

Earlier quoted context omitted.

Agreed. The question really is if you should demand the user to enforce that constraint on the size they pass to you, or if the function itself should signal an error in that case.

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.

For the alignment parameter I agree.

Re: Always Bump Downwards (2019)

#47

Post by toast0 »

dev_dwarf wrote: post #21
chrchang523 wrote: post #20

Earlier quoted context omitted.

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

Ok, I get it now. It would add an extra ptr to the struct, but wouldn't be significant overhead. I do wonder what benefit there is for you over just having two separate allocators, one for long term and one for short term. I imagine there could be benefits in very memory constrained scenarios.

BEAM (Erlang) uses something similar for process memory; a process gets a chunk of memory, heap grows up, stack grows down; when they meet, trigger GC, and if that doesn't reclaim enough, allocate a larger chunk of memory. More details if you're interested [1]. In general, I'd think anywhere that the combined size of two allocators should be a consideration, one going up and one going down would make a lot of sense.

[1] https://www.erlang.org/doc/apps/erts/garbagecollection

Re: Always Bump Downwards (2019)

#48

Post by pizlonator »

titzer wrote: post #45
pizlonator wrote: post #25

It’s possible to write many other bump algorithms, including ones that bump upwards but generate much much better code than OP’s forward upward bump. In particular, no overflow checks are needed if you write it carefully enough. My favorite is one where I only use subtraction but the direction of allocation is in the positive direction (I subtract a `remaining` counter, and the returned address is `end - remaining`).…

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 this would matter unless your allocation rate was obscene (if it isn’t then most scans of memory will be normal loops and not the allocator).

Re: Always Bump Downwards (2019)

#49

Post by dev_dwarf »

toast0 wrote: post #47
dev_dwarf wrote: post #21

Earlier quoted context omitted.

Ok, I get it now. It would add an extra ptr to the struct, but wouldn't be significant overhead. I do wonder what benefit there is for you over just having two separate allocators, one for long term and one for short term. I imagine there could be benefits in very memory constrained scenarios.

BEAM (Erlang) uses something similar for process memory; a process gets a chunk of memory, heap grows up, stack grows down; when they meet, trigger GC, and if that doesn't reclaim enough, allocate a larger chunk of memory. More details if you're interested [1]. In general, I'd think anywhere that the combined size of two allocators should be a consideration, one going up and one going down would make a lot of sense.…

Thats an interesting idea. I'm not sure I'm sold on it v.s. just having two seperate allocators and growing them seperately. The arena allocators I use take advantage of virtual memory to grow which might change my perception of the tradeoffs involved, as I wouldn't typically need to resize one of my allocators (you can just aggressively over-reserve memory and then only commit what is actually used).

Re: Always Bump Downwards (2019)

#50

Post by loeg »

dev_dwarf wrote: post #46
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.

For the alignment parameter I agree.

For both.
Post reply on HN