7 ms·

> objc_msgSend is written in assembly. There are two reasons for this: one is that it's not possible to write a function which preserves unknown arguments and j

by pakl 9y ago

> objc_msgSend is written in assembly. There are two reasons for this: one is that it's not possible to write a function which preserves unknown arguments and jumps to an arbitrary function pointer in C. Wow... this is a bit off topic but can anyone expand on this side note and explain why? (Every Objective-C implementation requires assembly code?)

ytch 9y ago
There is another interesting article on msgSend, its hacker news comments[1] may answer your question (I'm not sure)? [1] https://news.ycombinator.com/item?id=6984421 https://news.ycombinator.com/item?id=6984421
protomyth 9y ago
The original Stepstone Objective-C compiler compiled to C, so, no, assembly is not required. On the other hand, it is an optimization that would help a lot. I still wonder if hardware acceleration would have been possible in Apple's A-series of chips.
- twoodfin 9y ago
  What would hardware acceleration for objc_msgSend look like? If the success of RISC architectures taught us anything, it's that replacing simple primitive operations with special-purpose combinations is rarely worth the transistors. You can win if you're trying to speed up specialized bit-twiddling like AES, but implementing complex conditional control flow under the covers of a magic opcode or two probably hurts your ability to tune future implementations for performance rather than helps. Intel's iAPX 432 is a good example of what can go horribly wrong[1] when you try to directly support an object model in a CPU architecture. [1] https://www.researchgate.net/publication/220439234_Performance_Effects_of_Architectural_Complexity_in_the_Intel_432 https://www.researchgate.net/publication/220439234_Performan...
  - protomyth 9y ago
    Well, given every A-series chip has a lot of special purpose transistors (GPU, encoding, decoding, etc.) and I notice the bitcoin crowd has a lot of love for special purpose transistors, I don't think the lessons of RISC are that cut and dried. I would imagine a dynamic dispatch instruction would be an interesting addition that would require some thinking on the CPU and MMU. Pulling out the iAPX 432 (or even the Itanium for anything VLIW) is a nice historical note, but they are single projects that had more than technical problems. Not thinking about all the possible solutions when a company controls not only the software but the hardware at such a low level would be sad.
  - dom0 9y ago
    > If the success of RISC architectures taught us anything, it's that replacing simple primitive operations with special-purpose combinations is rarely worth the transistors. RISC-V argues the exact opposite :)
    - twoodfin 9y ago
      What parts of RISC-V did you have in mind?
      - dom0 9y ago
        The whole idea of building an ecosystem of an open ISA with open implementations, where the ISA can be extended for specific applications. See e.g. https://riscv.org/wp-content/uploads/2016/12/Tue1100-RISC-V-Workshop-RoHC-ASIP-Accelerator-Cox-Synopsys.pdf https://riscv.org/wp-content/uploads/2016/12/Tue1100-RISC-V-... but it was also a salient point in the Patterson talk that was on the front page a few days ago.
  - pcwalton 9y ago
    You could imagine a hardware circuit that searches all fields of the cache simultaneously. I doubt it would move the performance needle though. objc_msgSend is probably running near memory bandwidth limits already.
  - gumby 9y ago
    > If the success of RISC architectures taught us anything, it's that replacing simple primitive operations with special-purpose combinations is rarely worth the transistors. That's not actually the lesson of RISC. The points of RISC (going back to the Radin paper) were: 1> compilers are "now" (i.e. very late 70s/early 80s) better than humans in many cases 2> there were many tradeoffs in implementing CISC instructions that aren't used by lots of programmers and 3> those tradeoffs blocked you from other optimizations (register/cache files, speculative execution etc). So if you look at the x86, it's a RISC machine with an x86 instruction set implemented in software (microcode)...only it's more than that: the ID and pipeline scheduling reflect an understanding of the high level opcodes typically used by contemporary compilers. In addition there is plenty of useful stuff to be done that reflects an object level model: pointer boxing/unboxing (look at the RISC-V pointer cache), kernel/ user mode protection, FPUs and GPUs which treat specific kinds of bit representations specially.... As with all engineering it's all about the tradeoffs.
    - pjmlp 9y ago
      Another lesson from RISC, is that memory safe systems programming languages are perfectly fine for writing OSes, yet we are still catching up with it. https://en.wikipedia.org/wiki/PL/8 https://en.wikipedia.org/wiki/PL/8
cyphar 9y ago
> > objc_msgSend is written in assembly. There are two reasons for this: one is that it's not possible to write a function which preserves unknown arguments and jumps to an arbitrary function pointer in C. > Wow... this is a bit off topic but can anyone expand on this side note and explain why? I believe it's because C's variadic argument function call interface is not the same as the fixed-arguments function call interface so you can't just cast a function pointer to a variadic function pointer. And even if it worked on some architectures it sure as hell would not be standards compliant code.
mikeash 9y ago
A C implementation of objc_msgSend would look like: ... objc_msgSend(id self, SEL _cmd, ...) { fptr = ...lookup code... return fptr(self, _cmd, args...) } There's no way to express that args... argument when calling the function pointer, and no way to express forwarding an arbitrary return value. However, Objective-C does not require objc_msgSend. With objc_msgSend, a method call site generates code that's essentially equivalent to (for a method that takes one object parameter and returns void): ((void (*)(id, SEL, id))objc_msgSend)(object, selector, parameter); In other words, take objc_msgSend, cast it to a function pointer of the correct type, and call it. Instead of objc_msgSend, the runtime can provide a function which looks up the method implementation and returns it to the caller. The caller can then invoke that implementation itself. This is how the GNU runtime does it, since it needs to be more portable. Their lookup function is called objc_msg_lookup. The generated code would look like this: void (*imp)(id, SEL, id) = (void (*)(id, SEL, id))objc_msgLookup(object, selector); imp(object, selector, parameter); However, each call now suffers the overhead of two function calls, so it's a bit slower. Apple prefers to put in the extra effort of writing assembly code to avoid this, since it's so critical to their platform.
- tom_mellior 9y ago
  > There's no way to express that args... argument when calling the function pointer Yes there is: va_list. > no way to express forwarding an arbitrary return value Of course there is, and lots and lots of language runtimes implemented in C use those ways. Usually it boils down to having a base type called Object or Value and passing around pointers to that. In fact, from your example it looks like the "id" type is meant to play this role. This is not syntax checked, but the code above would be something like: Object *objc_msgSend(id self, SEL cmd, ...) { fptr = ...lookup code... va_list args; va_start(cmd, args); Object *result = fptr(self, cmd, args); va_end(args); return result; } Yes, this can be faster in assembly, but it's not true that there is no way to express this. (Unless I'm misunderstanding something.)
  - connorcpu 9y ago
    The missing bit is that objc_msgSend doesn't know how many parameters are being forwarded, and fptr is just a normal function on the other end, it isn't expecting a va_list, it expects arguments to be passed in the C ABI exactly how they're passed to objc_msgSend
topkekz 9y ago
Only skimmed the article but i think they want something like this <T> objc_msgSend(Object *receiver, String *method, ...) { return get_method(receiver->class, method)(receiver, ...); } where the tail call is translated into an unconditional jump (like goto). EDIT: this GNU C extension could help avoiding assembly for implementing objc_msgSend https://gcc.gnu.org/onlinedocs/gcc-7.1.0/gcc/Constructing-Calls.html https://gcc.gnu.org/onlinedocs/gcc-7.1.0/gcc/Constructing-Ca...
- mikeash 9y ago
  That's nifty, but I don't think it quite gets you there: "It is not always simple to compute the proper value for size. The value is used by __builtin_apply to compute the amount of data that should be pushed on the stack and copied from the incoming argument area." If there was a variant that didn't need this size argument (would probably require being a tail call) then that would do it.
  - panic 9y ago
    Could you do it with a C++ variadic template?
    - asveikau 9y ago
      That requires knowing types at compile time, and expands to just the code with the specific types used in the instantiation. That doesn't work with a virtual method dispatch kind of scenario where the types in the target method are not known to the runtime.
    - mikeash 9y ago
      Sort of. If you did it that way, then the message dispatch code would get compiled into the calling code rather than being a separate function. That would work, but it would greatly increase code size, and would also mean Apple couldn't make incompatible changes to how messaging works without breaking old code. This last part is fairly important: Apple does make such changes, and the fact that objc_msgSend is part of the system means that old programs just keep on working. They've introduced non-pointer isas and tagged pointers this way.
deleted 9y ago
[deleted]
gumby 9y ago
>> objc_msgSend is written in assembly. There are two reasons for this: one is that it's not possible to write a function which preserves unknown arguments and jumps to an arbitrary function pointer in C. > Wow... this is a bit off topic but can anyone expand on this side note and explain why? There are some good detailed replies in this thread but I thought I'd address your question at a higher level. People often refer to C as "an assembly language" but the usage is joking, or as an analogy. The C language has a high level representation of stack frames and the like (which, BTW, intimately reflect the architecture of the PDP-7/PDP-11 class of machines -- and thus due to the popularity of C have constrained the architecture of contemporary CPUs as well). If you want to violate C's assumptions you can't by definition do it in C. ObjC messages are essentially Smalltalk messages and they have different semantics. You don't have to become an assembly wizard but I suggest you may enjoy reading the C ABI for your favorite processor and then write a small assembly program that constructs a stack frame and calls a C function, and write an assembly function that can be called from C. More broadly, you may be interested in the theoretical work of programming language semantics (consider reflective languages like 2Lisp and 3Lisp, Brown etc) and consider why macros (not what C calls macros) aren't a way of trying to optimize code but actually extend language syntax. Theoretical computer science can seem arcane, yet really Gödel, Russel, et al really are applicable to machine code generation.
- panic 9y ago
  ObjC messages are essentially Smalltalk messages and they have different semantics. The method bodies themselves are ordinary C functions -- you can call methodForSelector: on any object to get one of its methods as a function pointer. The only problem is passing the arguments correctly.

by pakl 9y ago

ytch 9y ago

There is another interesting article on msgSend, its hacker news comments[1] may answer your question (I'm not sure)? [1] https://news.ycombinator.com/item?id=6984421 https://news.ycombinator.com/item?id=6984421

protomyth 9y ago

The original Stepstone Objective-C compiler compiled to C, so, no, assembly is not required. On the other hand, it is an optimization that would help a lot. I still wonder if hardware acceleration would have been possible in Apple's A-series of chips.

twoodfin 9y ago
What would hardware acceleration for objc_msgSend look like? If the success of RISC architectures taught us anything, it's that replacing simple primitive operations with special-purpose combinations is rarely worth the transistors. You can win if you're trying to speed up specialized bit-twiddling like AES, but implementing complex conditional control flow under the covers of a magic opcode or two probably hurts your ability to tune future implementations for performance rather than helps. Intel's iAPX 432 is a good example of what can go horribly wrong[1] when you try to directly support an object model in a CPU architecture. [1] https://www.researchgate.net/publication/220439234_Performance_Effects_of_Architectural_Complexity_in_the_Intel_432 https://www.researchgate.net/publication/220439234_Performan...
- protomyth 9y ago
  Well, given every A-series chip has a lot of special purpose transistors (GPU, encoding, decoding, etc.) and I notice the bitcoin crowd has a lot of love for special purpose transistors, I don't think the lessons of RISC are that cut and dried. I would imagine a dynamic dispatch instruction would be an interesting addition that would require some thinking on the CPU and MMU. Pulling out the iAPX 432 (or even the Itanium for anything VLIW) is a nice historical note, but they are single projects that had more than technical problems. Not thinking about all the possible solutions when a company controls not only the software but the hardware at such a low level would be sad.
- dom0 9y ago
  > If the success of RISC architectures taught us anything, it's that replacing simple primitive operations with special-purpose combinations is rarely worth the transistors. RISC-V argues the exact opposite :)
  - twoodfin 9y ago
    What parts of RISC-V did you have in mind?
    - dom0 9y ago
      The whole idea of building an ecosystem of an open ISA with open implementations, where the ISA can be extended for specific applications. See e.g. https://riscv.org/wp-content/uploads/2016/12/Tue1100-RISC-V-Workshop-RoHC-ASIP-Accelerator-Cox-Synopsys.pdf https://riscv.org/wp-content/uploads/2016/12/Tue1100-RISC-V-... but it was also a salient point in the Patterson talk that was on the front page a few days ago.
- pcwalton 9y ago
  You could imagine a hardware circuit that searches all fields of the cache simultaneously. I doubt it would move the performance needle though. objc_msgSend is probably running near memory bandwidth limits already.
- gumby 9y ago
  > If the success of RISC architectures taught us anything, it's that replacing simple primitive operations with special-purpose combinations is rarely worth the transistors. That's not actually the lesson of RISC. The points of RISC (going back to the Radin paper) were: 1> compilers are "now" (i.e. very late 70s/early 80s) better than humans in many cases 2> there were many tradeoffs in implementing CISC instructions that aren't used by lots of programmers and 3> those tradeoffs blocked you from other optimizations (register/cache files, speculative execution etc). So if you look at the x86, it's a RISC machine with an x86 instruction set implemented in software (microcode)...only it's more than that: the ID and pipeline scheduling reflect an understanding of the high level opcodes typically used by contemporary compilers. In addition there is plenty of useful stuff to be done that reflects an object level model: pointer boxing/unboxing (look at the RISC-V pointer cache), kernel/ user mode protection, FPUs and GPUs which treat specific kinds of bit representations specially.... As with all engineering it's all about the tradeoffs.
  - pjmlp 9y ago
    Another lesson from RISC, is that memory safe systems programming languages are perfectly fine for writing OSes, yet we are still catching up with it. https://en.wikipedia.org/wiki/PL/8 https://en.wikipedia.org/wiki/PL/8

cyphar 9y ago

mikeash 9y ago

A C implementation of objc_msgSend would look like: ... objc_msgSend(id self, SEL _cmd, ...) { fptr = ...lookup code... return fptr(self, _cmd, args...) } There's no way to express that args... argument when calling the function pointer, and no way to express forwarding an arbitrary return value. However, Objective-C does not require objc_msgSend. With objc_msgSend, a method call site generates code that's essentially equivalent to (for a method that takes one object parameter and returns void): ((void (*)(id, SEL, id))objc_msgSend)(object, selector, parameter); In other words, take objc_msgSend, cast it to a function pointer of the correct type, and call it. Instead of objc_msgSend, the runtime can provide a function which looks up the method implementation and returns it to the caller. The caller can then invoke that implementation itself. This is how the GNU runtime does it, since it needs to be more portable. Their lookup function is called objc_msg_lookup. The generated code would look like this: void (*imp)(id, SEL, id) = (void (*)(id, SEL, id))objc_msgLookup(object, selector); imp(object, selector, parameter); However, each call now suffers the overhead of two function calls, so it's a bit slower. Apple prefers to put in the extra effort of writing assembly code to avoid this, since it's so critical to their platform.

tom_mellior 9y ago
> There's no way to express that args... argument when calling the function pointer Yes there is: va_list. > no way to express forwarding an arbitrary return value Of course there is, and lots and lots of language runtimes implemented in C use those ways. Usually it boils down to having a base type called Object or Value and passing around pointers to that. In fact, from your example it looks like the "id" type is meant to play this role. This is not syntax checked, but the code above would be something like: Object *objc_msgSend(id self, SEL cmd, ...) { fptr = ...lookup code... va_list args; va_start(cmd, args); Object *result = fptr(self, cmd, args); va_end(args); return result; } Yes, this can be faster in assembly, but it's not true that there is no way to express this. (Unless I'm misunderstanding something.)
- connorcpu 9y ago
  The missing bit is that objc_msgSend doesn't know how many parameters are being forwarded, and fptr is just a normal function on the other end, it isn't expecting a va_list, it expects arguments to be passed in the C ABI exactly how they're passed to objc_msgSend

topkekz 9y ago

Only skimmed the article but i think they want something like this <T> objc_msgSend(Object *receiver, String *method, ...) { return get_method(receiver->class, method)(receiver, ...); } where the tail call is translated into an unconditional jump (like goto). EDIT: this GNU C extension could help avoiding assembly for implementing objc_msgSend https://gcc.gnu.org/onlinedocs/gcc-7.1.0/gcc/Constructing-Calls.html https://gcc.gnu.org/onlinedocs/gcc-7.1.0/gcc/Constructing-Ca...

mikeash 9y ago
That's nifty, but I don't think it quite gets you there: "It is not always simple to compute the proper value for size. The value is used by __builtin_apply to compute the amount of data that should be pushed on the stack and copied from the incoming argument area." If there was a variant that didn't need this size argument (would probably require being a tail call) then that would do it.
- panic 9y ago
  Could you do it with a C++ variadic template?
  - asveikau 9y ago
    That requires knowing types at compile time, and expands to just the code with the specific types used in the instantiation. That doesn't work with a virtual method dispatch kind of scenario where the types in the target method are not known to the runtime.
  - mikeash 9y ago
    Sort of. If you did it that way, then the message dispatch code would get compiled into the calling code rather than being a separate function. That would work, but it would greatly increase code size, and would also mean Apple couldn't make incompatible changes to how messaging works without breaking old code. This last part is fairly important: Apple does make such changes, and the fact that objc_msgSend is part of the system means that old programs just keep on working. They've introduced non-pointer isas and tagged pointers this way.

deleted 9y ago

[deleted]

gumby 9y ago

>> objc_msgSend is written in assembly. There are two reasons for this: one is that it's not possible to write a function which preserves unknown arguments and jumps to an arbitrary function pointer in C. > Wow... this is a bit off topic but can anyone expand on this side note and explain why? There are some good detailed replies in this thread but I thought I'd address your question at a higher level. People often refer to C as "an assembly language" but the usage is joking, or as an analogy. The C language has a high level representation of stack frames and the like (which, BTW, intimately reflect the architecture of the PDP-7/PDP-11 class of machines -- and thus due to the popularity of C have constrained the architecture of contemporary CPUs as well). If you want to violate C's assumptions you can't by definition do it in C. ObjC messages are essentially Smalltalk messages and they have different semantics. You don't have to become an assembly wizard but I suggest you may enjoy reading the C ABI for your favorite processor and then write a small assembly program that constructs a stack frame and calls a C function, and write an assembly function that can be called from C. More broadly, you may be interested in the theoretical work of programming language semantics (consider reflective languages like 2Lisp and 3Lisp, Brown etc) and consider why macros (not what C calls macros) aren't a way of trying to optimize code but actually extend language syntax. Theoretical computer science can seem arcane, yet really Gödel, Russel, et al really are applicable to machine code generation.

panic 9y ago
ObjC messages are essentially Smalltalk messages and they have different semantics. The method bodies themselves are ordinary C functions -- you can call methodForSelector: on any object to get one of its methods as a function pointer. The only problem is passing the arguments correctly.