yudai / golcs Goto Github PK
View Code? Open in Web Editor NEWGo Longest Common Subsequence
License: MIT License
Go Longest Common Subsequence
License: MIT License
See: http://semver.org/
Helps a lot when using go package management tools like https://github.com/golang/dep
Thanks
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
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)?
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.