Last active
May 13, 2019 13:38
-
-
Save paniq/1a55ae2fed724294d110e25dd64619f5 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # implementation of | |
| https://gist.github.com/paniq/856241af5d8a69a76a5b7e941b2533f0 | |
| using import Array | |
| let IdIndexT = u32 | |
| let GenT = u32 | |
| # must be at least 1 | |
| let MIN_UNUSED = 1 | |
| typedef PoolHandle : IdIndexT | |
| struct PoolAllocator | |
| # object -> id, but also id -> object | |
| _map : (Array IdIndexT) | |
| # id -> generation | |
| _gen : (Array IdIndexT) | |
| _pop_offset : IdIndexT = 0 | |
| _push_offset : IdIndexT = 0 | |
| inline __typecall (cls) | |
| local self = | |
| super-type.__typecall cls | |
| 'append self._map (0 as IdIndexT) | |
| 'append self._gen (0 as GenT) | |
| deref self | |
| inline generation (self id) | |
| deref (self._gen @ id) | |
| # lookup index from id or id from index | |
| inline resolve (self id_or_index) | |
| deref (self._map @ id_or_index) | |
| fn capacity (self) | |
| (countof self._map) as IdIndexT | |
| fn valid-index? (self index) | |
| let pushofs = (deref self._push_offset) | |
| let popofs = (deref self._pop_offset) | |
| let mapsize = (capacity self) | |
| < | |
| ((index - popofs + mapsize) % mapsize) | |
| ((pushofs - popofs + mapsize) % mapsize) | |
| inline valid-id? (self id gen) | |
| and | |
| id < (countof self._map) | |
| (generation self id) == gen | |
| 'valid-index? self ('resolve self id) | |
| inline identity? (self id_or_index) | |
| ('resolve self id_or_index) == id_or_index | |
| """"Implements support for the `countof` operator. Returns the current | |
| number of elements allocated in `self`. | |
| inline __countof (self) | |
| let capacity = (capacity self) | |
| (self._push_offset - self._pop_offset + capacity) % capacity | |
| fn countof-unused (self) | |
| (capacity self) - (countof self) | |
| # swap the ids of two indices (or the indices of two ids) | |
| fn swap (self a b) | |
| # ids can only be twisted or untwisted, map must not be shuffled any further | |
| assert ((a == b) | |
| or ((('resolve self a) == a) & (('resolve self b) == b)) | |
| or ((('resolve self a) == b) & (('resolve self b) == a))) | |
| 'swap self._map a b | |
| inline generator (self) | |
| Generator | |
| inline () (deref self._pop_offset) | |
| inline (i) (i != self._push_offset) | |
| inline (i) i | |
| inline (i) ((i + 1) % (capacity self)) | |
| inline __as (cls otherT) | |
| static-if (otherT == Generator) generator | |
| else () | |
| # allocate a new id from the pool | |
| user must copy slot[index(id)] to slot[count] after | |
| allocation. obtain() returns a { src, dst } tuple indicating | |
| how data must be moved; if (dst == src), then no move is necessary. | |
| src is also identical to the newly obtained id | |
| fn obtain (self) | |
| let capacity = (capacity self) | |
| if ((countof-unused self) <= MIN_UNUSED) | |
| # we are out of space | |
| # add new identity entry | |
| 'append self._map capacity | |
| let gen = (0 as GenT) | |
| 'append self._gen gen | |
| # if entry is in valid range, return it | |
| if (valid-id? self capacity gen) | |
| return capacity capacity gen | |
| let capacity = ('capacity self) | |
| # index of new last element | |
| let index = (deref self._push_offset) | |
| # id of new last element | |
| let id = ('resolve self index) | |
| # generation of id | |
| let gen = (generation self id) | |
| # swap with index that matches this id, | |
| # so that index(id) == id if they were swapped - otherwise no effect | |
| swap self index id | |
| # increase number of elements | |
| self._push_offset = (self._push_offset + 1) % capacity | |
| # return index, index of moved item and generation | |
| return id (dupe index) gen | |
| # release an obtained id to the pool | |
| user must copy slot[count] to slot[index(id)] after | |
| deletion. (release id) returns a (src dst) tuple indicating | |
| how data must be moved; if (src == dst), then no move is necessary. | |
| fn release (self id gen) | |
| if (not ('valid-id? self id gen)) | |
| 'dump self | |
| print "id =" id | |
| assert ('valid-id? self id gen) | |
| # generation of element | |
| self._gen @ id += 1 | |
| # index of element to be deleted | |
| let index = ('resolve self id) | |
| # if element is twisted, untwist | |
| swap self index id | |
| # index and id of element to take its place | |
| let capacity = (capacity self) | |
| let last_index = (deref self._pop_offset) | |
| let last_id = ('resolve self last_index) | |
| # if last element is twisted then this will untwist it | |
| swap self last_index last_id | |
| # swap indices so that tailing element fills the gap (twist) | |
| swap self index last_id | |
| # decrease number of elements | |
| self._pop_offset = (self._pop_offset + 1) % capacity | |
| # return index of element to be moved and index of gap | |
| return last_index index | |
| fn dump (self) | |
| print "id-gen index -> ID:" | |
| let _1 = (1 as IdIndexT) | |
| let end = (countof self) | |
| for i id in (enumerate self._map) | |
| let i = (i as IdIndexT) | |
| if (self._pop_offset == i) | |
| print "vvvv pop" | |
| if (self._push_offset == i) | |
| print "^^^^ push" | |
| let valid? = (valid-index? self i) | |
| let ri = ('resolve self id) | |
| generation self i; _ i; ? (i == id) "=" "X"; _ id; ? valid? "" "free" | |
| ? (i != ri) "!" "" | |
| print ((countof self) as i32) "used elements," | |
| \ "capacity:" (capacity self) | |
| \ "pop offset:" (self._pop_offset as i32) | |
| \ "push offset:" (self._push_offset as i32) | |
| unlet swap | |
| fn test-pool-alloc () | |
| using import ..tukan.random | |
| let N = 10000 | |
| # our "data array", which just stores the id again, so we can easily verify | |
| # if an id still matches its assigned content | |
| local data : (array u32 N) | |
| local pool : PoolAllocator | |
| fn move_entry (data k0 k1) | |
| if (k0 != k1) | |
| data @ k1 = data @ k0 | |
| fn verify_data (pool data) | |
| local twisted = 0:u32 | |
| for i in pool | |
| let id = ('resolve pool i) | |
| assert (data @ i == id) | |
| assert (('resolve pool id) == i) | |
| if (not ('identity? pool i)) | |
| twisted += 1:u32 | |
| deref twisted | |
| fn test_obtain (pool data) | |
| let k0 k1 gen = ('obtain pool) | |
| move_entry data k0 k1 | |
| data @ k0 = k0 | |
| _ k0 gen | |
| fn test_release (pool data id gen) | |
| let k0 k1 = ('release pool id gen) | |
| move_entry data k0 k1 | |
| fn packid (id gen) | |
| | | |
| id << 16 | |
| gen & 0xffff | |
| fn unpackid (id) | |
| _ | |
| id >> 16 | |
| id & 0xffff | |
| # array of ids in use | |
| local used : (array u32 N) | |
| local mintwisted : u32 = N | |
| local maxtwisted : u32 = 0 | |
| local total : u32 = 0 | |
| local steps : u32 = 0 | |
| local used_count : u32 = 0 | |
| local maxused : u32 = 1 | |
| for i in (range N) | |
| used @ i = (packid 0:u32 0:u32) | |
| # keep 0 handle | |
| do | |
| let k gen = (test_obtain pool data) | |
| print "obtained" k | |
| #'dump pool | |
| used @ used_count = (packid k gen) | |
| used_count += 1 | |
| assert (used_count == (countof pool)) | |
| verify_data pool data | |
| local rnd : (Random) | |
| 'seed rnd 14 | |
| 'dump pool | |
| static-if 1 | |
| let STEPS = 100000 | |
| # do random obtains/releases, see if something breaks | |
| for i in (range STEPS) | |
| if ((('range rnd 0 100) < 48) & (used_count > 1)) | |
| let used_index = ('range rnd 1:u32 used_count) | |
| let id gen = (unpackid (deref (used @ used_index))) | |
| #print "released" id | |
| # remove from used array and fill | |
| used_count -= 1 | |
| used @ used_index = used @ used_count | |
| used @ used_count = (packid 0:u32 0:u32) | |
| test_release pool data id gen | |
| #'dump pool | |
| assert (used_count == (countof pool)) | |
| let t = (verify_data pool data) | |
| mintwisted = (min mintwisted t) | |
| maxtwisted = (max maxtwisted t) | |
| total += t | |
| steps += 1 | |
| else | |
| let k gen = (test_obtain pool data) | |
| #print "obtained" k | |
| #'dump pool | |
| used @ used_count = (packid k gen) | |
| used_count += 1 | |
| maxused = (max maxused used_count) | |
| assert (used_count == (countof pool)) | |
| verify_data pool data | |
| #else | |
| # attempt to fabricate a worst case | |
| for i in (range N) | |
| test_obtain pool data | |
| for i in (range 0:u32 N 2:u32) | |
| test_release pool data i | |
| let t = (verify_data pool data) | |
| mintwisted = (min mintwisted t) | |
| maxtwisted = (max maxtwisted t) | |
| total += t | |
| steps += 1 | |
| 'dump pool | |
| \ "max used:" maxused | |
| \ "releases:" steps | |
| \ "min twisted:" mintwisted | |
| \ "max twisted:" maxtwisted | |
| \ "total twisted:" total | |
| \ "average:" (total / steps) | |
| print "OK." | |
| ; | |
| test-pool-alloc; | |
| ; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment