wc3campaigns
WC3C Homepage - www.wc3c.netUser Control Panel (Requires Log-In)Engage in discussions with other users and join contests in the WC3C forums!Read one of our many tutorials, ranging in difficulty from beginner to advanced!Show off your artistic talents in the WC3C Gallery!Download quality models, textures, spells (vJASS/JASS), systems, and scripts!Download maps that have passed through our rigorous approval process!

Go Back   Wc3C.net > Warcraft III Modding > Developer's Corner > Triggers & Scripts
User Name
Password
Register Rules Get Hosted! Chat Pastebin FAQ and Rules Members List Calendar



Reply
 
Thread Tools Search this Thread
Old 04-09-2010, 04:01 PM   #1
Tot
6
 
Tot's Avatar
 
Join Date: Oct 2008
Posts: 841

Tot will become famous soon enough (53)Tot will become famous soon enough (53)

Default 'normal' arrays in vJass

This is a lil script I made some time ago to have passable and individual seizable arrays in vJass.

my first attampt was a hastable-array, but it was awkward, so I tried this...

Collapse JASS:
library AdvArray
//**********************************************************************************************************************************************************************************
//* 
//* Version: 1.00
//* 
//* Author: Tot
//* 
//* This allows the use of individually sized, passable arrays, without a significant speed-loss (1 array-lookup and an addition more compared to blizz-arrays)
//* 
//**********************************************************************************************************************************************************************************
//* API:
//* - create(<integer>)-> $type$Array:  takes a size-parameter; creates a new Array; size can't be bigger then free fields
//* - flush() -> nothing:               nulls the array
//* - destroy()-> nothing:              destroys the array
//* - defragmentate() -> nothing:       static method which defragmentates the data-array (!slow!)
//* - free:                             an integer that holds the number of free values
//* - [<integer>] -> $type$:            gets the value nr <integer> from the array
//* - [<integer>]=<$type$> -> nothing:  sets the value nr <integer> from the array to <$type$>
//**********************************************************************************************************************************************************************************
//* Define your own array:
//* to define your own type-Array, simply type //! runtextmacro ArrayMacro("<your desired type>","<null-value of your type>") in the macro-section (Run your array-macros here...)
//**********************************************************************************************************************************************************************************
//* Configuration:
    globals
        private constant integer    OP_LIMIT            = 400   //lower: slower Iterations, but saver against abortion through op-limit (only defragmentate())
                                                                //higher: faster iterations, but less save against abortion through op-limit (only defragmentate())
        private constant integer    ARRAY_OVERALL_SIZE  = 8192  //overall maximal number of values all arrays of one type can hold
        private constant boolean    SAVE_OPERATORS      = true  //false: inlineable, not save against too big/small indices
                                                                //true: not inlineable, save against too big/small indices 
                                                                //[]= returns a boolean, weather the index was valid or not
    endglobals
//**********************************************************************************************************************************************************************************
//* Run your array-macros here...
//**********************************************************************************************************************************************************************************
//! runtextmacro ArrayMacro("integer","0")
//! runtextmacro ArrayMacro("boolean","false")
//! runtextmacro ArrayMacro("real","0.0")
//! runtextmacro ArrayMacro("string","null")

//**********************************************************************************************************************************************************************************
//DO\\ //NOT\\ //CHANGE\\ //ANYTHING\\ //BELOW\\ //THIS\\ //LINE\\ //UNLESS\\ //YOU\\ //ARE\\ //KNOWING\\ //WHAT\\ //YOU\\ //ARE\\ //DOING\\
//**********************************************************************************************************************************************************************************

