Extending an array 'The right way'. Guidence needed!
224 views
Skip to first unread message
Stuart Davies
Oct 15, 2019, 6:16:35 AM10/15/19
to golang-nuts
Hi
I have a slice backed by an array.
My understanding is that I can extend the slice (append) up to the capacity of the array.
After that I do not understand the correct procedure. Append fails when the backing array indexes are exceeded.
So I have this temporary piece of code:
if p.LineCount >= len(p.Offsets) {
newLen := p.LineCount + 50
sb := make([]int64, newLen)
for i := 0; i < p.LineCount; i++ {
sb[i] = p.Offsets[i]
}
p.Offsets = sb
}
I know there must be an array copy function that will do this more efficiently but I failed to find it!
Please help.
Jan Mercl
Oct 15, 2019, 7:03:22 AM10/15/19
to Stuart Davies, golang-nuts
On Tue, Oct 15, 2019 at 12:16 PM Stuart Davies <sdd.d...@gmail.com> wrote:
> I have a slice backed by an array.
>
> My understanding is that I can extend the slice (append) up to the capacity of the array.
I guess that by 'extend the slice' you mean reslicing. Yes, that can
> I have a slice backed by an array.
>
> My understanding is that I can extend the slice (append) up to the capacity of the array.
be done while len <= cap. However, appending is a different operation,
performed by the predeclared function `append`.
Please let us know what is the ultimate goal you need to achieve. Best
is to share the minimal, compilable code you have already at the Go
playground: https://play.golang.org
Stuart Davies
Oct 15, 2019, 7:24:07 AM10/15/19
to golang-nuts
My goal is to contain a list of integers that may extend to possibly a couple of thousand entries. Initial size is 100. Extensions add 50 entries at a time.
I declared the array initially with:
make([]int64, 100).
I tried using the Append function but could not Append past the 100 entries. The 101 entry threw a panic so I detirmined to extend the array myself.
I would have thought Append should extend if required but it did not (or am I using it incorrectly). I looked at some other code examples but could not find a solution.
In C there is an array copy function that is implemented by the processor directly, it's been a long time since I used C and assembler but I rememer there were non overlapping mem copy instructions that would make an array copy very fast.
Is there somthing similar in GO.
This is a general question, it is not really specific to my application. I just want to know the best practices for 'extending' an array of arbitrary type.
Wojciech S. Czarnecki
Oct 15, 2019, 7:33:16 AM10/15/19
to golan...@googlegroups.com
On Tue, 15 Oct 2019 03:16:35 -0700 (PDT)
Stuart Davies <sdd.d...@gmail.com> wrote:
> Hi
>
> I have a slice backed by an array.
>
> My understanding is that I can extend the slice (append) up to the
> capacity of the array.
Its good understanding.
Stuart Davies <sdd.d...@gmail.com> wrote:
> Hi
>
> I have a slice backed by an array.
>
> My understanding is that I can extend the slice (append) up to the
> capacity of the array.
> Append fails when the backing array indexes are exceeded.
> I know there must be an array copy function that will do this more
> efficiently but I failed to find it!
https://golang.org/ref/spec#Appending_and_copying_slices
> Please help.
Hope this helps,
--
Wojciech S. Czarnecki
<< ^oo^ >> OHIR-RIPE
Wojciech S. Czarnecki
Oct 15, 2019, 7:44:28 AM10/15/19
to golan...@googlegroups.com
Uh, the important citation got deleted somehow:
[...]
https://golang.org/ref/spec#Appending_and_copying_slices
"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. "
Correct use of append is to reassign the target array:
target = append(target, toappend)
then append will take care of resizing/copying for you.
[...]
https://golang.org/ref/spec#Appending_and_copying_slices
"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. "
Correct use of append is to reassign the target array:
target = append(target, toappend)
then append will take care of resizing/copying for you.
Marvin Renich
Oct 15, 2019, 7:53:06 AM10/15/19
to golang-nuts
[When you are replying to someone else's message, reply to that message,
not your original message. Your reply lost the context of the message
to which you were replying (Jan Mercl's).]
* Stuart Davies <sdd.d...@gmail.com> [191015 07:24]:
properly. There is a good explanation of slices on the Go blog at
«https://blog.golang.org/go-slices-usage-and-internals». The builtin
append function will append to the existing backing array if there is
enough capacity, but will allocate a new backing array if necessary.
Because of this, it always returns the new slice, and you must use the
returned slice, rather than the original. Here is a playground link
demonstrating the use of append:
«https://play.golang.org/p/5Pl16hN-T5u».
...Marvin
not your original message. Your reply lost the context of the message
to which you were replying (Jan Mercl's).]
* Stuart Davies <sdd.d...@gmail.com> [191015 07:24]:
> My goal is to contain a list of integers that may extend to possibly a
> couple of thousand entries. Initial size is 100. Extensions add 50 entries
> at a time.
>
> I declared the array initially with:
>
> make([]int64, 100).
>
> I tried using the Append function but could not Append past the 100
> entries. The 101 entry threw a panic so I detirmined to extend the array
> myself.
>
> I would have thought Append should extend if required but it did not (or am
> I using it incorrectly). I looked at some other code examples but could not
> find a solution.
>
> In C there is an array copy function that is implemented by the processor
> directly, it's been a long time since I used C and assembler but I rememer
> there were non overlapping mem copy instructions that would make an array
> copy very fast.
>
> Is there somthing similar in GO.
>
> This is a general question, it is not really specific to my application. I
> just want to know the best practices for 'extending' an array of arbitrary
> type.
The append function should do exactly what you want, but you must use it
> couple of thousand entries. Initial size is 100. Extensions add 50 entries
> at a time.
>
> I declared the array initially with:
>
> make([]int64, 100).
>
> I tried using the Append function but could not Append past the 100
> entries. The 101 entry threw a panic so I detirmined to extend the array
> myself.
>
> I would have thought Append should extend if required but it did not (or am
> I using it incorrectly). I looked at some other code examples but could not
> find a solution.
>
> In C there is an array copy function that is implemented by the processor
> directly, it's been a long time since I used C and assembler but I rememer
> there were non overlapping mem copy instructions that would make an array
> copy very fast.
>
> Is there somthing similar in GO.
>
> This is a general question, it is not really specific to my application. I
> just want to know the best practices for 'extending' an array of arbitrary
> type.
properly. There is a good explanation of slices on the Go blog at
«https://blog.golang.org/go-slices-usage-and-internals». The builtin
append function will append to the existing backing array if there is
enough capacity, but will allocate a new backing array if necessary.
Because of this, it always returns the new slice, and you must use the
returned slice, rather than the original. Here is a playground link
demonstrating the use of append:
«https://play.golang.org/p/5Pl16hN-T5u».
...Marvin
Marvin Renich
Oct 15, 2019, 8:04:32 AM10/15/19
to golang-nuts
P.S. If you are still having trouble after reading the responses to your
query, use the go playground (https://play.golang.org/) to create a
simple program that demonstrates what you are trying, and post the link
you get from clicking the "Share" button, and explain what you would
like the output to be. People can then modify your playground entry to
help you.
Note that when passing slices to other functions that might modify the
slice, you either need to return the modified slice or pass a pointer to
the slice. This is why the append function is the way it is.
...Marvin
query, use the go playground (https://play.golang.org/) to create a
simple program that demonstrates what you are trying, and post the link
you get from clicking the "Share" button, and explain what you would
like the output to be. People can then modify your playground entry to
help you.
Note that when passing slices to other functions that might modify the
slice, you either need to return the modified slice or pass a pointer to
the slice. This is why the append function is the way it is.
...Marvin
thatipelli santhosh
Oct 15, 2019, 8:07:37 AM10/15/19
to golang-nuts
Hi Marvin,
I am curious to know if we approx 100000 ( we don't know exact amount of slice entries) add to slice. Slice will grow based on our size of data and underlying array size but doing this create multiple underlying arrays (more memory resource utilization, processing). In such case, what is the optimum solution?
--
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...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/20191015115219.dca3mjcdj54qxslq%40basil.wdw.
Stuart Davies
Oct 15, 2019, 8:55:45 AM10/15/19
to golang-nuts
Ok I will have a rethink.
Is there a way I can control the expansion. I do not want to double the storage each time. I want to be able to control and limit the growth if necessary.
Thanks for the assistance. I will re-read the article.
On Tuesday, 15 October 2019 11:16:35 UTC+1, Stuart Davies wrote:
Marvin Renich
Oct 15, 2019, 10:13:12 AM10/15/19
to golang-nuts
* thatipelli santhosh <santhoshth...@gmail.com> [191015 08:07]:
array with the exact size needed for the new slice; it allocates a slice
with extra capacity. It uses some heuristics to give a reasonable
speed/memory-usage trade-off for "typical" cases. The current algorithm
can be found in src/runtime/slice.go in the function growslice. Note
that the specific algorithm is not covered by the Go compatibility
guarantee.
If you are trying to be practical, you should start by implementing the
obvious and straight-forward algorithm first (i.e. use append as it was
intended), and then profile your code (the whole application, not just
the code that grows the slice) to determine where optimization will be
useful. It is very unlikely that the calls to append will be worth
spending time improving.
If this is an academic question, start the same way, but how you decide
where to spend time analyzing the results may be different.
In an application that is only going to have a slice of about 100,000
integers, the cost of append is unlikely to be of any concern at all on
any real production machine.
If it turns out that the append is a bottleneck (memory or speed), you
can write your own Append function by starting with the AppendByte
function from the go-slices-usage-and-internals blog that I linked to in
my previous message. Do the obvious fix-ups for byte to int (or
whatever your data type is), and modify the algorithm that determines
the capacity of the new slice (the (n+1)*2 in that function). Then use
your Append function instead of the built-in append. (Again, note that
this simple (n+1)*2 is _not_ what the built-in append function uses.)
A very simple first optimization (without resorting to your own Append
function) is to initially create the slice using make([]int, 0,
initialCapacity) where you choose initialCapacity to be larger than the
expected maximum size by some arbitrary percentage (e.g. 25%).
This playground link «https://play.golang.org/p/qtfHaoK-6Hy» shows
exactly where the allocations will occur. It took exactly 28
allocations to reach 100,000 elements. To show how insignificant that
is, on my laptop it took only 11ms to run that program. Is that 11ms
really significant in your program?
...Marvin
> Hi Marvin,
>
> I am curious to know if we approx 100000 ( we don't know exact amount of
> slice entries) add to slice. Slice will grow based on our size of data
> and underlying array size but doing this create multiple underlying arrays
> (more memory resource utilization, processing). In such case, what is the
> optimum solution?
The built-in append function does not simply allocate a new backing
>
> I am curious to know if we approx 100000 ( we don't know exact amount of
> slice entries) add to slice. Slice will grow based on our size of data
> and underlying array size but doing this create multiple underlying arrays
> (more memory resource utilization, processing). In such case, what is the
> optimum solution?
array with the exact size needed for the new slice; it allocates a slice
with extra capacity. It uses some heuristics to give a reasonable
speed/memory-usage trade-off for "typical" cases. The current algorithm
can be found in src/runtime/slice.go in the function growslice. Note
that the specific algorithm is not covered by the Go compatibility
guarantee.
If you are trying to be practical, you should start by implementing the
obvious and straight-forward algorithm first (i.e. use append as it was
intended), and then profile your code (the whole application, not just
the code that grows the slice) to determine where optimization will be
useful. It is very unlikely that the calls to append will be worth
spending time improving.
If this is an academic question, start the same way, but how you decide
where to spend time analyzing the results may be different.
In an application that is only going to have a slice of about 100,000
integers, the cost of append is unlikely to be of any concern at all on
any real production machine.
If it turns out that the append is a bottleneck (memory or speed), you
can write your own Append function by starting with the AppendByte
function from the go-slices-usage-and-internals blog that I linked to in
my previous message. Do the obvious fix-ups for byte to int (or
whatever your data type is), and modify the algorithm that determines
the capacity of the new slice (the (n+1)*2 in that function). Then use
your Append function instead of the built-in append. (Again, note that
this simple (n+1)*2 is _not_ what the built-in append function uses.)
A very simple first optimization (without resorting to your own Append
function) is to initially create the slice using make([]int, 0,
initialCapacity) where you choose initialCapacity to be larger than the
expected maximum size by some arbitrary percentage (e.g. 25%).
This playground link «https://play.golang.org/p/qtfHaoK-6Hy» shows
exactly where the allocations will occur. It took exactly 28
allocations to reach 100,000 elements. To show how insignificant that
is, on my laptop it took only 11ms to run that program. Is that 11ms
really significant in your program?
...Marvin
Stuart Davies
Oct 15, 2019, 10:28:10 AM10/15/19
to golang-nuts
Thanks.
The copy command was the thing I missed. It does exactly what I need and I can control the extension of the backing array with fine detail.
I assume the copy command is implemented efficiently but even if it just loops it is a packaged process and will have been optomised by the Go devs so it is as good as I am likly to get.
Thanks all for your help :-)
On Tuesday, 15 October 2019 11:16:35 UTC+1, Stuart Davies wrote:
Luis Furquim
Oct 16, 2019, 6:58:27 AM10/16/19
to golang-nuts
Em terça-feira, 15 de outubro de 2019 07:16:35 UTC-3, Stuart Davies escreveu:
if p.LineCount >= len(p.Offsets) {
newLen := p.LineCount + 50
sb := make([]int64, newLen)
for i := 0; i < p.LineCount; i++ {
sb[i] = p.Offsets[i]
}
p.Offsets = sb
}
Note that this code executes only when p.LineCount >= len(p.Offsets), your loop is based on p.LineCount and inside the loop you try to access p.Offsets[i] (where i increments until it reaches p.LineCount). When i >= len(p.Offsets) your code tries to access beyond p.Offsets bounds and this may be the cause of the panic you reported. So, in order to copy (if you don't choose to use the builtins copy() or append() functions) you should control your loop based on the length of the smaller array/slice, like this: for i := 0; i < p.Offsets; i++ .
Best regards!
Luis Otavio
Stuart Davies
Oct 17, 2019, 6:47:37 AM10/17/19
to golang-nuts
Luis
Thanks for you comments. I agree the limit for 'i' should be defined by the length of the smaller array.
However in the loop, 'i' is always less than p.LineCount and p.LineCount would never be more than the array size.
I could have used
if p.LineCount = len(p.Offsets)But >= felt more correct even though p.LineCount is only ever increnented by 1.
This code has loads of tests that ensure it's behaviour is correct.
The loop has now been removed and replaced by a 'copy' statement so there is no longer a loop of my ow making.
I did not use 'append' in the end because I wanted to control the growth of the array. It's function is very specific and I wanted to optomise the performance myself.
regards
Stuart
Reply all
Reply to author
Forward
0 new messages