letterpwn icon indicating copy to clipboard operation
letterpwn copied to clipboard

timeout for pathological boards

Open neilk opened this issue 12 years ago • 2 comments

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

neilk avatar Feb 12 '13 23:02 neilk

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

neilk avatar Feb 14 '13 00:02 neilk

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

neilk avatar Feb 15 '13 07:02 neilk