The golcs from yudai

Test failure on 32bit platforms

I'm seeing the tests fail as below on i686 and armv7hl platforms due to insufficient addressable memory. Can we reduce the size of these allocations in the test, while preserving the tests integrity? I suspect these are the relevant lines in golcs_test.go ...

        left := make([]interface{}, 100000) // takes over 1 sec
        right := make([]interface{}, 100000)

This is the test log ...

+ go test -buildmode pie -compiler gc -ldflags '-extldflags '\''-Wl,-z,relro -Wl,--as-needed  -Wl,-z,now -specs=/usr/lib/rpm/redhat/redhat-hardened-ld '\'''
runtime: out of memory: cannot allocate 401408-byte block (2851766272 in use)
fatal error: out of memory
runtime stack:
runtime.throw(0x54899a, 0xd)
	/usr/lib/golang/src/runtime/panic.go:617 +0x60
runtime.largeAlloc(0x61a84, 0x4a0101, 0xa3f7f7a8)
	/usr/lib/golang/src/runtime/malloc.go:1057 +0x148
runtime.mallocgc.func1()
	/usr/lib/golang/src/runtime/malloc.go:950 +0x38
runtime.systemstack(0x4ac0c0)
	/usr/lib/golang/src/runtime/asm_arm.s:354 +0x90
runtime.mstart()
	/usr/lib/golang/src/runtime/proc.go:1153
goroutine 20 [running]:
runtime.systemstack_switch()
	/usr/lib/golang/src/runtime/asm_arm.s:298 +0x4 fp=0x202c694 sp=0x202c690 pc=0x4ac1cc
runtime.mallocgc(0x61a84, 0x5b8520, 0x1301, 0xbeb72000)
	/usr/lib/golang/src/runtime/malloc.go:949 +0x8c8 fp=0x202c6f8 sp=0x202c694 pc=0x45a2e8
runtime.makeslice(0x5b8520, 0x186a1, 0x186a1, 0xbeb72000)
	/usr/lib/golang/src/runtime/slice.go:49 +0x70 fp=0x202c70c sp=0x202c6f8 pc=0x4959bc
github.com/yudai/golcs.(*lcs).TableContext(0x2080340, 0x5d7090, 0x20786a0, 0x202c77c, 0x202c780, 0x4, 0x205e540, 0x5460f8)
	/builddir/build/BUILD/golcs-ecda9a501e8220fae3b4b600c3db4b0ba22cfc68/_build/src/github.com/yudai/golcs/golcs.go:73 +0xa8 fp=0x202c750 sp=0x202c70c pc=0x543234
github.com/yudai/golcs.(*lcs).LengthContext(0x2080340, 0x5d7090, 0x20786a0, 0x20786a0, 0x2074260, 0xe7c4068d)
	/builddir/build/BUILD/golcs-ecda9a501e8220fae3b4b600c3db4b0ba22cfc68/_build/src/github.com/yudai/golcs/golcs.go:104 +0x2c fp=0x202c774 sp=0x202c750 pc=0x5435c0
github.com/yudai/golcs.TestContextCancel(0x20a0140)
	/builddir/build/BUILD/golcs-ecda9a501e8220fae3b4b600c3db4b0ba22cfc68/_build/src/github.com/yudai/golcs/golcs_test.go:117 +0x204 fp=0x202c7b4 sp=0x202c774 pc=0x546120
testing.tRunner(0x20a0140, 0x5d5184)
	/usr/lib/golang/src/testing/testing.go:865 +0xb0 fp=0x202c7e4 sp=0x202c7b4 pc=0x509f98
runtime.goexit()
	/usr/lib/golang/src/runtime/asm_arm.s:868 +0x4 fp=0x202c7e4 sp=0x202c7e4 pc=0x4ae0ac
created by testing.(*T).Run
	/usr/lib/golang/src/testing/testing.go:916 +0x2f0
goroutine 1 [chan receive]:
testing.(*T).Run(0x20a0140, 0x549465, 0x11, 0x5d5184, 0x1)
	/usr/lib/golang/src/testing/testing.go:917 +0x310
testing.runTests.func1(0x20a0000)
	/usr/lib/golang/src/testing/testing.go:1157 +0x68
testing.tRunner(0x20a0000, 0x203af14)
	/usr/lib/golang/src/testing/testing.go:865 +0xb0
testing.runTests(0x2088010, 0x677880, 0x2, 0x2, 0x0)
	/usr/lib/golang/src/testing/testing.go:1155 +0x290
testing.(*M).Run(0x20800c0, 0x0)
	/usr/lib/golang/src/testing/testing.go:1072 +0x158
main.main()
	_testmain.go:44 +0x170
goroutine 21 [sleep]:
runtime.goparkunlock(...)
	/usr/lib/golang/src/runtime/proc.go:307
time.Sleep(0x3b9aca00, 0x0)
	/usr/lib/golang/src/runtime/time.go:105 +0x178
github.com/yudai/golcs.TestContextCancel.func1(0x2074260)
	/builddir/build/BUILD/golcs-ecda9a501e8220fae3b4b600c3db4b0ba22cfc68/_build/src/github.com/yudai/golcs/golcs_test.go:113 +0x24
created by github.com/yudai/golcs.TestContextCancel
	/builddir/build/BUILD/golcs-ecda9a501e8220fae3b4b600c3db4b0ba22cfc68/_build/src/github.com/yudai/golcs/golcs_test.go:112 +0x1dc
exit status 2
FAIL	github.com/yudai/golcs	0.461s

Pathologically bad performance with long input

This is also documented somewhat over at gojsondiff (yudai/gojsondiff#9 where maybe some API changes can help), but the core issue is here in golcs.

It's possible to construct strings of around 10000 bytes (on my machine at least) that cause lcs.Length() to run indefinitely. I've added a test case over here: https://github.com/pteichman/golcs/tree/infinite-hang

Is your sense that this could be improved with a different algorithm in golcs, or should the API be extended to allow cancellation if a deadline is exceeded (using, say, context.Context)?

Please use semver tagging

See: http://semver.org/

Helps a lot when using go package management tools like https://github.com/golang/dep

Thanks

yudai / golcs Goto Github PK

golcs's People

Contributors

Stargazers

Watchers

Forkers

golcs's Issues

Test failure on 32bit platforms

Pathologically bad performance with long input

Please use semver tagging

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent