Comments (8)
Point of order. Please keep the Nim discussion out of Nimskull except for point of reference. Nim is where we're starting from but not where we're going, nor are we here to fix Nim issues.
from nimskull.
Note that most compilers are designed to deal with vtables: https://pithlessly.github.io/allocgate.html
from nimskull.
Hi, @mrgaturus
The dispatcher based on if statements is not slow if the hierarchy is shallow (should be as good as the dispatcher based on VTable). Do you happen to have some benchmarks to show that it affects the efficiency of dynamic dispatch or your program?
from nimskull.
In fact, it doesn't outperform better than the current if dispatcher implementation since the subtype checking is O(1) now and the vtable
implementation which uses indirect call incurs some penalties, which make it stoop to the same level of the if dispatcher. Nevertheless, ARC with either of them is 10x faster than refc in this benchmark. See also nim-lang/Nim#20897
from nimskull.
In fact, it doesn't outperform better than the current if dispatcher implementation since the subtype checking is O(1) now and the
vtable
implementation which uses indirect call incurs some penalties, which make it stoop to the same level of the if dispatcher. Nevertheless, ARC with either of them is 10x faster than refc in this benchmark. See also nim-lang/Nim#20897
if dispatcher seems to be faster than vtable dispatcher on smaller cases but not on bigger cases
50 object types with 5 methods and 100 instances benchmark:
https://gist.github.com/mrgaturus/ed04d22ddc4f50c7677c7e00ad21495d
# -----------
# Nim Version
# -----------
Nim Compiler Version 1.9.1 [Linux: amd64]
Compiled at 2023-02-03
Copyright (c) 2006-2023 by Andreas Rumpf
git hash: 8e53fba083a7450b8c2e9771cba8d477468a520e
active boot switches: -d:release
# ---------------
# REFC Benchmarks
# ---------------
nim c --mm:refc -d:release branch.nim
dummy value: 34803480
time: 0.127926617
nim c --mm:refc -d:release vtable.nim
dummy value: 34803480
time: 0.033211028
# --------------
# ARC Benchmarks
# --------------
nim c --mm:arc -d:release branch.nim
dummy value: 34803480
time: 0.13270458
nim c --mm:arc -d:release vtable.nim
dummy value: 34803480
time: 0.034363664
from nimskull.
@mrgaturus to clarify, I'm willing to accept improvements to our existing implementation, so we can discuss that. Meaning, if you'd like Nimskull to make changes and consider improvements, it's totally ok to file this issue and have it open.
from nimskull.
@mrgaturus do you have a a sketch of what sort of coffee we should generate? Not for the purposes of making the code generator do exactly that but highlighting the story of techniques one might employ in improving things?
I'm steering nimskull away from the transpiling focus, instead treating C as purely an IR/output target as one might llvm. It's a subtle difference, but instead of mapping high-level semantics into C, we're instead mapping a few core concepts to C and everything else is built atop those.
Generally, I'm trying to discover what a useful subset we should have. Particularly, vtable/runtime dispatch is an area that I see significantly informing the set of primitives we need to consider.
from nimskull.
@saem a vtable is an array of function pointers which contains methods of an object type, each vtable is different when a method is overwritten on an inherited object type, it uses indirect calls but is not worse than many if branches. Refactoring all stuff related object-oriented (methods to vtables, inheritance, etc) is a good idea.
look this toy C example about vtables:
// you can test this
// gcc vtable.c -o vtable
#include <stdio.h>
#include <stdlib.h>
// -------------------
// Function Pointer Types
// -----------------
typedef void (*widget_draw_proc)(void*);
typedef void (*widget_update_proc)(void*);
typedef void (*widget_layout_proc)(void*);
typedef void (*widget_event_proc)(void*);
// ----------------
// Default Widget
// ----------------
typedef struct {
void** vtable;
int x, y, w, h;
} widget_t;
typedef struct {
widget_t root;
} default_t;
static void empty_draw(widget_t* self) { printf("drawed nothing\n"); }
static void empty_update(widget_t* self) { printf("update nothing\n"); }
static void empty_layout(widget_t* self) { printf("layout nothing\n"); }
static void empty_event(widget_t* self) { printf("event nothing\n"); }
// vtable for a default widget
const void* vtable_default[] = {
(void*) empty_draw,
(void*) empty_update,
(void*) empty_layout,
(void*) empty_event,
};
default_t* default_new() {
default_t* w = malloc(sizeof(default_t));
// Look, we define the vtable
w->root.vtable = (void**) vtable_default;
return w;
}
// ----------------
// Widget Button
// ----------------
typedef struct {
widget_t root;
char* label;
} button_t;
static void button_draw(button_t* self) { printf("%s\n", self->label); }
static void button_event(button_t* self) { printf("evented button\n"); }
// vtable for button widget, look overwrites
const void* vtable_button[] = {
(void*) button_draw, // Overwrite
(void*) empty_update,
(void*) empty_layout,
(void*) button_event // Overwrite
};
button_t* button_new(char* label) {
button_t* w = malloc(sizeof(button_t));
// Look, we define the vtable
w->root.vtable = (void**) vtable_button;
// Define Button Thing
w->label = label;
return w;
}
// -----------------------
// Usage of VTable
// -----------------------
int main() {
button_t* btn0 = button_new("Button 0");
button_t* btn1 = button_new("Button 1");
default_t* default0 = default_new();
// Usage of VTable, look at casting
printf("-- Draw Method\n");
( (widget_draw_proc) btn0->root.vtable[0] ) (btn0);
( (widget_draw_proc) btn1->root.vtable[0] ) (btn1);
( (widget_draw_proc) default0->root.vtable[0] ) (default0);
printf("-- Event Method\n");
( (widget_event_proc) btn0->root.vtable[3] ) (btn0);
( (widget_event_proc) btn1->root.vtable[3] ) (btn1);
( (widget_event_proc) default0->root.vtable[3] ) (default0);
printf("-- Update Method\n");
( (widget_update_proc) btn0->root.vtable[1] ) (btn0);
( (widget_update_proc) btn1->root.vtable[1] ) (btn1);
( (widget_update_proc) default0->root.vtable[1] ) (default0);
// Free Data
free(btn0);
free(btn1);
free(default0);
// Exit
return 0;
}
from nimskull.
Related Issues (20)
- calls introduced by macros does not exhibit automatic typedesc conversion HOT 1
- Generic parameters `void` and `not void` clash HOT 3
- stdlib_*.nim.c files generated incompatible with my platform HOT 2
- unconditional pointer member access is generated in C for inheritance HOT 2
- NULL dereference when an empty seq is passed to openArray HOT 1
- stdlib: organize the standard library modules (`lib`) HOT 4
- objChecks:off not respected in pragma form HOT 2
- confusion of forvar type when supplied as typed macro argument HOT 2
- attempt to define call operator can crash the compiler HOT 1
- getType doesn't reveal complete generic arguments
- CI failures due to inconsistent binaries buildt on M1 runners HOT 1
- Emscripten compilation runs into undeclared `Tm` when importing `std/times` HOT 12
- incorrect control-flow when indirect call raises with `--panics:on` HOT 5
- UFCS issue iterator into macro HOT 4
- set[int8] cannot initialized with values HOT 4
- linking error when using `{.compile.}` pragma on .c files with same name but located on different paths HOT 1
- dot function call syntax inside a template can't lookup symbols of an imported module when the template is called from another module HOT 1
- ` .threadvar`s aren't destroyed on thread exit HOT 1
- value is implicitly moved even though it's used afterwards HOT 2
- procedure result is not cleaned up if the procedure raises HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from nimskull.