Integrated Dynamics

Integrated Dynamics

Mods
63M Downloads

Iteration through lists of ValueTypeListProxyConcat is O(n^2)

michaelPoul opened this issue · 1 comments

commented

Issue type:

  • 🐌 Performance issue

Short description:

For large concatenated lists, ValueTypeListProxyConcat::getLength is linear in regards to the number of concatenations. Since ValueTypeList's iterator calls getLength for each call to hasNext(), this makes iteration O(n^2) in regards to the number of concatenations.

A similar issue may exist in ValueTypeListProxyTail and ValueTypeListProxySlice, since their getLength implementations are also recursive.

Steps to reproduce the problem:

  1. Create 16 single chests, put some items in, and attach inventory readers to each
  2. Concatenate all the inventories together to create a large list of all inventories
  3. Perform an operation that traverses through the concatenated inventory list, such as filter(pipe(itemsize, 32<=...), biglist)
  4. Display the output
    On a new world, this already took roughly 6.7% of the server thread's time

Versions:

  • This mod: 1.12.2-1.0.11
  • Minecraft: 1.12.2
  • Forge: 14.23.5.2838
    This issue was observed using the FTB Interactions modpack

Profiler output:

Profile from my FTB Interactions world with a very large inventory system
id_interactions.zip

Profile from the simple world with 16 chests:
id_simple.zip

commented

Thanks for reporting, I'll look into it as soon as possible!