Register to post in forums, or Log in to your existing account
 

Play RetroMUD
Post new topic  Reply to topic     Home » Forums » CMUD General Discussion Goto page 1, 2  Next
Zugg
MASTER


Joined: 25 Sep 2000
Posts: 23377
Location: Colorado, USA

PostPosted: Fri Jul 20, 2007 4:30 am   

FASTER string lists and database variables in CMUD v2.0!
 
When I was working on some problems with the Lua implementation in CMUD 2.0, I decided I really needed to change my horribly inefficient routines for string lists and database variables to something better and faster. So far I have just improved the string lists (database variables will get their turn next week). But the results are astounding!

Here are the two scripts that I am testing:
Code:
#ALIAS makelist {
  list=""
  $last=%secs
  #loop 1000 {#additem list %i}
  #show (%secs-$last)
  }
#ALIAS searchlist {
  $last=%secs
  #loop 1000 {$a=%ismember(500,@list)}
  #show (%secs-$last)
  }

So, I'm creating a string list with 1000 elements in "makelist". Then, in "searchlist" I am checking the item in the middle of the list to see if it exists in the list. Here are the results:

CMUD v1.34: makelist = 13750 ms, searchlist = 12891 ms
CMUD v2.00: makelist = 13266 ms, searchlist = 310 ms

The new %ismember function is *much* faster. But it gets even better. There is a new #SORT command that sorts a list. Unlike the existing %sort function that just returns the sorted list, the #SORT command actually turns on a flag within the list to tell it to keep itself sorted as new items are added. In addition, this causes the %ismember function to use a binary search method. When we use the "#SORT list" command, and then execute "searchlist", the new results are 91 ms! So that's over 100 times faster than in v1.34!

But wait, there's more :) Can something be done about the "makelist" time? What causes that to be so slow? Well, in CMUD, each time a variable is changed (or any other setting), it needs to be written to the internal database cache, so that it can later be saved to disk. So each time a new item is added to the list, the internal database value gets updated, which is rather slow. Also, each time the string list is changed, the internal list structure needs to be converted to a string value (so it can be saved in the database, printed to the screen, etc).

So, what I added was two new commands: #BEGINUPDATE, and #ENDUPDATE. Each command takes the name of a setting (and an optional setting type). When you use #BEGINUPDATE, you are telling CMUD to suspend saving the setting to the database, and suspend updating it's string value. When you use #ENDUPDATE, the setting is immediately saved and it's string value is updated. These commands actually increment and decrement a counter...so if you use nested BEGINUPDATEs (like in another alias or trigger), only the last #ENDUPDATE will actually cause the setting to start saving itself again.

Here is the modified "makelist" script now:
Code:
#ALIAS makelist {
  list=""
  $last=%secs
  #beginupdate list
  #loop 1000 {#additem list %i}
  #endupdate list
  #show (%secs-$last)
  }

When you run the new "makelist", the time is now 141 ms! That's another factor of 100 improvement in speed!

This actually gives you another way to get the speed benefit of a local variable, without using a local variable. Just use "#BEGINUPDATE varname 1" and the variable will no longer be saved in the background. The "1" option in the 3rd argument tells CMUD to stop writing the variable to the database, but to still update the value of the string when using string list operations. Use this for variables that you don't need to save between sessions. In fact, if you set the "Use Default" option for a variable in v2.0, it will automatically set the "#beginupdate varname 1" so that the variable is faster (since any saved value gets overwritten by the default when you load it again anyway).

I was pretty amazed with these speed improvements. The changes to the string list were not very severe. I actually expect a lot more success from the database variable changes next week. I'll be using a true hash-table associative array structure for database variables (much like Lua's tables), so I expect them to be really fast. I'll post the database variable benchmarks next week when I have something to report.

The next time a friend gives you an excuse why they aren't using CMUD, you should have now a *lot* of reasons to give them for upgrading. Of course, once the new version is stable ;)
Reply with quote
Tech
GURU


Joined: 18 Oct 2000
Posts: 2733
Location: Atlanta, USA

PostPosted: Fri Jul 20, 2007 7:42 am   
 
That's great news Zugg. My stuff isn't tooo heavy but I know the heavy hitter scripters are drooling over this. I've been talking CMUD up and I suspect 2.0 will blow away 1.0 make others go "zMUD who"

