Hashbased Allocation?

[Pinzu]

Will this work or am I missing something? I'm trying to create a hash based allocation and I'm wondering if I've failed to take something into account.

Secondly, whats the correct way to check for double free? I would like to raise an exception if that happens.

library HashRecyler
 
 
    struct HashRecyler extends array

        readonly static hashtable table = InitHashtable()
 
        static method operator[] takes integer k returns integer
            return LoadInteger(table, -1, k)
        endmethod

        static method operator []= takes integer k, integer tb returns nothing
            call SaveInteger(table, -1, k, tb)
        endmethod

        private static method onInit takes nothing returns nothing
            set thistype[0] = 1
        endmethod

        static method alloc takes nothing returns integer
            local integer t =  thistype[0]
            if (thistype[t] == 0) then
                set thistype[0] = t + 1
            else
                set thistype[0] = thistype[t]
            endif
            call BJDebugMsg("Allocated: " + I2S(t))
            return t
        endmethod

        static method free takes integer t returns nothing
            call BJDebugMsg("deallocated: " + I2S(t))
            set thistype[t] = thistype[0]
            set thistype[0] = t
        endmethod
    endstruct
endlibrary

The purpose is if you want to use Table based allocation and be given a unique key, but don't want to be slowed down by using method wrappers from Bribe's Table, such as when you're creating Table based data structures.

Example Usage:

struct List extends array
 
        private static hashtable ht
 
        private static method onInit takes nothing returns nothing
            set ht = HashRecyler.table
        endmethod
 
        static method create takes nothing returns thistype
            local thistype this = HashRecyler .alloc()
            return this
        endmethod
 
        method destroy takes nothing returns nothing
            call HashRecyler .free(this)
        endmethod
 
        method operator length= takes integer index returns nothing
            call SaveInteger(ht, this, -1, index)
        endmethod

        method operator length takes nothing returns integer
            return LoadInteger(ht, this, -1)
        endmethod
 
        method clear takes nothing returns nothing
            call FlushChildHashtable(ht, this)
            set .length = 0
        endmethod
 
       ....
endstruct

local thistype this = Table(this).create() ---> local thistype this = HashRecyler.alloc()
Table(this).destroy() ---> HashRecyler.free(this)
Table(this).integer[index] = value --> SaveInteger(ht, this, index, value)
etc

Forgot to update changes: the free method should flush the child key and the method operators should be private.

 

[Overfrost]

but don't want to be slowed down by using method wrappers from Bribe's Table

All the methods inside Table 100% inline, except for creators, destroyers, and (TableArray).flush. The 2 methods on the top inside HashTable won't inline, but the rest will. So Table doesn't slow anything down at all, except the fact that it is a hashtable. A faster way is by using arrays instead, but arrays are limited.

I have tested inlining behavior properly, here are the rules. Test it out yourself if you want.

 

[Pinzu]

All the methods inside Table 100% inline, except for creators, destroyers, and (TableArray).flush. The 2 methods on the top inside HashTable won't inline, but the rest will. So Table doesn't slow anything down at all, except the fact that it is a hashtable. A faster way is by using arrays instead, but arrays are limited.

I have tested inlining behavior properly, here are the rules. Test it out yourself if you want.

I tested it and i managed to sort 1900 units without table but only 1400 with. Is that simply due to the method operator calls?

Table vs directly using hash functions.

 

[Overfrost]

I tested it and i managed to sort 1900 units without table but only 1400 with. Is that simply due to the method operator calls?

Then the sort function you're mentioning here involves repeated allocation/deallocation of instances, I presume. Because Table allocates instances by using its hashtable, while yours allocates instances by using an array. That's the only difference between the two there is, because as I said before, Table's wrappers are all inlined by the compiler which causes no performance loss.

 

[Pinzu]

Then the sort function you're mentioning here involves repeated allocation/deallocation of instances, I presume. Because Table allocates instances by using its hashtable, while yours allocates instances by using an array. That's the only difference between the two there is, because as I said before, Table's wrappers are all inlined by the compiler which causes no performance loss.

