• 🏆 Texturing Contest #33 is OPEN! Contestants must re-texture a SD unit model found in-game (Warcraft 3 Classic), recreating the unit into a peaceful NPC version. 🔗Click here to enter!
  • It's time for the first HD Modeling Contest of 2024. Join the theme discussion for Hive's HD Modeling Contest #6! Click here to post your idea!

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

Status
Not open for further replies.
Level 19
Joined
Jan 3, 2022
Messages
320
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.
JASS:
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
Lua:
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:
That's from an older code version when generated strings were created in order.
Bash:
user$ strings -2 WarcraftIII.dmp | grep -F '|r|r' > outputfile.txt
Code:
 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):
Code:
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)

time per 50k.png

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 stringsTime in seconds to gen 50000Inserts/second
00.300166666
500000.467107142
4500001.13344117
10000002.13323437
34500009.1335474

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.
 

Attachments

  • lua_idiomatic - string test.w3m
    14.5 KB · Views: 9
  • jass - string test.w3m
    15.2 KB · Views: 9
  • Jass String Performance Analysis.xls
    40.5 KB · Views: 10

Cokemonkey11

Spell Reviewer
Level 29
Joined
May 9, 2006
Messages
3,534
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
 
Level 19
Joined
Jan 3, 2022
Messages
320
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

Spell Reviewer
Level 29
Joined
May 9, 2006
Messages
3,534
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
 
Level 19
Joined
Jan 3, 2022
Messages
320
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).
 
Last edited:
Status
Not open for further replies.
Top