WML vs lua Speedtest

[Dugi]

I was trying to compare the speed of WML and lua. For this purpose, I have created a short code with highly repetitive calculations to create something that would take a measurable amount of time, and would be easy to transfer between lua and WML.

This was the code (written in C, because it is the shortest):

Code: Select all

int a=1;
int b;
while(a<50000) {
	a=a+1;
	b=1;
	while(b<20000) {
		b=b+1;}}
printf("1 000 000 000 iterations done\n");

(I intentionally didn't use the for cycle because it does not exist in WML.)
To my surprise, lua seemed to be 1000 times faster than WML at executing this (the number of cycles had to be reduced for WML in order to avoid falling asleep during the experiment). Compared to C, lua was still 7 times slower.

Then I came to try something with more numerical calculations. I added a few pointless and ugly divisions and multiplications to the code. The code looked like this:

Code: Select all

int a=1;
int b;
double c;
while(a<50000) {
	a=a+1;
	b=1;
	c=1000;
	while(b<20000) {
		b=b+1;
		c=(c+47)/43*13;}}
printf("1 000 000 000 iterations done\n");

Executing this took much more time than executing the previous code (C needed like 7 times more time). WML did it 500 times slower than lua, and lua did it 8 times slower than C.
According to some sources (I cannot remember which ones), lua is many times faster than java in computations of this kind, so lua is not as slow as it might seem.

I have not tried how fast it would be if I was doing operations that cannot be done by C normally, like storing units, searching WML variable arrays and other stuff, I hope to do it once. The only lesson that came from this is that because WML is so incredibly slow, if transparency is not really needed and a lot of things has to be done without direct interactions with the game, lua should be used instead of WML, either like newly created WML tags or using the [lua] tag directly in an event.

Conclusion: lua can be hundreds of times faster than WML.

[Pentarctagon]

To clarify, was the Lua and WML run by Wesnoth or just the WML part of the test?

[Dugi]

The Lua was run by Wesnoth (so it was also performed by a single core).

[Iris]

I was trying to compare the speed of WML and lua. For this purpose, I have created a short code with highly repetitive calculations to create something that would take a measurable amount of time, and would be easy to transfer between lua and WML.

[...]

Conclusion: lua can be hundreds of times faster than WML.

Where’s the actual WML and Lua code you used to reach this conclusion? What was the measurement strategy? Was this done in a clean environment where Wesnoth could run on a single processor without scheduling and/or migration overhead? Etc.

Also, I’m moving this to Coders’ Corner.

[Sapient]

Conclusion: lua can be hundreds of times faster than WML.

This statement is a bit misleading as a form of guidance for WML authors. Just because you rewrite your WML code in Lua does not mean it is likely to run 100 times faster.

Clearly there are some areas where Lua excels over WML for speed. But those types of situations that require Lua to overcome speed bottlenecks are exceptional and rare. Custom AIs are one good example. For most authors, however, it is highly unlikely that the real bottleneck will be with performing large numbers of scalar variable operations and retrievals, as you show here.

[Dugi]

Where’s the actual WML and Lua code you used to reach this conclusion? What was the measurement strategy? Was this done in a clean environment where Wesnoth could run on a single processor without scheduling and/or migration overhead? Etc.

I have not kept the exact codes in WML and lua I used, but the lua code was almost the same as the C code, only with altered syntax and the WML code was almost using set_variable and while in the expectable way, nothing complex. It was probably done in a clean environment, I was not running any program besides it and when it was running, all other system processes were moved to other cores, so all tested processes (wesnoth and also the C program) used 100% CPU of a single core (I verified it in system monitor).

This statement is a bit misleading as a form of guidance for WML authors. Just because you rewrite your WML code in Lua does not mean it is likely to run 100 times faster.

In fact yes, it can be misleading, I certainly would never replace some simple and short WML codes by lua equivalents (dialogues, simple variable stuff, creating some units, and other things when lua basically does things in the same way as WML), but if something more complex is being done (such as any RPG-related code, just a lot variable-related stuff), using lua should be reconsidered, because in that case it will be 100-times faster. I said it can be much faster, I did not say it is always faster.
Should I edit it?

[Iris]

Running WML inevitably goes through the Lua engine nowadays:

Long list:

[message] [show_if] wrapper, [chat], [gold], [store_cold], [clear_variable], [store_unit_type], [store_unit_type_ids], [fire_event], [allow_recruit], [allow_extra_recruit], [disallow_recruit], [disallow_extra_recruit], [set_recruit], [set_extra_recruit], [store_map_dimensions], [unit_worth], [wml_action], [lua], [music], [switch], [scroll_to], [scroll_to_unit], [lock_view], [unlock_view], [select_unit], [unit_overlay], [remote_unit_overlay], [store_turns], [store_turn], [sound], [store_locations], [store_reachable_locations], [hide_unit], [unhide_unit], [move_unit], [capture_village], [terrain], [delay], [floating_text], [petrify], [unpetrify], [harm_unit], [transform_unit], [store_side], [add_ai_behavior], [find_path], [store_strating_location], [store_villages], [objectives], [show_objectives], [item], [remove_item], [store_items] (as of trunk r56301)

The complexity of every WML action varies regardless of whether it is implemented directly in C++ or Lua, and every hard-coded custom Lua function in the wesnoth table is a call back to the C++ engine with very little overhead. I’d say it really depends on the exact implementation of a particular algorithm whether it will give better results when run directly in Lua or in WML. For most cases, it shouldn’t matter enough to strongly advocate for either approach solely on grounds of computing performance — Wesnoth doesn’t strike me as an application where you would do a lot of number crunching anyway.

Inefficiencies in the storing and unstoring of units or locations can be attributed to badly designed filters (on the part of the UMC coder) or issues with whatever algorithm is enclosed by the loop that walks through the stored objects — that is, whenever you are actually working with an array of them rather than an individual item. It has been brought up before that using [filter_wml] as a fallback for filtering attributes that are not regularly supported by SUFs other than those that may be in the unit’s [variables] container tends to be detrimental to the filter’s performance due to the need to convert additional candidate units to WML before being actually sure they actually match the filter.

Another thing is that WML, as opposed to popular belief, is not parsed on the fly; it is all already parsed and processed in memory. Additional overhead during the execution of an event handler can also be attributed to abuse of variable interpolation or dynamic WML insertion via [insert_tag].

In general, as with most programming languages (even C++!), it really depends on exactly what you are trying to achieve and how you are doing it.

Also, you haven’t yet explained what the measurement strategy you used was. Did you use something like this?

Code: Select all

{VARIABLE_OP start_ts time stamp}

# Lots of Lua or WML code

{VARIABLE_OP end_ts time stamp}

{ERROR ("took $(($end_ts - $start_ts) / 1000) seconds")}

Incidentally, inline formulas are another convenient alternative to a series of verbose and indeed potentially taxing WML [set_variable] operations.

[Dugi]

In the measurement, I have used formulae to accelerate the execution of the WML code if it was possible. Macros seem to hate them, however, so formulas in macros have to wrapped in quotation marks.
There were no frequent ineffectivenesses in my code, and still it was surprisingly slow. Like if one incrementation cycle, with one simple arithmetic operation and one variable check needed more than a thousand binary operations of CPU, that surprised me. I am not trying to tell that WML is awkward, just that sometimes it might not be the best thing to use.

My measurement method was simple - I just set the number of cycles to set the execution time to several dozens of seconds and then I measured it manually, making it display something at the start and end of the execution - I did not aim for high precision, just to get an idea about the speed.

I am not telling that I am putting forward either approach only the performance. I have written by whole campaign in WML. Partially because I have learned to use lua only recently, but I don't plan to convert it because nobody would learn a thing from it then; but I have learned that writing in lua has its advantages, it is loaded from the add-on's files when a save file is loaded, so debugging is incredibly faster, and the same code in WML is much longer than the code in lua. But lua has to be loaded with WML anyway, and the compatibility between lua variables and WML variables is a pain. I am somewhat missing WML macros and [insert_tag] in lua, its local functions are far from being a perfect replacement.

Your comment about ineffective usage of WML is perfectly correct, but somewhat incomplete, I would like to add that using radii in location filters is also really slow, and that filter_wml looking for statuses is not slow, just like with variables. But filters are the same in lua and WML.

I never told that WML is parsed on the fly - macros are inserted from defintions, definitions are checked before, a few attributes are ordered, and this pure WML code is saved into memory - all scenarios, all units, everything (however, I have a suspicion that something is removed if the memory gets filled by this, but how are the things done then, I don't know), it does not need much experimentation to learn this. Variables are structured just like the pure WML in save files, so insert_tag has no problem with this kind of code.

[Iris]

I never told that WML is parsed on the fly - macros are inserted from defintions, definitions are checked before, a few attributes are ordered, and this pure WML code is saved into memory - all scenarios, all units, everything (however, I have a suspicion that something is removed if the memory gets filled by this, but how are the things done then, I don't know) [...]

I am not sure what this particular statement (the part I quoted in bold) is intended to mean.

Wesnoth config objects (the internal representation of a WML node) allocate all the memory they require using the platform’s default C++ memory allocator. Unless you are compiling Wesnoth on some weird embedded contraption, this means that this memory is allocated from the heap, and current operating systems are very permissive about the matter — swapping memory pages out to disk if necessary.

There are more concrete limits for many of the standard containers Wesnoth uses for various things, but they are usually too high (as in (size_t)-1 high) to matter to any reasonable UMC coder; you would be more likely to hit your system’s combined virtual memory limit first, and even that is extremely unlikely unless you are abusing WML or Lua on purpose or stumbled upon some resource leak bug.

[Dugi]

I am not sure what this particular statement (the part I quoted in bold) is intended to mean.

I meant that when I disabled a few optimalisations I used in my campaign, it ate more than 2 gigabytes of virtual memory (a ton of macros that was added to each of 90 scenarios; I am usually using a trick to load these events into scenarios with a dummy unit, so that it is added on preload and it is not a part of the scenarios), and then the amount of virtual memory it was taking dropped. It could have been saved to the disk by the operating system as you mentioned, but I was not sure with that because this effect is usually accompanied by extreme slowdowns of everything and it was far from having consumed all virtual memory. But I have not read the source files, so you will probably know better.

[Iris]

I meant that when I disabled a few optimalisations I used in my campaign, it ate more than 2 gigabytes of virtual memory (a ton of macros that was added to each of 90 scenarios; I am usually using a trick to load these events into scenarios with a dummy unit, so that it is added on preload and it is not a part of the scenarios), and then the amount of virtual memory it was taking dropped. It could have been saved to the disk by the operating system as you mentioned, but I was not sure with that because this effect is usually accompanied by extreme slowdowns of everything and it was far from having consumed all virtual memory. But I have not read the source files, so you will probably know better.

I don’t know what operating system you normally use, but a process’ virtual memory usage on e.g. Linux does not necessarily reflect its real combined RAM and swap usage accurately because of shared memory, shared libraries, copy-on-write handling of memory pages for forked processes sharing their process image, etc. If you are using a top-like utility, you should pay attention to the resident set size (RSS) instead.

Going back on topic:

From what you describe it sounds like you are comparing including a really large amount of duplicate WML in a really large amount of scenarios versus just including it at runtime for every single game status snapshot via the [unit]/[unit_type] [event] trick. Somehow I am not surprised by inefficiencies in the former use case, considering that the game must keep a whole WML document in memory consisting of the entirety of the preprocessed tree (including all [scenario] nodes and its descendants, amongst other stuff, e.g. [units]) at various points.

And I really don’t think anyone even considered that someone would make a WML-heavy campaign with 90 scenarios at any point.

[Coffee]

...each of 90 scenarios...

Well there's your problem

From the title of the thread I was hoping for some objective speed test suite of WML vs LUA for common usage cases for UMC. This looks to be mainy about your specific campaign.

Have you thought about actually combining all 90 scenarios into 1,2, or maybe 10 and using replace_map/replace_scedule/replace_turns/etc. This would be much more efficient for your campaign and something I thought of doing for mine when I encountered the vast miriad of wesnoth multiplayer campaign bugs (I only didn't do it because there was no turns_replace feature at the time). I figure now that the bugs are slowly being tackled though by people who want to see them fixed for their own usages.

For the general speed comparison I would have thought WML would be faster for most (commonly applied) things, as it ties into C++ code directly and is very easy to test. I just set a command-line entry or script to start a scenario of choice and quit wesnoth, update a file, run again and it is easy to test. Until LUA has more feature compatibility or is tied in better I personally don't see the usage being faster to debug or write. Even in the often cited case of AI I don't want to use LUA because I can't tack on advanced AI features to any side because it must be hard-coded to a particular faction before a game starts and (ironically) not dynamically added like WML. For math speed I assume it would be faster, but you can't yet (AFAIK) set random variables. A bit of maturity and it will be useful and a proper speed comparison suite, etc. might help adoption from UMC authors like myself.

[Dugi]

@shadowmaster
I am using Linux, but I don't know how the memory is swapped, so I was far from sure if it was removed from cache or something else was done. I wrote right at the start that I only have a suspicion about it, nothing more.

I learned that WML heavy campaigns with 90 scenarios were not expected, so I had it invent that trick with events loaded through unit_type, and macro arguments were replaced by variables. I have removed the optimalisation trick once to see what happens if cached WML was about to fill the virtual memory.

@coffee
It was not me who drove the discussion to my campaign, I merely explained the method how I tried to fill the RAM memory with cached WML.
Replace map, replace schedule, replace turns and other tricks would have helped maybe only a bit, most of the scenarios were unique and directing all the events with variables would make it painfully slow (there would be like 200 moveto events, and that would slow down every movement, for example). Another problem with this method were changing scenario names, without it you would have no save files.

And you're right, in lua you cannot set random variables (without OoS errors and other problems), you have to use WML for it. But you can for example use WML to generate a random seed at the start of the lua code and base all random values on modulo functions calculated from the initial random seed.

[Pentarctagon]

Seeing as tests for things that would be more generally useful than massive amounts of calculations (which even then seem to be controversial) don't exist, are there general rules of thumb as to when Lua would be faster than WML and vice versa?

[8680]

And you're right, in lua you cannot set random variables (without OoS errors and other problems), [...]

One can use helper.rand and (I think) math.random in singleplayer, where OoS-ness is irrelevant, and they can (I think) be synchronized with wesnoth.synchronize_choice in multiplayer.

[...] are there general rules of thumb as to when Lua would be faster than WML and vice versa?

The only ActionWML tag that I know isn’t implemented in Lua is [event]; calling the functions directly from Lua would I think almost always be faster, but not by much for common tasks. A better question would I think be “when is it worth using Lua?” — for someone like me who prefers Lua, the answer is “always”, but for someone who prefers ActionWML, or already has a significant ActionWML codebase, the answer would depend on the complexity of the add-on.