Handles instead of Pointers

Explain
1

Hi,

Handles (indexes) instead of pointers seems to be very hot topic.

I recently watched a video about distinct handle types in Ada.
And similar thing is supported by Odin.

As I see it - you define separate type to index certain array.
And when you later pass index alone - it defines 1-to-1 which array it applies to.

Here Andrew is saying that indexes are used instead of pointers in Zig widely.
And that he uses wrappers around them not just u32.

So my question is - is it actually enough and no need to bring it into the language?

Is struct wrapped around the u32 just basically the same as distinct types in Ada or Odin?

Do we add additional mechanism to this struct like pointer to array and getter?
So that this index doesn’t need unwrapping to be applied (which makes it hard to use it wrong)?

1 Like
2

I don’t know the full picture, nor how the other languages work, but you can effectively get distinct types with enums:

const MyID = enum(u32) { _ };

You can add methods and if you make other handle types like this, and you get compilation errors if you mix them up.

9 Likes
3

Relevant proposal: request: distinct types ¡ Issue #1595 ¡ ziglang/zig ¡ GitHub

Closed with this comment:

This use case is adequately addressed by non-exhaustive enums and packed structs.

Relevant video:

9 Likes
4

Thank you guys both for such prompt replies.

I think I see it clearly now.

1 Like
5

IMHO it’s more of a library feature instead of language feature (although it’s fun thinking about what such a handle-based language would look like) - in general it’s pretty close to the allocator idea, except the allocator being limited to a single type, and returning opaque handles instead of pointers. Tagged index handles provide temporal (run-time) memory safety, so they can be used to close a safety gap in Zig, e.g. I think the idea fits pretty well into Zig.

The important part is that the handle is not just an index, but also has a few bits for detecting dangling handles (those bits usually contain the value of a ‘slot generation counter’ at the time the handle was created).

Shameless plug: link to my old blog post about the topic: Handles are the better pointers

Also see: GitHub - zig-gamedev/zpool: Generic pool & handle implementation for Zig.

14 Likes
6

Wow, you authored that? It has been a source of ideas and inspiration for quite some time now. I finally get to say “thank you very much”!

7 Likes
7

Yeah, I had the link to your article in my original question post, but forum allowed only 2 links. :slight_smile:
I think that was original place where I known the idea from.
(I think Alex Kladov from TigerBeetle was referencing it)

Thank you!

2 Likes
8

You can ping @matklad, he’s here with us, I’m sure he won’t mind. :wink:

1 Like
9

I won’t mind! My contract is that you can ping me liberally for whatever reason at whatever time without thinking twice, but, symmetrically, I reserve the right to not feel bad if I don’t respond!

I wouldn’t say that handles are particularly “hot” in temporal locality sense — this is quite an old trick. I personally first learned about it from the famous https://gameprogrammingpatterns.com book (though I “spoke prose” before that in the small, when working with graphs).

I would also maybe caution against talking about “the Handle pattern”. As with terms like OOP and FP, this is a nebulous concept which can be applied to many quite different patterns & language features, and, while it is useful to refer to an element of this cloud, if you want to think about it, you have to think very concretely about a specific implementation, as details matter a lot. Are compressed pointers in HotSpot JVM handles?

From this point of view:

Zig’s enum(usize) { _ } is “a happy accident of language design” (heard this memorable turn of the phrase from yole). It is a way to give an integer a fancy, snobbish top-hat, which prevents its mingling with lowly ints. I don’t think _ was meant for that, I think the original use-case was “I want to have an enum with a list of known variants, but sometimes I want to store an unknown one”, and then later it was discovered that you can flip it around and make _ the 99% percent use-case.

This is a distinct feature than newtypes as found in Haskell/Go/Odin. Those languages allow for

type email = string;

but you can’t const email = enum([]const u8) { _ } in Zig. At the same time, in low-level languages 99% of the time you want to newtype, you want to newtype a handle/index, so Zig gets to eat 80% of cake using 0% of extra features.

Ada’s Access types are something else entirely. They are nominal pointers and the interesting thing about them is not whether they are indexes or pointers internally (I actually don’t know that!), but the associated memory management machinery. This is something I’d love to understand better: how Ada actually manages memory? I think it sits “between” pure stack allocation and general RAII, but I am confused by everything I’ve read so far. I can’t concisely explain how Ada does unbounded strings, how it returns dynamically-sized values.

8 Likes
10

One would think that in the modern world one can just ask AI, but it seems just as confused as me, and clueless about its own confusion on top. I was able to narrow down my confusion to a litmus test program:

with Ada.Text_IO; use Ada.Text_IO;
with Ada.Integer_Text_IO; use Ada.Integer_Text_IO;

procedure Demo is

   -- Define a type for an array of integers
   type Int_Array is array (Positive range <>) of Integer;

   -- Function to create an array of integers from 1 to N
   function Make_Array (N : Positive) return Int_Array is
      Result : Int_Array(1 .. N);
   begin
      for I in Result'Range loop
         Result(I) := I;
      end loop;
      return Result;
   end Make_Array;

   -- Function to choose between two arrays
   function Choose_Array (N1, N2 : Positive; Use_First : Boolean) return Int_Array is
      A1 : constant Int_Array := Make_Array(N1);
      A2 : constant Int_Array := Make_Array(N2);
   begin
      if Use_First then
         return A1;
      else
         return A2;
      end if;
   end Choose_Array;

begin
   -- Call Choose_Array from main and print its elements
   declare
      A : Int_Array := Choose_Array(3, 7, Use_First => False);
   begin
      for I in A'Range loop
         Put(A(I));
         Put(" ");
      end loop;
      New_Line;
   end;

end Demo;

But the best explanation there is still On the Ada Secondary Stack, and Allocation in the Real-World which doesn’t actually explain all that much, besides explicitly noticing that that’s interesting.

EDIT: asked humans: Request for an explanation: secondary stack - Help - Ada Forum

11

Interesting. In Zig terms, this sort of reads like RLS with runtime-known sized instances being placed on a secondary heap-allocated stack structure, where the compiler injects secondary-stack pop’s in the caller’s lexical scope.

12

I would actually love to be able to select between ‘distinct’ and ‘structural’ typing.

E.g. why are items of types A and B assignable to each other here:

const A = u32;
const B = u32;

…but here A and B are incompatible:

const A = struct { x: u32 };
const B = struct { x: u32 };

…I mean, the “why” is clear, that’s just how it was ‘inherited’ from C and other languages, but sometimes structural typing comes in really handy (I’d even go as far to say that structural typing should be the default and distinct/strong/newtype typing should require explicit annotation (or the other way around, I don’t care, it should just be consistent between primitive and struct types).

PS: this mess is why handles in sokol-gfx are structs instead of simple integer typedefs btw:

typedef struct { uint32_t id; } sg_buffer;
3 Likes
13

This is equivalent to

const A = std.net.Address;
const B = std.net.Address;

u32 is just a name that refers to a builtin type. In contrast, struct is a keyword that mints a new type. Not super-practical, but you can remove nominally from struct if you launder it via a function:

const std = @import("std");

const A = @"struct"(&.{.{ "x", u32 }});
const B = @"struct"(&.{.{ "x", u32 }});

test {
    var a: A = .{ .x = 92 };
    const b: B = .{ .x = 62 };
    a = b;
}

fn @"struct"(comptime fields: []const struct { []const u8, type }) type {
    var struct_fields: [fields.len]std.builtin.Type.StructField = undefined;
    for (0..fields.len) |i| {
        const name, const @"type" = fields[i];
        struct_fields[i] = .{
            .name = name ++ "",
            .type = @"type",
            .default_value_ptr = null,
            .is_comptime = false,
            .alignment = @alignOf(@"type"),
        };
    }
    return @Type(.{ .@"struct" = .{
        .layout = .auto,
        .is_tuple = false,
        .decls = &.{},
        .fields = &struct_fields,
    } });
}

What is inconsistent is that @Type(.{ .@"struct" = ... }) behaves as if it mints a new type, while @Type(.{ .Int = ... }) behaves as if its a normal user-space comptime function.

2 Likes
14

Sorry for derailing this further than further from topic, but I can’t resist my nerdry temptations: this was actually changed in C23 Parameterized types in C using the new tag compatibility rule

4 Likes
15

Thank you for all this information!
It is very interesting (at least part that I think I understood).

Now I see that my view on the problem was one-sided.

Direct answer to my original question is - yes, it is supported by unexhaustive enums and structs.

And second part of the idea (I tried implementing Andrew’s examples myself)
is bringing all the data to the top level.

It is all fine if data is created once and never modified.

But modifications bring another complexity aren’t they?

In general we allocate collections on heap when size is not determined - might grow, might get relocated, might shrink as well - such a bag - one size fits all.

And it is stored dense and modifications are effective.
But it case of 1-level pointer depth we either a) not dense or b) a lot of effort on relocating things?

Probably there is answer already in one of your links I didn’t catch.

16

Here is how I understood motivation for “handles instead of pointers” change.

  • indirection
    no direct pointers, opaque handles which allow internal changes

  • ownership in one place
    store is the only owner

Some consequences:

  • handles can be smarter and signal lifespan
  • cache locality, data density
  • better serialization

it really looks like another allocation system, self-created managed level of storage.

And there can be different aspirations of internal storage changes.

  • performance
    it looks there are many pitfalls with this concept

  • memory density
    related to previous and when implemented naively
    structure can become sparse.

  • different modes of operation of store for different phases of lifecycle

17

(Did I already say that I’m not a system programmer myself?
So my questions might be dumb.)

one more Q -
Provided that we implemented a store with Handles access only and no pointers deeper than 1 level.

Then what do we give outside?
Client has a Handle but then he wants something substatial - what do we give?

Access to store’s internal arrays?
But it relies on premise that pointer is not long-living, right.
And still it is risky.
And to make it completely safe we need to make a copy somewhere and the dispose of it somehow.

Wow, even in basic-basic scenario looks daunting.

And this whole technique is not “incapsulatable” into library, right?
I mean in zpool (mentioned above) they’ve done only a thin wrapper around MultiArrayList.

18

Ideally the ‘client’ never needs to access the memory behind the handle but only passes the handle around and back into the library it got the handle from (which then may access the memory behind the handle - e.g. it’s always the library which ‘owns’ the memory behind a handle, not the client code).

E.g. the library API becomes the safety barrier. Any code outside the library cannot access memory behind a handle, only pass the handles it got from the library back into the library. That means that any memory corruption errors involving the memory behind the handle must have happened inside the library implementation, which is very useful for debugging.

This is basically the memory safety premise of handles, they narrow down any potential memory corruption issues to a small part of an application code base (similar idea as Rust’s unsafe blocks).

You also want to want to have proper ‘meaty’ library functions, e.g. don’t have an API which requires simple setters/getters, because each setter/getter would need to convert the handle to a pointer, instead you’d want big fat functions which do a lot of work to minimize the handle-to-pointer conversion runtime overhead (which is very small though, just some bit masking, an index access, and a comparison of the generation count).

If you need to convert the handle to a pointer outside the library which creates the handle then the memory safety guarantees are gone, but you can still establish some rules to minimize the impact:

  • don’t store the pointer anywhere (because next time you use the pointer it may be invalid)
  • don’t keep the pointer across functions calls (since the code inside the function call may invalidate the pointer)
3 Likes
19

Thank you, Alex, I’ve skimmed the book (with chat) and read the chapter about Cache Locality.

So it seems there are 3 intertwined ideas:

  • A cache locality (Nystrom’s) - continuous dense chunks of data processed sequentially.
  • B max pointer depth level of 1 (Andrew’s) - all data are together, no jumps
  • C handles (indices) instead of pointers ( Andre’s)

Nystrom suggests to link cold data with a pointer, in Andrew’s approach it would be separate array of cold data.

And C relates to both, for A it allows rebuilding the storage (putting active items together) without breaking all the existing pointers.