Up to Main Index Up to Journal for April, 2016
JOURNAL FOR THURSDAY 14TH APRIL, 2016
______________________________________________________________________________
SUBJECT: Slices, slicing and re-slicing bug
DATE: Fri 15 Apr 00:11:50 BST 2016
March was a good month with eight journal entries, a lot of coding and some
progress made. It's now April 14th and I haven't made a single entry yet this
month. So far this month sucks :(
So when I did get a minute or two to myself what was I working on?
I have been working on adding player accounts. While doing so I discovered a
few resource related issues which I have been dealing with. However testing is
slow as it can take half an hour to an hour[1] to get stats back that I can
then go through and analyse. I think I've fixed the issues now and will try to
get the changes uploaded as soon as I can.
I've also found and fixed a bug in the Thing.Remove method. Took a while until
I realised what was happening. The reason is obvious when you see it and
interesting to fix. The following is a small program to replicate the problem:
package main
import (
"fmt"
)
type units struct {
unit []int
}
func main() {
u := &units{[]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}}
u.Remove(1,2,3,4,5,6,7,8)
fmt.Printf("%v\n", u.Units())
}
func (u *units) Remove(e ...int) {
for _, e := range e {
for j, v := range u.unit {
if e == v {
u.unit = append(u.unit[:j], u.unit[j+1:]...)
break
}
}
}
}
func (u *units) Units() []int {
return u.unit
}
If we run the above we get the right answer printed:
[0 9]
Remove has removed the units passed to it (1,2,3,4,5,6,7,8) from the
initialised units (0,1,2,3,4,5,6,7,8,9) leaving just 0 and 9. So it works!
Yay! So where is the problem? How can this go wrong? What if we wanted to
remove all of the elements and changed main to:
func main() {
u := &units{[]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}}
u.Remove(u.Units()...) // <-- Changed this line
fmt.Printf("%v\n", u.Units())
}
If we re-run the program it now prints:
[1 3 5 7]
Ya... er... nope, not working. All of the units we specified were not removed.
Why and why did we get the sequence 1 3 5 7? The reason for the wrong answer
is that the slice of values passed to Remove and the slice of values we are
removing from have the same backing array - Units just returns the unit slice.
What about the 9? Shouldn't we get the sequence 1, 3, 5, 7, 9? Hrm, no. This
is because of the re-slicing and the appending used to perform the actual
delete. As more and more values are removed the expression u.unit[j+1...]
steps off the end of the slice that has been 'shrinking'. Meanwhile the input
slice can see beyond the end of the slice we are removing from as it's view
into the backing array isn't changing - values in the backing array are
though... that's what I think anyway...
Why the odd pattern of values? Removing a value from the u.unit slice also
removes it from the passed in slice. When the value is removed all values move
back by one slot to 'fill in the gap' but the next range iteration on the
input slice moves us on by one slot as well. In effect skipping a value:
input parameters: 0 1 2 3 4 5 6 7 8 9 The ^ indicates the current
^ element of the input slice
delete 0 from list: 1 2 3 4 5 6 7 8 9 we are working on.
^
next range iteration: 1 2 3 4 5 6 7 8 9
| ^
|
skipped!
We could fix the problem by modifying the Units method to return a copy of the
slice:
func (u *units) Units() []int {
U := make([]int, len(u.unit), len(u.unit))
copy(U, u.unit)
return U
}
For WolfMUD this wasn't a good option due to performance and additional memory
allocations. What else could we do? We could make a copy of the input slice in
the Remove method itself:
func (u *units) Remove(e ...int) {
E := make([]int, len(e), len(e))
copy(E, e)
for _, e := range E {
for j, v := range u.unit {
if e == v {
u.unit = append(u.unit[:j], u.unit[j+1:]...)
break
}
}
}
}
Now we only incur the performance hit and allocations when removing values.
Can we do better than this? Can we find a solution that avoids the copy but
still works if the input is sliced from the value we want to remove?
Yes we can :)
func (u *units) Remove(e ...int) {
for i := len(e) - 1; i >= 0; i-- {
for j := len(u.unit) - 1; j >= 0; j-- {
if e[i] == u.unit[j] {
u.unit = append(u.unit[:j], u.unit[j+1:]...)
break
}
}
}
}
Instead of ranging over the slices in the loops we iterate through the length
of the slices - but backwards - and access the slices by index. This means
when we remove a value and 'close up the gap' it happens to elements we have
already processed and are not interested in any more.
Final working code:
package main
import (
"fmt"
)
type units struct {
unit []int
}
func main() {
u := &units{[]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}}
u.Remove(u.Units()...)
fmt.Printf("%v\n", u.Units())
}
func (u *units) Remove(e ...int) {
for i := len(e) - 1; i >= 0; i-- {
for j := len(u.unit) - 1; j >= 0; j-- {
if e[i] == u.unit[j] {
u.unit = append(u.unit[:j], u.unit[j+1:]...)
break
}
}
}
}
func (u *units) Units() []int {
return u.unit
}
Now it doesn't matter if the passed in values are sliced from the values we
are working with or not.
Hard to find, hard to explain, simple solution - nice :)
--
Diddymus
[1] Running the server with 60,000 bots and a few live Telnet sessions.
Up to Main Index Up to Journal for April, 2016