Giter Club home page Giter Club logo

Comments (8)

saem avatar saem commented on June 2, 2024 1

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.

alaviss avatar alaviss commented on June 2, 2024 1

Note that most compilers are designed to deal with vtables: https://pithlessly.github.io/allocgate.html

from nimskull.

ringabout avatar ringabout commented on June 2, 2024

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.

ringabout avatar ringabout commented on June 2, 2024

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.

mrgaturus avatar mrgaturus commented on June 2, 2024

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.

saem avatar saem commented on June 2, 2024

@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.

saem avatar saem commented on June 2, 2024

@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.

mrgaturus avatar mrgaturus commented on June 2, 2024

@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)

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo 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.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.