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

runtime: reserve address space for large slice backing stores to make slice growth cheaper #57337

Open
snadrus opened this issue Dec 15, 2022 · 3 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. FeatureRequest NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Milestone

Comments

@snadrus
Copy link

snadrus commented Dec 15, 2022

When append() sees the underlying array is used to capacity, it allocates a bigger array, copies values, zeroes the rest, and returns.

This proposal will make this grow() logic cheaper:

If the OS offered an extend() then it would be possible to avoid the copy. However this is unlikely because the following virtual address space is often claimed already.

Q: In supported 64-bit OSes, what if all unbounded requests asked the OS for 1TB of reserved memory?
A: Then most all grow() calls could just claim and zero the next chunk of reserved memory. That's because extra reserved memory is just an address until it page-faults into existence.

In practical terms, I see 2 ways to go:

  1. Expressing 1TB of capacity to the user would require either zeroing on exposure.
  2. Expressing a much smaller capacity to the user would require the allocator to have a separate capacity concept that it would consult to determine if a new allocation is necessary (typically not).

There's likely a refinement sweet-spot around the variables of:

  • at what growth size should we allocate a giant allocation?
  • how big is giant allocation (1TB in the example above)?
  • should we have a smaller "giant allocation" for initial slices, like initially 1MB then 1TB?
  • Does this upset the Linux OOM killer?
@gopherbot gopherbot added this to the Proposal milestone Dec 15, 2022
@mateusz834
Copy link
Contributor

mateusz834 commented Dec 15, 2022

I don't think that this is safe to do, consider:

a := make([]byte, 16, 16)
b := append(a, 1)
if &a[0] == &b[0] {
	panic("sth weird")
}

This is not going to fail with the current go version.

@snadrus
Copy link
Author

snadrus commented Dec 15, 2022

The difference @mateusz834 found is not guaranteed The spec says:

  • If the capacity of s is not large enough to fit the additional values, append allocates a new, sufficiently large underlying array that fits both the existing slice elements and the additional values. Otherwise, append re-uses the underlying array.

There's no guarantee of an address change. An advanced version of the compiler could do the same.

@seankhliao seankhliao changed the title proposal: Cheap grow() calls runtime: Cheap grow() calls Dec 15, 2022
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Dec 15, 2022
@seankhliao seankhliao removed this from the Proposal milestone Dec 15, 2022
@seankhliao seankhliao added the NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one. label Dec 15, 2022
@mknyszek
Copy link
Contributor

mknyszek commented Dec 21, 2022

Slice backing arrays are just allocated from the usual heap (except where they're of course, stack allocated). Something like this would be complex to implement since it would basically have to be a separate mechanism entirely. All the usual GC paths would also need to know about this special address space mapping for each slice backing store.

I think the worst part here might be the overhead of mapping new memory for a new slice backing store to begin with; it's a fairly expensive operation, and small slices are common.

Unless, you mean to apply this optimization to only large slices, which is more feasible. Today, it wouldn't be too hard to implement an "try extend" operation in the page allocator, though I suspect it wouldn't succeed often; within a GC cycle, the runtime is generally good at densely packing memory at the granularity of pages, since most page allocations consist of a single page.

Your memory reservation idea for large slice backing stores only (say, >2 MiB or something) I think has merit, though I suspect at that point a much more effective workaround is to just overallocate the capacity of the slice in user code to begin with. The runtime is generally okay about not zeroing newly-mapped memory, so there should be no zeroing overhead. (And the fact that the capacity is oversized should mean that copies are avoided as well.)

@mknyszek mknyszek changed the title runtime: Cheap grow() calls runtime: reserve address space for large slice backing stores to make slice growth cheaper Dec 21, 2022
@mknyszek mknyszek added this to the Unplanned milestone Dec 21, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. FeatureRequest NeedsInvestigation Someone must examine and confirm this is a valid issue and not a duplicate of an existing one.
Projects
Status: No status
Development

No branches or pull requests

5 participants