ECSQL

Introduction

This is the source code for ECSQL.

(inferior-lisp (file-truename "./ecsql"))

Tasks

Since we must rely on some piece of software for project management, we will use the most reliable one (in terms of longevity): Emacs.

Design

Basic ECS Architecture [4/4]

• State “DONE” from “TODO” [2024-03-12 Tue 13:03]

Automatically generated Entity IDs

• State “DONE” from “DOING” [2024-02-05 Mon 14:51]
• State “DOING” from “TODO” [2024-02-05 Mon 14:51]

• Simple generational ID system.
• Hash IDs to get indices so we don’t have to aggressively collect them like in Tecs.

Component “Ownership”

• State “DONE” from “TODO” [2024-02-14 Wed 17:15]
  Basically copied Mertens’s blog post; this isn’t an area of focus for the project.

• What components does an Entity have?
  • Array of Component IDs per archetype(?)
  • Something like Flecs: Each Component has a hash set of the archetypes that contain it, and provide an efficient facility to identify an Entity’s archetype.
• API for +/-?
• Don’t conflate data layout and Component type: Many Components may be a single number or vector, and it should be possible to treat them as such.

Component Storage

• State “DONE” from “DOING” [2024-02-14 Wed 17:16]
  We currently have a single dynamically allocated vector per Column, rather than chunks as originally planned. Making the switch would be moderately hard, and unlikely to have any apparent effect on performance, so we probably won’t bother.
• State “DOING” from “TODO” [2024-02-05 Mon 14:52]

• Archetype tables: Entity=row, Component data=column.

System Scheduler

• State “DONE” from “DOING” [2024-03-12 Tue 12:50]
  Most basic solution, done a few weeks ago.
• State “DOING” from “TODO” [2024-02-05 Mon 15:14]

• Fairly tangential to the premise of ECSQL, so either:

  Manual

  User code to specify the order of execution.

  Ordering Relation Tree

  As in Flecs.

  Order of creation

  Fine for non-rendering Systems.

ECSQL Language Specification [0/11]

• State “CANCELLED” from “DOING” [2024-03-12 Tue 12:51]
  See the doc string of the ecsql macro for what little of this was necessary. The interface is essentially a Lisp library, and the boundary between those and DSLs is blurry at the best of times.
• State “DOING” from “TODO” [2024-03-12 Tue 12:51]

• [ ] Create and delete entities
• [ ] Add and remove Components
• [ ] Display and edit Component data
• [ ] Entity/Component selection with Queries, based on the Entity relationships in the ECS design.
• [ ] Start and stop systems
• [ ] List running systems
• [ ] Component data transformation, via calls to Systems and functions
• [ ] System composition, and definition of new systems based on these compositions
• [ ] FFI to Systems written in host language
• [ ] Deferred event queue
• [ ] BNF grammar

BNF Grammar

<query> ::= (and <query> <query>*)
         |  (not <query>)
         |  (or <query> <query>*)
         |  (opt <query>) ; Optional
         |  (has <query>) ; Matches without loading data.
         |  <component>

<component> ::= <symbol>  ; An Entity/Component name.
             |  <integer> ; An Entity/Component ID.

<argument> ::= ?<symbol>  ; Query variable
            |  *          ; Wildcard
            |  <literal>  ; Matches with equal(p?) (ACL p. 318)

Many Languages

• State “CANCELLED” from “DOING” [2024-04-05 Fri 18:10]
  Didn’t have time for it.
• State “DOING” from “TODO” [2024-01-15 Mon 11:06]

If ECSQL is implemented with heavy use of macros, a relatively small amount of additional work would be necessary to also implement more languages that may work with ECS. Our ideas are as follows:

Story/Dialog System

Conversation trees could be implemented quite naturally as a Lisp DSL, containing arbitrary calls to Lisp code for conditions like “has the player got the macguffin?”.

Text Markup

Allow arbitrary tree structure for pieces of text, with basic bold and italic markup. E.g:

("This is something I" (_ "have") "to see.")
(say npc-jeff
 (if (has player macguffin)
     "My macguffin! Please return it."
   "I need someone to find my macguffin..."))

This snippet includes a check using the has predicate, which could be generated by ECSQL based on a relationship with the same name.

Scene Tree

Inspired by Flecs, it would be convenient to represent the entire state of a game as list structure, especially for (de-)serialisation.

Graph/Data Flow Language

On Mertens’ wish list; probably easy to represent a graph structure as Lisp data, could help to justify extreme slowness, quite novel.

Lisp Compiler Target

• State “DONE” from “DOING” [2024-01-26 Fri 15:36]
  Just do the naive interpreter, unless we are done done, with everything else, very early.
• State “DOING” from “TODO” [2024-01-26 Fri 15:36]

Options:

Naive Interpreter

Potentially useful for testing and bootstrapping purposes.

LLVM IR

Advantages	Disadvantages
Native speed	Complex C++ API, incomplete C API
Intrinsics	A large, heavy dependency
Familiarity	Not for the C API
Phi nodes

