Witness-Based Lightweight Generics (WLG)

[Eudox67]

DISCUSSION/PROPOSAL TO FIX GENERICS

The current Generics implementation in Free Pascal (FPC) utilizes a "Template Expansion" model. While providing high performance for specific types, it results in substantial binary bloat and prolonged compilation times due to code duplication. I am asking for the consideration of a Witness-Based Lightweight Generics (WLG) system. By utilizing implicit dictionary passing (Witness Tables), the compiler could generate a single binary implementation for generic procedures, using specialize only as a metadata-binding instruction rather than a code-generation trigger.

---

1. The Technical Philosophy

1. Code Sharing (Railing): All specializations of reference types (classes, interfaces) share a single physical implementation.
2. Witness Tables: For value types, the compiler passes an implicit pointer to a record containing type-specific logic (Size, Copy, Compare).
3. Preservation of specialize: The keyword is retained to maintain one-pass compilation efficiency and explicit type safety, but its backend behavior is transformed from "Copy-Paste" to "Link-and-Bind."

---

2. The Architecture

2.1 The Witness Table (Internal)

The compiler implicitly defines a structure for every T involved in a specialization.

type
  TWitnessTable = record
    TypeSize: PtrUint;
    OpAssign: procedure(Dest, Src: Pointer);
    OpCompare: function(A, B: Pointer): Integer;
    OpFinalize: procedure(P: Pointer);
  end;
  PWitnessTable = ^TWitnessTable;

2.2 Polymorphic Implementation

The body of a generic function is compiled into a "Railed" version. Instead of knowing type T, the machine code utilizes the PWitnessTable to manipulate memory.

---

3. An Example

3.1 Generic Definition

The definition remains standard Pascal, ensuring no declarations exist within the function parameters.

unit Generics.Lightweight;

interface

type
  generic TSimpleList<T> = record
  strict private
    FData: Pointer;
    FCount: Integer;
    FCapacity: Integer;
  public
    procedure Add(const Item: T);
    function GetItem(const Index: Integer): T;
  end;

implementation

{ The compiler generates ONE version of this code }
procedure TSimpleList.Add(const Item: T);
var
  Target: Pointer;
  Witness: PWitnessTable;
begin
  { Implicitly handled by compiler: Witness := GetWitness(T) }
  if FCount = FCapacity then
    // Resize logic using Witness^.TypeSize ...
    
  Target := FData + (FCount * Witness^.TypeSize);
  Witness^.OpAssign(Target, @Item);
  FCount := FCount + 1;
end;

end.

3.2 Specialization Site

The specialize keyword now acts as a linker directive.

var
  IntList: specialize TSimpleList<Integer>;
  ByteList: specialize TSimpleList<Byte>;

Compiler Action:

• Generate a Witness Table for Integer.
• Generate a Witness Table for Byte.
• Map all calls to IntList.Add and ByteList.Add to the same memory address of the shared implementation.

---

4. Formal Considerations and Rules

1. Parameter Declarations: Consistent with strict Pascal, function parameters must be predefined types or generic placeholders. No inline declarations allowed.
   Why: Generics rely on Type Identity. If the compiler allows inline type declarations in the parameter list of a generic specialization, it becomes nearly impossible to verify if two specializations are identical.
2. Constant Definitions: Constants within generic blocks must be literal or derived from base types. They cannot be defined by variables or non-static constants.
   Why: In Pascal, a const is often treated as a "true" constant (substituted at compile time). If a constant within a generic is allowed to be defined by a variable or a non-static result, it becomes a "read-only variable."
3. Variable Sections: Inline variables have been allowed in FPC Unleashed. For a good Generics implementation, this could be a complication. Generics with witness tables rely on the compiler knowing the exact memory layout of the stack frame at the start of a procedure. In a "railed" generic, the size of a variable var T is unknown at compile time. Allowing for inline variables like var x: T := ... halfway through a block, forces the compiler to perform "dynamic stack adjustment" or "deferred stack allocation." This does not make compilation impossible, but adds complexity. This is just a note for consideration.

---

5. Verification (FPCUnit)

To prove effectiveness, the following test suite should verify that different specializations maintain data integrity while sharing logic.

unit Test.WLG;

interface

uses
  fpcunit, testregistry;

type
  { Simple generic for verification }
  generic TBox<T> = record
    Value: T;
    procedure SetValue(const NewValue: T);
  end;

  TTestWLG = class(TTestCase)
  published
    procedure TestTypeIntegrity;
  end;

implementation

procedure TBox.SetValue(const NewValue: T);
begin
  Value := NewValue;
end;

procedure TTestWLG.TestTypeIntegrity;
var
  IntBox: specialize TBox<Integer>;
  StrBox: specialize TBox<ShortString>;
begin
  IntBox.SetValue(500);
  StrBox.SetValue('Pascal');

  AssertEquals('Integer integrity', 500, IntBox.Value);
  AssertEquals('String integrity', 'Pascal', StrBox.Value);
  
  { New generic compilation: The assembly for SetValue 
    is stored once. The calling convention passes the 
    address of IntBox/StrBox and the hidden Witness 
    pointer for Integer/ShortString respectively. }
end;

initialization
  RegisterTest(TTestWLG);
end.

---

6. Recovery of Legacy Performance

To ensure no performance regression for critical paths (e.g., high-performance math), I propose an attribute to opt-out of sharing:

{ This forces the old template expansion for speed }
type
  {$Modeswitch GenericPerformanceCritical}
  TFastVector = specialize TArray<Single>;

7. Summary of Benefits

• Compilation Speed: Drastic reduction in time as the compiler stops re-parsing and re-emitting code for every specialize.
• Binary Size: Potential reduction of 40-70% in projects heavily using containers.
• Instruction Cache: Improved CPU performance via reduced code footprint (smaller working set).
• Developer Experience: Retains the familiar specialize syntax, providing a bridge for existing code bases while fixing the underlying "bloat" bug.

[Eudox67]

Application of Indexed Labels to Lightweight Generics

I just discovered the Indexed Labels in FPC Unleashed. In the Witness-Based Generics proposal above, indexed labels could be a dream for the compiler.

If you have a shared implementation of a generic list, the compiler might need to handle "Special Cases" for different power-of-two sizes. Instead of bloat, it uses one shared function with an indexed label:

procedure SharedGenericAdd(const Witness: PWitnessTable);
label 
  HandleSize[1, 2, 4, 8];
begin
  { The compiler can jump to the optimal MOV instruction based on size }
  goto HandleSize[Witness.TypeSize];

  HandleSize[4]:
     { Perform 32-bit optimized copy }
     exit;
  HandleSize[8]:
     { Perform 64-bit optimized copy }
end;