Optimizing hashtable.grow() for faster hashtables (#459)
* Using a specialized version of Insert to speed up hashmap expansion
* Further improvements
* undo changes and update TODO
diff --git a/starlark/hashtable.go b/starlark/hashtable.go
index 1550e95..252d21d 100644
--- a/starlark/hashtable.go
+++ b/starlark/hashtable.go
@@ -155,13 +155,12 @@
func (ht *hashtable) grow() {
// Double the number of buckets and rehash.
- // TODO(adonovan): opt:
- // - avoid reentrant calls to ht.insert, and specialize it.
- // e.g. we know the calls to Equals will return false since
- // there are no duplicates among the old keys.
- // - saving the entire hash in the bucket would avoid the need to
- // recompute the hash.
- // - save the old buckets on a free list.
+ //
+ // Even though this makes reentrant calls to ht.insert,
+ // calls Equals unnecessarily (since there can't be duplicate keys),
+ // and recomputes the hash unnecessarily, the gains from
+ // avoiding these steps were found to be too small to justify
+ // the extra logic: -2% on hashtable benchmark.
ht.table = make([]bucket, len(ht.table)<<1)
oldhead := ht.head
ht.head = nil
