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

[Skybuck Flying]

Hello,

*** Short version (more technical) ***:

Pointers to classes should be stored in a CPU or GPU pointer cache to prevent the pointer from being pushed out of the cache by other data items which might never be accessed again.

Pointers to classes have a higher likelyhood of being used again than just random/arbitrary data which is algorithm/data structure specific and cannot be know in advance by the CPU/GPU/Compiler.

My assumptions for this idea are:

1. Pointers to classes are mostly stored on the heap, in slow RAM.

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

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” ?

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

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

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 ? 

*** Medium version (bit whacky/vague/redundant) ***:

In Delphi classes are “reference-based” or something like that.

A pointer is stored in the variable, which points to some memory on the heap.

The pointer itself could also be on the heap.

This creates a little bit a pointer chasing problem and could be the reason why Delphi might sometimes be slower than C/C++, especially if the class nesting is deep.

I am not exactly sure how these pointers are encoded into the instruction stream ? For now I will assume these pointers are not encode into the instruction but instead reside on the heap/memory and are retrieved into registers. (So pointers are not stored as constants in the instruction itself).

Under these assumptions I propose a “pointer cache” in hardware/CPUs/GPUs which can store these pointers to classes. The idea is basically that these pointers are re-used a lot and should lead to high cache hit rates thus it’s pretty much garantueed that cache hits will occur and thus a smart decision to cache these, since highly likely hood of higher performance because of it. This would be at the expense of larger data cache. It’s not always garantueed that data will be hit again, unlike these pointers which probably have higher likelyhood of being used again... thus these pointers should be preferred to caching instead of random data.

I would like some feedback from free pascal developers if I am correct about how pointers to classes are stored either in Free Pascal and/or Delphi.

*** Longer version (bit boring/lengthy, obvious hardware implemention ideas) ***:

Here is the usenet message I posted on comp.arch and such for further details:

Delphi's classes/object instances work with pointers/references. This could 
mean Delphi has a level of indirection, this could mean Delphi applications 
perform a little bit slower when accessing objects because of this small 
pointer chasing problem.

However these pointers are accessed frequently would be my guess. Therefore 
the chance of a cache hit if these pointers were stored in a special pointer 
cache should be pretty high, thereby making the concept of a pointer cache 
possibly effective.

Not so with data caches. There is no garantee that the data will be accessed 
twice, and thus the likely hood of cache hits is unpredictable/uncertain.

Instructions are more likely to be re-execute hence an instruction cache.

The same could be done with these special pointers, a pointer cache.

So below the idea is explained a little bit more:

The pointer cache is ment to cache these pointers which point to 
objects/references. I am not sure where these pointers reside in memory. Are 
they hardcoded into the instruction stream ? Or are they indeed little 
pointer blocks somewhere in memory/on the heap ? If the last is the case 
then a pointer cache would benefit Delphi/reference/pointer languages.

The CPU or perhaps even in the future the GPU might need a hint to indicate 
that this pointer that is to be retrieved is a special pointer and should be 
stored in the pointer cache.

For 31 bit pointers a possibility could be to use the 32th bit to indicate 
that it's a special pointer. Alternatively perhaps a special instruction 
could be used to indicate that the next data access is to be stored in the 
pointer cache as well.

Before trying to retrieve data it is first examined if the data is already 
in the pointer cache thus leading to a pointer cache hit, the pointer can 
then be retrieved from the pointer cache.

The pointer cache would work like a regular data cache, the pointers used 
the most stay in the pointer cache or whatever caching strategy is used or 
contrieved.

Further examination of why the Delphi actually generates code should be able 
to shine some light if this idea is viable and interesting and usefull or 
not.

Perhaps consultation with Delphi compiler engineers might shine some further 
light on it.

Finally some simulations on super computers which are capable of executing 
x86 instructions and future ideas/instructions could also reveal if this 
idea is interesting or not ;)

Suppose the pointer cache idea does work and does lead to higher Delphi 
application performance/execution than the adventage of a value based 
language like C/C++ could be reduced and no longer a good reason to use 
C/C++ except perhaps if Delphi programs use way too many pointers ;)

An alternative idea could be to introduce a new class type or perhaps simply 
the old Tobject from turbo pascal so that Delphi can have "value based" 
types as well instead of references everywhere. Though references are pretty 
handy... but perhaps sometimes value based objects might make some sense as 
well for performance reasons...

Bye,
  Skybuck. 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freepascal.org/pipermail/fpc-devel/attachments/20111227/dbb37449/attachment.html>