starlark: NewDict(n) creates a dict with space for n elements (#183)
Hashtable growth keeps showing up in my profiling.
Preallocating the table when the size is known makes it much faster.
The NewDict function lets API clients control this.
Also NewSet.
diff --git a/starlark/value.go b/starlark/value.go
index c5d1fc3..66cf710 100644
--- a/starlark/value.go
+++ b/starlark/value.go
@@ -659,10 +659,21 @@
}
// A *Dict represents a Starlark dictionary.
+// The zero value of Dict is a valid empty dictionary.
+// If you know the exact final number of entries,
+// it is more efficient to call NewDict.
type Dict struct {
ht hashtable
}
+// NewDict returns a set with initial space for
+// at least size insertions before rehashing.
+func NewDict(size int) *Dict {
+ dict := new(Dict)
+ dict.ht.init(size)
+ return dict
+}
+
func (d *Dict) Clear() error { return d.ht.clear() }
func (d *Dict) Delete(k Value) (v Value, found bool, err error) { return d.ht.delete(k) }
func (d *Dict) Get(k Value) (v Value, found bool, err error) { return d.ht.lookup(k) }
@@ -916,10 +927,21 @@
func (it *tupleIterator) Done() {}
// A Set represents a Starlark set value.
+// The zero value of Set is a valid empty set.
+// If you know the exact final number of elements,
+// it is more efficient to call NewSet.
type Set struct {
ht hashtable // values are all None
}
+// NewSet returns a dictionary with initial space for
+// at least size insertions before rehashing.
+func NewSet(size int) *Set {
+ set := new(Set)
+ set.ht.init(size)
+ return set
+}
+
func (s *Set) Delete(k Value) (found bool, err error) { _, found, err = s.ht.delete(k); return }
func (s *Set) Clear() error { return s.ht.clear() }
func (s *Set) Has(k Value) (found bool, err error) { _, found, err = s.ht.lookup(k); return }