No I simply replaced this with it's hashtable equivalent and similar table operators inside the sort. No allocation or deallocation was performed, only Save and Load. The only other thing would be if the random seed has changed, but this doesn't happen often in debug mode (same seed is used).

set temp = Table(this).unit[a]
set Table(this).unit[a] = Table(this).unit[b]
set Table(this).unit[b] = temp

Spoiler: Sort used

 private method quicksort takes integer first, integer last returns nothing
            if first < last then
                set up = first
                set down = last
                set pivot = Load$VAR$(HashRecyler.ht, this, first)
                loop
                    loop
                        set other = Load$VAR$(HashRecyler.ht, this, up)
                        exitwhen up >= last or TriggerEvaluate(t)
                        set up = up + 1
                    endloop
                    loop
                        set other = Load$VAR$(HashRecyler.ht, this, down)
                        exitwhen  not TriggerEvaluate(t)
                        set down = down - 1
                    endloop
                    if up < down then
                        set temp = Load$VAR$(HashRecyler.ht, this, up)
                        call Save$VAR$(HashRecyler.ht, this, up, Load$VAR$(HashRecyler.ht, this, down))
                        call Save$VAR$(HashRecyler.ht, this, down, temp)
                    endif
                    exitwhen up >= down
                endloop
                set temp = Load$VAR$(HashRecyler.ht, this, first)
                call Save$VAR$(HashRecyler.ht, this, first, Load$VAR$(HashRecyler.ht, this, down))
                call Save$VAR$(HashRecyler.ht, this, down, temp)
                // down = partition
                call .quicksort(first, down - 1)
                call .quicksort(down + 1, last)
            endif
        endmethod

Just realized i could remove the if up < down inside the outer loop and place the exitwhen condition there instead. This now made it possible to sort 2000 units for that seed, not tested for Table. D:

Push method OP limit benchmark:
No method operators and hashtable based: 3880
Method operator but using temp variable to decrease: 3861
Method operators for .length 3813
Table based with method operators: 3621

I know that the difference in this case is negligible but I just wanted to show that inlining does not appear to be happening.

// This is example of method operators but using temp var.
method push takes $TYPE$ value return thistype
   set len = .length
   call Save$VAR$(HR.ht, this, len, value)
   set len = len + 1
   set .length = len
    return this
endmethod

 

[Overfrost]

I know that the difference in this case is negligible but I just wanted to show that inlining does not appear to be happening.

You know that to check whether a function inlines or not is by checking the raw code generated by the compiler right? E.g. by using mpq-editor, opening the map, and seeing war3map.j.

Perhaps the excessive brackets that got generated due to the inlines matter? It's rather silly, but function inlining does make a ton of brackets.

You should attach the map used for the test mate.

 

[Pinzu]

You know that to check whether a function inlines or not is by checking the raw code generated by the compiler right? E.g. by using mpq-editor, opening the map, and seeing war3map.j.

Perhaps the excessive brackets that got generated due to the inlines matter? It's rather silly, but function inlining does make a ton of brackets.

You should attach the map used for the test mate.

My connection is down and only have mobile access and a usb-stick, too annoying to send... But just do something like:

local Table table = Table.create()
local integer i = 0
loop
     exitwhen i = 100
     set table.unit[i] = CreateUnit(...)
     set i = i + 1
endloop

// You could also test this:

struct S
method operator length= takes integer index returns nothing
     set Table(this).integer[-1] = index // Also try without the .integer keyword
endmethod

method operator length takes nothing returns integer
     return Table(this).integer[-1]
endmethod

and use it somewhere

 set .length = .length + 1 // You get the idea hopefully
endstruct

... Fine I'll send it. ^^

Demo Map - Array List | HIVE

 

[Overfrost]

Push method OP limit benchmark:
No method operators and hashtable based: 3880
Method operator but using temp variable to decrease: 3861
Method operators for .length 3813
Table based with method operators: 3621

Just noticed that you were testing by the OP limit, which of course makes sense given how many brackets function inlining generates.

I'm sure testing it that way doesn't directly mean their speed is compared. If speed is of concern, I'm sure there's only a minuscule difference. Even with this fact, just comparing the data you provided, the top-result only yields ~7% better output compared to the bottom.