Poor performance of std.findSubstr

[sm-gravid-day]

std.findSubstr is very, very slow. Running the following:

time ../jsonnet --ext-str var1=test --ext-code var2='{x:1,y:2}' stdlib.jsonnet

at commit 6694cef takes ~ 1.2 seconds for me, but if I add the following additional test:

std.assertEqual(std.findSubstr('aa bb cc', 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx'), []) &&

Then running the above now takes ~ 2.2 seconds. That's a whole second extra! In my use case this is rendering findSubstr essentially useless.

[sm-gravid-day]

Looks like a problem here:

std.filter(function(i) str[i:i + pat_len] == pat, std.range(0, str_len - pat_len))

[sbarzowski]

@sm-gravid-day
Thank you for reporting this. It should be quite easily fixable.

You can try https://github.com/google/go-jsonnet, which is a newer implementation. It's less terribly slow for your example (8x faster). Generally if you care about performance it is a much better bet (since our development focus is primarily on the Go version). Anyway even in Jsonnet version it could be made much faster.

[sm-gravid-day]

Thanks @sbarzowski; however, I'm not having much luck with the go version...

INTERNAL ERROR: (CRASH) Desugaring desugared object
goroutine 1 [running]:
runtime/debug.Stack(0xc000861438, 0x55b880, 0x5e42c0)
	/usr/local/go/src/runtime/debug/stack.go:24 +0x9d
github.com/google/go-jsonnet.(*VM).evaluateSnippet.func1(0xc000869d00)
	/src/go-jsonnet/vm.go:129 +0x60
panic(0x55b880, 0x5e42c0)
	/usr/local/go/src/runtime/panic.go:522 +0x1b5
github.com/google/go-jsonnet.desugar(0xc0001201a0, 0x4, 0x0, 0x0)

[sbarzowski]

@sm-gravid-day
Uh, wow, is it happening on the newest master? If so, please report a bug with an example code for which this is happening as this is a pretty big deal and I want to fix it ASAP.

[sm-gravid-day]

@sbarzowski sorry for my very late reply.

I can confirm your go-jsonnet fix worked for me - thank you.

I'm now working with go-jsonnet and am very happy with it; however, my original bug here still stands for the c++ implementation.

Thanks again.

[lihaoyi-databricks]

For what it's worth, interpreting test_suite/stdlib.jsonnet including your long findSubstr assertion takes ~5.5 milliseconds on Sjsonnet (on a warm JVM)