Some memory leak and efficiency problem in the SliceTricks on community wiki

[David DENG]

The SliceTricks page ( http://code.google.com/p/go-wiki/wiki/SliceTricks ) shows some one-line tricks for using a slice as a vector. But I think there are some hidden memory-leaks or efficiency problem in them, which should be given attensions.

1) Cut/Delete actions do not clear the elements at the original positions for some moved elements. These elements may not be GC until the whole slice is.

e.g. If a slice has the value of [1, 2, 3, 4, 5], and the third value is deleted, the elements in the internal array will be [1, 2, 4, 5, 5]. If the first 5 is replaced by some other elements, the latter 5 will be referenced hiddenly, which may cause a memory leak. (I use integers as the example  to easily demostrating, but in practice that could be an object). Code: http://play.golang.org/p/kzQVT_I7Oq

Correct implementations could be:

// Remove removes the element at the specified position in this slice.

func (s *Slice) Remove(index int) interface{} {

    e := (*s)[index]

    copy((*s)[index:], (*s)[index + 1:])

    (*s)[len(*s) - 1] = nil

    *s = (*s)[:len(*s) - 1]

    return e

}

// RemoveRange removes all of the elements whose index is between from, inclusive, and to, exclusive, from this slice.

func (s *Slice) RemoveRange(from, to int) {

    if to <= from {

        return

    } // if

    

    copy((*s)[from:], (*s)[to:])

    for i, j := to-from, len(*s) - 1; i > 0; i, j = i - 1, j - 1 {

        (*s)[j] = nil

    } // for i

    *s = (*s)[:len(*s) - (to - from)]

}

2) The Insert is inefficient. A brand new(new internal array and, of course, the slice object) slice has to be created, i.e. the second parameter of the first append.

Correct implementation could be:

func (s *Slice) Insert(index int, e... interface{}) {

    if cap(*s) >= len(*s) + len(e) {

        *s = (*s)[:len(*s) + len(e)]

    } else {

        *s = append(*s, e...)

    } // else

    copy((*s)[index + len(e):], (*s)[index:])

    copy((*s)[index:], e[:])

}

(The above code fragments are from my helper package: https://github.com/daviddengcn/go-villa , Slice is a defined as: type Slice []interface{} )

Does anyone know how to join the community. I just wanna give some comments on the wiki.

Thank you!

David

[Andrew Gerrand]

On 19 December 2012 15:10, David DENG <david...@gmail.com> wrote:

Does anyone know how to join the community. I just wanna give some comments on the wiki.

I just added you.

Andrew

[Dave Cheney]

Hello,

With respect to a possible memory leak, please redo your code using large objects, say []byte of 100mb. Testing is the only way to be sure. 

Dave

--
 
 

[David DENG]

Thank you!

David

[David DENG]

I wrote a code fragment for testing:

http://play.golang.org/p/zoe_phL_Rn

Commeting Line 24, which nils the invisible elements of the slice, makes finalized from 98 to 0. The exact number may vary under different systems, but I think the results proved my guest.

David

[Kamil Kisiel]

This only matters if the elements of the slice are pointers as the slice's backing array doesn't actually shrink. If you have a slice of basic types like ints or floats you won't save any memory by zeroing the elements.

[Kyle Lemons]

On Tue, Dec 18, 2012 at 11:10 PM, David DENG <david...@gmail.com> wrote:

The SliceTricks page ( http://code.google.com/p/go-wiki/wiki/SliceTricks ) shows some one-line tricks for using a slice as a vector. But I think there are some hidden memory-leaks or efficiency problem in them, which should be given attensions.

Not to say that the page shouldn't say this, but those slice tricks are not intended to be performant or efficient.  Note that they're "tricks," not "how you should always XYZ with a slice."  They're intended to show you potential ways to do, with slices, what you could do with otherwise more "featureful" container types.  I don't think the wiki page really needs to go into all of the times in which you shouldn't use those, as there are a number of other problems with using some of those in various situations.

 

David

--
 
 

[David DENG]

Yeah, tricks are fun, but the problems I just pointed out are not so easy to be found. So some comments are really helpful.

On the other hand, that also shows, only using slices, which are low-level support of go-lang, is not enough. The Team may reconsider the requirement of vector-like support in the standard libarary.

David

[Kyle Lemons]

When you write the operation out like it is written in SliceTricks, it is reasonably clear what the performance implications are of the code.  When you call a method, it's all completely hidden from you.  You can't as easily tell if the person is inappropriately using a slice to insert/delete from the middle when they should be using a linked list or some similar data structure, for instance.

--
 
 

[bryanturley]

On Wednesday, December 19, 2012 8:06:13 PM UTC-6, David DENG wrote:

Yeah, tricks are fun, but the problems I just pointed out are not so easy to be found. So some comments are really helpful.

I avoid them for similar reasons.

 

On the other hand, that also shows, only using slices, which are low-level support of go-lang, is not enough. The Team may reconsider the requirement of vector-like support in the standard libarary.

Do you mean library or builtin?
This exists http://tip.golang.org/pkg/container/list/ not really a vector but close enough.

 

David

[David DENG]

container/list is a double-linked list, not a vector. The cost of visiting an arbitrary element is O(n) not O(0) as in a vector or a linear list.

And I wrote a wrapper for slices of interface{}/int/float64/complex128 (mentioned in my early posts) , but that does not end the story. Maybe template can do, but it is not so easy to be well designed.

David

[David DENG]

Yeah, sometimes a linked list should be used. But as my experience, lined lists are much less used than a slice-like data-structure. That's why slice is a build-in, while the linked list is only in the standard library.

Actually I saw that wiki page when I was just a newbie to Go (maybe still now), and also think removing the vector library is just for what the post says. But now I doubt, because requriing every person in the team to notice this efficiency or memory leak problem is not practical. A well designed and debugged library can save a lot of time. And since it's open source, some careful person can read the implementation of a method to be sure.

David

[bryanturley]

So your response to
"This exists http://tip.golang.org/pkg/container/list/ not really a vector but close enough. "  (note the end of that sentence where I say it is not a vector...)
is

On Thursday, December 20, 2012 5:35:20 PM UTC-6, David DENG wrote:

container/list is a double-linked list, not a vector.

Sometimes I wonder if people read what I type at all... ;)

And if you want a linear list that is a slice. 
The main problem I have with slices was deleting from the center of large ones which is generally a fast operation on linked lists.
I also have the same problem with arrays in every language and so do others which is one of the reasons linked lists are popular.

[Kyle Lemons]

On Thu, Dec 20, 2012 at 6:48 PM, David DENG <david...@gmail.com> wrote:

Yeah, sometimes a linked list should be used. But as my experience, lined lists are much less used than a slice-like data-structure. That's why slice is a build-in, while the linked list is only in the standard library.

Actually I saw that wiki page when I was just a newbie to Go (maybe still now), and also think removing the vector library is just for what the post says. But now I doubt, because requriing every person in the team to notice this efficiency or memory leak problem is not practical.

It's not a memory leak.  It might be an inefficiency, but it's still a horse of an entirely different color.

 

--