Re: The current object

From	Bernd Paysan <bernd.paysan@gmx.de>
Newsgroups	comp.lang.forth
Subject	Re: The current object
Date	2013-05-15 16:46 +0200
Organization	1&1 Internet AG
Message-ID	<kn0aqb$d3v$1@online.de> (permalink)
References	(8 earlier) <klmji7$dm6$1@online.de> <2013May1.190138@mips.complang.tuwien.ac.at> <klsb20$7hk$1@online.de> <2013May2.162843@mips.complang.tuwien.ac.at> <klu9fd$ifv$1@online.de>

Show all headers | View raw

Andrew Haley wrote:
>> You need inline caches, when a vtable dispatch isn't possible.  The
>> standard explanation why a vtable dispatch is "more costly" than an
>> inline cache doesn't hold for contemporary processors with
>> pattern-based branch target buffers: There, the vtable dispatch is
>> better.
> 
> I doubt that.

Please do some measurements, if you don't believe me.  A call *offset(reg) 
is, when correctly predicted, exactly as fast as a direct call (with 
constant address) on a Core i7.

> But even if vtable dispatch is somewhat better, a
> cacheing "virtual function" approach is much more general-purpose, for
> very little extra cost.  It is the Rosetta Stone that allows different
> OOP systems, static and dynamic, to talk to each other.

The cost of misprediction is way too high.

>> And the inline cache, because it modifies an instruction on every
>> mis-predict,
> 
> No, no, no!  It does not do that; if it did the performance would be
> tragic.  What actually happens is that when a miss is detected the
> call site is rewritten to be polymorphic.  That only happens once.

That's one implementation option.  It has the disadvantage that any 
occasional polymorphic call makes the whole thing slow.  Wikipedia has at 
least a short summary on different options, for those who don't want to dig 
too deep into the details.

http://en.wikipedia.org/wiki/Inline_caching

> I'm not surprised you think this technique is slow, given your
> misunderstanding of how it actually works.  What are you thinking?
> That the people who write such systems are incompetent?

Always is a possibility.  I've seen a lot of very inefficient dispatch code, 
and things that I really don't understand - unless I consider incompetence.  
People tend to think very complicated, and don't find easy ways.  The easy 
way often needs several out-of-the-box steps to be in reach.

The original idea of inline caching (which is what I described above) sounds 
pretty awful, at least on today's CPUs.  It gives only benefits when your 
original dispatcher is a quite complex beast (like walking a list or so, 
searching for the right message).  In any case, I expect a language with a 
non-OOP foundation like Forth to have more polymorphic and less monomorphic 
calls - the vast amount of monomorphic calls in a pure OOP language like 
Smalltalk comes from using polymorphic methods for everything, even when 
there's absolutely no point - because that's the only thing you have.

So you have to optimize for polymorphic code, and take advantage of the 
improvements of current CPU architectures.  The monomorphic code is less 
likely.

>> No code update whatsoever needed, all caching happens in the CPU,
>> which is certainly better at caching.
> 
> Certainly?  Big tables aren't going to be a win with a small data
> cache.

You don't need to cache the entire table.  Chances are high that the 
relevant messages are in a small part of the table.  The idea is to 
increment the index for every selector you declare, so naturally, interfaces 
would have good locality.

> I think that obsessing about trivia like dispatch speed is completely
> the wrong way to design a system.  The right way to design it is not
> "what is fastest?" but to design the right system for *use*, one that
> accommodates different styles of OOP, and then decide on the best way
> to implement it.

But I'm already in the last phase.  I identified two needs: any message -> 
any object, and vtables, because a number of OOP thingies in Forth do 
construct vtables directly.  So since this is a primitive, I have the 
following requirements: No loops, no branches except the one call that is 
inevitable, no self-modifying code, as few instructions as possible.

Standard Forth programming style suggests that lookup tables are the best 
thing to do, don't walk lists.  Anton proposes a single sparse vtable, I 
suggest a two-stage approach, which should result in better memory 
utilization if several OOP programs are loaded into one system.  We have 
this in a number of places already, and consolidation of these (usually very 
limited) OOP-thingies is IMHO a good idea.

The other standard Forth suggestion is to do all the complicated stuff at 
compile time.  IMHO the only benefit you can get from inline caching is when 
you can completely inline the called method, and thus save the call 
completely, and open up opportunities to optimize more things (which 
inlining usually does).

> As part of the ARM64 HotSpot port I'll have a look at the vtable
> option and see if it helps.  I doubt it, but I'll try anything that
> might get me performance, especially if it doesn't involve much work.

I still wonder why you said that vtables are slow.  My measurements say that 
they are as fast as direct calls, when correctly predicted (and the 
predictors can even handle A/B/A/B/A patterns today).  What's different with 
your vtables?

My guestimate is that a

if(class==constant) then call <method> else rewrite_polymorphic(); fi