Keep up the great work!
_________________
Asati di tempari!
Reply with quote
Ice
Beginner


Joined: 07 Sep 2005
Posts: 12

PostPosted: Fri Jul 20, 2007 10:23 am   
 
All kinds of speed improvements are always very welcome, so this is great to hear! And the ultimate part is that it is automatic. What I am curious about though is if it will automatically apply to converted zMUD scripts as well?

//Ice
Reply with quote
forren
Novice


Joined: 26 Apr 2007
Posts: 44

PostPosted: Fri Jul 20, 2007 12:10 pm   
 
This is awesome.
Reply with quote
Zugg
MASTER


Joined: 25 Sep 2000
Posts: 23377
Location: Colorado, USA

PostPosted: Fri Jul 20, 2007 6:01 pm   
 
Quote:
What I am curious about though is if it will automatically apply to converted zMUD scripts as well?

Yep, definitely. It's a fundamental change in the low-level algorithms that are used in all aspects of CMUD, including the zMUD compatibility module.
Reply with quote
Caled
Sorcerer


Joined: 21 Oct 2000
Posts: 821
Location: Australia

PostPosted: Fri Jul 20, 2007 11:11 pm   
 
#SORT Smile

That's verra noice, Zugg. My whole curing system is based around using %sort on a stringlist. And now you say it will sort itself automatically, faster. I'm quite happy now that I made the right choice in sticking to my stringlist based system, rather than being tempted by #switch. Wink

The begin/end-update part, I will rarely use, though I can see one use for it in capturing my inventory. Nice I suppose, though without needing to do it at any time-crucial ..times, I'm more excited about #sort.

Anyhow, great work.
_________________
Athlon 64 3200+
Win XP Pro x64
Reply with quote
Fang Xianfu
GURU


Joined: 26 Jan 2004
Posts: 5155
Location: United Kingdom

PostPosted: Fri Jul 20, 2007 11:21 pm   
 
Surely you can use it for afflictions as well. They're not the kind of thing you need to keep track of between sessions. I was actually thinking about this and there are very, very few things you need to keep track of between sessions - stat maximums if they're not on your prompt and you can't be bothered to #event onconnect score, preferences... that's about it.
_________________
Rorso's syntax colouriser.

- Happy bunny is happy! (1/25)
Reply with quote
jed
Adept


Joined: 18 Dec 2005
Posts: 246

PostPosted: Sat Jul 21, 2007 2:02 am   
 
NICE!!! I have a couple stringlists that are 1200 or so entries long that I loop through so this will be great!!!! I know 2.0 is coming out, and will be a vast improvement over the already great 1.34, but admittedly it sounds like some pretty root level changes and I'm a bit apprehensive about using it as soon as it's released... Sooo my question is, will 2.0 be released as a public release, or as a beta release???
Just to reiterate, I'm a HUGE fan of CMUD... Just a tad concerned about the debugging period after what appears to be a major overhaul to some core level stuff.
Jed
Reply with quote
Thinjon100
Apprentice


Joined: 12 Jul 2004
Posts: 190
Location: Canada

PostPosted: Sat Jul 21, 2007 2:41 am   
 
OK... maybe I'm going WAY too far with this, but is there a possibility of an optional argument to sort... a pointer to a compare function that accepts two parameters, that can be used for the sort function?

Why this might be useful...

Imagine you're storing a list of unique identifier keys in a string list... information about each unique key is stored in different lists.

Let's say the UIDs reference weapons. You could have information such as "item level", "damage type", "damage dice", "avg damage", "weapon type", etc etc stored in parallel string lists.

Now, let's say I want to sort my uid list by level ASC, and then by avgdam ASC... I could easily write a compare function that takes two UIDs (A and B) and returns 1 if A > B, 0 if A ==B, and -1 if A < B. This way, you could sort by any criteria you want.

Now, before I get replies saying "this could easily be done with db"... I currently avoid the db module like the plague. I will probably make HEAVY use of it when it gets rewritten, but personally I dislike using it currently. :)
_________________
If you're ever around Aardwolf, I'm that invisible guy you can never see. Wizi ftw! :)
Reply with quote
Zugg
MASTER


Joined: 25 Sep 2000
Posts: 23377
Location: Colorado, USA

PostPosted: Sat Jul 21, 2007 2:50 am   
 
