Skip to content

Use a Javascript Map for Go Maps. Improves performance of len() calls by orders of magnitude. 🗺️ #1136

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 1 commit into from
Aug 24, 2022
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension


Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
4 changes: 2 additions & 2 deletions circle.yml
Original file line number Diff line number Diff line change
Expand Up @@ -3,13 +3,13 @@
# This configuration has one build_and_test workflow designed to run on all commits
# and pull requests. It consists of three jobs:
#
# - build: Builds and runs GopherJS unit tests, as well as lits, smoke tests, etc.
# - build: Builds and runs GopherJS unit tests, as well as lints, smoke tests, etc.
# This job is designed to provide quickest feedback on the most important
# functionality. It should not include anything heavyweight and should be kept
# under 2-3 minutes of runtime.
#
# - gopherjs_tests: Runs standard library and GopherJS package tests using GopherJS
# *itself*. This is the most comprehensive test suite we have and it is sharded
# *itself*. This is the most comprehensive test suite we have, and it is sharded
# into 4 parallel instances for faster execution.
#
# - gorepo_tests: Runs language tests from the Go compiler test suite. The objective
Expand Down
31 changes: 24 additions & 7 deletions compiler/expressions.go
Original file line number Diff line number Diff line change
Expand Up @@ -475,9 +475,21 @@ func (fc *funcContext) translateExpr(expr ast.Expr) *expression {
}
key := fmt.Sprintf("%s.keyFor(%s)", fc.typeName(t.Key()), fc.translateImplicitConversion(e.Index, t.Key()))
if _, isTuple := exprType.(*types.Tuple); isTuple {
return fc.formatExpr(`(%1s = %2e[%3s], %1s !== undefined ? [%1s.v, true] : [%4e, false])`, fc.newVariable("_entry"), e.X, key, fc.zeroValue(t.Elem()))
}
return fc.formatExpr(`(%1s = %2e[%3s], %1s !== undefined ? %1s.v : %4e)`, fc.newVariable("_entry"), e.X, key, fc.zeroValue(t.Elem()))
return fc.formatExpr(
`(%1s = $mapIndex(%2e,%3s), %1s !== undefined ? [%1s.v, true] : [%4e, false])`,
fc.newVariable("_entry"),
e.X,
key,
fc.zeroValue(t.Elem()),
)
}
return fc.formatExpr(
`(%1s = $mapIndex(%2e,%3s), %1s !== undefined ? %1s.v : %4e)`,
fc.newVariable("_entry"),
e.X,
key,
fc.zeroValue(t.Elem()),
)
case *types.Basic:
return fc.formatExpr("%e.charCodeAt(%f)", e.X, e.Index)
default:
Expand Down Expand Up @@ -919,9 +931,9 @@ func (fc *funcContext) translateBuiltin(name string, sig *types.Signature, args
return fc.formatExpr("$makeSlice(%s, %f)", t, args[1])
case *types.Map:
if len(args) == 2 && fc.pkgCtx.Types[args[1]].Value == nil {
return fc.formatExpr(`((%1f < 0 || %1f > 2147483647) ? $throwRuntimeError("makemap: size out of range") : {})`, args[1])
return fc.formatExpr(`((%1f < 0 || %1f > 2147483647) ? $throwRuntimeError("makemap: size out of range") : new $global.Map())`, args[1])
}
return fc.formatExpr("{}")
return fc.formatExpr("new $global.Map()")
case *types.Chan:
length := "0"
if len(args) == 2 {
Expand All @@ -940,7 +952,7 @@ func (fc *funcContext) translateBuiltin(name string, sig *types.Signature, args
case *types.Pointer:
return fc.formatExpr("(%e, %d)", args[0], argType.Elem().(*types.Array).Len())
case *types.Map:
return fc.formatExpr("$keys(%e).length", args[0])
return fc.formatExpr("(%e ? %e.size : 0)", args[0], args[0])
case *types.Chan:
return fc.formatExpr("%e.$buffer.length", args[0])
// length of array is constant
Expand Down Expand Up @@ -969,7 +981,12 @@ func (fc *funcContext) translateBuiltin(name string, sig *types.Signature, args
case "delete":
args = fc.expandTupleArgs(args)
keyType := fc.pkgCtx.TypeOf(args[0]).Underlying().(*types.Map).Key()
return fc.formatExpr(`delete %e[%s.keyFor(%s)]`, args[0], fc.typeName(keyType), fc.translateImplicitConversion(args[1], keyType))
return fc.formatExpr(
`$mapDelete(%1e, %2s.keyFor(%3s))`,
args[0],
fc.typeName(keyType),
fc.translateImplicitConversion(args[1], keyType),
)
case "copy":
args = fc.expandTupleArgs(args)
if basic, isBasic := fc.pkgCtx.TypeOf(args[1]).Underlying().(*types.Basic); isBasic && isString(basic) {
Expand Down
20 changes: 10 additions & 10 deletions compiler/gopherjspkg/fs_vfsdata.go

Large diffs are not rendered by default.

4 changes: 4 additions & 0 deletions compiler/natives/doc.go
Original file line number Diff line number Diff line change
Expand Up @@ -5,5 +5,9 @@
// in src subfolder.
package natives

import (
_ "github.com/shurcooL/vfsgen" // Force go.mod to require this package
)

//go:generate vfsgendev -source="github.com/gopherjs/gopherjs/compiler/natives".FS -tag=gopherjsdev
//go:generate gofmt -w -s fs_vfsdata.go
350 changes: 175 additions & 175 deletions compiler/natives/fs_vfsdata.go

Large diffs are not rendered by default.

16 changes: 8 additions & 8 deletions compiler/natives/src/internal/reflectlite/reflectlite.go
Original file line number Diff line number Diff line change
Expand Up @@ -475,7 +475,7 @@ func makechan(typ *rtype, size int) (ch unsafe.Pointer) {
}

func makemap(t *rtype, cap int) (m unsafe.Pointer) {
return unsafe.Pointer(js.Global.Get("Object").New().Unsafe())
return unsafe.Pointer(js.Global.Get("Map").New().Unsafe())
}

func keyFor(t *rtype, key unsafe.Pointer) (*js.Object, string) {
Expand All @@ -489,7 +489,7 @@ func keyFor(t *rtype, key unsafe.Pointer) (*js.Object, string) {

func mapaccess(t *rtype, m, key unsafe.Pointer) unsafe.Pointer {
_, k := keyFor(t, key)
entry := js.InternalObject(m).Get(k)
entry := js.InternalObject(m).Call("get", k)
if entry == js.Undefined {
return nil
}
Expand All @@ -508,12 +508,12 @@ func mapassign(t *rtype, m, key, val unsafe.Pointer) {
entry := js.Global.Get("Object").New()
entry.Set("k", kv)
entry.Set("v", jsVal)
js.InternalObject(m).Set(k, entry)
js.InternalObject(m).Call("set", k, entry)
}

func mapdelete(t *rtype, m unsafe.Pointer, key unsafe.Pointer) {
_, k := keyFor(t, key)
js.InternalObject(m).Delete(k)
js.InternalObject(m).Call("delete", k)
}

type mapIter struct {
Expand All @@ -531,7 +531,7 @@ type mapIter struct {
func (iter *mapIter) skipUntilValidKey() {
for iter.i < iter.keys.Length() {
k := iter.keys.Index(iter.i)
if iter.m.Get(k.String()) != js.Undefined {
if iter.m.Call("get", k) != js.Undefined {
break
}
// The key is already deleted. Move on the next item.
Expand All @@ -540,7 +540,7 @@ func (iter *mapIter) skipUntilValidKey() {
}

func mapiterinit(t *rtype, m unsafe.Pointer) unsafe.Pointer {
return unsafe.Pointer(&mapIter{t, js.InternalObject(m), js.Global.Call("$keys", js.InternalObject(m)), 0, nil})
return unsafe.Pointer(&mapIter{t, js.InternalObject(m), js.Global.Get("Array").Call("from", js.InternalObject(m).Call("keys")), 0, nil})
}

type TypeEx interface {
Expand All @@ -559,7 +559,7 @@ func mapiterkey(it unsafe.Pointer) unsafe.Pointer {
return nil
}
k := iter.keys.Index(iter.i)
kv = iter.m.Get(k.String())
kv = iter.m.Call("get", k)

// Record the key-value pair for later accesses.
iter.last = kv
Expand All @@ -574,7 +574,7 @@ func mapiternext(it unsafe.Pointer) {
}

func maplen(m unsafe.Pointer) int {
return js.Global.Call("$keys", js.InternalObject(m)).Length()
return js.InternalObject(m).Get("size").Int()
}

func cvtDirect(v Value, typ Type) Value {
Expand Down
2 changes: 1 addition & 1 deletion compiler/natives/src/internal/reflectlite/value.go
Original file line number Diff line number Diff line change
Expand Up @@ -266,7 +266,7 @@ func (v Value) Len() int {
case Chan:
return v.object().Get("$buffer").Get("length").Int()
case Map:
return js.Global.Call("$keys", v.object()).Length()
return v.object().Get("size").Int()
default:
panic(&ValueError{"reflect.Value.Len", k})
}
Expand Down
42 changes: 29 additions & 13 deletions compiler/natives/src/reflect/reflect.go
Original file line number Diff line number Diff line change
Expand Up @@ -620,21 +620,24 @@ func makechan(typ *rtype, size int) (ch unsafe.Pointer) {
}

func makemap(t *rtype, cap int) (m unsafe.Pointer) {
return unsafe.Pointer(js.Global.Get("Object").New().Unsafe())
return unsafe.Pointer(js.Global.Get("Map").New().Unsafe())
}

func keyFor(t *rtype, key unsafe.Pointer) (*js.Object, string) {
func keyFor(t *rtype, key unsafe.Pointer) (*js.Object, *js.Object) {
kv := js.InternalObject(key)
if kv.Get("$get") != js.Undefined {
kv = kv.Call("$get")
}
k := jsType(t.Key()).Call("keyFor", kv).String()
k := jsType(t.Key()).Call("keyFor", kv)
return kv, k
}

func mapaccess(t *rtype, m, key unsafe.Pointer) unsafe.Pointer {
if !js.InternalObject(m).Bool() {
return nil // nil map
}
_, k := keyFor(t, key)
entry := js.InternalObject(m).Get(k)
entry := js.InternalObject(m).Call("get", k)
if entry == js.Undefined {
return nil
}
Expand All @@ -653,12 +656,15 @@ func mapassign(t *rtype, m, key, val unsafe.Pointer) {
entry := js.Global.Get("Object").New()
entry.Set("k", kv)
entry.Set("v", jsVal)
js.InternalObject(m).Set(k, entry)
js.InternalObject(m).Call("set", k, entry)
}

func mapdelete(t *rtype, m unsafe.Pointer, key unsafe.Pointer) {
_, k := keyFor(t, key)
js.InternalObject(m).Delete(k)
if !js.InternalObject(m).Bool() {
return // nil map
}
js.InternalObject(m).Call("delete", k)
}

// TODO(nevkonatkte): The following three "faststr" implementations are meant to
Expand Down Expand Up @@ -696,7 +702,8 @@ type hiter struct {
func (iter *hiter) skipUntilValidKey() {
for iter.i < iter.keys.Length() {
k := iter.keys.Index(iter.i)
if iter.m.Get(k.String()) != js.Undefined {
entry := iter.m.Call("get", k)
if entry != js.Undefined {
break
}
// The key is already deleted. Move on the next item.
Expand All @@ -705,10 +712,19 @@ func (iter *hiter) skipUntilValidKey() {
}

func mapiterinit(t *rtype, m unsafe.Pointer, it *hiter) {
mapObj := js.InternalObject(m)
keys := js.Global.Get("Array").New()
if mapObj.Get("keys") != js.Undefined {
keysIter := mapObj.Call("keys")
if mapObj.Get("keys") != js.Undefined {
keys = js.Global.Get("Array").Call("from", keysIter)
}
}

*it = hiter{
t: t,
m: js.InternalObject(m),
keys: js.Global.Call("$keys", js.InternalObject(m)),
m: mapObj,
keys: keys,
i: 0,
last: nil,
}
Expand All @@ -724,7 +740,7 @@ func mapiterkey(it *hiter) unsafe.Pointer {
return nil
}
k := it.keys.Index(it.i)
kv = it.m.Get(k.String())
kv = it.m.Call("get", k)

// Record the key-value pair for later accesses.
it.last = kv
Expand All @@ -742,7 +758,7 @@ func mapiterelem(it *hiter) unsafe.Pointer {
return nil
}
k := it.keys.Index(it.i)
kv = it.m.Get(k.String())
kv = it.m.Call("get", k)
it.last = kv
}
return unsafe.Pointer(js.Global.Call("$newDataPointer", kv.Get("v"), jsType(PtrTo(it.t.Elem()))).Unsafe())
Expand All @@ -754,7 +770,7 @@ func mapiternext(it *hiter) {
}

func maplen(m unsafe.Pointer) int {
return js.Global.Call("$keys", js.InternalObject(m)).Length()
return js.InternalObject(m).Get("size").Int()
}

func cvtDirect(v Value, typ Type) Value {
Expand Down Expand Up @@ -1379,7 +1395,7 @@ func (v Value) Len() int {
case Chan:
return v.object().Get("$buffer").Get("length").Int()
case Map:
return js.Global.Call("$keys", v.object()).Length()
return v.object().Get("size").Int()
default:
panic(&ValueError{"reflect.Value.Len", k})
}
Expand Down
8 changes: 4 additions & 4 deletions compiler/prelude/jsmapping.go
Original file line number Diff line number Diff line change
Expand Up @@ -61,9 +61,9 @@ var $externalize = function(v, t, makeWrapper) {
return $externalize(v.$val, v.constructor, makeWrapper);
case $kindMap:
var m = {};
var keys = $keys(v);
var keys = Array.from(v.keys());
for (var i = 0; i < keys.length; i++) {
var entry = v[keys[i]];
var entry = v.get(keys[i]);
m[$externalize(entry.k, t.key, makeWrapper)] = $externalize(entry.v, t.elem, makeWrapper);
}
return m;
Expand Down Expand Up @@ -312,12 +312,12 @@ var $internalize = function(v, t, recv, seen, makeWrapper) {
return new mapType($internalize(v, mapType, recv, seen, makeWrapper));
}
case $kindMap:
var m = {};
var m = new Map();
seen.get(t).set(v, m);
var keys = $keys(v);
for (var i = 0; i < keys.length; i++) {
var k = $internalize(keys[i], t.key, recv, seen, makeWrapper);
m[t.key.keyFor(k)] = { k: k, v: $internalize(v[keys[i]], t.elem, recv, seen, makeWrapper) };
m.set(t.key.keyFor(k), { k: k, v: $internalize(v[keys[i]], t.elem, recv, seen, makeWrapper) });
}
return m;
case $kindPtr:
Expand Down
8 changes: 8 additions & 0 deletions compiler/prelude/prelude.go
Original file line number Diff line number Diff line change
Expand Up @@ -100,6 +100,14 @@ var $mapArray = function(array, f) {
return newArray;
};

// $mapIndex returns the value of the given key in m, or undefined if m is nil/undefined or not a map
var $mapIndex = function(m, key) {
return typeof m.get === "function" ? m.get(key) : undefined;
};
// $mapDelete deletes the key and associated value from m. If m is nil/undefined or not a map, $mapDelete is a no-op
var $mapDelete = function(m, key) {
typeof m.delete === "function" && m.delete(key)
};
// Returns a method bound to the receiver instance, safe to invoke as a
// standalone function. Bound function is cached for later reuse.
var $methodVal = function(recv, name) {
Expand Down
2 changes: 1 addition & 1 deletion compiler/prelude/prelude_min.go

Large diffs are not rendered by default.

4 changes: 2 additions & 2 deletions compiler/prelude/types.go
Original file line number Diff line number Diff line change
Expand Up @@ -617,10 +617,10 @@ var $mapType = function(key, elem) {
return typ;
};
var $makeMap = function(keyForFunc, entries) {
var m = {};
var m = new Map();
for (var i = 0; i < entries.length; i++) {
var e = entries[i];
m[keyForFunc(e.k)] = e;
m.set(keyForFunc(e.k), e);
}
return m;
};
Expand Down
22 changes: 18 additions & 4 deletions compiler/statements.go
Original file line number Diff line number Diff line change
Expand Up @@ -211,10 +211,15 @@ func (fc *funcContext) translateStmt(stmt ast.Stmt, label *types.Label) {
iVar := fc.newVariable("_i")
fc.Printf("%s = 0;", iVar)
keysVar := fc.newVariable("_keys")
fc.Printf("%s = $keys(%s);", keysVar, refVar)
fc.translateLoopingStmt(func() string { return iVar + " < " + keysVar + ".length" }, s.Body, func() {
fc.Printf("%s = %s ? %s.keys() : undefined;", keysVar, refVar, refVar)

sizeVar := fc.newVariable("_size")
fc.Printf("%s = %s ? %s.size : 0;", sizeVar, refVar, refVar)
fc.translateLoopingStmt(func() string { return iVar + " < " + sizeVar }, s.Body, func() {
keyVar := fc.newVariable("_key")
entryVar := fc.newVariable("_entry")
fc.Printf("%s = %s[%s[%s]];", entryVar, refVar, keysVar, iVar)
fc.Printf("%s = %s.next().value;", keyVar, keysVar)
fc.Printf("%s = %s.get(%s);", entryVar, refVar, keyVar)
fc.translateStmt(&ast.IfStmt{
Cond: fc.newIdent(entryVar+" === undefined", types.Typ[types.Bool]),
Body: &ast.BlockStmt{List: []ast.Stmt{&ast.BranchStmt{Tok: token.CONTINUE}}},
Expand Down Expand Up @@ -700,7 +705,16 @@ func (fc *funcContext) translateAssign(lhs, rhs ast.Expr, define bool) string {
fc.pkgCtx.errList = append(fc.pkgCtx.errList, types.Error{Fset: fc.pkgCtx.fileSet, Pos: l.Index.Pos(), Msg: "cannot use js.Object as map key"})
}
keyVar := fc.newVariable("_key")
return fmt.Sprintf(`%s = %s; (%s || $throwRuntimeError("assignment to entry in nil map"))[%s.keyFor(%s)] = { k: %s, v: %s };`, keyVar, fc.translateImplicitConversionWithCloning(l.Index, t.Key()), fc.translateExpr(l.X), fc.typeName(t.Key()), keyVar, keyVar, fc.translateImplicitConversionWithCloning(rhs, t.Elem()))
return fmt.Sprintf(
`%s = %s; (%s || $throwRuntimeError("assignment to entry in nil map")).set(%s.keyFor(%s), { k: %s, v: %s });`,
keyVar,
fc.translateImplicitConversionWithCloning(l.Index, t.Key()),
fc.translateExpr(l.X),
fc.typeName(t.Key()),
keyVar,
keyVar,
fc.translateImplicitConversionWithCloning(rhs, t.Elem()),
)
}
}

Expand Down
2 changes: 1 addition & 1 deletion go.mod
Original file line number Diff line number Diff line change
Expand Up @@ -9,6 +9,7 @@ require (
github.com/neelance/sourcemap v0.0.0-20200213170602-2833bce08e4c
github.com/shurcooL/go v0.0.0-20200502201357-93f07166e636
github.com/shurcooL/httpfs v0.0.0-20190707220628-8d4bc4ba7749
github.com/shurcooL/vfsgen v0.0.0-20200824052919-0d455de96546
github.com/sirupsen/logrus v1.8.1
github.com/spf13/cobra v1.2.1
github.com/spf13/pflag v1.0.5
Expand All @@ -20,7 +21,6 @@ require (

require (
github.com/inconshreveable/mousetrap v1.0.0 // indirect
github.com/shurcooL/vfsgen v0.0.0-20200824052919-0d455de96546 // indirect
golang.org/x/term v0.0.0-20220411215600-e5f449aeb171 // indirect
golang.org/x/xerrors v0.0.0-20220411194840-2f41105eb62f // indirect
)
Loading