//! textmacro ArrayMacro takes type, null
    struct $type$Array[ARRAY_OVERALL_SIZE]
        private static $type$ array data[ARRAY_OVERALL_SIZE]
        private static integer array fragmentStart[ARRAY_OVERALL_SIZE]
        private static integer array fragmentEnd[ARRAY_OVERALL_SIZE]
        private static integer fragmentCount
        private static integer max
        readonly static integer free
        
        private static integer currPos
        private static integer off
        private static integer next
        
        private static method onInit takes nothing returns nothing
            set .free=ARRAY_OVERALL_SIZE
            set .fragmentCount=0
            set .max=0
        endmethod    
        
        private static method getPlace takes integer size returns integer
            local integer i=0
            local integer lost=-1
            local integer length
            local integer start=-1
            if .fragmentCount>0 then
                loop
                    exitwhen i==.fragmentCount
                    set length=.fragmentEnd[i]-.fragmentStart[i]
                    if (length-size)>=0 and (length-size<lost or lost<0) then
                        set lost=length-size
                        set start=i
                    endif
                    set i=i+1
                endloop
                if start>=0 then
                    set .fragmentCount=.fragmentCount-1
                endif
            else
                if start+size>ARRAY_OVERALL_SIZE then
                    set start=-1
                else
                    set start=.max
                    set .max=start+size
                endif
            endif
            return start
        endmethod
        
        private static method getNextFreeBlockMin takes integer curr returns integer
            local integer i=0
            local integer d
            local integer dist=-1
            local integer ret=-1
            loop
                exitwhen i==.fragmentCount
                set d=.fragmentStart[i]-curr
                if d>0 and (d<dist or dist<0) then
                    set dist=d
                    set ret=i
                endif
                set i=i+1
            endloop
            return ret
        endmethod
        
        private static method defragLoop takes nothing returns nothing
            local integer i=0
            local integer a=0
            local integer c=0
            loop
                set c=i+currPos
                set a=c+off
                exitwhen i==OP_LIMIT or a==.max
                if i==next then
                    set off=off+.fragmentEnd[next]-.fragmentStart[next]
                    if .fragmentCount>0 then
                        set .fragmentCount=.fragmentCount-1
                        set .fragmentStart[next]=.fragmentStart[.fragmentCount]
                        set .fragmentEnd[next]=.fragmentEnd[.fragmentCount]
                        set next=thistype.getNextFreeBlockMin(c)
                        if next<0 then
                            debug call BJDebugMsg("|cffFF0000"+SCOPE_PREFIX+"$type$Array.defragmentate_CRITICAL ERROR: DEFRAGMETATION FAILED!|r")
                            return
                        endif
                    endif
                endif
                //move data
                set .data[c]=.data[a]
                set .data[a]=$null$
                //move array
                if $type$Array(c).size!=0 then
                    set $type$Array(c).offset=$type$Array(c).offset-off
                endif
                set i=i+1
            endloop
            set currPos=i+currPos
            if currPos+off<.max then
                call ExecuteFunc(thistype.defragLoop.name)
            endif
        endmethod
        
        static method defragmentate takes nothing returns nothing
            if .fragmentCount>0 then
                set currPos=0
                set off=0
                set next=thistype.getNextFreeBlockMin(currPos)
                if next<0 then
                    debug call BJDebugMsg("|cffFF0000"+SCOPE_PREFIX+"$type$Array.defragmentate_CRITICAL ERROR: DEFRAGMETATION FAILED!|r")
                    return
                endif
                set .fragmentCount=.fragmentCount-1
                set .fragmentStart[next]=.fragmentStart[.fragmentCount]
                set .fragmentEnd[next]=.fragmentEnd[.fragmentCount]
                call ExecuteFunc(thistype.defragLoop.name)
            endif
        endmethod
        
        readonly integer size
        private integer offset
        
        method flush takes nothing returns nothing
            local integer i=0
            loop
                exitwhen i==.size
                set .data[.offset+i]=$null$
                set i=i+1
            endloop
        endmethod
        
        static method create takes integer size returns $type$Array
            local $type$Array this
            local integer start=-1
            if size<=0 or size>ARRAY_OVERALL_SIZE then
                debug call BJDebugMsg(SCOPE_PREFIX+"invalid array size; size must be between 1 and "+I2S(ARRAY_OVERALL_SIZE))
                return 0
            elseif size>.free then
                debug call BJDebugMsg(SCOPE_PREFIX+"you can't allocate an array with size "+I2S(size)+", when only "+I2S(.free)+" fields are free")
                return 0
            endif
            set start=.getPlace(size)
            if start<0 then
                debug call BJDebugMsg(SCOPE_PREFIX+"have "+I2S(.free)+" free fields, but can't allocate an matching suffix; defragmentating array")
                call .defragmentate()
                set start=.getPlace(size)
                if start<0 then
                    debug call BJDebugMsg("|cffFF0000"+SCOPE_PREFIX+"$type$Array.create_CRITICAL ERROR: DEFRAGMETATION FAILED!|r")
                    return 0
                endif
            endif
            set .free=.free-size
            set this=$type$Array(start) 
            set .offset=start
            set .size=size
            return this
        endmethod
        
static if SAVE_OPERATORS then
        method operator [] takes integer index returns $type$
            if index>=0 and index<.size then
                return .data[.offset+index]
            endif
            return $null$
        endmethod
        
        method operator []= takes integer index, $type$ val returns boolean
            if index>=0 and index<.size then
                set .data[.offset+index]=val
                return true
            endif
            return false
        endmethod
