Performance Issues
knoxz opened this issue · 36 comments
Hi there,
I just ran a quick debug to see why my server is lagging. One single exporter is taking a huge chunk of server resources! I had a quick look at your code and nearly started to cry. I didnt go that deep but I think I got deep enough to find the performance issue with the server world only beeing a few days old.
You interate over ArrayLists with in the worst case 64k Entrys and try to find the the Items to extract.
This is like the worst you can do in efficiency!
Ever wondered why AppliedEnergistics only has 64 different ItemSlots/Storage.
Because interating over 64k Entrys takes for ever and is a terrible idea.
If you really want to store 64k Stacks you should put your ItemStacks in HashMaps not ArrayLists!!!
If you try to find an Item its 1 one Single Operation (retrival from the HashMap via Key) VS in the worst case 64k Operations.
You can use the ItemStack identifier like minecraft:dirt as key and a list of Stacks as value. You just need to track how many stacks are inside the disk and update accordingly.
This is not the optimal way but its like a few thousand percent more efficient as you are doing it now.
If you want to be really efficient you have to do it like ae2 does it and store items with a low number of different items but a huge storage/item.
You can't run your mod on servers at this time. As 2-3 exporter on a decently sized storage take the server below 20 TPS.
Even if they just TRY to export stuff.
Unfortunately this is not a trivial fix but you need to fix this sooner or later otherwise I don't see any real future in this mod.
After further testing, it seems like the issue is not about iterating.
I've added a debug thingy to storage disks that adds a 10K itemcount for every item in the registry.
If I remove the part of the code that merges items from different storages, everything runs very smooth.
Somehow I'd have to optimize this:
private void updateItems() {
combinedItems.clear();
combinedItemsIndices.clear();
for (int i = 0; i < items.size(); ++i) {
if (combinedItemsIndices.contains(i)) {
continue;
}
ItemStack stack = items.get(i);
for (int j = i + 1; j < items.size(); ++j) {
if (combinedItemsIndices.contains(j)) {
continue;
}
ItemStack otherStack = items.get(j);
if (RefinedStorageUtils.compareStackNoQuantity(stack, otherStack)) {
// We copy here so we don't modify the quantity of the ItemStack IStorage uses.
// We re-get the ItemStack because the stack may change from a previous iteration in this loop
ItemStack newStack = items.get(i).copy();
newStack.stackSize += otherStack.stackSize;
items.set(i, newStack);
combinedItems.add(otherStack);
combinedItemsIndices.add(j);
}
}
}
items.removeAll(combinedItems);
}There might be an issue there too.
But I just added a quick debug how often your compare method is called.
I made sure only the one exporter is active on a network with 8 16k disk drives.
I didnt even connect to the server.
The server was running way below 20tps. Most likely of the debug spam, so the actual number at 20 tps should be even higher.
Here is the log.
I did cut it because I dont think you can upload 100mb of log to pastebin.
http://pastebin.com/LxyJZban
I did make the debug "slightly" less spammy and only debugging every 10 000th time to run the server at full tps.
Your compare method was called over 12 Million times in 4 Seconds.
Thats 150000 times each minecraft tick.
Be aware this is still one single tile that is active, 1 exporter, 1 DiskDrive not even doing something as there is no ores in the system.
I still think you have a "slight" iteration issue ;-)
Also, saying that the for loop has to iterate over 64 000 entries is simply false. If you have 1 item that has an itemcount of 20 000 items, that counts as 1 entry, not 20 000 or 20 000 / 64.
Don't think I didn't try to go through the hashmap route, it's simply not possible or very hard to pull off simply because take takes comparison flags. I could use a MultiMap that maps an Item to different ItemStacks, but the performance win in that seems neglible.
Well it cant stay that way.
Here is the dump.
One exporter is active in the world which was trying to export ores to process them. "Only" 8 16k storage disks are active on that network.
And he brings the server below 20 tps.
Also, I'd appreciate it if you change your tone a bit. This is an issue tracker, not a means to dump your frustration.
You dont need to use MutliMaps if you store way smaller lists behind the key as value of the HashMap. This would give a huge performance boost and you dont need to change that much.
You could make a class that contains these compare flags and the itemStacks and save those as value.
Try this build please (it's for 1.10) and tell me if you still have lag
Rename .zip to .jar
It why would it be different? The part of your code which is responsible havent been altered. I made my observations on your source code.
Unfortunately dont have a setup for that.
Just have a few storage cells (64k) fill with lots of different stuff like a normal player would use it and then try to export 8 different items which are not in the network.
do /debug track the ticks used.
you should be able to compare one exporter to like the monster AI. Sadly the debug does not give exact numbers. you have to use other means of debugging performance like visualVM or something like that to do that.
You could also do a dirty counter debug. If one extract takes like 100 operations on a medium storage system.
Imagine a "big" server with like 20 players. After a few weeks everyone has a few storage disks and a few systems which do storage calls. Thats 20 player * 8 (importer/exporter/interfaces ) * 100.
Thats 16k operations.
As one single exporter can push the server tps below 20 I image the 100 operations to be more like a few thousand. You can do the math.
You should really try to reduce the number of operations your storage calls do somehow.
I still would suggest HashMaps with a custom class which saves all the nessesary informations, but there are also different ways.
In the best case storage calls should not interate at all.
The core problem isn't fixed. even in your latest build.
I know that you worked like houndreds of hours on that mod and I appriciate the time you invested. I have really much fun automating stuff with your mod.
If you want your mod to be succesfull you have to tackle this performance issues.
this is not me being rude, but giving you facts and not sugarcoating them.
Nope, no iteration issue. Iterating around 10 - 20 values per storage disk isn't slow. The JVM can handle that.
The problem is, like I said, in the method that I posted. I could see it when I removed that code. I have to optimize that.
This seem to apply to crafting as well. I noticed as my network got more complex and added more and more disks things started to slow down, way down. With about 12 64k disks it can hang the entire server for about 5-15 secs just asking JEI to fill out the crafting grid. If i shift craft a stack it can take up to 20-40 secs, some times even timing out everyone on the server. One thing to note is i only use interfaces, no exporters or importers. Here is a snapshop of me making a few stacks of storage draws. Was taking about 45 secs each stack. https://db.tt/MbupgkpZ Please get in touch with me if you need a test server to see if any changes may help this out or just to see it for youself.
My girlfriend always says I would be a terrible teacher. I am too direct sometimes. I am sorry.
Believe me, there is an issue. 12 MILLION compares in 4 seconds are an issue! Even 1 million are still 950 000 to many! Your mod is not the only one who wants to calculate stuff. That method might be flawed, but there are more deeper issues with your implementation. An jvm might be able to handle one maybe two of your exporter, but that might be the limit. I am working on my masters degree in computer science and do help bachelor students with programming as a daytime job.
If your mod gets used by a wide range audience, people will complain about performance. You obviously have a lot of experience with programming and your code is really good. Still I have to remove your mod because more than one guy is starting to use it and the server cannot handle it.
I know that a mod like that is a huge chunk of work. Its just a recommendation.
If you say, you don't have an issue, we might as well close this issue.
Trust me, I know where the issue is. And I don't need a bachelor or master for that. I'm going to fix it, but you need some patience. Keep in mind that I worked constantly on this mod for the past few weeks, I need a break too.
Hey, can we rename this issue title? It doesn't accurately convey the issue itself, and to me just comes off as passive aggressive/rude.
@knoxz
Remember that the author is making this mod in his spare time -- play nice 😄
@knoxz
To prove my point, here is a build that removes inventory merging.
Do this:
- Load up a new world
- Take a storage disk
- Right click it to populate it with every item from the registry (keep in mind, these are like 900 000 items per disk)
- Place it in a disk drive
- Setup an exporter that exports an item at full speed
You'll see, no lag. You can even duplicate the same disk with middle click in the disk drive and you'll see, even if you filled the whole disk drive with that same disk, there will be no lag because the inv merging is removed.
(Just don't open the grid, that WILL be laggy, but due to other reasons than this issue)
This proves my point that there is no issue with the base IStorage impls.
The worrisome thing is. You have to reduce the 12 Million compare operations to a few thousands.
Thats in numbers like 120000%(?) more performance.
You could start with only ticking tiles once every 20 ticks. But that does not really solve anything.
You say it should only interate over 20-30 values per storage disk, but how do you explain the 12 million compare operations a really small system does with just trying to export stuff?
If the server is locked for 5-15 seconds with only filling out the crafting grid on a medium-big system you might not be accurate on how it works.
You might need to go into debug mode and go step by step through how it searches for stuff.
With Eclipse and a forge environment this is easy to do.
If you update your 1.9.4 branch I can compile and test it on our server world. I still do not have a 1.10 test setup.
I did some tests on the updateItems() logic to come up with a better way to combine the item lists. I was able to remove the O(N^2) nested loop with a hash of the data that needs to be combined upon. Tests on our server went from 60ms per tick to 0.9ms per tick average for the update function, restoring playability. It is a bit hacky, but it seems to work fine.
I see though that you already changed this logic and I haven't had a chance to find what happened to it yet. Since it fixed our problems I figured I would post it here anyway.
Inside RefinedStorageUtils.java: http://pastebin.com/aZpygnkb
Inside TileController.java: http://pastebin.com/XATiyNqC
Seems to me that even if changes are sent as deltas rather than re-sending the whole list, you still have to merge when the grid is first opened? If so, a fast merge would still be useful :)
Yes, I'll still have to merge (serverside AND clientside) but it will be more efficient nonetheless as it won't rebuild the whole items list. It will just increase the item stored, similair how NBTStorage works.
This is how I'm doing it currently:
add and remove are called as soon as an item is added / removed to any IStorage.
rebuild is only called when a new storage is added, or removed.
As for the list in the storage itself, it seems to me that a hashtable could be used even though there are pull flags to worry about. Either there could be a hashtable for every combination of pull flags (probably too much bookkeeping cost) or there could be one hashtable only, with the least restrictive flags applied. So, you could group everything by item only ignoring NBT and damage, so a pull/push only has to iterate through all stacks of the same item rather than every stack. In most cases I suspect that would be a nice improvement.
That is how GroupedStorage does it. It's using a Multimap, which does the same thing you're describing. Is a Hashtable more performant?
Nice, I love it when people go in the code and fix it themselves.
However, I'm working on a fix that eliminates the merging alltogether. As an added bonus, it will be possible as well to just send over inventory changes to the grid and not the whole inventory every time.
That's exactly what I said at the beginning.
Use a HashTable where you have itemIdentifiers as Keys (minecraft:ironSword for example)
and as value you can have ArrayLists of itemStacks with all the different swords with nbt and dmg.
Even if there are 1000 of different items you can get the right item with a single operation.
You only have to iterate if you have more of the same item.
I would not use MultiMaps. It makes things more complicated with no real value.
That would get you so much more performance.
I think multimaps and hashtables are exactly the same thing, no? What is the difference between a multimap<item, itemstack> and a hashtable<item, list<itemstack>>? I think the multimap route is even cleaner.
Well you could get into trouble when you try to edit the different stacks.
No idea how smart java or google and their multimap is in that regard.
If you use list you use list = remove(item)
then you can work on the list and after you are done use put(item,list) or do nothing if the list is empty to update the list in inside table.
I have no idea if you have tested it already but you might be duping a lot of items with your current implementation of remove. If everything is referenced you might be fine. If not you are not. ;-)
You completely avoid these problems if you use lists and update every time you do something with them.
Also with multi maps it will get more complicated to not do any errors.
At the end of the day its just preferences. Both should work.