Own bytecode

Advantages	Disadvantages
Fewer dependencies	Slower
	Lots of irrelevant problems

LibGCCJIT

Advantages	Disadvantages
GNU	Unfamiliar
Very simple(?)	No Phi nodes
Similar to LLVM	Limited documentation
C is primary API
Primarily intended for JIT(?)

The lack of Phi nodes is notable because they fuse the results of branches in an expression. We may be able to hack them on top of the conditional and switch instructions.

Compiler Architecture

• State “DONE” from “DOING” [2024-01-26 Fri 15:36]
  Evaluator. See *Lisp Compiler Target.
• State “DOING” from “TODO” [2024-01-26 Fri 15:36]

1. Reader (lex + parse): Output is already Lisp data!
2. Lisp → Stack Machine:

   (label
    (push 5)
    (push 4)
    (call + )
    (return))
       

   • As in Queinnec. Probably the most complex part, and it can be totally backend-independent!
   • Stack machine has a limited, but non-trivial instruction set that should easily map to libgccjit or LLVM IR, notably including (variadic) function calls.
   • CFG form(?)
   • Maximum stack depth in each function is known statically (deepest expression nesting level).
3. Evaluator: libgccjit or simple interpreter.

Demo Application

• State “DONE” from “DOING” [2024-03-12 Tue 12:58]
  Extended version of evaluation day demo.
• State “DOING” from “TODO” [2024-02-20 Tue 10:39]

• 2D Raylib game

Asynchronous REPL

• State “DONE” from “DOING” [2024-03-12 Tue 12:57]
  Done a while ago, in the dumbest way possible.
• State “DOING” from “TODO” [2024-03-12 Tue 12:57]

We want the game to progress and have the REPL available simultaneously, without blocking either.

Problems:

• Lexer uses a global, static buffer for reading in lexemes, which is not thread-safe (easy).
• Lisp memory allocation (medium).
• Namespace/environment access etc (hard-ish: what is “etc”?).
• ECS, in general, is not thread-safe.

Goal:

• Main game loop is mostly normal, running a set of Systems and refreshing the screen each frame.
  • Can call into Lisp(?), perhaps only via a special Lisp callback System.
• REPL available simultaneously. Once a complete sexp is read, the input Lisp form is evaluated, perhaps on the next frame, and the result is printed out.

Options:

• [ ] Single threaded with non-blocking I/O.
  • Use non-blocking stdio for the reader (unlocked_stdio(3)), and dispatch to Lisp as soon as a complete sexp is read.
  • Relies on non-standard (POSIX) functions
  • Potentially unpredictable
  • Complex to structure(?) since we need to repeatedly call the reader polling function.
• [ ] Basic locking: Allow simultaneous threads, but acquire a lock to allocate memory, add to a namespace etc.
  • Extreme false dependencies and high contention, since current Lisp implementation conses continously to evaluate code, leading to slower, serial execution regardless.
  • Hard to be sure all thread-unsafe operations are locked properly.
  • Could be viable if we replace the evaluator with a bytecode VM that conses less during execution, but we don’t have time for that now (<2024-02-20 Tue>).
