Hifi Suggestion: Parallel Entity Tree (specific to crappy engine architecture in fall 2015)

gistfile1.txt

Suggestion: Entity tree could be much more efficient and simpler w/ a rewrite that uses parallel operations

Current implementation:
 - Octree w/ one model
 – Entities are stored + owned by buckets in the tree
 – Synchronous / immediate operations w/ random reads / writes; thread safety via lock guards
drawbacks:
 - Tree must be locked for reads / writes
 – Operations are synchronous, but order is undefined / random (from a threaded script PoV)
    - though multiple scripts shouldn't be competing for the same resource, obviously
 – Lookup by id is O(lg(n) + m, m < n) to find an entity in the tree
 – Almost ALL script operations use lookups by id
 – Operations are super complicated (tons of code + slow), and possibly not implemented correctly
 – Limited to a single thread
 – No support for distributed entity simulations AFAIK (though I'm not proposing to add this)

Suggested implementation:
 – Double-buffered (sorta), with one readonly entity interface, and a queue of write-only entity
  operations that gets flushed once (or several times) per frame
 – Three structures instead of just one:
 – Entity List: stores all entities as a hashtable of entityId => Entity (and has ownership)
 – Entity Tree: Octree (or some kind of spatial structure) of cells / buckets containing a list
   of Entity references fully contained within that cell.
 – Pending Ops Queue: stores write operations until they are applied to the entity tree
   (thus all threads have safe, lock-free write access to the tree until the write / update step
   is started (which would be guarded by a global lock))
 – Fully parallel (and thus scalable) update operations
 – Much simpler code (~50% code reduction?)
 – Does not affect entity feature set
drawbacks:
 – All scripted entity operations become fully async (though if users don't like dealing with 
   REST / CRUD we could write a JS abstraction layer that gives you immediate operations, maybe 
   even similar to Unity's API (for example))
 - rewrite would be a fairly large project

Note: this looks more complex (more data structures), but it's really not. Compare Octree impl 
  + Entity tree impl + EntityOperator classes (which are probably an order of magnitude slower 
  than the following algorithm for updates), etc


How we would implement this:

Create operation:
would be done later during updates, but:
    insert entity into list (O(1))
    walk tree (O(lg(n))) + insert into the smallest existing cell that fully contains the entity
    tree balancing operations can be done later / in bulk

Read operation (from id):
    lock for read (if in write update, block until it finishes)
    get entity from list (O(1)) and return it (readonly)
    unlock
    
read operation (spatial):
    lock tree for read
    alloc list
    walk tree, adding all entities within bounds / spatial query to the list
    unlock + return list

Update operation:
    push operation onto pending updates (O(1))

Delete operation:
would be done later during updates, but:
    walk tree to find entity (O(lg(n))), delete w/ swap (O(1))
    remove entity from list (hashtable) O(1)    


Actual update / flush operations (done in bulk from the pending op queue)
    sort pending operations by entity id (sequential)
    - can be done using a hashtable of entityId => list of entity updates for that id
    - this is an O(n) traversal of the update list
    
    lock the tree for write

    for each entity w/ updates (parallel):
     – Walk tree to find current cell / node (this could be cached)
     - Apply updates (positional, properties, create / delete, etc)
     – if entity still exists, walk tree to find the cell it should be in based on position + bounds
        – readonly, so lockless
        - if done relative to current cell, this is very fast
     – if new cell != last cell, add this entity to:
        - deletion list for last cell (or if we got a delete operation)
        - addition list for new cell  (or if we got a create operation)

     for each cell in the tree (parallel):
        - resolve and clear add + delete lists
        - can use an O(n) algorithm that uses swaps
        – check load balance, and flag for split / merge

     rebalance tree:
        - split nodes that are flagged for split, and do so recursively until
        all are below threshold (parallel)
        – merge nodes by checking each leaf-with-only-child nodes for their child count,
        merging if they are below this threshold, and then adding their parents to the to-be-checked
        list (also parallel, but cannot be run at the same time as split)
     
     unlock the tree + continue w/ everything else