Hacker News Reader

Comment by choeger | Hacker News Reader

Well written!

I wonder if there's a way to efficiently implement it without resorting to monomorphization?

A function that's polymorphic can be transformed into a more primitive (say C or assembly) function that gets extra arguments that carry the "shape" of the type variable (think of sizes, pointers vs. values, etc.). Is there a similar strategy for these polymorphic records?

I see two issues:

1. The offset of any particular field in the record is unknown at compile time

2. The size of the record itself is unknown at compile time (but this should be trivial as an extra argument.)

View on HN

Swift solves this by using witness tables. Witness table is a skeleton of the desired record shape. It records offsets of desired fields as found in the actual supplied record. Each function call the actual record is not passed, but its corresponding witness table instead.

For instance, if the "prototype" of the argument is {int foo, float bar}, and I supply {int foo, int baz, float bar}, the table will be {foo: base+0 bytes, bar: base+8 bytes}.

Why doesn't it limit what it pushes on the stack to (foo,bar) instead of pushing (foo,baz,bar) along with an offset table? If the offset table is possible to construct at the callsite, compiling it into the call is also possible.

Because the polymorphic function called may also need to pass the whole record it was given to some other polymorphic function a la "void storeInGlobalStorage(key: string, value: T)".

> I wonder if there's a way to efficiently implement it without resorting to monomorphization?

Depends on what you consider "efficient".

Monomorphization is necessary for the most efficient code. But you can have a vtable or a restricted type lookup.

> Monomorphization is necessary for the most efficient code.

That is not always true. Monomorphisation also leads to code size increase, because the function is compiled for each type. This may decrease cache efficiency.

Right. Monomorphization is very often a requirement for getting the most performance.

But not always, and won't always increase your performance either.

For another approach without monomorphization see also my comment at [0] although it's only really meant for the immutable records.

[0] https://osa1.net/posts/2023-01-23-fast-polymorphic-record-ac...

What pistoleer said basically. Lets say a function expects a 2D point and you want to pass in a rectangle struct (which has x and y plus more info). You'd do something like:

void f({float x, float y} p);

Becomes

void f(void* p, size_t offsets[2]);

Careful: the function definition doesn't remove the records but the call site does. You could transform into a type erased "access at each offset dynamically" form.

Reply on news.ycombinator.com