How are interfaces and methods implemented?

[funny-falcon]

It is very intriguing how are methods and interfaces implemented?

I'm very "polyphormism" addicted man, so I like Golang's interfaces very much. And I did some interface implementations in pure-C as well. So I can imagine many different ways of "interface" implementations.

But which way C3 follows? Given one may add dynamic method even to builtin int type (as documentation says), it is very curious how actual mechanism looks alike.

[funny-falcon]

I'll try to answer myself.
I use godbolt for that (c3's version is 0.6.2):

• there're type description/reflection structures
• third field of type description is a start of single-linked list
• every dynamic method is just added to this linked list as struct method { void *funcptr; const char *selector; struct method *next} (excuse me for using C syntax).
• selector is compared as a pointer (to constant string), not as a string itself. (btw, how it will work on Windows? Or LLVM on Windows does immutable string literals as well?)
• interface is a struct with two pointers: to type's reflection structure and to value.

So, there is not "method tables" in terms of C++ virtual functions or Go's interfaces. Just list of name-pointer pairs, and runtime lookup into. And while C3's interface looks like Go's empty interface (interface{}), it doesn't look like Go's interface with methods, ie any interface points to the same reflection structure of value's type.

And there's .c3_dynamic_register function which, I believe, is executed by C3's entry point.

Well, it is not bad while not super efficient. I believe, it will be changed to at least to hash table with fixed count of buckets in following releases.

Next question raises: how it will work with dynamically loaded shared libraries? Who will call .c3_dynamic_register ?

And looks like there's no runtime protection from signature mismatch: if I change int.myname signature to return int instead of String, it will happily crash

fn int int.myname(int* self) @dynamic
{
    return *self;
}

15:04:59 $ ./output
I am Baz!
1

ERROR: 'Out of bounds memory access.'
  in std.core.builtin.sig_segmentation_fault (/home/yura/Install/c3/lib/std/core/builtin.c3:737) [./output]
  in __GI___sigaction (source unavailable) [/lib/x86_64-linux-gnu/libc.so.6]
  in std.core.string.ZString.len (/home/yura/Install/c3/lib/std/core/string.c3:521) [./output]
  in std.core.string.ZString.str_view (/home/yura/Install/c3/lib/std/core/string.c3:507) [./output]
  in std.io.Formatter.out_str (/home/yura/Install/c3/lib/std/io/formatter.c3:216) [./output]
  in std.io.Formatter.vprintf (/home/yura/Install/c3/lib/std/io/formatter.c3:528) [./output]
  in std.io.printf (/home/yura/Install/c3/lib/std/io/io.c3:258) [./output]
  in output.whoareyou (/home/yura/tmp/test_dyna.c3:48) [./output] [inline]
  in output.main (/home/yura/tmp/test_dyna.c3:62) [./output]
  in @main_to_void_main (/home/yura/Install/c3/lib/std/core/private/main_stub.c3:18) [./output] [inline]
  in main (/home/yura/tmp/test_dyna.c3:56) [./output]
  in __libc_start_call_main (./csu/../sysdeps/x86/libc-start.c:58) [/lib/x86_64-linux-gnu/libc.so.6]
  in __libc_start_main_impl (./csu/../csu/libc-start.c:360) [/lib/x86_64-linux-gnu/libc.so.6]
  in _start (source unavailable) [./output]
Illegal instruction (core dumped)

[funny-falcon]

I see: .c3_dynamic_register is called from libc's call_init. I believe, it is registered same way as __attribute__((constructor)) functions in GCC/CLang, ie it is placed into init_array section.

[lerno]

The solution had to be modified for MacOS for example. But as for the hash, it is somewhat doubtful. Doing a lookup is going through a linked list, and the lookup is proportional to the number of dynamic methods on the type. I am optimizing here for a high number of types implementing only 1-2 methods. E.g. the Printable interface. The allocator interface consists of 3 methods and so on.

Each call (somewhat wasteful in some cases, but should be properly optimized away) will get the lookup cached at the calling site, so in the case of a loop over the same type it will be very fast. However, this optimization is not possible in the case of foreach (x : foo) blurb(x); where the reflection happens inside of "blurb" since the cache is local to the function call. With some asm one might be able to turn that some optimized lock-free check, but it's a problem that the cache needs a value that is two pointers wide. On some machines it's possible to perform an atomic check but not all. So that's where the optimization should probably be.

[funny-falcon]

I don't mean, key-value storage should be radically changed. It could be just 8 or 16 linked lists with current list hardwired into lookup. Code will differ from current only in list header choice.