letterpwn
letterpwn copied to clipboard
timeout for pathological boards
a board entered by the user consisting of all e's and t's and a's would create millions of possible moves - need to abort before that happens
the backgrounder lib ameliorates the problem, but then:
- we have separate copies of the whole dictionary for each worker, and all memoized results - uses much memory than needed. Ideally we would do what unix has always does, namely, load everything and then REALLY fork, and take advantage of copy-on-write not to blow our memory limit. (we could do some memoization with memcached, maybe. It depends if can store references to the dictionary as ints or something).
- we can still timeout - we need to abort the call to the children if it goes over 10s or something
backgrounder approach improved in commit 931e83b - now we process dictionaries in main node process, but move combinations are farmed out to workers. This works because scanning the dict is O(n) generally quite fast, but move combos can be in the neighborhood of O(n**k-1/(k-1)!) where k is average length of words. Now just need to solve the timeout problem for really pathological cases