FAQ
Hi,


I'd like to know how does the reallocation process for slices / maps
reallocation works with regards to the memory layout?
Will the allocator assign a new continuous memory area for the values to be
used? Or will it allow for segmentation, meaning the "initial area" can be
split from the "new area"?

From my (very basic) knowledge of how things work I lean towards the first
one.

The reason I'm asking this is because I wonder if there could be an option
to have a process like this:
1) define a new slice with an initial capacity, lets call this A
2) fill in the slice
3) resize for the same size as A not with a copy process but rather by
allocating a new zone B
4) fill the new zone as well
5) repeat 3) two - six more times
6) after 5 happens a few times reallocate everything in a new, continuous
memory area
7) now consider the new memory area as zone A and continue with it from 2)
as needed

This could lead maybe to some improvements in the compiler / runtime which
could detect when allocations happen in a loop (say write lots of entries
in a slice) and, at the end of the loop, unify all the segments in a single
zone for example.
Might not be the brightest idea as you need always to have 2x the memory
size of your slice available (unless the performance impact for leaving the
memory fragmented is small enough). On the other hand, the throughput in
creating such an slice / map should be increased due to less copying around
of elements when reallocation happens (no?)

Thank you.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Search Discussions

  • James Aguilar at Feb 15, 2016 at 2:31 am
    What you're describing is basically how the C++ deque is typically implemented. It's not a bad idea, but flexibility like this in the basic array type of a programming language is not great. The reason is that this extra complexity now has to be managed anywhere slices are used, slowing down other cases that can't benefit from the optimization. Meanwhile, in the current state of the world, anyone is free to write this optimization by hand if profiling finds that it would be helpful.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Keith Randall at Feb 16, 2016 at 1:32 am

    On Sunday, February 14, 2016 at 6:31:15 PM UTC-8, James Aguilar wrote:
    What you're describing is basically how the C++ deque is typically
    implemented. It's not a bad idea, but flexibility like this in the basic
    array type of a programming language is not great. The reason is that this
    extra complexity now has to be managed anywhere slices are used, slowing
    down other cases that can't benefit from the optimization. Meanwhile, in
    the current state of the world, anyone is free to write this optimization
    by hand if profiling finds that it would be helpful.

    Just to be clear, in any segmented scheme the implementation of s[i]
    becomes much more complicated. Our current philosophy is that the speed of
    s[i] trumps any improvement to s=append(s, x).

    Of course, there is at least the possibility of optimizing for both. Maybe
    we can delay the reorganization into a contiguous slice until a certain
    number of s[i] operations have happened. But I don't know how you would do
    that efficiently. How do you record that info? How do you synchronize the
    copy if it doesn't happen at append time? Just among many of the questions
    that would need to be answered. I don't see any such scheme actually
    working.

    Your idea of using the compiler to optimize some of this sounds more
    fruitful. If there's a loop that does appends but no [i] (and related)
    operations, then I think we could find a workable scheme to do appends in
    chunks and reorg only at the end of the loop. (Or preallocate the right
    size to begin with - see for example
    https://github.com/golang/go/issues/14325 .)

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Florin Patan at Feb 16, 2016 at 10:46 pm
    Hi James, Keith,

    Thank you for replies.
    Indeed C++'s deque sounds something like what I'm looking for, only that
    I'd "like" to use that principle only for the creation part (in the for
    loop), then "migrate" everything in a single, continuous memory area.
    To explain it a bit better, I would imagine that since on every resize a
    large chunk of data has to be moved around (for medium to large
    slices/maps). it's better to move data around say every 2-4 times when
    resizing not every resize.
    Also, maybe on a similar idea, can the current allocator detect if it can
    append the memory being used for a slice, and thus remove the need to move
    the data, rather than creating a memory area?
    https://github.com/golang/go/issues/14325
    <https://www.google.com/url?q=https%3A%2F%2Fgithub.com%2Fgolang%2Fgo%2Fissues%2F14325&sa=D&sntz=1&usg=AFQjCNHr4yPso8v_UFSjRhAg1IJWEgJZ9Q> sounds
    like a good step forward and I guess it would eliminate my initial idea.


    Kind regards,
    Florin

    On Tuesday, February 16, 2016 at 2:32:29 AM UTC+1, keith....@gmail.com
    wrote:

    On Sunday, February 14, 2016 at 6:31:15 PM UTC-8, James Aguilar wrote:

    What you're describing is basically how the C++ deque is typically
    implemented. It's not a bad idea, but flexibility like this in the basic
    array type of a programming language is not great. The reason is that this
    extra complexity now has to be managed anywhere slices are used, slowing
    down other cases that can't benefit from the optimization. Meanwhile, in
    the current state of the world, anyone is free to write this optimization
    by hand if profiling finds that it would be helpful.

    Just to be clear, in any segmented scheme the implementation of s[i]
    becomes much more complicated. Our current philosophy is that the speed of
    s[i] trumps any improvement to s=append(s, x).

    Of course, there is at least the possibility of optimizing for both.
    Maybe we can delay the reorganization into a contiguous slice until a
    certain number of s[i] operations have happened. But I don't know how you
    would do that efficiently. How do you record that info? How do you
    synchronize the copy if it doesn't happen at append time? Just among many
    of the questions that would need to be answered. I don't see any such
    scheme actually working.

    Your idea of using the compiler to optimize some of this sounds more
    fruitful. If there's a loop that does appends but no [i] (and related)
    operations, then I think we could find a workable scheme to do appends in
    chunks and reorg only at the end of the loop. (Or preallocate the right
    size to begin with - see for example
    https://github.com/golang/go/issues/14325 .)
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Keith Randall at Feb 17, 2016 at 1:18 am

    On Tuesday, February 16, 2016 at 2:46:51 PM UTC-8, Florin Patan wrote:
    Hi James, Keith,

    Thank you for replies.
    Indeed C++'s deque sounds something like what I'm looking for, only that
    I'd "like" to use that principle only for the creation part (in the for
    loop), then "migrate" everything in a single, continuous memory area.
    To explain it a bit better, I would imagine that since on every resize a
    large chunk of data has to be moved around (for medium to large
    slices/maps). it's better to move data around say every 2-4 times when
    resizing not every resize.
    Also, maybe on a similar idea, can the current allocator detect if it can
    append the memory being used for a slice, and thus remove the need to move
    the data, rather than creating a memory area?
    For small objects (<32KB?) the Go allocator keeps objects segregated by
    size. As a result, it isn't possible to allocate the subsequent object and
    avoid the copy. For large objects, it may be possible.

    https://github.com/golang/go/issues/14325
    <https://www.google.com/url?q=https%3A%2F%2Fgithub.com%2Fgolang%2Fgo%2Fissues%2F14325&sa=D&sntz=1&usg=AFQjCNHr4yPso8v_UFSjRhAg1IJWEgJZ9Q> sounds
    like a good step forward and I guess it would eliminate my initial idea.


    Kind regards,
    Florin

    On Tuesday, February 16, 2016 at 2:32:29 AM UTC+1, keith....@gmail.com
    wrote:

    On Sunday, February 14, 2016 at 6:31:15 PM UTC-8, James Aguilar wrote:

    What you're describing is basically how the C++ deque is typically
    implemented. It's not a bad idea, but flexibility like this in the basic
    array type of a programming language is not great. The reason is that this
    extra complexity now has to be managed anywhere slices are used, slowing
    down other cases that can't benefit from the optimization. Meanwhile, in
    the current state of the world, anyone is free to write this optimization
    by hand if profiling finds that it would be helpful.

    Just to be clear, in any segmented scheme the implementation of s[i]
    becomes much more complicated. Our current philosophy is that the speed of
    s[i] trumps any improvement to s=append(s, x).

    Of course, there is at least the possibility of optimizing for both.
    Maybe we can delay the reorganization into a contiguous slice until a
    certain number of s[i] operations have happened. But I don't know how you
    would do that efficiently. How do you record that info? How do you
    synchronize the copy if it doesn't happen at append time? Just among many
    of the questions that would need to be answered. I don't see any such
    scheme actually working.

    Your idea of using the compiler to optimize some of this sounds more
    fruitful. If there's a loop that does appends but no [i] (and related)
    operations, then I think we could find a workable scheme to do appends in
    chunks and reorg only at the end of the loop. (Or preallocate the right
    size to begin with - see for example
    https://github.com/golang/go/issues/14325 .)
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedFeb 15, '16 at 12:39a
activeFeb 17, '16 at 1:18a
posts5
users3
websitegolang.org

People

Translate

site design / logo © 2022 Grokbase