else
        method operator [] takes integer index returns $type$
            return .data[.offset+index]
        endmethod
        
        method operator []= takes integer index, $type$ val returns nothing
            set .data[.offset+index]=val
        endmethod
endif
        
        method destroy takes nothing returns nothing
            call .flush()
            set .fragmentStart[.fragmentCount]=.offset
            set .fragmentEnd[.fragmentCount]=.offset+.size
            set .fragmentCount=.fragmentCount+1
            set .size=0
            set .free=.free+.size
        endmethod
    endstruct
    
//! endtextmacro
endlibrary

I'm posting this her and not in submissions, cause I want first to hear/read some constructive criticism, especially for the defragmetation-method and I need someone who does some benchmarks to compare (local lookup-, global lookup-, blizz-array lookup- and my-array lookupspeed), cause for me it feels still slow, when I use it...
__________________
Current Projects:
  • Masters Of WarCraft: Some mixture of AoS and RPG
    Terrain: 100%, Coding: 75%, Heroes: 0%, Items: 0%, Creeps: 0%, Upgrades: 0%
  • hunting emos
____________________________________
scheiss kack dreck sausacksau bundeswehr
Tot is offline   Reply With Quote
Sponsored Links - Login to hide this ad!
Old 04-09-2010, 04:23 PM   #2
Anachron
User
 
Anachron's Avatar
 
Join Date: Mar 2009
Posts: 1,079

Anachron will become famous soon enough (51)Anachron will become famous soon enough (51)

Default

I made something similar, its faster, easier and uses less code.

Collapse JASS:
library CustomTable

    //: CnP from Vexorians Table. 
    //: Sorry dude, there is no other way.
    //=============================================================
    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    
        // Actually this is the data holder
    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

        //=============================================================
        // initialize it all.
        //
        private static method onInit takes nothing returns nothing
            set ht = InitHashtable()
        endmethod

    endstruct

    //: Setup textmacros for table creation.
    //! textmacro AdvancedTable_make takes name, valType, func, funcPref, hashType, paraType, keyType, key, value
    struct $name$Table extends GTable
    
        method operator [] takes $keyType$ key returns $valType$
            return Load$func$$funcPref$(ht, integer(this), $key$)
        endmethod

        method operator []= takes $keyType$ key, $paraType$ value returns nothing
            call Save$func$$funcPref$(ht,  integer(this)  ,$key$, $value$)
        endmethod
        
        method exists takes integer key returns boolean
            return HaveSavedHandle(ht, integer(this), key)
        endmethod

        method flush takes $keyType$ key returns nothing
            call RemoveSaved$hashType$(ht, integer(this), $key$)
        endmethod

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

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

    endstruct
    //! endtextmacro
    
    //: Finally create our crazy tables.
    //                                  TableName   DataType    Func        Prefix      hashID      paraType    keyType     key     value
    //! runtextmacro AdvancedTable_make("Integer", "integer",  "Integer",  "",         "Integer",  "integer",   "integer",  "key",   "value")
    //! runtextmacro AdvancedTable_make("Boolean", "boolean",  "Boolean",  "",         "Boolean",  "boolean",   "integer",  "key",   "value")
    //! runtextmacro AdvancedTable_make("Unit",    "unit",     "Unit",     "Handle",   "Handle",   "unit",      "integer",  "key",   "value")
    //! runtextmacro AdvancedTable_make("Item",    "item",     "Item",     "Handle",   "Handle",   "item",      "integer",  "key",   "value")
    //! runtextmacro AdvancedTable_make("Player",  "player",   "Player",   "",         "Handle",   "player",    "integer",  "key",   "value")
