FS#4830 - AI can effectively hang OpenTTD by sorting a very large array.

Attached to Project: OpenTTD
Opened by Thijs Marinussen (Yexo) - Tuesday, 08 November 2011, 22:13 GMT
Last edited by Thijs Marinussen (Yexo) - Thursday, 10 November 2011, 19:41 GMT
Type Bug
Category Script → NoAI
Status Closed
Assigned To No-one
Operating System All
Severity Low
Priority Normal
Reported Version Version?
Due in Version Undecided
Due Date Undecided
Percent Complete 100%
Votes 0
Private No


Example: savegame from this post:

An AI calls sort() on an array with 50000 elements. This runs squirrels builtin function _qsort (found in sqbaselib.cpp). Since quicksort is worst-case O(N**2) this quickly takes too long.

OpenTTD cannot suspend in the middle of the _qsort call. One possible solution is to disable the builtin sort() function and write a comparable one in squirrel which can be suspended. Downside of this approach is that it'll hurt performance. A more complication solution is to limit the builtin function in size, and write a wrapper that splits the input and calls the builtin function.
This task depends upon

Closed by  Thijs Marinussen (Yexo)
Thursday, 10 November 2011, 19:41 GMT
Reason for closing:  Fixed
Additional comments about closing:  In r23186