is at least one cycle worse on a Core i7 than a predicted vtable call, 
because the Core i7 can't do two branches in one cycle.  And given that the 
high-end ARM64 implementation will come from AMD, I expect to see very 
similar structures there, maybe with a conditional call (could help, but is 
there still one?).  There will be low-power AMD64 devices (like the 
big/little pair we have now) which won't do such a great job on indirect 
calls; they will stall the CPU and stop consuming power instead of doing it 
ultra-fast.

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: The current object (was: Went open source with my GA144 ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-02 14:28 +0000
  Re: The current object (was: Went open source with my GA144 ...) Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-02 19:58 +0200
    Re: The current object (was: Went open source with my GA144 ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-03 16:50 +0000
      Re: The current object (was: Went open source with my GA144 ...) Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-04 18:58 +0200
        Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-04 13:35 -0500
          Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-05 01:08 +0200
            Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-04 18:29 -0500
              Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-05 03:00 +0200
                Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-05 03:48 -0500
                Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-05 23:15 +0200
                Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-06 05:01 -0500
                Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-07 03:23 +0200
                Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-07 03:39 -0500
                Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-07 19:00 +0200
                Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-07 13:34 -0500
                Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-07 22:00 +0200
                Re: The current object anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-08 07:26 +0000
                Re: The current object Doug Hoffman <glidedog@gmail.com> - 2013-05-05 06:39 -0400
                Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-05 09:15 -0500
                Re: The current object Paul Rubin <no.email@nospam.invalid> - 2013-05-05 09:25 -0700
                Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-05 11:43 -0500
                Re: The current object Paul Rubin <no.email@nospam.invalid> - 2013-05-05 09:59 -0700
                Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-06 05:06 -0500
                Re: The current object Mark Wills <forthfreak@gmail.com> - 2013-05-06 00:19 -0700
                Re: The current object "WJ" <w_a_x_man@yahoo.com> - 2013-05-13 22:45 +0000
            Re: The current object Doug Hoffman <glidedog@gmail.com> - 2013-05-05 06:39 -0400
              Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-05 23:40 +0200
        Re: The current object Doug Hoffman <glidedog@gmail.com> - 2013-05-05 06:39 -0400
          Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-05 23:29 +0200
            Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-06 05:10 -0500
            Re: The current object Doug Hoffman <glidedog@gmail.com> - 2013-05-08 07:35 -0400
              Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-09 00:06 +0200
                Re: The current object Doug Hoffman <glidedog@gmail.com> - 2013-05-09 06:41 -0400
                Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-11 21:31 +0200
                Re: The current object Doug Hoffman <glidedog@gmail.com> - 2013-05-12 07:40 -0400
                Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-14 01:10 +0200
                Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-14 03:58 -0500
                Re: The current object anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-14 14:51 +0000
                Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-15 03:48 -0500
                Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-14 18:37 +0200
                Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-14 14:42 -0500
                Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-15 00:22 +0200
                Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-15 02:56 -0500
                Re: The current object stephenXXX@mpeforth.com (Stephen Pelc) - 2013-05-15 13:52 +0000
                Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-15 17:58 +0200
                Re: The current object albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-05-17 14:01 +0000
                Re: The current object johno <email@address.com> - 2013-05-15 22:38 +0100
                Re: The current object Doug Hoffman <glidedog@gmail.com> - 2013-05-14 06:27 -0400
                Re: The current object albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-05-09 16:06 +0000
        Re: The current object (was: Went open source with my GA144 ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-06 16:12 +0000
          Re: The current object (was: Went open source with my GA144 ...) Alex McDonald <blog@rivadpm.com> - 2013-05-06 10:25 -0700
          Re: The current object (was: Went open source with my GA144 ...) Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-07 04:00 +0200
            Re: The current object (was: Went open source with my GA144 ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-07 15:02 +0000
          Re: The current object (was: Went open source with my GA144 ...) Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-07 04:09 +0200
            Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-07 03:41 -0500
              Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-07 19:02 +0200
            Re: The current object (was: Went open source with my GA144 ...) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-07 14:33 +0000
              Re: The current object (was: Went open source with my GA144 ...) Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-07 19:40 +0200
    Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-15 16:46 +0200
      Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-15 13:11 -0500
        Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-15 23:23 +0200
          Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-16 02:24 -0500
            Re: The current object anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-16 13:55 +0000
            Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-16 17:45 +0200
              Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-18 05:13 -0500
                Re: The current object Doug Hoffman <glidedog@gmail.com> - 2013-05-18 06:43 -0400
                Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-18 10:03 -0500
                Re: The current object Doug Hoffman <glidedog@gmail.com> - 2013-05-18 11:30 -0400
                Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-19 01:20 +0200
                Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-19 12:33 -0500
                Re: The current object Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-19 01:07 +0200
                Re: The current object Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-19 03:58 -0500
        OO dispatch (was: The current object) anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-16 14:07 +0000
          Re: OO dispatch Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-18 05:28 -0500
            Re: OO dispatch anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-20 11:28 +0000
              Re: OO dispatch Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-20 09:00 -0500
                Re: OO dispatch Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-21 01:37 +0200
                Re: OO dispatch Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-21 03:21 -0500
                Re: OO dispatch anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-21 12:24 +0000
                Re: OO dispatch Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-21 10:18 -0500
                Re: OO dispatch anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-05-21 16:03 +0000
                Re: OO dispatch Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-05-21 12:55 -0500
                Re: OO dispatch Bernd Paysan <bernd.paysan@gmx.de> - 2013-05-29 00:00 +0200
                Re: OO dispatch Mark Wills <markrobertwills@yahoo.co.uk> - 2013-05-28 15:49 -0700

csiph-web