Jed: It will definitely be a BETA release. My guess is that it will take a couple of months to get it back to a Public release state. That's exactly why I am doing so much new stuff at once. If I add something that might break stuff and cause bugs, then I might as well add *lots* of new stuff at the same time and just make it really clear that it's a BETA version.

Thinjon: As you mentioned yourself...doing this would be more appropriate in a database. I could do this for the %sort function, but not the #SORT command. Delphi doesn't have any hook in their component to keep a list sorted in a custom manner as new items are added to it. I'd rather put my time into getting the database module rewritten in the future.

Also, you can probably already do this with the Lua implementation in CMUD v2.0. There is a lot more power in Lua, especially when it comes to stuff like custom functions.
Reply with quote
Thinjon100
Apprentice


Joined: 12 Jul 2004
Posts: 190
Location: Canada

PostPosted: Sat Jul 21, 2007 3:01 am   
 
Nodnod... I haven't attempted to do it in Lua yet, but I've already written custom-sort aliases for CMud... the concept of sorting isn't that difficult, I just thought, if possible, that it would make a great addition to the new sorting algorithm... the speed benefit would be awesome :)
_________________
If you're ever around Aardwolf, I'm that invisible guy you can never see. Wizi ftw! :)
Reply with quote
Fang Xianfu
GURU


Joined: 26 Jan 2004
Posts: 5155
Location: United Kingdom

PostPosted: Sat Jul 21, 2007 3:13 am   
 
At the risk of derailing the thread, I'll just mention that all sorting in Lua is custom sorting. You give the function that sorts the table a function as an argument. The argument takes two parameters that're items of the list, and returns true or false depending on whether or not the first should come after or before the second.
_________________
Rorso's syntax colouriser.

- Happy bunny is happy! (1/25)
Reply with quote
Thinjon100
Apprentice


Joined: 12 Jul 2004
Posts: 190
Location: Canada

PostPosted: Sun Jul 22, 2007 4:17 am   
 
Oh, Zugg... another question...

In the usage of BEGINUPDATE and ENDUPDATE... will these prevent accessing a variable between aliases/triggers? i.e. if I have a set of triggers that loop over several lines captured from the mud, and each triggering line is going to add something to a string list, would it work to use BEGINUPDATE before the first line, and then ENDUPDATE at the end of the trigger set?

If so, would the speed benefit still remain?
_________________
If you're ever around Aardwolf, I'm that invisible guy you can never see. Wizi ftw! :)
Reply with quote
Fang Xianfu
GURU


Joined: 26 Jan 2004
Posts: 5155
Location: United Kingdom

PostPosted: Sun Jul 22, 2007 11:28 am   
 
It seems like #endupdate just suspends database writes and not internal cache writes. You'll be able to change the value of something that you've #beginupdated but no changes will be saved to disk until you #endupdate it. It'd be quite useless if you made a "Use Default" variable and then couldn't change its value with anything.
_________________
Rorso's syntax colouriser.

- Happy bunny is happy! (1/25)
Reply with quote
Thinjon100
Apprentice


Joined: 12 Jul 2004
Posts: 190
Location: Canada

PostPosted: Sun Jul 22, 2007 4:23 pm   
 
Well, I figured that it would be possible to write to the variable while it was under the effect of #BEGINUPDATE... what I was more curious about was the scope of the effect. i.e. if I intend to append values, do all my writes have to occur in the same alias/trigger between the calls to BEGINUPDATE/ENDUPDATE ?

Let's say I have an alias that checks/catalogs my inventory. The alias enables a class, sends the MUD 'inv' command, and executes BEGINUPDATE on my @invlist string list.
Now, one of the triggers in the enabled class fires for each line in the 'inv' return... let's say the list looks like this:

a wooden spoon [1]
a rusty dagger [5]
(2) a flying potion [1]

On the first trigger catch, I might add 'wooden spoon' to @invlist. In the scope of this trigger call, I'm sure @invlist would then equal "wooden spoon".
No, on the second trigger catch, if I add "rusty dagger", does @invlist = "wooden spoon|rusty dagger" or does the value from the first trigger catch carry over under the effect of BEGINUPDATE ? If not, then my @invlist now equals "rusty dagger" - within this trigger's scope.
The third trigger catch would yield either "wooden spoon|rusty dagger|flying potion" or just "flying potion"

Now if I have another trigger, perhaps that fires on ^$, that disables the class, and executes #ENDUPDATE on @invlist, I could have either an empty list, or have 3 items in it.