endlibrary
__________________
CustomInventory [Discussion - Download] - Got Directors Cut!
CustomMissle [Discussion - [Download (not yet)] - In development!
Other systems [Spawn System] [Move System] [CustomBar] [SpellBar]
Anachron is offline   Reply With Quote
Old 04-09-2010, 04:46 PM   #3
Tot
6
 
Tot's Avatar
 
Join Date: Oct 2008
Posts: 841

Tot will become famous soon enough (53)Tot will become famous soon enough (53)

Default

Quote:
Originally Posted by Anachron
I made something similar, its faster, easier and uses less code.

Collapse JASS:
library CustomTable

    //: CnP from Vexorians Table. 
    //: Sorry dude, there is no other way.
    //=============================================================
    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    
        // Actually this is the data holder
    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

        //=============================================================
        // initialize it all.
        //
        private static method onInit takes nothing returns nothing
            set ht = InitHashtable()
        endmethod

    endstruct

    //: Setup textmacros for table creation.
    //! textmacro AdvancedTable_make takes name, valType, func, funcPref, hashType, paraType, keyType, key, value
    struct $name$Table extends GTable
    
        method operator [] takes $keyType$ key returns $valType$
            return Load$func$$funcPref$(ht, integer(this), $key$)
        endmethod

        method operator []= takes $keyType$ key, $paraType$ value returns nothing
            call Save$func$$funcPref$(ht,  integer(this)  ,$key$, $value$)
        endmethod
        
        method exists takes integer key returns boolean
            return HaveSavedHandle(ht, integer(this), key)
        endmethod

        method flush takes $keyType$ key returns nothing
            call RemoveSaved$hashType$(ht, integer(this), $key$)
        endmethod

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

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

    endstruct
    //! endtextmacro
    
    //: Finally create our crazy tables.
    //                                  TableName   DataType    Func        Prefix      hashID      paraType    keyType     key     value
    //! runtextmacro AdvancedTable_make("Integer", "integer",  "Integer",  "",         "Integer",  "integer",   "integer",  "key",   "value")
    //! runtextmacro AdvancedTable_make("Boolean", "boolean",  "Boolean",  "",         "Boolean",  "boolean",   "integer",  "key",   "value")
    //! runtextmacro AdvancedTable_make("Unit",    "unit",     "Unit",     "Handle",   "Handle",   "unit",      "integer",  "key",   "value")
    //! runtextmacro AdvancedTable_make("Item",    "item",     "Item",     "Handle",   "Handle",   "item",      "integer",  "key",   "value")
    //! runtextmacro AdvancedTable_make("Player",  "player",   "Player",   "",         "Handle",   "player",    "integer",  "key",   "value")
endlibrary

yea...know it, but it's a hashtable and not an array --> (theoretically) slower
__________________
Current Projects:
  • Masters Of WarCraft: Some mixture of AoS and RPG
    Terrain: 100%, Coding: 75%, Heroes: 0%, Items: 0%, Creeps: 0%, Upgrades: 0%
  • hunting emos
____________________________________
scheiss kack dreck sausacksau bundeswehr
Tot is offline   Reply With Quote
Old 04-09-2010, 07:44 PM   #4
Ammorth
I blink, therefore I am.
 
Ammorth's Avatar
 
Join Date: Sep 2006
Posts: 1,812

Submissions (10)

Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)

Default

I wrote something like this before, for personal use. Our implementation is rougly the same.

Defragging is costly, and there isn't much you can do to change that. You can try to find ways of either reducing the number of "moves" defragging does, or modifying how memory is allocated so more space is always avaliable.

For example, only moving arrays that are less than 5% of the total allocation size, or moving arrays from smallest to largest. You can also say empty space of less than 1% is ignored (unless something will fit in it). When you create, you can check if there is another space that is more suited (Create(50) and there is a 52 space avaliable) instead of using the first avaliable space that fits.

There isn't much use behind dynamic sizable arrays. Cost wise of maintainning the arrays vs using type MyArray extends integer array[size] may not be very effecient.
__________________
Ammorth is offline   Reply With Quote
Old 04-10-2010, 01:42 PM   #5
Tot
6
 
Tot's Avatar
 
Join Date: Oct 2008
Posts: 841

Tot will become famous soon enough (53)Tot will become famous soon enough (53)

Default

Quote:
Originally Posted by Ammorth
I wrote something like this before, for personal use. Our implementation is rougly the same.

Defragging is costly, and there isn't much you can do to change that. You can try to find ways of either reducing the number of "moves" defragging does, or modifying how memory is allocated so more space is always avaliable.

For example, only moving arrays that are less than 5% of the total allocation size, or moving arrays from smallest to largest. You can also say empty space of less than 1% is ignored (unless something will fit in it). When you create, you can check if there is another space that is more suited (Create(50) and there is a 52 space avaliable) instead of using the first avaliable space that fits.

There isn't much use behind dynamic sizable arrays. Cost wise of maintainning the arrays vs using type MyArray extends integer array[size] may not be very effecient.

type MyArray extends integer array[size] is for every size a new jass array with 8912 fields, which is a waste of memory...

I'm currently using the best-fit method.


