4 ms·

V-tables aren't a very expensive abstraction. They prevent inlining, which isn't exactly ideal (hell, that's the main point of the post), but nowadays their cos

by jeorgun 12y ago

V-tables aren't a very expensive abstraction. They prevent inlining, which isn't exactly ideal (hell, that's the main point of the post), but nowadays their cost over a normal function call is basically negligible.

coherentpony 12y ago
> V-tables aren't a very expensive abstraction. They prevent inlining, which isn't exactly ideal (hell, that's the main point of the post), but nowadays their cost over a normal function call is basically negligible. This is not true. Sweeping general statements like this are almost never true. It is really problem dependent whether a particular type of abstraction is 'too expensive' or not. I have to actively avoid vtbl lookups in my domain, and this is because if I don't I lose about 15% in execute time. You might think 15% "isn't very long", but it is when your application uses several thousand MPI processes.
- jasode 12y ago
  > I lose about 15% in execute time. Can you paste a representative snippet of your code that demonstrates this 15% penalty? In my experience with tight loops executing a million iterations, the extra indirection of a vtable lookup is never more than 1% slower. Others also observe similar minor differences.[1] [1]http://stackoverflow.com/a/667680 http://stackoverflow.com/a/667680
  - haberman 12y ago
    I have definitely observed penalties much greater than 1% (closer to 15%). This paper is old, but measures the direct cost of virtual table lookups (not taking into account indirect costs arising from the inability to inline) as 5% in real C++ programs. When they converted the C++ programs to use all virtual functions, the overhead rose to 13.7%: http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf
    - jasode 12y ago
      I didn't make it clear but I wasn't comparing inline to virtual.[1] That type of drastic difference can be greater than 10% which is understandable. I was comparing non-inline function to virtual function and I haven't been able to recreate a 15% slowdown even with zero compiler optimization switches. The stackoverflow observation and mine were on more modern cpus. Maybe that has something to do with the conflicting anecdotes. If someone has a small snippet of code that shows non-inlined function calls running 15% faster than vtable calls, I'd like to study it. [1]the context in grandparent post was already constrained to (non-inlined) normal function calls: ", but nowadays their cost over a normal function call is basically negligible." https://news.ycombinator.com/item?id=8476208 https://news.ycombinator.com/item?id=8476208
      - haberman 12y ago
        I had this benchmark that used to show a 10% difference between non-inlined and virtual: https://gist.github.com/haberman/5621682 https://gist.github.com/haberman/5621682 But since I wrote that, compilers have gotten too smart. When I tried it just now, the compiler devirtualized the function call (which I verified by reading the assembly language output). I should mention though, the the inability to inline virtual functions is part of what makes them less efficient in some cases. Isolating the inlining factor removes one of the benefits that makes non-virtual functions perform better.
      - srean 12y ago
        > I was comparing non-inline function to virtual function Then you are fighting a strawman. The decision to use virtuals or not has to be taken in the context of all the benfits, and inlining is a prominent one among them. Another is vectorization. Inlining a single function sometimes trigger an avalanche of other optimizations, so the cost of using virtuals can be quite high in such scenarios. It is a n unrepresentative to rule out some of the main motivators for choosing non virtual over virtual. In my experience people who harp on the line that virtual functions are free, are those who do not write number crunching code, where the benefits are most apparent. That said, vtable is really a neat performance optimization that targets runtime polymorphism. The problem lies in the fact that many people believe that runtime polymorphism is the only path to polymorphism. Java programmers certainly believe so, for a reason of course. Many uses of runtime polymorphism can be replaced by compile time polymorphism without any loss in flexibility, and frequent gains in performance. In many parts of code I know for certain that the types wont change, and in such cases runtime polymorphism is un-necessary. Many a game engine, array processing code has been written with zero or very sparse use of that feature. There is this raging debate about whether C++ / D functions should default to virtuals, just like in Java. I certainly am in the camp that believes that they should not because runtime polymorphism is not as uniform a necessity as it is made out to be, as long as the language offers compile time polymorphism. Java is out of luck here, its designers did not include compile time polymorphism features or syntactic sugars (if I am not mistaken) but for C++ and D their defaults make sense. @Jasode Indeed and in fact I had upvoted your comment even before writing my comment above.

by jeorgun 12y ago

coherentpony 12y ago

> V-tables aren't a very expensive abstraction. They prevent inlining, which isn't exactly ideal (hell, that's the main point of the post), but nowadays their cost over a normal function call is basically negligible. This is not true. Sweeping general statements like this are almost never true. It is really problem dependent whether a particular type of abstraction is 'too expensive' or not. I have to actively avoid vtbl lookups in my domain, and this is because if I don't I lose about 15% in execute time. You might think 15% "isn't very long", but it is when your application uses several thousand MPI processes.

jasode 12y ago
> I lose about 15% in execute time. Can you paste a representative snippet of your code that demonstrates this 15% penalty? In my experience with tight loops executing a million iterations, the extra indirection of a vtable lookup is never more than 1% slower. Others also observe similar minor differences.[1] [1]http://stackoverflow.com/a/667680 http://stackoverflow.com/a/667680
- haberman 12y ago
  I have definitely observed penalties much greater than 1% (closer to 15%). This paper is old, but measures the direct cost of virtual table lookups (not taking into account indirect costs arising from the inability to inline) as 5% in real C++ programs. When they converted the C++ programs to use all virtual functions, the overhead rose to 13.7%: http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf http://www.cs.ucsb.edu/~urs/oocsb/papers/oopsla96.pdf
  - jasode 12y ago
    I didn't make it clear but I wasn't comparing inline to virtual.[1] That type of drastic difference can be greater than 10% which is understandable. I was comparing non-inline function to virtual function and I haven't been able to recreate a 15% slowdown even with zero compiler optimization switches. The stackoverflow observation and mine were on more modern cpus. Maybe that has something to do with the conflicting anecdotes. If someone has a small snippet of code that shows non-inlined function calls running 15% faster than vtable calls, I'd like to study it. [1]the context in grandparent post was already constrained to (non-inlined) normal function calls: ", but nowadays their cost over a normal function call is basically negligible." https://news.ycombinator.com/item?id=8476208 https://news.ycombinator.com/item?id=8476208
    - haberman 12y ago
      I had this benchmark that used to show a 10% difference between non-inlined and virtual: https://gist.github.com/haberman/5621682 https://gist.github.com/haberman/5621682 But since I wrote that, compilers have gotten too smart. When I tried it just now, the compiler devirtualized the function call (which I verified by reading the assembly language output). I should mention though, the the inability to inline virtual functions is part of what makes them less efficient in some cases. Isolating the inlining factor removes one of the benefits that makes non-virtual functions perform better.
    - srean 12y ago
      > I was comparing non-inline function to virtual function Then you are fighting a strawman. The decision to use virtuals or not has to be taken in the context of all the benfits, and inlining is a prominent one among them. Another is vectorization. Inlining a single function sometimes trigger an avalanche of other optimizations, so the cost of using virtuals can be quite high in such scenarios. It is a n unrepresentative to rule out some of the main motivators for choosing non virtual over virtual. In my experience people who harp on the line that virtual functions are free, are those who do not write number crunching code, where the benefits are most apparent. That said, vtable is really a neat performance optimization that targets runtime polymorphism. The problem lies in the fact that many people believe that runtime polymorphism is the only path to polymorphism. Java programmers certainly believe so, for a reason of course. Many uses of runtime polymorphism can be replaced by compile time polymorphism without any loss in flexibility, and frequent gains in performance. In many parts of code I know for certain that the types wont change, and in such cases runtime polymorphism is un-necessary. Many a game engine, array processing code has been written with zero or very sparse use of that feature. There is this raging debate about whether C++ / D functions should default to virtuals, just like in Java. I certainly am in the camp that believes that they should not because runtime polymorphism is not as uniform a necessity as it is made out to be, as long as the language offers compile time polymorphism. Java is out of luck here, its designers did not include compile time polymorphism features or syntactic sugars (if I am not mistaken) but for C++ and D their defaults make sense. @Jasode Indeed and in fact I had upvoted your comment even before writing my comment above.