Skip to content

Commit fda6a40

Browse files
nevkontaktenevkontakte
authored
Merge pull request #1136 from tomconnell-wf/javascript_map_impl
Use a Javascript Map for Go Maps. Improves performance of len() calls by orders of magnitude. 🗺️
2 parents 32d447b + 9771b78 commit fda6a40

File tree

16 files changed

+701
-228
lines changed

16 files changed

+701
-228
lines changed

‎circle.yml

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3,13 +3,13 @@
33
# This configuration has one build_and_test workflow designed to run on all commits
44
# and pull requests. It consists of three jobs:
55
#
6-
# - build: Builds and runs GopherJS unit tests, as well as lits, smoke tests, etc.
6+
# - build: Builds and runs GopherJS unit tests, as well as lints, smoke tests, etc.
77
# This job is designed to provide quickest feedback on the most important
88
# functionality. It should not include anything heavyweight and should be kept
99
# under 2-3 minutes of runtime.
1010
#
1111
# - gopherjs_tests: Runs standard library and GopherJS package tests using GopherJS
12-
# *itself*. This is the most comprehensive test suite we have and it is sharded
12+
# *itself*. This is the most comprehensive test suite we have, and it is sharded
1313
# into 4 parallel instances for faster execution.
1414
#
1515
# - gorepo_tests: Runs language tests from the Go compiler test suite. The objective

‎compiler/expressions.go