Maybe defrag on memory allocation (search the best fitting and move all following data <length of block>-<size of array> fields forward...
Then after an array is destroyed, all following had to be moved <size of destroyed array> fields forward...


- no unused blocks --> no need for defragmetation
- 2 integer arrays an 1 integer per array-type saved
...


- slower allocation and destruction
...

(only typing what I'm thinking...)
__________________
Current Projects:
  • Masters Of WarCraft: Some mixture of AoS and RPG
    Terrain: 100%, Coding: 75%, Heroes: 0%, Items: 0%, Creeps: 0%, Upgrades: 0%
  • hunting emos
____________________________________
scheiss kack dreck sausacksau bundeswehr
Tot is offline   Reply With Quote
Old 04-10-2010, 05:25 PM   #6
0zyx0
Perfectionist noob
 
0zyx0's Avatar
 
Join Date: Mar 2009
Posts: 255

0zyx0 will become famous soon enough (38)0zyx0 will become famous soon enough (38)

Default

Quote:
Originally Posted by Tot
type MyArray extends integer array[size] is for every size a new jass array with 8912 fields, which is a waste of memory...

Today, memory isn't that much of an issue. CPU usage is more so.
__________________
My new signature - Now easier to understand than ever!
0zyx0 is offline   Reply With Quote
Old 04-10-2010, 05:42 PM   #7
Tot
6
 
Tot's Avatar
 
Join Date: Oct 2008
Posts: 841

Tot will become famous soon enough (53)Tot will become famous soon enough (53)

Default

Quote:
Originally Posted by 0zyx0
Today, memory isn't that much of an issue. CPU usage is more so.

yea...but if you want wc to allocate too much memory, the game will crash...
__________________
Current Projects:
  • Masters Of WarCraft: Some mixture of AoS and RPG
    Terrain: 100%, Coding: 75%, Heroes: 0%, Items: 0%, Creeps: 0%, Upgrades: 0%
  • hunting emos
____________________________________
scheiss kack dreck sausacksau bundeswehr
Tot is offline   Reply With Quote
Old 04-10-2010, 06:20 PM   #8
Ammorth
I blink, therefore I am.
 
Ammorth's Avatar
 
Join Date: Sep 2006
Posts: 1,812

Submissions (10)

Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)Ammorth is a glorious beacon of light (461)

Default

Quote:
Originally Posted by Tot
yea...but if you want wc to allocate too much memory, the game will crash...

I really doubt you could ever reach this point with a custom map that wasn't designed to use memory. Sure, if you brute force it, but not under normal use (unless you don't ever clean up anything).
__________________
Ammorth is offline   Reply With Quote
Old 04-11-2010, 10:06 AM   #9
Tot
6
 
Tot's Avatar
 
Join Date: Oct 2008
Posts: 841

Tot will become famous soon enough (53)Tot will become famous soon enough (53)

Default

Quote:
Originally Posted by Ammorth
I really doubt you could ever reach this point with a custom map that wasn't designed to use memory. Sure, if you brute force it, but not under normal use (unless you don't ever clean up anything).

That's a point...
__________________
Current Projects:
  • Masters Of WarCraft: Some mixture of AoS and RPG
    Terrain: 100%, Coding: 75%, Heroes: 0%, Items: 0%, Creeps: 0%, Upgrades: 0%
  • hunting emos
____________________________________
scheiss kack dreck sausacksau bundeswehr
Tot is offline   Reply With Quote
Old 04-15-2010, 11:41 AM   #10
SHAƎDY
User
 
Join Date: Apr 2010
Posts: 14

SHAƎDY has little to show at this moment (0)

Default

Collapse JASS:
 This allows the use of individually sized, passable arrays, without a significant speed-loss
I highly suggest you benchmark this for speedfreaks.

Collapse JASS:
static method create takes integer size returns $type$Array
Shouldn't it be private?
SHAƎDY is offline   Reply With Quote
Old 04-15-2010, 11:43 AM   #11
SHAƎDY
User
 
Join Date: Apr 2010
Posts: 14

SHAƎDY has little to show at this moment (0)

Default

Your create method is not private.

Also, I highly suggest you benchmark the creation of an array with your system in comparison to others.
SHAƎDY is offline   Reply With Quote
Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off


All times are GMT. The time now is 05:02 AM.


Affiliates
The Hubb The JASS Vault Clan WEnW Campaign Creations Clan CBS GamesModding Flixreel Videos

Powered by vBulletin (Copyright ©2000 - 2019, Jelsoft Enterprises Ltd).
Hosted by www.OICcam.com
IT Support and Services provided by Executive IT Services