-
Notifications
You must be signed in to change notification settings - Fork 9
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
Idea: Allocation Splitting #105
Comments
I don't know if any allocator actually supports this. |
One that's directly backed by |
When I came up with the idea I was more thinking about allocators that might use other storage as backing perhaps? Like using a big slice of static bytes as backing storage in an embedded environment, or perhaps providing restricted memory usage for some sub-process function. For these sorts of allocators being able to reduce copies and avoid even temporary allocation is pretty valuable (at least in my opinion), as it can reduce the risk of some inner process unnecessarily overflowing some inner memory usage restriction when it would otherwise be fine. For cases where it can't split an allocation block like that you could have a default fallback that reallocates and copies (like essentially occurs in the default implementation of In terms of issues of allocator chunk size, if you work with allocators more specialised for specific types or with backing storage chunked out to multiples of the alignment of a smaller type, it becomes more relevant, I think. For example I think this allocator would probably be able to split it's allocations into smaller pieces if the type in the layout has a size and alignment of the chunk size. |
Any individual allocator is free to provide its own methods if it can do something special (such as forcibly resetting a bump allocator). However, if it's not something that can generally be provided by most or all allocators then it's not a good fit for the Allocator trait in general. |
The issue with that - at least IMO - is that it means that the liballoc collections are essentially pessimistic in how they use memory when the option to avoid copies is available, which forces anyone who wants to take advantage of a feature like this for an allocator to rewrite their own data structures. Especially in the case of larger Vecs being chunked off into smaller pieces, such an ability in an allocator could provide a significant performance advantage when available by avoiding linear copies if unnecessary. We already have grow and shrink with appropriately defined fallbacks for when an allocator doesn't support them, so I think adding another allocator primitive with a fallback like that would be worth the potentially significant performance gains in some cases, and avoid requiring people reimplement Vec just to get a single function like that. Of course there is the potential issue of people being careless with this kind of splitting in cases where an allocator does not have that capability and such that the vectors in question just constantly allocate, but such a situation would already be the case if you need to copy the contents to a new location anyhow. |
I mean it would be nice, but I've never seen an allocator that provides this functionality. It seems difficult to implement in a way that's very memory efficient, which seems important for those cases. Regardless, even if it is possible to implement efficiently (not really on topic for this discussion), there are plenty of niche allocator APIs that aren't worth providing on the Allocator trait, even though that means the standard collections can't use them. |
The existence of Note though that adding new allocator methods isn't (nearly) free the way adding defaulted methods to other traits is. Adding a method to a trait adds an entry to the vtable to reference the implementation function. For a normal trait, this cost is fairly negligible. For For something like aside about
|
Ahhh, I wasn't aware of some of that special runtime magic necessary for this. My main interest in this potential allocation primitive comes from attempting to combine zero copy parsing and partial/interruptible parsing where buffers may be extended by further input, where being able to peel off of owning buffers of input efficiently without copying or extra space is highly useful (as it allows you to detach the lifetimes of two halves of a buffer so that the second can be modified while something else holds onto the first). I also realised this might provide significant benefits for the case where people construct tree structures out of sequential backing buffers for primarily reading. I think I may have been underrecognising how specialised this concept seems, especially with having to add runtime magic. Still, I will probably be adding this as a specialised trait to my own library instead as in my case it provides very significant performance gains in that case. And the optimiser point is a good one, though I think in that case it would be a tradeoff of if you are meta-optimising for the case where people always or often use the split-off piece and extend that, or the case where they only rarely use it and hence the extra allocations could have been elided, in combination with how likely people are to write to the first half, forcing an allocation. 12 thoughts on storageI'm definitely interested in the idea of a storage API (I'm fairly ambivalent on the issue of storage vs allocators for containers) and I can certainly see how putting this sort of function on a multi-storage might be more viable than on allocators where it's a fairly niche feature, unlike storages where splitting things in half is a fairly standard capability.I think there's be some issues with splitting at dynamic offsets though, if we start talking about inline stack-based storages. It works better with the use of references in that case, but that's an implementation detail of storages more than anything and could be easily fixed with a slightly different custom storage.... I might close the issue in another day or two, if people don't think this is viable or people don't have other thoughts on that. To be honest I don't know what the policy for closing and opening issues is. Footnotes
|
Right now, Allocator provides methods to grow and shrink an allocation, as well as to allocate and deallocate. This lets us do things like efficiently grow a Vec without copying if there's more memory available to allocate in the same place, and return that memory to the allocator if it's no longer needed.
However, there is no way currently to divide an allocation in two such that deallocating one half does not deallocate the other.
This means that if you want to, say, split off a vector into two halves, it requires a copy and a new allocation to occur so that one vector does not accidentally deallocate parts of the other vector.
Even if you
shrink_to_fit
the vector before splitting, it is required that there is at least n more bytes available from the allocator (where n is the number of bytes required to store the split off data), and you have to copy it.The idea, then, is to add a method to the
Allocator
trait that looks something like the following:Where the new layout halves have the same alignment as the old layout, and each returned pointer can be deallocated separately.
This would let you develop something like:
which splits a slice into two slices at the given point, each owned independently.
Or perhaps
which divides the underlying slice at the index, leaving the first vector with no free capacity and giving the rest of the underlying slice and capacity to the second vector, which can then do all the standard vector things like trying to grow allocations, shrink, be deallocated or have references taken, etc. With a well-defined allocator, this means that no copying or new allocation has to occur whatsoever.
Especially in the case where an allocator calls out to a systemwide allocator, this might provide significant performance benefits if chunking up large pieces of data to pass around in which only small amounts of that data are likely to get modified afterwards, even where the original large buffer might disappear later (which prevents the use of typical slice splitting methods due to lifetime complexity).
This could also make conversion of owned types like String into tree-ish types like string ropes far more efficient as well, reducing copies significantly by allowing owned chunks of data to be split in a similar manner to what we can do with slices today.
Thoughts?
The text was updated successfully, but these errors were encountered: