[fpc-devel] Pointer cache for fast class/pointer access.

[Skybuck Flying]

> My assumptions for this idea are:
>  1. Pointers to classes are mostly stored on the heap, in slow RAM.

"
What's fast RAM?
"

That would be the CPU L1 cache ;)

> 2. Nested/delegated classes incur a pointer access penalty, the deeper the 
> nesting the higher the penalty.

"
Why? Nested classes are not a problem in OPL, more in C++ (multiple
inheritance!).
"

Nested classes are a problem because of the pointer overhead.

For example 100 nested classes will require 100 pointer lookups and thus 100 
instructions.

However there is an interesting solution for Free Pascal and Delphi which is 
the old "object" type.

This object type seems to behave in a nested way where it's one large data 
structure and only 1 to 2 instructions are needed for retrieving and storing 
the final nested level.

The Free Pascal/Lazarus and Delphi compiler calculates the final nested 
field offset just like Visual Studio 2010 C/C++ compiler does.

> 3. Pointers are rarely if ever stored in constant values in the 
> instruction encoding ?? Could you give an example of a “constant pointer 
> in an instruction” ?

"
E.g. address of a non-virtual method.
"

To get to the methods still requires a pointer to the class instance I 
think... so accessing a field, property or method doesn't matter, it all 
requires the same: a pointer to the instance, or in this case 100 pointers 
to the 100th nested class.

Or only 1 pointer to the calculated offset for the 100th nested object.

> 4. Pointers are probably frequently pushed out of data cache by other 
> data.

"
More frequently than what? A pointer can be used to access multiple
(different) items, so that pointers are more frequently used than other
data.
"

Arbitrary data/fields which might be accessed just once... so no further 
cache hits, or perhaps a single cache hit if it was cached thanks to cache 
lines... so even a single cache hit is still interesting for data. This 
would need to be take in carefull consideration ;)

For now a better solution seems to be for Delphi to keep supporting the 
object type and programmers requiring high performance to switch to object 
type. However I am not yet sure what the effect is of switching to object 
type, this might lead to reduced capabilities.

So a good question would be: what capabilities do classes have which objects 
do not have ?

> 5. CPUs/GPUs do not have pointer caches yet or anything else that detects 
> data as being pointers ?!

"
This indicates that there exists no need or no chance to improve the
current design.
"

Hmm this depends a bit on how you look at it. If all pascal/delphi 
programmers know what they are doing then yes.

But there is probably a whole lof of code/delphi programmers out there which 
simply default to "class type" while in same cases the "object type" might 
have been a better choice for performance.

This is known in cpu world where programmers do "dumb/unthoughtfull things" 
and then the cpu people get to solve it ! LOL.

So any CPU manufacturer wanting to accelerate Delphi programs might still 
benefit greatly by implementing a pointer cache. If there are enough Delphi 
applications out there to warrant this is a different matter.

One example of why Delphi programmers are limited to the current situation 
is the VCL: this is written entirely with classes and has pretty deep 
nesting. There is pretty much nothing a Delphi programmer can do about this, 
except modifieing the entire VCL and replacing every class with an object 
version of it.

So while in theory it might be possible, practice would be a different 
matter, time restrictions could also play a roll ;) :)

> 6. And finally the pointer cache would speed up Free Pascal/Delphi 
> application execution speed because of less stalls for pointer retrieval. 
> (Free Pascal/Delphi could then rival C/C++ or perhaps even exceed it 
> because of other smart Delphi features like Strings (no null terminator 
> searching required)).
>  Are these assumptions valid ?

"
Not really. Pointers rarely are used by themselves, instead they are
mostly used to access data in other memory areas (pointed to). It's more
important to keep related data together, e.g. in the same memory page.
"

I think for Delphi all of the assumptions I made are pretty valid, I am not 
sure about Free Pascal and Lazarus for example, does Lazarus LCL use classes 
everywhere ? If so then the same would apply to Lazarus as well.

The problem is with the pointers to the other memory areas as you describe 
it themselfes. The pointers function as a gate. To get to the other areas 
requires retrieving the pointer itself first. The pointer itself is also 
stored in memory and not in the instruction as you might believe. The more 
nesting the more gates there are and thus the slower the performance.

Conclusion:

By using classes gates are introduced into code, this can be prevented by 
using objects instead.

The gates can lead to CPU stalls when those gates are not in the CPU cache 
(and must first be retrieved from main memory), thus the suggestion for a 
"gate" cache, or pointer cache ;)

Bye,
  Skybuck.