System SimCache (Game Cache without cache's)

[TriggerHappy]

SimCache
TriggerHappy187​

Introduction

I never really expected anything out of this, I was just messing around trying to simulate game cache.

Turns out S2ID returns low enough integers that can be stored by struct indexes.

And by combining the missionKey, a divider and the key into S2ID(missionKey + "$|#%&" + key)

it produces a unique value (seemingly, unless someone can prove this wrong)

Thats all there really is to it, i'm waiting for someone to prove this wrong as I am still in disbelief that I simulated game cache by adding two values.

Here is an example usage..

Spoiler

scope SimCacheTest initializer InitTrig

    function Actions takes nothing returns nothing
        local integer i
        call CacheInteger("test", "ing", 10)
        call CacheInteger("a", "", 15)
        set i = RestoreInteger("a", "") + RestoreInteger("test", "ing")
        call BJDebugMsg(I2S(i)) // this will display 25.
    endfunction

    //===========================================================================
    function InitTrig takes nothing returns nothing
        local trigger t = CreateTrigger()
        call TriggerRegisterTimerEventSingle( t, 0.00 )
        call TriggerAddAction( t, function Actions )
    endfunction

endscope

The Code

//***************************************************************************
//*
//*  SimCache - By TriggerHappy187
//*
//***************************************************************************
//*
//*  Installation
//*     All you need to do is copy this script into your map and you can use
//*     the provided functions.
//*
//***************************************************************************
//*
//*  Requirements
//*     This requires no external systems, all it requires is JassHelper.
//*
//***************************************************************************
//*
//*  Limitations
//*    if your strings id is greater than 16380, then this will bug.
//*
//***************************************************************************

library SimCache
    
    private function S2ID takes string s returns integer
        return s
        return 0
    endfunction
   
    //! textmacro SimCache takes TYPE,HANDLE,DEF
    
    globals
        private $HANDLE$ array $HANDLE$_val
        private $HANDLE$ array $HANDLE$_val_safe
    endglobals
    
    function Cache$TYPE$ takes string missionKey, string key, $HANDLE$ value returns nothing
        local integer i = S2ID(missionKey + "$|#%&" + key)
        if i < 8191 then
            set $HANDLE$_val<i> = value
        else
            set $HANDLE$_val_safe[i-8190] = value
        endif
    endfunction
    
    function Restore$TYPE$ takes string missionKey, string key returns $HANDLE$ 
        local integer i = S2ID(missionKey + &quot;$|#%&amp;&quot; + key)
        if i &gt; 8190 then
            return $HANDLE$_val_safe[i-8190]
        endif
        return $HANDLE$_val<i>
    endfunction
    
    function Flush$TYPE$ takes string missionKey, string key returns nothing
        local $HANDLE$ def = $DEF$
        set $HANDLE$_val[S2ID(missionKey + &quot;$|#%&amp;&quot; + key)] = def
    endfunction
    
    //! endtextmacro
    
    //! runtextmacro SimCache(&quot;Integer&quot;,&quot;integer&quot;,&quot;0&quot;)
    //! runtextmacro SimCache(&quot;Real&quot;,&quot;real&quot;,&quot;0.&quot;)
    //! runtextmacro SimCache(&quot;Boolean&quot;,&quot;boolean&quot;,&quot;false&quot;)
    //! runtextmacro SimCache(&quot;String&quot;,&quot;string&quot;,&quot;null&quot;)
endlibrary</i></i>

 

[bOb666777]

And what strings does Restore/Cache$TYPE$ take? At least 1 different string for each stored data, hm?
Would it work with H2I?

Edit: err, yeah, oops, theres no function for handles, although i guess it could just work with storing a H2I integer? or adding a store handle textmacro..... idk

But then, whats the point of storing a h2i integer with a S2ID ahhhh

Perhaps more explanations >.<?

 

[TriggerHappy]

I don't see how you would do this with H2I.

The functions take the same arguments as GameCache, except you don't have to provide a game cache.

So no flushing and initializing.

Though this limits you to 8190 values able to be stored.

EDIT:

whats the point of storing a h2i integer with a S2ID

Your not storing an h2i integer..

Have you ever used game cache before?

Also, this system doesn't even contain h2i, S2ID returns a hopefully unique value for the missionKey, and the key.

That value is set as a structs index, with the value you want stored inside of that struct.

EDIT2:

Obviously adding two numbers doesn't produce a unique number (silly me ), but i've updated the script, and hopefully it should be fine now.

 

[Jesus4Lyf]

If you put this into a map that does any sort of character by character string iteration of player messages, you know you'd be pretty stuffed, right? :thup:

But yeah, you're reinventing the wheel. The problem is you can't -flush-. You can actually get dirty reads like this. For example, a struct is destroyed and recreated with the same id. You go to get an attached integer because you need to set it if it hasn't been set. Oops! It returns some old value.

However, I did in fact make what I think is a perfect gamecache simulation on this technique, however it ends up being the same speed as gamecache (?). Gamecache isn't actually slow, it seems.

This includes hashing and flushing, and hence needs 2d linked-lists.

Spoiler

library Table
//***************************************************************
//***    Jesus4Lyf's    **    TABLE-X   **    Version 1.01    ***
//***************************************************************
//* Table object
//* ------------
//*
//*   set t=Table.create() - instanceates a new table object
//*   call t.destroy()     - destroys it
//*   t[1234567]           - Get value for key 1234567
//*                          (zero if not assigned previously)
//*   set t[12341]=32      - Assigning it.
//*   call t.flush(12341)  - Flushes the stored value, so it
//*                          doesn't use any more memory
//*   t.exists(32)         - Was key 32 assigned? Notice
//*                          that flush() unassigns values.
//*   call t.reset()       - Flushes the whole contents of the
//*                          Table.
//*
//*   call t.destroy()     - Does reset() and also recycles the id.
//*
//*   If you use HandleTable instead of Table, it is the same
//* but it uses handles as keys, the same with StringTable.
//*
//***************************************************************
//* This version of Table does not use GameCache.
//* Please note that all data attaching is messed up if you load
//*  a saved game. Use normal Table if you need to load games.

    ///////////////
    // Constants //
//===============================================================
    globals
        private constant integer MAX_INSTANCES=8100 //400000
        private constant integer MAX_ATTACHMENTS=16200 //400000
        // MAX_ATTACHMENTS is the maximum number of things being
        // attached to in total + the number of tables in
        // existance + 1, at any one time.

    ///////////////////////////
    // System Implementation //
//===============================================================
        private constant integer MAX_STRINGID=MAX_ATTACHMENTS-1
        private integer RandomData=MAX_ATTACHMENTS
    endglobals
    
    private keyword GTable
    
    //////////////////////////////////////////////////////
    // 2D DOUBLY LINKED-LIST HASHING TABLE SYNTAX CANDY //
    /////////////////////////////////////////////////////////////
    // Sounds fun? Think again. Use (for my own reference):
    // d.delete()
    // d.chainDelete()
    // Data.getPointer() --> Data
    // Data.getForRead(stringid) --> Data or 0
    // Data.getForWrite(trackingPointer, stringid) --> Data
    private struct Data[MAX_ATTACHMENTS] // Not really a struct, just syntax candy.
        integer stringid
        integer value
        Data prev
        Data next
        Data drill // down
        Data roll // counter-down (for unlinking)
        /////////////
        // GENERAL //
        /////////////////////////////////////////////////////////
        private method wipe takes nothing returns nothing
            set this.stringid=0
            set this.value=0
            set this.prev=0
            set this.next=0
            set this.drill=0
            set this.roll=0
        endmethod
        private method move takes Data targ returns Data
            // Copy
            set targ.stringid=this.stringid
            set targ.value=this.value
            set targ.prev=this.prev
            set targ.next=this.next
            set targ.drill=this.drill
            set targ.roll=this.roll
            // Fix pointers
            set this.next.prev=targ
            set this.prev.next=targ
            set this.drill.roll=targ
            set this.roll.drill=targ
            // Clean up
            call this.wipe()
            // Done
            return targ // Probably unneeded.
        endmethod
        private method init takes Data prev, integer stringid returns nothing
            set this.stringid=stringid
            set prev.next.prev=this
            set this.next=prev.next
            set prev.next=this
            set this.prev=prev
        endmethod
        private static method getRandom takes nothing returns Data
            local integer oldrandom=RandomData
            set RandomData=RandomData-1
            loop
                if RandomData<1 then
                    set RandomData=MAX_ATTACHMENTS-1
                endif
                exitwhen Data(RandomData).stringid==0
                if RandomData==oldrandom then
                    call BJDebugMsg("Table-X out of space. Increase MAX_ATTACHMENTS constant.")
                endif
                set RandomData=RandomData-1
            endloop
            return RandomData
        endmethod
        method delete takes nothing returns nothing
            set this.next.prev=this.prev
            set this.prev.next=this.next
            set this.drill.roll=this.roll
            set this.roll.drill=this.drill
            if this.roll==0 and this.drill!=0 then
                call this.drill.move(this)
            else
                call this.wipe()
            endif
        endmethod
        method chainDelete takes nothing returns nothing
            if this==0 then
                return
            endif
            call this.next.chainDelete()
            if this.roll==0 and this.drill!=0 then
                call this.drill.move(this)
            else
                call this.wipe()
            endif
        endmethod
        static method getPointer takes nothing returns Data
            local Data d=Data.getRandom()
            set d.stringid=-1
            return d
        endmethod
        
        //////////////////////////
        // STACKING ABSTRACTION //
        /////////////////////////////////////////////////////////
        private method stack takes Data nextDown returns Data
            set this.drill.roll=nextDown
            set nextDown.drill=this.drill
            set this.drill=nextDown
            set nextDown.roll=this
            return nextDown
        endmethod
        private static method get takes integer stringid returns Data
            local Data d=stringid-(stringid/MAX_STRINGID)*MAX_STRINGID+1
            loop
                if d.stringid==stringid then
                    return d // d.stringid=stringid
                endif
                exitwhen d.drill==0
                set d=d.drill
            endloop
            return d // may be empty or not, but is not the stringid's data, so stack or init here.
        endmethod
        static method getForRead takes integer stringid returns Data
            local Data d=Data.get(stringid)
            if d.stringid==stringid then
                return d
            endif
            return 0 // d.stringid is 0 or a different string id
        endmethod
        static method getForWrite takes Data flushList, integer stringid returns Data
            local Data d=Data.get(stringid)
            if d.stringid==stringid then
                return d
            endif
            if d.stringid!=0 then
                set d=d.stack(Data.getRandom()) // Get one stacked onto returned one.
                // d has become the result of getRandom here.
            endif
            call d.init(flushList,stringid)
            return d
        endmethod
    endstruct
    
    private function StringID takes string s returns integer
        return s
        return 0
    endfunction
    private function H2I takes handle h returns integer
        return h
        return 0
    endfunction
    
    private struct GTable[MAX_INSTANCES]
        // A "protected" keyword would've been really nice here.
        // Don't play with "trackingPointer" or "base" in your map.
        // Looking for ideas on how to protect them, still.
        Data trackingPointer
        string base
        
        method reset takes nothing returns nothing
            call this.trackingPointer.chainDelete()
            set this.trackingPointer=Data.getPointer()
            //call FlushStoredMission(gc,I2S(this))
        endmethod
        
        private method onDestroy takes nothing returns nothing
            call this.trackingPointer.chainDelete()
            //call FlushStoredMission(gc,I2S(this))
        endmethod
    endstruct
    
    //Hey: Don't instanciate other people's textmacros that you are not supposed to, thanks.
    //! textmacro Table__make takes name, type, key
    struct $name$ extends GTable
        static method create takes nothing returns $name$
            local $name$ d=$name$.allocate()
            set d.trackingPointer=Data.getPointer()
            set d.base=I2S(d)+"x"
            return d
        endmethod
        
        method operator [] takes $type$ key returns integer
            //set Data(0).value=0 // Value at 0 is 0 by default anyway.
            return Data.getForRead(StringID(this.base+$key$)).value
        endmethod
        
        method operator []= takes $type$ key, integer value returns nothing
            set Data.getForWrite(this.trackingPointer,StringID(this.base+$key$)).value=value
        endmethod
        
        method flush takes $type$ key returns nothing
            local Data d=Data.getForRead(StringID(this.base+$key$))
            if d!=0 then
                call d.delete()
            endif
        endmethod
        
        method exists takes $type$ key returns boolean
            return Data.getForRead(StringID(this.base+$key$))!=0
        endmethod
    endstruct
    //! endtextmacro
    
    //! runtextmacro Table__make("Table","integer","I2S(key)")
    //! runtextmacro Table__make("StringTable","string","key")
    //! runtextmacro Table__make("HandleTable","handle","I2S(H2I(key))")
endlibrary

I had the same idea.

Edit: Oh, and your system is useless unless you benchmark it against gamecache and find that it's significantly faster, of course...

 

[TriggerHappy]

Yea, I saw your table-x, which is why I contacted you on this.

I can try and figure out some way to simulate flushing, though I don't see why you would need it.

Seeing as you can't define your own cache's, though i'll see what I can do.

Oh, and your system is useless unless you benchmark it against gamecache and find that it's significantly faster, of course...

Useless, how?

On a side note, I'm working on defining and flushing your own caches.

 

[Jesus4Lyf]

You can actually get dirty reads like this. For example, a struct is destroyed and recreated with the same id. You go to get an attached integer because you need to set it if it hasn't been set. Oops! It returns some old value.

That's why.

And the way to simulate flushing is demonstrated in my code. Along with the way to make this system actually stable. You can rip whatever you like from my code, although a thanks note is always nice...

But if you don't implement support for attaching to over 8191 strings, and you don't implement flushing, then people may as well just use hashing and H2I systems for attaching. I mean, what purpose would this serve? Is it faster than H2I + hashing + collision detection? It's certainly not more stable. I'm told the string table is lost on a save --> load.

>Useless, how?
If it's slower than gamecache, how is it useful?

PS. I don't mean to upset you or anything, I'm just listing the reasons I didn't do this myself.

 

[TriggerHappy]

How would this be slower than game cache?

The function calls are pretty much not used, I think this will be inlined once called.

so calling..

call CacheInteger("test", "ing", 69)

would result in..

Integerdata(S2ID("test"+ "$|#%&" + "ing")).val = 69

At least, if I understand inlining correctly.

 

[Jesus4Lyf]

Yes, which would compile down further into a single array read. But you also have the overhead of S2ID. Gamecache executes a read and a write in about 4 nanoseconds on my computer, and I forget how fast array read and writes are on my computer, but I think you'd be pretty pressed. The overhead of S2ID I'm not sure of, but function calls do have overhead regardless.

>How would this be slower than game cache?
You need to benchmark it regardless before you say that it isn't. And give a percentage difference, nanosecond difference on your computer, and show us the test.

 

[Romek]

> Gamecache isn't actually slow, it seems.
Well, I doubt Blizzard would just make it slower for the sake of making it slow.
It's fast enough to be usable, and it's still the safest one out there.

Anyway, we don't need 2 gamecache imitations in the system index, so one of these (This or Table-X) is going to be graveyarded. Unless you can tell me how this is superior to Table-X, it's the current candidate.

And benchmarks would indeed be quite helpful.

 

[Viikuna]

Actually, I heard a rumor that Blizzard made gamecache faster to help DotA that uses gamecache a lot.

 

[Flare]

As it is, I don't really see any useful application of this. The only time I can think that anyone would need to associate anything with two strings would be if you wanted to transfer data to another map in a campaign and I highly doubt that this is capable of carrying data to another map

 

[Jesus4Lyf]

>we don't need 2 gamecache imitations
Funnily enough, I replaced the front page of Table-X with Faster Table instead, because the speed was the same. Although the original gamecache immitating code is there too in a spoiler.

>Actually, I heard a rumor that Blizzard made gamecache faster to help DotA that uses gamecache a lot.
That explains a bit. I thought gamecache used to be much slower. But rumours are rumours.

>As it is, I don't really see any useful application of this.
Ding. However, there is a useful application, and that is when you want to associate triggers with text commands. Instead of using the normal event spamming, you could have an array of triggers, and fire it based on the command entered (attach to text literally). The problem is, I would just use Trigger[S2ID("-command")]=... instead of a system.

Aside from that, I expect S2ID(I2S(int)) to be slower than hashing.

 

[Azlier]

I didn't need string attachment for triggers. It was for an RP map so I could have a nice array of abilities to add to a unit at any time. It gets erased on save/load, but that's alright. RP maps can't be played after save/load anyway due to UnitId/UnitId2String not working after save/load.

 

[Jesus4Lyf]

Same point. Use Ability[S2ID("ability")] not a system. Actually, you could even just spam triggers and attach the ability they are for (to the trigger) and this would carry over nicely through save/load (not that you need it, as said). In fact, doing this makes the last use of attaching to strings (I can think of) redundant, as it's more stable and more efficient since you don't need to parse the string out.

I'm not convinced strings are lost on save load if you store a reference to them in a global somewhere, by the way.

 

[Azlier]

The strings aren't lost(?), their place in the string table is. S2ID can act funny after saving and loading.

 

[Jesus4Lyf]

I'm not convinced strings IDS* are lost on save load if you store a reference to them in a global somewhere, by the way.

My reasoning is every variable pointing to a string would need to have its value changed. So I assume storing a reference would make it persist instead. Of course, I haven't tested this because I can't see any use for it anymore anyway.

 

[Romek]

> Funnily enough, I replaced the front page of Table-X with Faster Table instead, because the speed was the same.
If you look at the first few replies of Table, you'll see that someone did mention that I2S was slower than an array lookup. Though Vexorian was unsure.
Benchmarks are sure however. ^_^

> That explains a bit. I thought gamecache used to be much slower. But rumours are rumours.
I really don't think Blizzard made gamecache slow just for the sake of it. It obviously takes some time to save stuff, and it's still probably one of the safest ways of attaching an integer.
People just moaned it was slow because they didn't use it for what it was designed, and a lot of it's "features" (saving games, keys, missions) went to waste.
You only begin to appreciate that it's fast when you see how much it does, and try to recreate it.

Does anyone know which version the speed supposedly improved? We could benchmark it.

 

[TriggerHappy]

I've simulated flushing, op updated.

I also removed the struct and just replaced it with a global array, seems like it would be faster to directly use one.

I've also added a safe array, just in-case your handle count goes above 8190.

I would really appreciate it if someone could do a benchmark test with this against GC.

They both produced the same results.

And yes, I also know I initialized the game cache wrong, but I doubt it would effect this test.

Also, I have added strings.

EDIT: I've benchmarked this using wc3jass's JassBenchmark, my script was a little faster, according to about 15 tests.



Script 1 being SimCache, #2 being GameCache.

I uploaded the test map for you all to test.

That was for the store function, apparently my restore function is slower by ~20% if the restored value is nothing (never been stored). But if the value has been stored before, then my restore function is about the same.

 

[Romek]

> benchmarked this using wc3jass's JassBenchmark
Could you (or someone) do a proper benchmark?
That map is rubbish.

> just in-case your handle count goes above 8190.
I fail to see how handle count would affect this system.

 

[TriggerHappy]

> benchmarked this using wc3jass's JassBenchmark
Could you do a proper benchmark?

No, I don't have access to the stopwatch natives, though I may have someone that will do it for me.

I just did that benchmark as an idea of how fast the scripts are compared to each other.