search

MasonGulu / CC-MISC

Modular Inventory Storage and Crafting
https://misc.madefor.cc
MIT License
12 stars 5 forks source link

Optimize abstractInvLib defragmentation #14

Closed migeyel closed 1 year ago

migeyel commented 1 year ago

Rather than parallelizing against all possible item types, the new implementation keeps track of which items need defragmentation, figures out a schedule of transfers to perform, then dispatches them in parallel instead. Assuming hash table operations are O(1), the worst-case time complexity is proportional to the smallest possible number of transfers that solve the problem, which is optimal.

Scheduling is performed in a best-effort basis. Some changes in the inventory mid-defrag can cause the entire operation to cancel, but the state will remain consistent. batchExecute is modified to so we can try running schedules as soon as they are made available. This improves the memory usage of very large schedules, and also makes them less likely to cancel from clashing with other transfers.

The only large remaining improvement I see would be putting the scheduler into a coroutine so its computation can overlap with the wait time for existing transfers. I haven't done so because it would also require making something more advanced than parallel.waitForAll.

MasonGulu commented 1 year ago

Thank you for this, I'll accept this PR, but in the near future the only source of abstractInvLib will be https://gist.github.com/MasonGulu/57ef0f52a93304a17a9eaea21f431de6 so it has been merged there (+ credit).

I do see one spot for improvement, refreshItem will call getItemDetail on both inventories (2 yields). Since you know the amount of items being moved, you can modify the original item.item table to update the count, then call cacheItem to update the cache with the item table directly. If you're interested those changes will be uploaded once I have time to implement them.