Perhaps I don't know enough about the internal workings of z/CMud variables... but I figured it couldn't hurt to ask what this effect would be.
_________________
If you're ever around Aardwolf, I'm that invisible guy you can never see. Wizi ftw! :)
Reply with quote
Yamabushi
Apprentice


Joined: 29 Jul 2003
Posts: 101
Location: USA

PostPosted: Sun Jul 22, 2007 4:50 pm   
 
Do you have an estimate of what month we may see v2.0? It sounds like its going to be great.
_________________
Yama
Reply with quote
Fang Xianfu
GURU


Joined: 26 Jan 2004
Posts: 5155
Location: United Kingdom

PostPosted: Sun Jul 22, 2007 5:11 pm   
 
Thinjon: That's why I gave the "Use Default" example. Zugg said above that "Use Default" now works by setting #BEGINUPDATE for the variable as soon as CMUD starts. If that's the case, then the variable must still work exactly the same as it normally would, but database writes would be suspended. Your triggers will all write to the internal cache variable as they normally would, but the new values will only be written out to disk when you use #ENDUPDATE.

Yamabushi: Zugg's last estimate was either before or after the Sony Fan Faire. That's August 2nd-5th, so it'll be around then :)
_________________
Rorso's syntax colouriser.

- Happy bunny is happy! (1/25)
Reply with quote
oldguy2
Wizard


Joined: 17 Jun 2006
Posts: 1201

PostPosted: Sun Jul 22, 2007 8:32 pm   
 
Caled wrote:
#SORT Smile

That's verra noice, Zugg. My whole curing system is based around using %sort on a stringlist. And now you say it will sort itself automatically, faster. I'm quite happy now that I made the right choice in sticking to my stringlist based system, rather than being tempted by #switch. Wink

The begin/end-update part, I will rarely use, though I can see one use for it in capturing my inventory. Nice I suppose, though without needing to do it at any time-crucial ..times, I'm more excited about #sort.

Anyhow, great work.


I stuck to using a stringlist too for my curing system and storing all of my afflictions. However, I also made good use of #switch in my curing aliases. It works great and should even work better and faster with these changes.

What would be the advantage of using #sort?
Reply with quote
oldguy2
Wizard


Joined: 17 Jun 2006
Posts: 1201

PostPosted: Sun Jul 22, 2007 8:38 pm   
 
Zugg,

Hmm I copied your little scripts of makelist and searchlist and ran them on my computer with version 1.34 and came up with the following:

makelist = 312

searchlist = 219
Reply with quote
Fang Xianfu
GURU


Joined: 26 Jan 2004
Posts: 5155
Location: United Kingdom

PostPosted: Sun Jul 22, 2007 9:10 pm   
 
I get similar results, but that doesn't mean that you won't still see a speed improvement in the new version.
_________________
Rorso's syntax colouriser.

- Happy bunny is happy! (1/25)
Reply with quote
oldguy2
Wizard


Joined: 17 Jun 2006
Posts: 1201

PostPosted: Sun Jul 22, 2007 9:18 pm   
 
Fang Xianfu wrote:
I get similar results, but that doesn't mean that you won't still see a speed improvement in the new version.


Yes Fang. I never said it didn't. I was just pointing out the huge difference in my numbers compared to his.
Reply with quote
Caled
Sorcerer


Joined: 21 Oct 2000
Posts: 821
Location: Australia

PostPosted: Mon Jul 23, 2007 12:46 pm   
 
oldguy2 wrote:
I stuck to using a stringlist too for my curing system and storing all of my afflictions. However, I also made good use of #switch in my curing aliases. It works great and should even work better and faster with these changes.

What would be the advantage of using #sort?

You didn't play Mordyval by any chance?

Ahem, anyhow, from the sound of it, using #sort once means it will sort itself automatically ("..the #SORT command actually turns on a flag within the list to tell it to keep itself sorted as new items are added.) which means not having to %sort the stringlist every time the main curing alias gets run, which is a time-sensitive moment. Only minor I know, but its still 2 (3 on imperian) lines of code removed.

And yeah, I've used a few #switch commands here and there as well, but I specifically meant the decision about whether or not to have a flag variable per affliction, or a stringlist per cure class (herbs, salves etc). The improved expressions and #switch almost made me drop that completely, but a few things (like the simplicity of %expandlist(@herbaffs) in the statuswindow) made me stick with what I know.
_________________
Athlon 64 3200+
Win XP Pro x64
Reply with quote
Zugg
MASTER