Lines changed: 24 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -475,9 +475,21 @@ func (fc *funcContext) translateExpr(expr ast.Expr) *expression {
475475
}
476476
key := fmt.Sprintf("%s.keyFor(%s)", fc.typeName(t.Key()), fc.translateImplicitConversion(e.Index, t.Key()))
477477
if _, isTuple := exprType.(*types.Tuple); isTuple {
478-
return fc.formatExpr(`(%1s = %2e[%3s], %1s !== undefined ? [%1s.v, true] : [%4e, false])`, fc.newVariable("_entry"), e.X, key, fc.zeroValue(t.Elem()))
479-
}
480-
return fc.formatExpr(`(%1s = %2e[%3s], %1s !== undefined ? %1s.v : %4e)`, fc.newVariable("_entry"), e.X, key, fc.zeroValue(t.Elem()))
478+
return fc.formatExpr(
479+
`(%1s = $mapIndex(%2e,%3s), %1s !== undefined ? [%1s.v, true] : [%4e, false])`,
480+
fc.newVariable("_entry"),
481+
e.X,
482+
key,
483+
fc.zeroValue(t.Elem()),
484+
)
485+
}
486+
return fc.formatExpr(
487+
`(%1s = $mapIndex(%2e,%3s), %1s !== undefined ? %1s.v : %4e)`,
488+
fc.newVariable("_entry"),
489+
e.X,
490+
key,
491+
fc.zeroValue(t.Elem()),
492+
)
481493
case *types.Basic:
482494
return fc.formatExpr("%e.charCodeAt(%f)", e.X, e.Index)
483495
default:
@@ -919,9 +931,9 @@ func (fc *funcContext) translateBuiltin(name string, sig *types.Signature, args
919931
return fc.formatExpr("$makeSlice(%s, %f)", t, args[1])
920932
case *types.Map:
921933
if len(args) == 2 && fc.pkgCtx.Types[args[1]].Value == nil {
922-
return fc.formatExpr(`((%1f < 0 || %1f > 2147483647) ? $throwRuntimeError("makemap: size out of range") : {})`, args[1])
934+
return fc.formatExpr(`((%1f < 0 || %1f > 2147483647) ? $throwRuntimeError("makemap: size out of range") : new $global.Map())`, args[1])
923935
}
924-
return fc.formatExpr("{}")
936+
return fc.formatExpr("new $global.Map()")
925937
case *types.Chan:
926938
length := "0"
927939
if len(args) == 2 {
@@ -940,7 +952,7 @@ func (fc *funcContext) translateBuiltin(name string, sig *types.Signature, args
940952
case *types.Pointer:
941953
return fc.formatExpr("(%e, %d)", args[0], argType.Elem().(*types.Array).Len())
942954
case *types.Map:
943-
return fc.formatExpr("$keys(%e).length", args[0])
955+
return fc.formatExpr("(%e ? %e.size : 0)", args[0], args[0])
944956
case *types.Chan:
945957
return fc.formatExpr("%e.$buffer.length", args[0])
946958
// length of array is constant
@@ -969,7 +981,12 @@ func (fc *funcContext) translateBuiltin(name string, sig *types.Signature, args
969981
case "delete":
970982
args = fc.expandTupleArgs(args)
971983
keyType := fc.pkgCtx.TypeOf(args[0]).Underlying().(*types.Map).Key()
972-
return fc.formatExpr(`delete %e[%s.keyFor(%s)]`, args[0], fc.typeName(keyType), fc.translateImplicitConversion(args[1], keyType))
984+
return fc.formatExpr(
985+
`$mapDelete(%1e, %2s.keyFor(%3s))`,
986+
args[0],
987+
fc.typeName(keyType),
988+
fc.translateImplicitConversion(args[1], keyType),
989+
)
973990
case "copy":
974991
args = fc.expandTupleArgs(args)
975992
if basic, isBasic := fc.pkgCtx.TypeOf(args[1]).Underlying().(*types.Basic); isBasic && isString(basic) {

‎compiler/gopherjspkg/fs_vfsdata.go

Lines changed: 10 additions & 10 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎compiler/natives/doc.go

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,5 +5,9 @@
55
// in src subfolder.
66
package natives
77

8+
import (
9+
_ "github.com/shurcooL/vfsgen" // Force go.mod to require this package
10+
)
11+
812
//go:generate vfsgendev -source="github.com/gopherjs/gopherjs/compiler/natives".FS -tag=gopherjsdev
913
//go:generate gofmt -w -s fs_vfsdata.go

‎compiler/natives/fs_vfsdata.go

Lines changed: 175 additions & 175 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎compiler/natives/src/internal/reflectlite/reflectlite.go

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -475,7 +475,7 @@ func makechan(typ *rtype, size int) (ch unsafe.Pointer) {
475475
}
476476

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

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

490490
func mapaccess(t *rtype, m, key unsafe.Pointer) unsafe.Pointer {
491491
_, k := keyFor(t, key)
492-
entry := js.InternalObject(m).Get(k)
492+
entry := js.InternalObject(m).Call("get", k)
493493
if entry == js.Undefined {
494494
return nil
495495
}
@@ -508,12 +508,12 @@ func mapassign(t *rtype, m, key, val unsafe.Pointer) {
508508
entry := js.Global.Get("Object").New()
509509
entry.Set("k", kv)
510510
entry.Set("v", jsVal)
511-
js.InternalObject(m).Set(k, entry)
511+
js.InternalObject(m).Call("set", k, entry)
512512
}
513513

514514
func mapdelete(t *rtype, m unsafe.Pointer, key unsafe.Pointer) {
515515
_, k := keyFor(t, key)
516-
js.InternalObject(m).Delete(k)
516+
js.InternalObject(m).Call("delete", k)
517517
}
518518

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

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

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

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

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

580580
func cvtDirect(v Value, typ Type) Value {

‎compiler/natives/src/internal/reflectlite/value.go

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -266,7 +266,7 @@ func (v Value) Len() int {
266266
case Chan:
267267
return v.object().Get("$buffer").Get("length").Int()
268268
case Map:
269-
return js.Global.Call("$keys", v.object()).Length()
269+
return v.object().Get("size").Int()
270270
default:
271271
panic(&ValueError{"reflect.Value.Len", k})
272272
}

‎compiler/natives/src/reflect/reflect.go

Lines changed: 29 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -620,21 +620,24 @@ func makechan(typ *rtype, size int) (ch unsafe.Pointer) {
620620
}
621621

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

626-
func keyFor(t *rtype, key unsafe.Pointer) (*js.Object, string) {
626+
func keyFor(t *rtype, key unsafe.Pointer) (*js.Object, *js.Object) {
627627
kv := js.InternalObject(key)
628628
if kv.Get("$get") != js.Undefined {
629629
kv = kv.Call("$get")
630630
}
631-
k := jsType(t.Key()).Call("keyFor", kv).String()
631+
k := jsType(t.Key()).Call("keyFor", kv)
632632
return kv, k
633633
}
634634

635635
func mapaccess(t *rtype, m, key unsafe.Pointer) unsafe.Pointer {
636+
if !js.InternalObject(m).Bool() {
637+
return nil // nil map
638+
}
636639
_, k := keyFor(t, key)
637-
entry := js.InternalObject(m).Get(k)
640+
entry := js.InternalObject(m).Call("get", k)
638641
if entry == js.Undefined {
639642
return nil
640643
}
@@ -653,12 +656,15 @@ func mapassign(t *rtype, m, key, val unsafe.Pointer) {
653656
entry := js.Global.Get("Object").New()
654657
entry.Set("k", kv)
655658
entry.Set("v", jsVal)
656-
js.InternalObject(m).Set(k, entry)
659+
js.InternalObject(m).Call("set", k, entry)
657660
}
658661

659662
func mapdelete(t *rtype, m unsafe.Pointer, key unsafe.Pointer) {
660663
_, k := keyFor(t, key)
661-
js.InternalObject(m).Delete(k)
664+
if !js.InternalObject(m).Bool() {
665+
return // nil map
666+
}
667+
js.InternalObject(m).Call("delete", k)
662668
}
663669

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

707714
func mapiterinit(t *rtype, m unsafe.Pointer, it *hiter) {
715+
mapObj := js.InternalObject(m)
716+
keys := js.Global.Get("Array").New()
717+
if mapObj.Get("keys") != js.Undefined {
718+
keysIter := mapObj.Call("keys")
719+
if mapObj.Get("keys") != js.Undefined {
720+
keys = js.Global.Get("Array").Call("from", keysIter)
721+
}
722+
}
723+
708724
*it = hiter{
709725
t: t,
710-
m: js.InternalObject(m),
711-
keys: js.Global.Call("$keys", js.InternalObject(m)),
726+
m: mapObj,
727+
keys: keys,
712728
i: 0,
713729
last: nil,
714730
}
@@ -724,7 +740,7 @@ func mapiterkey(it *hiter) unsafe.Pointer {
724740
return nil
725741
}
726742
k := it.keys.Index(it.i)
727-
kv = it.m.Get(k.String())
743+
kv = it.m.Call("get", k)
728744

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

756772
func maplen(m unsafe.Pointer) int {
757-
return js.Global.Call("$keys", js.InternalObject(m)).Length()
773+
return js.InternalObject(m).Get("size").Int()
758774
}
759775

760776
func cvtDirect(v Value, typ Type) Value {
@@ -1379,7 +1395,7 @@ func (v Value) Len() int {
13791395
case Chan:
13801396
return v.object().Get("$buffer").Get("length").Int()
13811397
case Map:
1382-
return js.Global.Call("$keys", v.object()).Length()
1398+
return v.object().Get("size").Int()
13831399
default:
13841400
panic(&ValueError{"reflect.Value.Len", k})
13851401
}

‎compiler/prelude/jsmapping.go

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -61,9 +61,9 @@ var $externalize = function(v, t, makeWrapper) {
6161
return $externalize(v.$val, v.constructor, makeWrapper);
6262
case $kindMap:
6363
var m = {};
64-
var keys = $keys(v);
64+
var keys = Array.from(v.keys());
6565
for (var i = 0; i < keys.length; i++) {
66-
var entry = v[keys[i]];
66+
var entry = v.get(keys[i]);
6767
m[$externalize(entry.k, t.key, makeWrapper)] = $externalize(entry.v, t.elem, makeWrapper);
6868
}
6969
return m;
@@ -312,12 +312,12 @@ var $internalize = function(v, t, recv, seen, makeWrapper) {
312312
return new mapType($internalize(v, mapType, recv, seen, makeWrapper));
313313
}
314314
case $kindMap:
315-
var m = {};
315+
var m = new Map();
316316
seen.get(t).set(v, m);
317317
var keys = $keys(v);
318318
for (var i = 0; i < keys.length; i++) {
319319
var k = $internalize(keys[i], t.key, recv, seen, makeWrapper);
320-
m[t.key.keyFor(k)] = { k: k, v: $internalize(v[keys[i]], t.elem, recv, seen, makeWrapper) };
320+
m.set(t.key.keyFor(k), { k: k, v: $internalize(v[keys[i]], t.elem, recv, seen, makeWrapper) });
321321
}
322322
return m;
323323
case $kindPtr:

‎compiler/prelude/prelude.go

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -100,6 +100,14 @@ var $mapArray = function(array, f) {
100100
return newArray;
101101
};
102102
103+
// $mapIndex returns the value of the given key in m, or undefined if m is nil/undefined or not a map
104+
var $mapIndex = function(m, key) {
105+
return typeof m.get === "function" ? m.get(key) : undefined;
106+
};
107+
// $mapDelete deletes the key and associated value from m. If m is nil/undefined or not a map, $mapDelete is a no-op
108+
var $mapDelete = function(m, key) {
109+
typeof m.delete === "function" && m.delete(key)
110+
};
103111
// Returns a method bound to the receiver instance, safe to invoke as a
104112
// standalone function. Bound function is cached for later reuse.
105113
var $methodVal = function(recv, name) {

‎compiler/prelude/prelude_min.go

Lines changed: 1 addition & 1 deletion
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎compiler/prelude/types.go

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -617,10 +617,10 @@ var $mapType = function(key, elem) {
617617
return typ;
618618
};
619619
var $makeMap = function(keyForFunc, entries) {
620-
var m = {};
620+
var m = new Map();
621621
for (var i = 0; i < entries.length; i++) {
622622
var e = entries[i];
623-
m[keyForFunc(e.k)] = e;
623+
m.set(keyForFunc(e.k), e);
624624
}
625625
return m;
626626
};

‎compiler/statements.go

Lines changed: 18 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -211,10 +211,15 @@ func (fc *funcContext) translateStmt(stmt ast.Stmt, label *types.Label) {
211211
iVar := fc.newVariable("_i")
212212
fc.Printf("%s = 0;", iVar)
213213
keysVar := fc.newVariable("_keys")
214-
fc.Printf("%s = $keys(%s);", keysVar, refVar)
215-
fc.translateLoopingStmt(func() string { return iVar + " < " + keysVar + ".length" }, s.Body, func() {
214+
fc.Printf("%s = %s ? %s.keys() : undefined;", keysVar, refVar, refVar)
215+
216+
sizeVar := fc.newVariable("_size")
217+
fc.Printf("%s = %s ? %s.size : 0;", sizeVar, refVar, refVar)
218+
fc.translateLoopingStmt(func() string { return iVar + " < " + sizeVar }, s.Body, func() {
219+
keyVar := fc.newVariable("_key")
216220
entryVar := fc.newVariable("_entry")
217-
fc.Printf("%s = %s[%s[%s]];", entryVar, refVar, keysVar, iVar)
221+
fc.Printf("%s = %s.next().value;", keyVar, keysVar)
222+
fc.Printf("%s = %s.get(%s);", entryVar, refVar, keyVar)
218223
fc.translateStmt(&ast.IfStmt{
219224
Cond: fc.newIdent(entryVar+" === undefined", types.Typ[types.Bool]),
220225
Body: &ast.BlockStmt{List: []ast.Stmt{&ast.BranchStmt{Tok: token.CONTINUE}}},
@@ -700,7 +705,16 @@ func (fc *funcContext) translateAssign(lhs, rhs ast.Expr, define bool) string {
700705
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"})
701706
}
702707
keyVar := fc.newVariable("_key")
703-
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()))
708+
return fmt.Sprintf(
709+
`%s = %s; (%s || $throwRuntimeError("assignment to entry in nil map")).set(%s.keyFor(%s), { k: %s, v: %s });`,
710+
keyVar,
711+
fc.translateImplicitConversionWithCloning(l.Index, t.Key()),
712+
fc.translateExpr(l.X),
713+
fc.typeName(t.Key()),
714+
keyVar,
715+
keyVar,
716+
fc.translateImplicitConversionWithCloning(rhs, t.Elem()),
717+
)
704718
}
705719
}
706720

‎go.mod

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@ require (
99
github.com/neelance/sourcemap v0.0.0-20200213170602-2833bce08e4c
1010
github.com/shurcooL/go v0.0.0-20200502201357-93f07166e636
1111
github.com/shurcooL/httpfs v0.0.0-20190707220628-8d4bc4ba7749
12+
github.com/shurcooL/vfsgen v0.0.0-20200824052919-0d455de96546
1213
github.com/sirupsen/logrus v1.8.1
1314
github.com/spf13/cobra v1.2.1
1415
github.com/spf13/pflag v1.0.5
@@ -20,7 +21,6 @@ require (
2021

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

0 commit comments

Comments
 (0)