diff options
author | Robert Griesemer <gri@golang.org> | 2009-12-07 12:46:20 -0800 |
---|---|---|
committer | Robert Griesemer <gri@golang.org> | 2009-12-07 12:46:20 -0800 |
commit | a4a82241529ece5d5c7580b7b2df1b616c51b832 (patch) | |
tree | 7fb54895a5314efa8a597d314d6521627b87be8d | |
parent | 8c22dd24e0e5aa847bd56dc7e573092f8652e3c5 (diff) | |
download | go-a4a82241529ece5d5c7580b7b2df1b616c51b832.tar.gz go-a4a82241529ece5d5c7580b7b2df1b616c51b832.zip |
use a bootstrap array to avoid allocation for short vectors
R=r
https://golang.org/cl/165078
-rw-r--r-- | src/pkg/container/vector/vector.go | 42 | ||||
-rw-r--r-- | src/pkg/container/vector/vector_test.go | 4 |
2 files changed, 30 insertions, 16 deletions
diff --git a/src/pkg/container/vector/vector.go b/src/pkg/container/vector/vector.go index 94184eac4a..0408490bea 100644 --- a/src/pkg/container/vector/vector.go +++ b/src/pkg/container/vector/vector.go @@ -9,12 +9,28 @@ package vector // Vector is the container itself. // The zero value for Vector is an empty vector ready to use. type Vector struct { - a []interface{}; + a []interface{}; + bootstrap [8]interface{}; +} + + +func (p *Vector) realloc(length, capacity int) (b []interface{}) { + if length <= cap(p.bootstrap) && capacity <= cap(p.bootstrap) { + // don't allocate; use pre-allocated bootstrap array + b = p.bootstrap[0:length] + } else { + b = make([]interface{}, length, capacity) + } + copy(b, p.a); + p.a = b; + return; } // Insert n elements at position i. -func expand(a []interface{}, i, n int) []interface{} { +func (p *Vector) expand(i, n int) { + a := p.a; + // make sure we have enough space len0 := len(a); len1 := len0 + n; @@ -24,21 +40,20 @@ func expand(a []interface{}, i, n int) []interface{} { } else { // not enough space - double capacity capb := cap(a) * 2; - if capb <= len1 { + if capb < len1 { // still not enough - use required length capb = len1 } - // capb > len1 - b := make([]interface{}, len1, capb); - copy(b, a); - a = b; + // capb >= len1 + a = p.realloc(len1, capb); } // make a hole for j := len0 - 1; j >= i; j-- { a[j+n] = a[j] } - return a; + + p.a = a; } @@ -46,15 +61,14 @@ func expand(a []interface{}, i, n int) []interface{} { // If the new length is shorter than the current length, Resize discards // trailing elements. If the new length is longer than the current length, // Resize adds nil elements. The capacity parameter is ignored unless the -// new length or capacity is longer that the current capacity. +// new length or capacity is longer that the current capacity. The resized +// vector's capacity may be larger than the requested capacity. func (p *Vector) Resize(length, capacity int) *Vector { a := p.a; if length > cap(a) || capacity > cap(a) { // not enough space or larger capacity requested explicitly - b := make([]interface{}, length, capacity); - copy(b, a); - a = b; + a = p.realloc(length, capacity) } else if length < len(a) { // clear trailing elements for i := range a[length:] { @@ -101,7 +115,7 @@ func (p *Vector) Data() []interface{} { // Insert inserts into the vector an element of value x before // the current element at index i. func (p *Vector) Insert(i int, x interface{}) { - p.a = expand(p.a, i, 1); + p.expand(i, 1); p.a[i] = x; } @@ -121,7 +135,7 @@ func (p *Vector) Delete(i int) { // InsertVector inserts into the vector the contents of the Vector // x such that the 0th element of x appears at index i after insertion. func (p *Vector) InsertVector(i int, x *Vector) { - p.a = expand(p.a, i, len(x.a)); + p.expand(i, len(x.a)); copy(p.a[i:i+len(x.a)], x.a); } diff --git a/src/pkg/container/vector/vector_test.go b/src/pkg/container/vector/vector_test.go index 80221392ee..24486c58f2 100644 --- a/src/pkg/container/vector/vector_test.go +++ b/src/pkg/container/vector/vector_test.go @@ -27,8 +27,8 @@ func checkSize(t *testing.T, v VectorInterface, len, cap int) { if v.Len() != len { t.Errorf("expected len = %d; found %d", len, v.Len()) } - if v.Cap() != cap { - t.Errorf("expected cap = %d; found %d", cap, v.Cap()) + if v.Cap() < cap { + t.Errorf("expected cap >= %d; found %d", cap, v.Cap()) } } |