Joined: 25 Sep 2000
Posts: 23377
Location: Colorado, USA

PostPosted: Mon Jul 23, 2007 5:30 pm   
 
oldguy2: The timings that I posted are for the debug version of CMUD that I'm working on. You should expect to get much faster numbers because the version that you are running is the non-debug optimized release version. When I'm running CMUD for development, I have all sorts of debug stuff enabled that slows it down. Also, you never know how fast your computer is compared to mine. My computer is a few years old (I cannot game on this computer, for example).

In any case, while the exact numbers might change once I've got the compiled and optimized release, there should still be a similar huge difference in speed.

Back to the #beginupdate issue...remember that I mentioned that there is an additional argument to #beginupdate to control how the internal cache is updated. Well, I'm going to change things a bit to make this easier:

#BEGINUPDATE varname

This also turns off the writing of the variable to the database, but for string lists and database variables, it also disables the update of the string value of the variable. This case will give you more speed when updating the contents of a string list or database variable. CMUD stores the string list internally now as a hash table. But when you display the value of the variable (like with #SHOW @var) then CMUD needs the string value of the variable (like "Item1|Item2|Item3" etc). So normally, when you use something like #ADDITEM to add to a string list, the item is added to the internal hash table *and* the string value is recomputed. When adding a lot of items, there isn't any need to keep recomputing the string value until you are done. Using #ENDUPDATE tells CMUD to recompute the string value of the variable based upon the hash table.

#NOUPDATE varname

This will simply turn off the writing of the variable to the database. This is the same as the previous "#BEGINUPDATE varname 1" syntax. This has the same effect as setting the Use Default option for the variable (except that you can do it for any setting, not just variables).

Doing a #NOUPDATE varname or #NOUPDATE varname 0 will turn off updates (same as enabling the Use Update option). Using #NOUPDATE varname 1 will re-enable the update flag.

This will help separate the difference between #BEGINUPDATE/#ENDUPDATE which MUST be given in pairs, and mainly applies to string list and database variables, and the #NOUPDATE which can be used any time you want to stop updating a setting to the database file.

So, back to string lists: Using #BEGINUPDATE *will* cause problems if you try to access the value of the variable before the #ENDUPDATE call. For example:
Code:
List=""
#ADDITEM List "Zugg"
#SHOW @List
-> displays "Zugg"
#BEGINUPDATE List
#ADDITEM List "Chiara"
#SHOW @List
-> still displays "Zugg" because the list is not being updated
#ENDUPDATE List
#SHOW @List
-> now displays "Zugg|Chiara" because the list has been updated

Using #NOUPDATE would not have this side effect...it would just prevent the list from being stored to the disk database. But you won't get the full speed benefit from using #NOUPDATE because CMUD will still be updating the string value of a list whenever you add or remove items.
Reply with quote
Fang Xianfu
GURU


Joined: 26 Jan 2004
Posts: 5155
Location: United Kingdom

PostPosted: Mon Jul 23, 2007 6:07 pm   
 
And you can use #beginupdate and #endupdate on a variable that you've previously used #noupdate on, I assume, since they seem to do totally different things.
_________________
Rorso's syntax colouriser.

- Happy bunny is happy! (1/25)
Reply with quote
Zugg
MASTER


Joined: 25 Sep 2000
Posts: 23377
Location: Colorado, USA

PostPosted: Mon Jul 23, 2007 6:34 pm   
 
Yes, the #BEGINUPDATE/#ENDUPDATE are separate from #NOUPDATE.

And actually, I think I'm going to call it #NOSAVE instead of #NOUPDATE. That better matches what it is doing. Also, I'll add a "Saved" checkbox next to the "Enabled" checkbox in the settings editor to control this flag.

To try and make it perfectly clear: If you have used #NOSAVE on a variable, then the BEGINUPDATE and ENDUPDATE will still work (and still prevent string lists and database variables from being updated), but after the ENDUPDATE, the variable still won't save it's value to disk (until you turn off the NOSAVE option).
Reply with quote
Display posts from previous:   
Post new topic   Reply to topic     Home » Forums » CMUD General Discussion All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum

© 2009 Zugg Software. Hosted by Wolfpaw.net