Announcement: Be excellent to each other.

Caravel Forum : DROD Boards : Bugs : Deleting commands takes forever (...if there are a lot of them.)
 New Topic New Poll Post Reply
Poster Message
Xindaris
Level: Smitemaster
Avatar
Rank Points: 1587
Registered: 06-13-2015
IP: Logged
 icon Deleting commands takes forever (+1)  
I'm not really sure if this is a bug or just a consequence of the overall way commands are handled, but if there are a lot of commands in a character and I try to delete them all at once, DROD practically seems to freeze for several minutes before having finally gotten rid of the code. The first couple of times this happened I had it in fullscreen and thought my entire computer had locked up.

I realize that I'm talking about numbers on the order of almost 2000 commands, but the thing is that if I go into something like notepad++ with the same ~2000 commands copy-pasted in text form out of DROD's editor and ask it to delete the exact same information it takes it maybe half a second.

This comes up, and is extremely bothersome, when I need to reconfigure a lot of things on a big block of code, which is easier to do in an external text editor with basic functions like ctrl+f, and then I need to replace the old code with the new code, which requires deleting the old code. Also when I need to update this code on two very similarly coded characters that have a small but extremely important difference in behavior.

Notably, it seems to take the editor less time to delete the code when I do it in chunks, which seems counterintuitive as it should just be deleting the exact same amount of information? And doing so feels more like a workaround than a fix.

____________________________
109th Skywatcher

Here are some links to Things!
Click here to view the secret text

[Last edited by Xindaris at 08-03-2015 08:40 PM]
08-03-2015 at 08:36 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
mrimer
Level: Legendary Smitemaster
Avatar
Rank Points: 5138
Registered: 02-04-2003
IP: Logged
 icon Re: Deleting commands takes forever (0)  
I agree deleting all commands should probably go faster. Would you please attach a sample of a lot of commands that can reproduce this issue?

____________________________
Gandalf? Yes... That's what they used to call me.
Gandalf the Grey. That was my name.
I am Gandalf the White.
And I come back to you now at the turn of the tide.
12-10-2015 at 01:30 AM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores This architect's holds Quote Reply
Xindaris
Level: Smitemaster
Avatar
Rank Points: 1587
Registered: 06-13-2015
IP: Logged

File: Long Code Sample.hold (6.6 KB)
Downloaded 45 times.
License: Public Domain
 icon Re: Deleting commands takes forever (+2)  
Sure, here's one of the things I actually ran into this problem with while trying to echo some changes from one version to another of the same type of block (some custom pushables I've mostly finished developing, except for dealing with Construct-pushing-characters stuff that I need 5.1 for, and possibly incorporating weapon detection if it actually gets added):
Click here to view the secret text


It's...pretty long. But pasting it in takes just a second, while deleting takes so long that clicking the screen can cause windows to mark DROD as "Not responding" and ask me if I want it to force close.


EDIT: It's occurred to me the code requires some variables and refers to three different characters with custom graphics...so, I've just attached a one-room hold with the three relevant characters and all the variables and whatnot included so it should work properly.

____________________________
109th Skywatcher

Here are some links to Things!
Click here to view the secret text

[Last edited by Xindaris at 12-10-2015 03:46 AM]
12-10-2015 at 03:27 AM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
DezzTech
Level: Smiter
Rank Points: 327
Registered: 03-31-2009
IP: Logged
 icon Re: Deleting commands takes forever (+2)  
Assuming CCharacterDialogWidget::DeleteCommands is the function that deletes commands (which is a logical thing to assume, right?), I see where's the problem.

The loop over commands to delete is obviously the bottleneck here, let's look at it (note that I'm calculating complexity for the case when ALL commands are selected):

Loop (O(n)) goes over the commands in the reverse order, which means this line:
commands.erase(iter);

is always O(1).
But then THIS happens:
pActiveCommandList->RemoveItem(pCommand);


CListBoxWidget::RemoveItem performs a linear search (O(n)) on the Items vector EACH time it is invoked.
After item is found it calls GetSelectedItems() which is O(n log n), then Items->erase, which is O(1), since the item will always be in the last position.

But then it calls SelectItems and my brain is ******.
For EACH key it calls SelectItem, which AGAIN performs a linear search on Items and I'm SO DONE trying to calculate complexity for this. SelectItem in turn calls SelectLine, which, surprisingly doesn't perform any searches. But the first time it's called, it does call selectedLines.clear(); which is O(n).

My suggestion is to replace the Items vector with a hash map or whatever it's called in C++ (unordered_map?).

...

...

Click here to view the secret text
12-10-2015 at 01:33 PM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
skell
Level: Legendary Smitemaster
Avatar
Rank Points: 3764
Registered: 12-28-2004
IP: Logged
 icon Re: Deleting commands takes forever (0)  
Or add another optimized function for deleting multiple commands which does a proper cleanup after all entries are removed instead after every single command.

____________________________
My website
12-10-2015 at 01:51 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts High Scores This architect's holds Quote Reply
DezzTech
Level: Smiter
Rank Points: 327
Registered: 03-31-2009
IP: Logged
 icon Re: Deleting commands takes forever (0)  
skell wrote:
Or add another optimized function for deleting multiple commands which does a proper cleanup after all entries are removed instead after every single command.

Just make sure to use remove_if or something similar to keep it close to O(n)

____________________________
Click here to view the secret text
12-10-2015 at 02:26 PM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
skell
Level: Legendary Smitemaster
Avatar
Rank Points: 3764
Registered: 12-28-2004
IP: Logged
 icon Re: Deleting commands takes forever (+2)  
PR

4 thousand commands now take less than 2 seconds to remove, wherein previously about 800 commands would take about 7 seconds.

____________________________
My website
10-13-2020 at 11:49 AM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts High Scores This architect's holds Quote Reply
kieranmillar
Level: Smitemaster
Rank Points: 2846
Registered: 07-11-2014
IP: Logged
 icon Re: Deleting commands takes forever (+1)  
Can confirm in 5.1.1.alpha.2020-10-16 that pasting, selecting and deleting lots of script commands is very substantially faster. While my machine is not as quick as skell's, I did try to compare in the last stable version. Big mistake, it hung the program for ages. The latest alpha is very significantly faster.
10-18-2020 at 12:41 PM
View Profile Send Private Message to User Show all user's posts High Scores This architect's holds Quote Reply
New Topic New Poll Post Reply
Caravel Forum : DROD Boards : Bugs : Deleting commands takes forever (...if there are a lot of them.)
Surf To:


Forum Rules:
Can I post a new topic? No
Can I reply? No
Can I read? Yes
HTML Enabled? No
UBBC Enabled? Yes
Words Filter Enable? No

Contact Us | CaravelGames.com

Powered by: tForum tForumHacks Edition b0.98.8
Originally created by Toan Huynh (Copyright © 2000)
Enhanced by the tForumHacks team and the Caravel team.