• [ ] Lisp command event queue (cite: http://gameprogrammingpatterns.com/event-queue.html)
  • Game code and REPL send Lisp expressions to the event queue to evaluate, with a single thread receiving events and executing them.
  • Problematic since generating expressions (e.g. while parsing) requires consing, so we may need locked cons.
  • Callers often want the result of the expression, so they would need to block until their expression was evaluated.
• [X] Global Lisp lock: Public expression evaluation API acquires a lock stored in the LispEnv for the duration of evaluation, then releases it.
  • Could greatly increase complexity of existing code if all public APIs must include locking.
  • A fixed, finite number of places where locking happens (Lisp System wrapper System, REPL) makes this feasible.
  • REPL must be written in C.
• [ ] Pause the game to run the REPL, or any Lisp code (giving up):
  • Possibly suitable if I spin it right.
  • Main viable option for evaluation day (<2024-02-21 Wed>).

“Safe” Component +/- in Systems

• State “CANCELLED” from “DOING” [2024-02-20 Tue 23:23]
  Definitely a distraction
• State “DOING” from “TODO” [2024-02-20 Tue 23:19]

• Deferred change queue
• Due to the way (cached) queries work, we can probably add an Entity to an archetype immediately, and put the new Component data in the storage allocated for it there.
• Removals are what could lead to “dangling” references, so we can get mostly correct behaviour by immediately updating everything so the Entity “is in” the new Archetype, but not removing it from the old archetype until, for example, the System finished executing.

Automated Join/Outer Product/N-wise operations

• State “DONE” from “DOING” [2024-02-28 Wed 16:29]
  Implemented sufficiently in run_matching_self_join_systems, and associated Components.
• State “DOING” from “TODO” [2024-02-28 Wed 16:29]

• Classic example: Collisions
• Easier if user code is restricted to a specific pair of Entities, but that comes at the cost of efficiency.
• Current implementation uses plain indexable arrays for the iterators, but it may be possible to manipulate these to handle pairs properly.
• The “hard” problem: Iterating distinct pairs of Entities (i.e. (a, b) and (b, a) should not both occur, and perhaps no (a, a)).
• Doing an outer product on two distinct archetypes is easy: just pass 2 iterators to the user code, and all pairs are distinct.
  • This is the common case, even when joining a query on itself (as in collisions).
• Can and should this be generalised to N-way outer products?
  • I’ve only had the occasional need for pairwise operations. Operations on 3 or more Entities at once may either be represented as pairwise interactions between all Entities involved, or involve another mechanism to get at all the Entities in a sensible way.
  • Probably not.

Implementation

Lisp Interpreter [14/14]

• State “DONE” from “DOING” [2024-02-05 Mon 11:04]
  We have now implemented a sufficient interpreter to do some higher-level ECS stuff with macros, though that depends on having the ECS itself, so the primary Lisp implementation is done.
• State “DOING” from “TODO” [2024-02-05 Mon 11:04]

Lexer

• State “DONE” from “DOING” [2024-01-11 Thu 18:11]
  
  • Decided against active UTF-8 support, but it would probably work.
  • Treat @ as a stand-alone Token. The parser can easily “look ahead” when it gets a , to see if it should be a normal or splicing unquote.

• State “DOING” from “TODO” [2024-01-11 Thu 14:49]

• [X] Token type
• [ ] UTF-8

This either needs to operate on a string buffer in memory, or a FILE*. There are platform-dependent ways to access a string buffer as a FILE*, and many platform-independent operators for FILE*’s, so we will use FILE*.

Lisp Object Physical Representation

• State “DONE” from “DOING” [2024-01-15 Mon 10:26]
  We found a reasonable compromise representation.

• State “DOING” from “TODO” [2024-01-11 Thu 18:18]

• For this, consider 64-bit integer boxing.
• Notable: There are 12 unused bits in Mertens’s Entity representation, and we can probably shave off a few bits from the generation and Entity, so this could fit inside a NaN box!
• Queinnec: p. 391, tinylisp: p. 7-9

I need a representation for Lisp objects that is simple enough to manipulate inline with generated LLIR, and reasonably efficient.

Constraints/Requirements

• Must represent the following:
  • Standard Lisp types:
  • Vectors (ideally):
  • Entity IDs and relations (require c. 50b):
  • User-defined structs: Pointer to storage, getters, setters; Use the getelementptr LLIR instruction.
  • Archetypes:

  The question is how many of these must be hard-coded into the object representation. If a fundamental structure like Entity IDs can fit into an object inline, that allows some decent optimisation of how generated code can handle them.

• 64 bits: Biggest easily moveable size.

NaN Boxing

• tinylisp/van Engelen
• 51 bits for non-float values

Pointer/Int Boxing

• Queinnec, p. 390.
• LSB 1 → integer in upper 63 bits
• LSB 0 → pointer to object union.
• The pointer value is aligned, since the pointee is a large object, so 2+ LSBs are 0. The rest of the LSBs can store type info.
• Pointers can be used as-is, but getting the type for non-integers requires a separate memory read. Given the cost of memory access is orders of magnitude greater than individual instructions, we should include all such metadata in the immediate value, even if it is more work to extract.

Considerations for my version

• If we need even fewer than 63 bits, we can store more than just integers inline.
• If addresses are indices into the Lisp memory pool (useful for relocation, etc.), 32- or maybe 48-bit integers would be sufficient, and we don’t rely on pointer alignment, so the exact position of the bits is of less concern.
• The type recognition scheme needs to be simple and non-branching, since it will need to run almost continuously.
• 5 bits for Lisp type tag, to ensure we don’t run out.
• Definition: An immediate value contains its data, as opposed to an indirect value. The NaN-boxed address in Lisp memory is the representation for indirect values.

Discussion: Do the Entity ID types need to be explicitly in the types?

• If they are immediate, Lisp code can manipulate their contents highly efficiently.
• This could be achieved equally well by storing them in the integer type, right?
• Making them first-class was a primary justification for me building my own Lisp at all.
• With them built-in, we gain some protection from user input, since they can’t so easily supply a garbage integer value: Entity IDs can only be generated by the system itself.
• Cost of “blessing” them: Complexity?
• Poor unity of purpose having 5 possible immediate meanings?

NaN-Boxed

+-------------------------------+-----------------------------++
<-------------------- Double  (62b)----------------------------> Value is a valid double as-is!
s111111111111<--------Arbitrary Data Goes Here (46b)------><typ> QNaN boxed. Type
s111111111111<-------Entity (27b)------><---Gen (16b)--><-><typ> Type Flags (c. 3b)
s111111111111<--Comp/Rel T ------(27b)-><-- Rel  (16b)-><-><typ>

Undesirable:
<---------------Integer (63b)--------------------------------->1

Non-NaN-Boxed

NaN-boxing incurs an excessive overhead, which especially hurts the Entity ID representation due to Mertens, which is already squeezed tightly into 64 bits, especially for relation pairs. A 5-bit Lisp object type tag should be sufficient to represent all fundamental types in the language, while leaving plenty of space for immediate values.

+-------------------------------+-----------------------------++
<----------------------Data (59b)-------------------------><typ>
<-------Entity (32b)-----------><---Gen (16b)-->0000000<*-><typ> *Entity type flags (4b)
<--Comp/Rel T ------(32b)------><---Relation (23b)----><--><typ>
<----------------------Integer (59b)----------------------><typ>
<----------------------"Double" (64b)---------------------><typ>
<-----------Index   (43b)-----------------><-Metadata(16b)><typ>

Our double type could be handled specially: the 5 type bits align with the LSBs of a double’s mantissa. To get the represented value, we will mask out the type bits instead of shifting. This allows us to represent the full range of doubles, with only a moderate loss of precision. In reality, it will be easier to just box a 32-bit float normally, since these are the standard in games anyway.

We only have 23 bits for Entity relationships, but this still allows 8,388,608 different relationships to be represented, which should be plenty.

A lot of object values will contain a “pointer” to Lisp data (more likely an index), which may need to be accompanied by some metadata. The pointer size places an upper bound on how large Lisp memory can be (including the overhead of uncollected garbage), so we allocate an excessive 43 bits to it. The metadata will often be the length of a slice type (e.g. for arrays), which may not necessarily be in units of Lisp cells (e.g. for strings).

Pointer+length objects are called fat pointers, and provide numerous benefits such as creating slices of arrays without having to move the data.

Strings and symbols should probably be handled differently to keep things efficient.

The bare essential built-in types are:

• [X] Integer
• [X] Double
• [X] String
• [X] Symbol
• [X] Pair
• [X] Primitive function
• [X] Closure (lambda)
• [ ] Compiled Closure(?)
• [X] Fixed-length vectors(?)
• [X] Struct

We initially used a simple typedef for the Lisp object type, but this was error prone, since C was allowing implicit conversions between integers and Objects, which were invalid. We replaced this with a complex union with bit fields, immediately revealed a large number of such invalid conversions (<2024-02-08 Thu>).

Actual Implementation

+-------------------------------+-----------------------------++
<----------------------Data (59b)-------------------------><typ>
<-------Entity (32b)-----------><---Gen (16b)-->00000000000<typ>
<--Relation Target--(32b)------><---Relation (23b)----><--><typ>
000000000000000000000000000<--------Integer (32b)---------><typ>
000000000000000000000000000<---------Float (32b)----------><typ>
<-----------Index   (43b)-----------------><-Metadata(16b)><typ>

Mark-Sweep Tricolour Representation

+-------------------------------+-----------------------------++
<----------------------Data (59b)-------------------------**<ty>
<-------Entity (32b)-----------><---Gen (16b)-->0000000000**<ty>
<--Relation Target--(32b)------><---Relation (23b)----><->**<ty>
00000000000000000000000000<---------Integer (32b)-------->**<ty>
00000000000000000000000000<----------Float (32b)--------->**<ty>
<----------Index   (42b)-----------------><-Metadata(16b)>**<ty>

• The ** bits are used to store the mark value of an Object in Lisp memory: black, grey or white.

Scope, Namespaces etc.

• State “DONE” from “DOING” [2024-01-26 Fri 12:13]
  
  • We have created a trivial implementation of Lisp-3 (variables, functions, macros), with lexical scope for variables and only global scope for functions and macros.
  • Macros are implemented simply as closures.
• State “DOING” from “TODO” [2024-01-22 Mon 10:31]

• Lexical
• Lisp-1?
  • Lisp-1 is more conceptually elegant, but Lisp-2 may be easier/more efficient to compile.
• There’s a question of how to implement scopes. If they aren’t needed at run-time, it may be acceptable to use a naive alist structure.
• Conceptually pure approach: Only implement local/lexical binding through lambda parameter lists, though this requires either Lisp-1 or the “special case” first-position lambda of Common Lisp.
• Variable-length argument lists are a similar consideration: An actual Lisp list in the “AST” can easily be converted to a variable-length argument pack in libgccjit. On the other hand, in real Lisps, variable argument lists are treated as actual lists by the callee too, so the obvious solution may be sufficient.
  • Solution: Put all the arguments into a list, and for variable-length argument lists, make the “rest” parameter the cdr past a certain point.

Memory Allocation

• State “DONE” from “DOING” [2024-01-22 Mon 10:31]
  Garbage collection is actually quite low-priority, so we can defer it until we know we have time for it.
• State “DOING” from “TODO” [2024-01-22 Mon 10:31]

• Allocate in increments of 64-bit cells?
• The directly referenced values of global variables can be placed in a “static” data store, though this is a small optimisation.

Copying GC

• State “CANCELLED” from “TODO” [2024-01-26 Fri 15:37]
  Leaking into a 1GB+ buffer is fine, since GC isn’t relevant to the project concept.

Pure C Parser

• State “DONE” from “DOING” [2024-01-22 Mon 10:35]
  Actually implemented reader macro support with function pointers. It should be possible to write new ones as compiled functions.
• State “DOING” from “TODO” [2024-01-22 Mon 10:34]

• [X] List structure
• [X] Literals
• [X] ', `, ,, ?
• [ ] ,@: Requires more context, and quite niche: won’t do.

[#C] Parser with Macros

• State “DONE” from “DOING” [2024-01-22 Mon 10:37]
  See *Pure C Parser.
• State “DOING” from “TODO” [2024-01-22 Mon 10:37]

Macros are a productivity multiplier that may prove necessary in order to complete the project on time.

[#B] Splicing Unquote

• State “CANCELLED” from “TODO” [2024-01-26 Fri 12:10]
  We can use the dot operator to get most of the benefit of this with no extra work:
  • `(some things are so . ,(or 'cool 'lame))
  • (some things are so cool)

• This feature is essential for the ergonomics of a macro system.
• If not implemented “properly” as a reader macro, it would be easy enough to hard-code it into a pure C reader.

[#C] Read Macros

• State “DONE” from “DOING” [2024-01-22 Mon 10:38]
  See *Pure C Parser.
• State “DOING” from “TODO” [2024-01-22 Mon 10:38]

Code Generation

• State “CANCELLED” from “TODO” [2024-01-26 Fri 15:38]
  Not doing a compiler.

[#C] Optimisations

• State “CANCELLED” from “TODO” [2024-01-26 Fri 15:38]
  We don’t care about performance.

• Just turn on the feature in the code generator.

REPL

• State “DONE” from “DOING” [2024-01-26 Fri 12:06]
  Could be implemented in Lisp instead of C, but this periodic movement of control back out of Lisp is a good opportunity to perform garbage collection since the Lisp stack is empty at that point, so we only need to use global variables as roots.
• State “DOING” from “TODO” [2024-01-22 Mon 10:32]

Basically necessary to the way Lisp should function, including macros.

• [X] Read
• [X] Eval
• [X] Print: This will need extension every time we add a fundamental type, but
• [X] Loop

Error Handling

• State “DONE” from “DOING” [2024-01-26 Fri 12:05]
  Simplistic error message + longjmp is quite sufficient.
• State “DOING” from “TODO” [2024-01-22 Mon 10:59]

Ideally this should be entirely handled by the wrong function. Options:

• [ ] Invalid type/error object (de facto approach)
• [X] setjmp/longjump

[#C] LValues

• State “CANCELLED” from “TODO” [2024-02-05 Mon 11:02]
  This would introduce a very un-Lispy complication to the implementation.

• (setf place value): place must be an lvalue.
• In C/libgccjit, lvalues are a subkind of rvalues (normal values).
• Issues:
  • Can’t have references to globals, outside Lisp memory.
  • Potential efficiency cost, especially for struct accessors.

Struct Types

• State “DONE” from “DOING” [2024-02-14 Wed 17:11]
  Lisp can now generate struct types that should have the same alignment and padding as equivalent C structs (same member types, in the same order).
• State “DOING” from “TODO” [2024-02-12 Mon 15:54]
  We need to amend this slightly so we can work with packed, C-style struct data.
• State “DONE” from “DOING” [2024-02-05 Mon 11:02]
  Implemented in Lisp as far as possible (only using C to manipulate internal representations), with simple 1-cell alignment/size for all primitive types.
• State “DOING” from “TODO” [2024-02-05 Mon 11:02]

• Use libgccjit’s structs for reflection etc.

Requirements:

• [ ] Getters
• [ ] Setters: Do we attempt “generalised variables”? No.
• [ ] Field types: All fundamental types, or struct types(?).

Lisp Representation:

Storage

Vector, each member (which must be of the provided typespec, checked by lisp_type_spec_matches) in a cell.

Name

Symbol, bound in the function namespace as a constructor(?).

Definition

As below:

(defstruct v2
  (x f32)
  (y f32))

(defstruct player
  (rotation f32)
  (name string)
  (pos v2)) ; Recursive structs

(defvar a
  (make-player 90.0 "Aidan" (make-v2 -20.0 42.1)))
=> #*player(90.0 "Aidan" #*v2(-20.0 42.1))

(player-name a)
=> "Aidan"

(set-player-pos-x a 99.9)
a
=> #*player(90.0 "Aidan" #*v2(-20.0 99.9))
    

API

As below:

(node-car (make-node 'a 'b)) ; a
(set-v3f-x v (+ 1 (v3f-x v)))
(set-physics-pos-x player (+ 1 (physics-pos-x player)))
(set-physics-vel player (make-vector 2 2 2))
    

Single Inheritance

Possibly useful idea: Same members and interface as another struct, but considered a distinct type by Lisp.

• Could be as simple as physically splicing in the struct member list from the parent class and dispatching to normal defstruct.
• Include a cast to the base class.
• Not in the spirit of, or relevant to, what we are doing.

ECS [7/7]

• State “DONE” from “TODO” [2024-03-12 Tue 13:02]

Entity IDs

• State “DONE” from “DOING” [2024-02-09 Fri 12:45]
  23-bit unsigned integers.
• State “DOING” from “TODO” [2024-02-06 Tue 14:07]

Component Store

• State “DONE” from “DOING” [2024-02-09 Fri 12:52]
  As explained by Mertens, the implementation is the same with or without relations.
• State “DOING” from “TODO” [2024-02-06 Tue 14:07]

Lookup Archetype by Component List

• In Mertens’s blog post, which introduces a basic archetype-based Component store, he uses C++ stdlib sets and maps, which support hashing stdlib data structures, notably including hashing arrays of Components to access the correct Archetype. We have been using khash for sets and maps, and it only supports hashing integers and null-terminated strings.
• Mertens explains that array hashing is too slow for operations like adding or removing one Component in a hot loop: when is the Component[] → Archetype map actually useful?
• Extend khash to support hashing arrays? This sounds like a disappointingly brute-force solution.
• Naively store Archetypes in an array and search for them? This could yield O(n^2) lookup to find the Archetype for a particular Component set, if implemented poorly.
  • This “direct” access is exceptional anyway, so don’t worry about it being slow!
• One solution could be to limit Component IDs to [1, 255] and actually store them in null-terminated strings, but we want to implement relationships, and Entities as Components, so we need 32-bit Component IDs (since they are equivalent to Entity IDs).
• Traverse the Archetype graph by “adding” 1 Component at a time?
  • Doesn’t require direct access to the Component list.
  • Requires a path from the empty Archetype to every other, wasting memory for the many unused Archetypes.
  • Effectively O(n) linked list traversal, vs O(n) array hashing. This could be amortized if Archetype references are reused for creating many Entities.
  • This needs to be built initially, however.

Columns and Alignment

• State “CANCELLED” from “TODO” [2024-02-09 Fri 12:51]
  C automatically pads structs to ensure alignment, so we must solve any problems with alignment in struct.lisp.

• Columns store Component data in packed byte vectors, so it’s possible we could have alignment problems. A solution would be to add an alignment parameter for registering Component data blocks.

Bootstrapping Process

• It’s a nice idea to use a “Component Storage” Component to store the alignment and size of a Component, but it makes the initial setup a little awkward, since we need to add it to itself.
• Our solution is as follows:
  1. Create the “Component Storage” Component/Entity (it will go into the empty archetype),
  2. Create the Archetype for Entities with only the “Component Storage” Component, manually specifying the storage parameters in its only Column (which contains the Component Storage data),
  3. Add “Component Storage” to itself, with the appropriate data values.
  4. For all Subsequent Components with storage, simply add the “Component Storage” Component and it will just work™.

Queries

• State “DONE” from “DOING” [2024-03-12 Tue 12:59]
  
  • Single-entity queries in C & Lisp,
  • Pairwise queries in C.

• State “DOING” from “TODO” [2024-02-15 Thu 10:42]

The general API needs to be something like: Predicate → Archetype[]

Archetype Iteration Mechanism

• State “DONE” from “DOING” [2024-02-20 Tue 12:10]
• State “DOING” from “TODO” [2024-02-20 Tue 12:10]

We need to be able to efficiently iterate over all the Entities in an Archetype.

Query Representation

• State “DONE” from “DOING” [2024-02-20 Tue 22:42]
  See *Query Result Representation
• State “DOING” from “TODO” [2024-02-15 Thu 10:42]

• Queries may reasonably take the form of Lisp list structure.
• The syntax of Queries is partially defined in design.org in the cs310-project repository.

Query Result Representation

• State “DONE” from “DOING” [2024-02-20 Tue 22:42]
  Straightforwardish, kept abstract to make future changes easy.

• State “DOING” from “TODO” [2024-02-16 Fri 15:57]

• This informs the capabilities of the query system.
• Generality vs Efficiency?
• How do results and generated Lisp code (with bindings) match up?

Single-archetype queries:

struct QueryEntry {
  ArchetypeID archetype;
  /* What column each matched Component with storage is in.
   * The alternative is doing a lookup per Component per Archetype,
   * which could be alright if fragmentation is low. */
  size columns[];
};

Multiple-archetype Queries:

struct QueryEntry {
  ArchetypeID archetypes[];
  /* The Lisp macro or C system author should statically know what archetype to
   * use for each column index lookup. */
  size columns[];
};

Lisp Interface

• State “DONE” from “DOING” [2024-03-12 Tue 12:58]
  See select and ecsql in query.lisp.
• State “DOING” from “TODO” [2024-03-12 Tue 12:58]

Systems

• State “DONE” from “DOING” [2024-03-12 Tue 12:59]
  
  • Straightforward approach taken.
  • System data is stored as Components.
• State “DOING” from “TODO” [2024-03-12 Tue 12:59]

• Iteration over Archetypes:
  1. User supplies a function to the ECS.
  2. The ECS calls that function once for each matched (set of) Archetype(s)

[#C] Relationships

• State “DONE” from “DOING” [2024-02-28 Wed 11:31]
  We have a very dumb form of relationships, e.g. no wildcards, but we’re at the point of dimishing returns for this feature that is tangential to the focus of this project.
• State “DOING” from “TODO” [2024-02-09 Fri 19:19]

• Is this essential?
• What is the simplest form of relationships I could implement?

Mertens’ Roadmap, Culled

https://ajmmertens.medium.com/a-roadmap-to-entity-relationships-5b1d11ebb4eb

Mertens describes the first 5 steps as sufficient to produce a rudimentary implementation of relationships, with an estimated time to implement of 16 weeks.

1. [X] Components as entities
2. [ ] Observers
3. [X] Relationship pairs in archetype storage
4. [ ] Relationship component data storage: Flecs makes this highly complex with a sequence of rules that are tried. We can probably find a “worse” compromise set of rules, or exclude this feature altogether. Example compromise rules:
   1. Never create storage for the first element.
   2. Create the storage for the second element iff it’s a non-tag type:
      • e.add(apples, eats, {2})
      • e.add(parent, childOf)

   Or:

   1. Include a tag bit in the pair representation.
   2. Associate with type of first element, iff tag bit is 0.

   This might not work, since that tag bit isn’t representable in the Query DSL syntax:

   • (child-of parent),
   • ((eats 2) apples)

   In any case, we can simply add any data we want to one of the entities in the relationship.

5. [X] Wildcard queries: Looks impressive, and Mertens doesn’t even consider it especially hard, at “merely” 2 weeks.
6. [X] Component index
7. [ ] Cleanup: Important, but we must find a simplified approach if we are to consider implementing it.
8. [ ] Cleanup Traits
9. [ ] Multi-source queries
10. [ ] Relationship traversal
11. [ ] Query cache revalidation
12. [ ] Breadth first traversal
13. [ ] Uncached queries
14. [ ] Multi component observers
15. [ ] Event propagation
16. [ ] Empty table optimisation
17. [ ] Garbage collection
18. [ ] Rule engine
19. [ ] Exclusive relationships
20. [ ] Inheritance
21. [X] Query DSL

My Approach

• For starters, relationship components seem like a mostly unnecessary feature.
• How much could we hand off to a working Lisp implementation?
  • Notably, garbage collection?!
• Value trade-off of allowing an Entity to have the same relation to two distinct Entities?
  • Better to allow it.

[#A] Lisp API

• State “DONE” from “DOING” [2024-03-12 Tue 13:00]
  Pretty nice, with a whole load of macros.
• State “DOING” from “TODO” [2024-02-14 Wed 17:13]
  Current implementation: (set-v3-x (ecs-get player Velocity) 3)

• We should provide a flexible API, so new features/applications can be built entirely in Lisp.
• Is a Lisp callback API (“for each Entity”) sensible? Does a facsimile crafted with macros make more sense?
• Need to find a good way to make it terse: Lisp code interfacing with strong types can quickly become annoying to read and write:
  • Bad: (set-x (get-vec (get-velocity entity)) 3)
  • Better: (setf (x (velocity entity)) 3)
  • Better still: (setf (x velocity) 3), with velocity bound as an “lvalue” with macro/codegen sorcery.
  • (setf velocity [3 0 0])
• Trying to produce a nice API like one would have in C may be the wrong approach: Allow the C plumbing API to be awful, and build nice ones on top of that?

Accessing ECS Data from Lisp

• State “DONE” from “DOING” [2024-02-14 Wed 17:14]
  We chose option 1, since it was so simple to implement. Since the implementation exists just in the definition of Object and lisp_cell_at, we can easily change it later if necessary.
• State “DOING” from “TODO” [2024-02-14 Wed 17:14]

• The first, most basic problem is that ECS data isn’t stored in, or aligned to, Lisp memory.
• Can’t store Columns in Lisp memory since GC they need fairly frequent, large allocations, which wouldn’t be friendly to our “garbage collection strategy”.

Options:

1. Store pointers in Lisp memory and use double indirection
   • Inefficient(?), but easy to implement.
     • Possibly not so inefficient if we’re iterating over arrays?
   • Need to keep track of the type.
   • Implicit assumption that structs are at least 64-bit aligned?
     • Hopefully not necessary (appeal of double indirection)
   • Can’t store raw pointers for “a long time”, since Columns (and Archetypes) may get reallocated.
   • Possible implementations:
     • Add a flag bit to index boxes that indicates extra indirection, or a small number (2-4 bits) to indicate the number of times to indirect?
     • Negative indices indicate 1 level of indirection.
       • Breaks the assumption that we can simply add to an index to get an index for data at that offset, “for free”, but that was probably incorrectly API use to begin with. It was a mechanical fix to handle these cases properly.
2. Store Columns next to Lisp memory, and just use indices that reach out to them.
   • Error prone, and won’t work with data at less than 64 bits of alignment.
3. Support LValues
4. Custom addressing mode (not based on boxed indices) for Entities.
   • E.g. boxed tuple: (ArchetypeID, Column, Row, Offset/B)
     • Tight squeeze
     • 16 + 16 + 16
   • Greater complexity, and creates a hard distinction between structs inside and outside Lisp memory.

Structs and Components

• State “DONE” from “DOING” [2024-02-19 Mon 14:33]
  Just used existing Lisp struct reflection mechanism.
• State “DOING” from “TODO” [2024-02-07 Wed 17:38]

• It should be possible to implement Lisp structs in such a way that they blend with the ECS. Mertens proposes an approach to this.
• Struct metadata relation:
  • Name (symbol?) & type per struct member. This would be the maximally ECS’d option.
  • Reference to an entry in my existing Lisp struct metadata table. This may require less work, but isn’t as conceptually elegant.

Struct/Component Reflection Data in the ECS

As described by Mertens, have a “Struct” Component that contains reflection data. Adding it to a Component Entity associates that reflection data with the data stored for that Component type.

Reflection data includes:

• Size of the whole Component,
• Alignment of the whole Component,
• Information about sub-structure.

The ECS itself only needs the size and alignment for manipulating Component data: it just works with bytes and pointers. The information about sub-structure is only needed in Lisp. Sub-structure means the set of struct members, and the following information about each:

• Offset from the start of the struct,
• Type: A Component, with its own Reflection data Component(s)
  • Size,
  • Alignment,
  • Name,

A bar to hit for supporting general and useful structures could be to support structs that contain structs. Alternatively, we could rigidly require that a struct only contains primitive types, and use separate Components to group them together. That would probably be unnecessarily restrictive, and there are many plausible Components such as “Transform” that would contain multiple vectors/matrices for position and orientation.

Utility DSLs [3/3]

• State “DONE” from “DOING” [2024-03-12 Tue 13:02]
• State “DOING” from “TODO” [2024-03-12 Tue 13:02]

ecsql

• State “DONE” from [2024-02-28 Wed 11:33]

• Dispatch a query once, and run some code a single time on each result.

ecs-new-system

• State “DONE” from “DOING” [2024-02-28 Wed 11:34]
• State “DOING” from “TODO” [2024-02-28 Wed 11:34]

• Take a Query, function, and set of Components to add to a new system, that is immediately created and can start running in the game loop.

Scene Definition Macros

• State “DONE” from “DOING” [2024-03-12 Tue 13:00]
  Done a few weeks ago, and extended

• State “DOING” from “TODO” [2024-02-28 Wed 11:36]

Short-hand macros to make it easier and quicker to define (and manipulate) initial scene data.

• [X] ecs-add*
• [X] ecs-create

Documentation

• State “DONE” from “TODO” [2024-03-12 Tue 13:01]
  We implemented docstrings, with user-specifiable and auto-generated documentation for most notable Lisp code.

Garbage Collection

• [ ] Use mark-sweep collection so we don’t have to modify Objects.
• [ ] Use Mark-Sweep Tricolour Representation for Objects.
• [ ] Use a “contexts” array in LispEnv to keep track of live evaluation contexts.
  • Allocate a new context in eval, and deallocate at the end.
  • Could possibly work as (a) stack(s), with some hacking.
  • The fact that wrong sort of “works” with the hard-coded assumption that there’s always a single correct error_loc, we can probably hack it to make sure contexts are cleaned up properly.
    • [ ] Properly handle errors in Lisp run in the main game thread?
• [ ] Generate an array of (# objects) offsets into struct types where Objects are stored.
• It might actually be easier to fully commit and implement explicit support for multiple concurrent Lisp threads.

Tracking Execution Contexts

Options:

• Pass a reference to the contexts array around the evaluation functions
• Use an execution context wrapper struct (holding said reference)

Improvement Ideas

• Lisp system function argument list can be constructed once, with stored pointers at known places
  • Modify the stored pointers (+= sizeof(Component)) for each iteration

Development Notes

Recurring Bugs

Junk in unused bits of Object

• For consistency, unused bits of an Object should be zeroed.
• This ensures that two Objects that store the same value are bit-for-bit identical, so we can use the cheap C == operator to implement (eq) in Lisp.

Evaluation Day Survey Results

• Survey: https://docs.google.com/forms/d/1vUGaDhqMAvydt-CoOt62zEJN7ihMKbf38fNVJE4KdlI/edit
• We only got 0-2 responses per question, with the only helpful suggestion being adding documentation or a tutorial to make the system easier to use.

The Need for Garbage Collection

At the time of writing (<2024-03-01 Fri>) the system consumes 8GB of memory at 60FPS in 5 minutes, which is not long enough for the demo. Considering the functionality of the system is mostly complete, we can now strongly consider implementing a garbage collector.