4 ms·

Also perhaps of interest: making C faster than C by borrowing techniques from Smalltalk implementation. Piumarta, Ian, and Alessandro Warth. “Open, Extensible

• vidarh 5y ago
  That quote is a bit misleading even though it's entirely true. Faster than naive-switch-based polymorphic code, yes. Effectively it shows that slow lookup + function calls via a function pointer can be faster than large switch()'s, and that's useful to convince C programmers of... It's a fun paper that does a good job at presenting a the first few steps worth taking towards implementing well performing dynamic object models and showing that it may be worth considering those methods when writing C that requires different behaviour for different data structures over writing static code in those specific cases, but people have been writing vtable based object models for C "forever" that solves enough of those problems that it's rarely worth going the extra mile to get the dynamic model they present in the paper. When you actually need it, it's very useful to know these tricks, though, and for those unfamiliar with dynamic object models it's a great introduction. That said, it does miss one other simple trick that's worth considering. For inheritance it searches parents, and this is a large part of what makes the "bind" expensive and so makes the inline caching worthwhile. Protocol extension [1] provides a way to do this which can be implemented either as cheap as vtables for calls (costs more memory) or one indirect load more expensive (more space efficient). Basically the fastest approach is to make all vtables big enough to accommodate individual slots for each method name. The "slow" approach groups methods in interfaces and gives you a "vtable of vtables". Couple that with a simple method propagation algorithm that lets you override methods like in this paper but respects sub-classes overriding a method (by seeing if the pointer to the function implementing the method matches that in the parent vtable), and that's it. You might think this blows up really badly. But in practice in experimenting with in-progress-and-may-never-be-finished Ruby compiler, the memory overhead tends to be surprisingly small - few projects have large enough number of classes and large enough numbers of unique method names for it to be a major issue, but the two approaches can also be combined with fallback to more indirection). Even with a singly-rooted object hierarchy like Ruby it doesn't seem likely to be a big problem, and for a language implementation you can "mix and match" and put the most common method names in a shared vtable and fall back to more expensive lookup methods for less common methods if necessary to save memory. The main benefit comes with megamorphic call-sites (places where the vtable used for the call will frequently change at any given call-site, and where you thus otherwise end up falling back to the expensive method lookup very often), which is no more expensive than monomorphic call-sites with protocol extension. [1] Protocol Extension: A Technique for Structuring Large Extensible Software-Systems, 1995, Michael Franz https://www.semanticscholar.org/paper/Protocol-Extension%3A-A-Technique-for-Structuring-Franz/63ee36869cbb376d66780b533d052d647f70243b https://www.semanticscholar.org/paper/Protocol-Extension%3A-...
• agumonkey 5y ago
  Ian piumarta c code is often poetry. Look at Maru (Lisp meta compiler iirc).
• scroot 5y ago
  I love this paper! One thing I've never understood (because my C is poor) is what is means to access something at array[-1]. What does that even mean? Wouldn't it be a garbage value, if anything?
  • Jtsummers 5y ago
    C array access is (not totally accurate) replaceable with pointer arithmetic and dereferencing. So array[-1] is the same as *(array - 1). So long as your program controls that bit of memory, it is a safe operation (you won't be accessing memory outside of whatever the OS/runtime allocated to your process). For instance, if you have this struct definition: typedef struct { int a; int b[10]; } foo; Then the following will (likely) work: foo f; f.a = -1; printf("%d\n", f.b[-1]); // => -1 In fact, the following also works: f.b[0] = 10; printf("%d\n",(&(f.a))[1]); // => 10 C is very flexible in allowing you to do what you want with addresses (once obtained). But yes, if you don't control it then it is likely going to be garbage data.
    • scroot 5y ago
      > C array access is (not totally accurate) replaceable with pointer arithmetic and dereferencing. So array[-1] is the same as *(array - 1). Thanks, that part is clear. I guess in the Piumarta paper, he's assuming all of these objects are contiguous in memory? Because the vtable pointer is always to [-1] but it's not specified in any given struct...
      • Jtsummers 5y ago
        I also missed the specific solution the first time, but see figure 10 on page 6 (in section 3.1, the pages aren't numbered). It's doing a variant of what I described, in this case they're doing this (copied the document, pseudocode): function vtable_allocate(self, size) = let object = allocateMemory(PointerSize + size) object := object + PointerSize object[-1] := self return object This will guarantee that the memory is contiguous and properly allocated to the process so it's not using garbage data.