New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Potential stackoverflow in EnergyGridCache #1004

Closed
yueh opened this Issue Mar 11, 2015 · 2 comments

Comments

Projects
None yet
2 participants
@yueh
Member

yueh commented Mar 11, 2015

This affects a least EnergyGridCache.extractAEPower() as well as EnergyGridCache.injectAEPower()`.

It is mostly a theoretical issue and probably will not show up with normal use, but it is not outside of survival. The log itself is truncated and shows about 500 grids, but I would except that it occurs somewhere between 1k and 2k grids.

A 10x10x10 Cube of cables + quartz fiber connections might be enough.
So not to hard to obtain (1k cables + 3k quartz fiber) after a certain point and can be easily build with something like the BC builder.

The actual issue is the used recursion to visit the grids.
Changing it to a proper BFS/DFS approach using an explicit queue or stack (not the normal call stack) should mostly solve it. Changing it to a proper tail recursion might be also an idea, if possible.

It will also make the world impossible to load the world after the first crash.
But there is not log, just a notice that a stackoverflow occurred during the loading of the dimension.
Other methods beside inject/extract in EnergyGridCache are following the same pattern, but this could potentially be located somewhere else.

Obligatory log: http://pastebin.com/KChDsBjs

@thatsIch

This comment has been minimized.

Show comment
Hide comment
@thatsIch

thatsIch Mar 11, 2015

Member
  • DFS (Depth First Search)
  • BFS (Breadth First Search)
Member

thatsIch commented Mar 11, 2015

  • DFS (Depth First Search)
  • BFS (Breadth First Search)
@yueh

This comment has been minimized.

Show comment
Hide comment
@yueh

yueh Mar 11, 2015

Member

I am probably also in favor of a BFS. It feels more logical, if the adjacent grids are handled at first.

A PriorityQueue/SortedSet for the adjacent grids might also be an idea to prioritize the larger consumers first. But keeping it sorted might be an issue.

Member

yueh commented Mar 11, 2015

I am probably also in favor of a BFS. It feels more logical, if the adjacent grids are handled at first.

A PriorityQueue/SortedSet for the adjacent grids might also be an idea to prioritize the larger consumers first. But keeping it sorted might be an issue.

@yueh yueh added the type-bug label Mar 15, 2015

yueh added a commit that referenced this issue Aug 19, 2017

Performance improvements for the energygrid
Reworked the old recursive approach to a queue based loop.
Extract will try to prefer the next grid with the hightest amount of
stored energy.
Inject will try to prefer the grid with the lowest percentage stored.
Other operations are first come, first serve.

Fixes #1004

yueh added a commit that referenced this issue Aug 19, 2017

Performance improvements for the energygrid
Reworked the old recursive approach to a queue based loop.
Extract will try to prefer the next grid with the hightest amount of
stored energy.
Inject will try to prefer the grid with the lowest percentage stored.
Other operations are first come, first serve.

Fixes #1004

@yueh yueh closed this in #3051 Aug 24, 2017

yueh added a commit that referenced this issue Aug 24, 2017

Performance improvements for the energygrid (#3051)
* Performance improvements for the energygrid

Reworked the old recursive approach to a queue based loop.
Extract will try to prefer the next grid with the hightest amount of
stored energy.
Inject will try to prefer the grid with the lowest percentage stored.
Other operations are first come, first serve.

* Added a local buffer storage to EnergyGrid

This replaces the old not really working buffer with a special
IAEPowerStorage acting as buffer/proxy for the local energy demand as
well as temporary overflow should something provide more energy than
requested.

Currently it set to hold a maximum of 200 AE (+ optional overflow until
consumed). It will only be used locally, no other grid can use it to
avoid starving the neighbor grids before finding a energy cell.

* Fixes IExternalPowerSink

All implementations currently depend on the network demand being a valid
source, which might not be true.

Further it can cause the sink to iterate the network twice (demand and
inject) and both again for simulate and modulate.

Also it did not return the actual leftover amount instead of relying on
the demand matching it.

* Minor fixes related to removing nodes from a grid.

The grid did remove IStackWatcherHost not IEnergyWatcherHost, this was
fine for AE2 as only level emitters use it and they implement both.
But not for potential addons.

Also they would potentually not being removed as the are indexed by the
gridnodes not the machine.

Fixes #1004
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment