[JASS] Performance analysis of 'leaking' Jass strings & Lua

[Luashine]

Common knowledge has it Jass strings leak!!!1 and are bad!!!1 Let's benchmark by generating A TON of strings.

Test code & setup​

The code below takes your chat message, like "-10" and generates ONE 10-char long string (1=10/10). That's equivalent to generating 10 distinct unique strings in Jass, because we concatenate letters one by one: e.g. "a" + "b" + "c" + "d" + "e" + "f" + "g" +"h" + "i" + "j" -> "a", "ab", "abc"... and so on.
I measured the time by recording at 30 FPS and counting frames between my chat message and when it has updated the multiboard.

Spoiler: Jass and Lua code

function Trig_ChatJass_Actions takes nothing returns nothing
    // Get number from input "-12345"
    local integer num= 0
    local integer i= 0
    local integer j= 0
    local string str
    local integer c= 0
    // Len 62
    local string alphabet= "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyz"
    // Code
    set udg_inputNumber=S2I(SubStringBJ(GetEventPlayerChatString(), 2, 8))
    call DisplayTextToForce(GetPlayersAll(), ( "Generating strings..." + ( I2S(udg_UniqueStringsCreated) + " +amount" ) ))
    set num=udg_inputNumber + 1
    loop
        // only create this many final full-length strings
        exitwhen i >= ( num / 10 )
        set i=i + 1
        set j=0
        // all strings begin with this, a search marker to analyse memory dumps
        set str="|r|r"
        loop
            // get random letter
            set c=GetRandomInt(0, 61)
            // add to string
            set str=str + SubString(alphabet, c, c + 1)
            set j=j + 1
            // count how many unique Jass strings we've created
            set udg_UniqueStringsCreated=1 + udg_UniqueStringsCreated
            exitwhen j == 10
        endloop
        set udg_LastStringCreated=str
    endloop
    call DisplayTextToForce(GetPlayersAll(), ( "Generated strings..." + I2S(udg_UniqueStringsCreated) ))
    call TriggerExecute(gg_trg_MultiboardUpdate)
endfunction

function Trig_ChatLua_Actions()
    local num = 0
    local i = 0
    local j = 0
    local concatTbl
    local c = 0
    local alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyz"
    udg_inputNumber = tonumber(GetEventPlayerChatString():sub(2))
    DisplayTextToForce(GetPlayersAll(), string.format("Generating strings... %d +amount", udg_UniqueStringsCreated))
    DisplayTextToForce(GetPlayersAll(), string.format("Input: %s -- tonumber --> %d", GetEventPlayerChatString():sub(2), udg_inputNumber ))
    num = udg_inputNumber + 1
    while true do
        if i >= math.floor(num/10) then break end
        i = i + 1
        j = 0
        concatTbl = {"|r|r"}
        while true do
            c = GetRandomInt(1,62)
            local letter = alphabet:sub(c, c)
            concatTbl[#concatTbl + 1] = letter
            j = j + 1
            udg_UniqueStringsCreated = 1 + udg_UniqueStringsCreated
            if j == 10 then break end
        end
        udg_LastStringCreated = table.concat(concatTbl)
    end
    DisplayTextToForce(GetPlayersAll(), string.format("Generated strings... %d", udg_UniqueStringsCreated))
    TriggerExecute(gg_trg_MultiboardUpdate)
end

Looking at the memory dump​

Out of 10 generated strings we only make use of ONE, because it gets saved to a global variable and displayed in the multiboard. In reality Warcraft 3's Jass VM holds each created string in memory twice!
If we run the "-10" command 3 times (or "-30") then this is what we can find in game's memory dump:

Spoiler: Memory dump contents

That's from an older code version when generated strings were created in order.

user$ strings -2 WarcraftIII.dmp | grep -F '|r|r' > outputfile.txt

 1689f3 |r|rUVWXYZ0123
35d0bd3 |r|r
35d0bf3 |r|rA
35d0c13 |r|rA
35d0c33 |r|rAB
35d0c53 |r|rAB
35d0c93 |r|rABC
35d0cb3 |r|rABC
35d1823 |r|rABCD
35d1843 |r|rABCD
35d18a3 |r|rABCDE
35d18c3 |r|rABCDE
35d1903 |r|rABCDEF
35d1923 |r|rABCDEF
35d1963 |r|rABCDEFG
35d1983 |r|rABCDEFG
35d19e3 |r|rABCDEFGH
35d1a03 |r|rABCDEFGH
35d1a43 |r|rABCDEFGHI
35d1a63 |r|rABCDEFGHI
35d1aa3 |r|rABCDEFGHIJ
35d1ac3 |r|rABCDEFGHIJ
35d1b03 |r|rK
35d1b23 |r|rK
35d1b63 |r|rKL
35d1b83 |r|rKL
35d1be3 |r|rKLM
35d1c03 |r|rKLM
35d1c43 |r|rKLMN
35d1c63 |r|rKLMN
35d1ca3 |r|rKLMNO
35d1cc3 |r|rKLMNO
35d1d23 |r|rKLMNOP
35d1d43 |r|rKLMNOP
35d1da3 |r|rKLMNOPQ
35d1dc3 |r|rKLMNOPQ
35d1e23 |r|rKLMNOPQR
35d1e43 |r|rKLMNOPQR
35d1ea3 |r|rKLMNOPQRS
35d1ec3 |r|rKLMNOPQRS
35d1f23 |r|rKLMNOPQRST
35d1f43 |r|rKLMNOPQRST
35d1fa3 |r|rU
35d1fc3 |r|rU
35d2023 |r|rUV
35d2043 |r|rUV
35d2083 |r|rUVW
35d20a3 |r|rUVW
35d2103 |r|rUVWX
35d2123 |r|rUVWX
35d2163 |r|rUVWXY
35d2183 |r|rUVWXY
35d21c3 |r|rUVWXYZ
35d21e3 |r|rUVWXYZ
35d2203 |r|rUVWXYZ0
35d2223 |r|rUVWXYZ0
35d2243 |r|rUVWXYZ01
35d2263 |r|rUVWXYZ01
35d2283 |r|rUVWXYZ012
35d22a3 |r|rUVWXYZ012
35d22c3 |r|rUVWXYZ0123
35d22e3 |r|rUVWXYZ0123
// a line of Jass code:
1d797518         set str="|r|r"
24a26bf3 |r|rUVWXYZ0123
// Probably from Jass interpreter
252ddfa3 |r|r
// a line of Jass code:
26e847f8         set str="|r|r"
29a4e303 |r|rUVWXYZ0123

Each iteration of ABCD... & KLMN... are permanently held in memory twice. The UVWX... string appears in the dump 5 times: 2 from iteration, 1 from global variable, and the last 2 are a mystery to me.

Jass strings performance​

Due to Jass' op limit, "-50000" was the last command that executed in full. "-75000" was aborted amidst execution and the "UniqueStringsCreated" variable wasn't increased by 75k but a smaller odd number. So I've been running "-50000" command until I reached 3.5 Million total generated.

People here have talked about "the existence of a string hash table" that's used to store all created strings for deduplication. Here's what the game has to do when you create/modify a string (pseudocode):

func StringLookup(NEWSTR)
   for each OLDSTR in StringTable do:
      if OLDSTR == NEWSTR then
         return &OLDSTR
      endif
   endloop
   return StringTable.append(NEWSTR).getPointer()
endfunc

Whatever the case, this operation is costly because it takes time to iterate this "hash table".
Reusing strings from a variable has zero cost, because it's retrieved instantly via stored pointer: O(1) DisplayText(previous_msg)

If we create the first 50k strings, they're done in just 300ms or with a speed of 166k/s (2.7k strings in 16.6ms). Creating 50k strings with 3.45M already stored takes 9.1 seconds at 5.4k/s (91 strings in 16.6ms), yes that freezes the game for 9s.

Memorize 1: Creating or manipulating strings becomes gradually slower over time, because Jass never removes old strings from memory.
1.1: The look-up is practically linear in complexity O(n). It does not behave like a real hash table that would have a O(1) look-up phase before overfilling (although I've only tested string counts >=50k)
Memorize 2: Working with old strings has absolutely no impact on the FPS (e.g. stored in a variable). The renderer is not affected at all.

Existing strings	Time in seconds to gen 50000	Inserts/second
0	0.300	166666
50000	0.467	107142
450000	1.133	44117
1000000	2.133	23437
3450000	9.133	5474

When is it a problem?​

Performance: If you create hundreds of strings per second. Remember, you must count all intermediate substrings. So if you create colored numbers for multiboards: "|cff1234ddGold: 12345|r" - this will lookup/create 3-4 different strings and store double that in memory, depending on how you coded it.

Workaround: Reduce string manipulation/updates. Remove color codes. For floating text/multiboards use functions that set the entire line's color instead of adding color codes. E.g.

• Multiboard - Set Item Color

Memory: Practically never a problem. Now that Warcraft3.exe is 64-bit, leaking 100-200MB of strings during a game session shouldn't noticably affect the players.

Workaround: None, you can only avoid Jass by running Lua natively.

Lua maps​

I rewrote the trigger code to idiomatic Lua (except for while true) and tested it again.
Generating 0 -> 3.45M strings: 2.8 seconds or 1.23M/s
Generating 3.45M -> 3.5M strings: 0.1s or ~0.5M/s

Lua generated the first 3.45 Million strings in one go (impossible in Jass) about as fast as Jass needed for 1M->1.05M strings. The final 50k were fast, it's not worth discussing. Because Lua was so fast, I didn't bother capturing the other times.

Lua hype?​

Should you convert your map to Lua? No. Judging by above numbers, strings are the least likely cause for performance problems. Other than that, Lua's interpreter is still light years ahead of Jass in terms of speed. To be continued.

PS: Sorry if it's the wrong subforum, I don't know where it fits best.

 

[Cokemonkey11]

It is not really fair to say that string leaks - they interned with no cache invalidation behavior

Technically this is a leak. But it is much more effective and relevant to reason about handle leaks if you care about performance in your map

Edit: the first thing is a leak wc3 engine, and the second thing is a leak in the user code. Leaks in user code are vastly more expensive

 

[Luashine]

Since no intermediate strings are ever used outside of concatenation, I think it is very much correct to call it a leak. I wouldn't differentiate between "which side leaked". User code provokes certain engine behavior: a leak is a leak.

But it is much more effective and relevant to reason about handle leaks if you care about performance in your map

Yep that's the conclusion so far. Effectively strings behave just like handle leaks, with only one difference: handles are iterated each game tick, so they always cause performance problems. Strings will not slow down the game if not touched.

 

[Cokemonkey11]

Since no intermediate strings are ever used outside of concatenation, I think it is very much correct to call it a leak.

As I said:

Technically this is a leak.

But at best you are being pedantic and worst, misleading. Read through some random page of Things That Leak to get an idea of the level of understanding normal users have of leaks.

For all intents and purposes, the word leak in wc3 community refers to known and serious performance footgun. Talking about exceptions to the rule is just going to cause confusion.

It may be better to move this thread to Advanced Scripting

 

[Luashine]

But at best you are being pedantic and worst, misleading. Read through some random page of Things That Leak to get an idea of the level of understanding normal users have of leaks.

LOL so that's the problem you have with my post?

First, in quotes: Performance analysis of 'leaking' Jass strings & Lua
Second, sarcasm: Common knowledge has it Jass strings leak!!!1 and are bad!!!1
Third, unambiguous: Memory: Practically never a problem. Now that Warcraft3.exe is 64-bit, leaking 100-200MB of strings during a game session

Here's the community understanding:
"like string leaks" - Basic Memory Leaks
"[possible leak] strings used in functions" - [JASS] - [possible leak] strings used in functions
"The reason it is suggested to process chat messages 1 character at a time is that infrequently occurring unique strings can be considered a leak." - [General] - String contains
"It is important that you minimize the maximum string leak from chat commands" - Using a string to set a variable. / [Solved] - Map Leaking, can't find issue.

If you want to argue any further on semantics, continue in this dedicated thread: What and How do Strings Leak?

the word leak in wc3 community refers to known and serious performance footgun.

I've made it very clear in my last reply why usual handles always cause trouble and strings don't. Further, due to the linear search through the interned (thanks) string array, it is very easy to construct a plausible case where plain strings will cause performance problems (e.g. high speed crit towers with a high damage variance).

 

[Cokemonkey11]

You are right that there is a rare degenerative case

In any case i don't like your attitude, so goodbye

 

[DarkePacific]

I know I'm a bit late to this discussion but thank you for posting this in-depth benchmark. I have been using quite a bit of string concatenation in my map in particular when I had a custom Debugger set to on. It's nice to know that I don't need to worry about it causing significant performance issues.
Thanks.

 

[ThompZon]

Sweet, I've heard about internal strings and so on, but this means that I have have dynamic tooltips displaying actual damage values with break-down on each scaling component. It'll probably only generate a 10k-50k strings per play-session (over 1½ hours) and be no problem.