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

bytes: inefficient Buffer.grow algorithm #42984

Open
dsnet opened this issue Dec 3, 2020 · 5 comments
Open

bytes: inefficient Buffer.grow algorithm #42984

dsnet opened this issue Dec 3, 2020 · 5 comments

Comments

@dsnet
Copy link
Member

@dsnet dsnet commented Dec 3, 2020

According to sizeclasses.go, allocating any amount of space greater than the previous size class and below the current size class is inefficient (e.g., allocating 257B is 11% wasteful since it allocates 288B anyways).

The current Buffer.grow algorithm is inefficient since it may choose a buffer size that is in-between size classes, rather than optimally using the entire size class.

For example:

var bb bytes.Buffer
bb.Write(make([]byte, 1<<12))
fmt.Println(cap(bb.Bytes())) // exactly 1<<12
bb.WriteByte('a')
fmt.Println(cap(bb.Bytes())) // exactly (1<<13) + 1, 13.5% waste

While we should avoid teaching Buffer.grow about size classes, it could choose values that align with 2n or 2n+2n-1, which would have a high probability of lying exactly on a type-class boundary.

@josharian
Copy link
Contributor

@josharian josharian commented Dec 4, 2020

Related, for your entertainment: https://commaok.xyz/post/discovering-size-classes/

@martisch
Copy link
Contributor

@martisch martisch commented Dec 4, 2020

If buffer.grow would use append+make slice extending idiom to grow it could get that benefit without using sizeclasses: #21266

A size class aware make would also be an option if an addition to the Go language would be accepted: #24204

@cagedmantis cagedmantis added this to the Backlog milestone Dec 4, 2020
@cagedmantis
Copy link
Contributor

@cagedmantis cagedmantis commented Dec 4, 2020

@dsnet
Copy link
Member Author

@dsnet dsnet commented Dec 4, 2020

If buffer.grow would use append+make slice extending idiom to grow it could get that benefit without using sizeclasses

The current implementation of append has a growth rate that approaches 1.25x as the slice gets larger.
The current implementation of Buffer.grow has a growth rate of 2x.

While a growth rate of 1.25x is more memory efficient, it's probably slower due to the increased number of allocations+copying. Switching the growth rate from 2x to 1.25x seems to be a more substantial change than just addressing the wasted space.

@dsnet
Copy link
Member Author

@dsnet dsnet commented Dec 4, 2020

Nevermind, ignore my comment, I just realized an append+make effectively allows you control the growth rate by controlling the size of the make.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
4 participants