Thread: Table 3.1
View Single Post
Old 07-03-2008, 01:34 AM   #1
Vexorian
Free Software Terrorist
 
Vexorian's Avatar


Technical Director
 
Join Date: Apr 2003
Posts: 14,898

Submissions (37)

Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)Vexorian has a reputation beyond repute (1062)

Hero Contest #3 - 2nd Place

Default Table 3.1

Table used to be just vJassified gamecache, now it is vJassified 'hashtable'. It is made to look like using an associative array or 'dictionary'. And the methods are coded so they are inline friendly, in other words when you use sometable[someint] and set sometable[someint]=something , you are actually using native gamecache usage. So, even though the looks understandable and self documenting, it is very close to the fastest way to use gamecache. Perhaps saving the contents of I2S in some variable before calling these functions thrice would be mildly faster, but probably not in a relevant way, there is also no good reason for doing multiple consecutive calls on the same index either.

Why gamecache? In all seriousness, speed is gamecache's only issue, Table has some advantages over customly made hash systems and CSData:
- No practical limits
- Very multi instanceable. You can have more than 1 table at the same time, in fact you may have 400000 tables at the same time, each being an indepent associative array. Oh, and its multi instancibility won't make it so you end up with 50 lines of code per instance.
- Cleaning all the contents of one Table is possibly O(1)

Why hashtable? Basically, hashtable keeps all those advantages for gamecache but it is also quite fast. Theory has it that it is just 2x times an array usage...

Some stuff:
* You may change maxinstances, a big value will remove the 8000 limit and just make allocation slower, allocation does not really matter too much or at all when you use Table correctly.
* 2d array syntax to have access to simulate "mission keys", just calls StringHash on them.


Collapse Table 3.1 (for patch 1.23b +):
library Table
//***************************************************************
//* Table object 3.1
//* ------------
//*
//*   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.
//*
//*  You can use Table on structs' onInit  if the struct is
//* placed in a library that requires Table or outside a library.
//*
//*  You can also do 2D array syntax if you want to touch
//* mission keys directly, however, since this is shared space
//* you may want to prefix your mission keys accordingly:
//*
//*  set Table["thisstring"][ 7 ] = 2
//*  set Table["thisstring"][ 5 ] = Table["thisstring"][7]
//*
//***************************************************************

//=============================================================
    globals
        private constant integer MAX_INSTANCES=8100 //400000
        //Feel free to change max instances if necessary, it will only affect allocation
        //speed which shouldn't matter that much.

    //=========================================================
        private hashtable ht = InitHashtable()
    endglobals

    private struct GTable[MAX_INSTANCES]

        method reset takes nothing returns nothing
            call FlushChildHashtable(ht, integer(this) )
        endmethod

        private method onDestroy takes nothing returns nothing
            call this.reset()
        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

        method operator [] takes $type$ key returns integer
            return LoadInteger(ht, integer(this), $key$)
        endmethod

        method operator []= takes $type$ key, integer value returns nothing
            call SaveInteger(ht,  integer(this)  ,$key$, value)
        endmethod

        method flush takes $type$ key returns nothing
            call RemoveSavedInteger(ht, integer(this), $key$)
        endmethod

        method exists takes $type$ key returns boolean
            return HaveSavedInteger( ht,  integer(this)  ,$key$)
        endmethod

        static method flush2D takes string firstkey returns nothing
            call $name$(- StringHash(firstkey)).reset()
        endmethod

        static method operator [] takes string firstkey returns $name$
            return $name$(- StringHash(firstkey) )
        endmethod

    endstruct
    //! endtextmacro

    //! runtextmacro Table__make("Table","integer","key" )
    //! runtextmacro Table__make("StringTable","string", "StringHash(key)" )
    //! runtextmacro Table__make("HandleTable","handle","GetHandleId(key)" )

endlibrary

Expand Table 2.0 (for wc3 version 1.23 or earlier):

Changes in 2.0
* A 2D array syntax to handle mission keys, however, this comes with a price as in: function calls.
* The other aspects of Table have gotten a little faster as I2S is replaced with an array look up. this comes with a price as if you now change the instance limit to something larger than 8190, Table will become much slower. Just hope you don't ever, ever, need to do that.
* initializing is done using struct onInit instead of library initializer, this simply is to also allow other structs using onInit to use Tables, notice that as long as you use the Table in a library that requires Table or in a scope, its initializers are guaranteed to run after Table's.

Changes in 2.1
* Works in patch 1.23b.
* Will only work with patch 1.23b.

Thanks go to blizzard for listening in adding GetHandleId , without such native Table would have been killed.

Changes in 3.0
* Fuxing thanks to blizzard, the hashtable natives are great. Moved from gamecache to hashtable, the interface is the same, speed should have improved greatly, the static [] operator is faster. Basically, everything will get inlined to hashtable native usage now...

Changes in 3.1
* Can now be used in module initializers.
__________________
Zoom (requires log in)Wc3 map optimizer 5.0
Someone should fix .wav sound in this thing.
Zoom (requires log in)JassHelper 0.A.2.A
Turns your simple code into something that is complicated enough to work.
Faster != more useful
Vexorian is offline   Reply With Quote
Sponsored Links - Login to hide this ad!