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.

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

What's fast RAM?

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!).

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.

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.

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.

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.

DoDi

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 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 ;) :)

"
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.

Please give example code of what you consider "nested classes".

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

Better question: what common capabilitiers are implemented differently in Object and TObject?

Try to answer that question first, then we'll see what you didn't understand.

DoDi

Something like this ;):

type
TDepth3 = class
public
  mValue : integer;
  constructor Create;
  destructor Destroy; override;
end;
constructor TDepth3.Create;
begin
mValue := 666;
end;
destructor TDepth3.Destroy;
begin
end;
type
TDepth2 = class
public
  mDepth3 : TDepth3;
  constructor Create;
  destructor Destroy; override;
end;
constructor TDepth2.Create;
begin
mDepth3 := TDepth3.Create;
end;
destructor TDepth2.Destroy;
begin
mDepth3.Free;
end;
type
TDepth1 = class
public
  mDepth2 : TDepth2;
  constructor Create;
  destructor Destroy; override;
end;
constructor TDepth1.Create;
begin
mDepth2 := TDepth2.Create;
end;
destructor TDepth1.Destroy;
begin
mDepth2.Free;
end;
procedure Demo1;
var
mDepth1 : TDepth1;
vValue : integer;
begin
mDepth1 := TDepth1.Create;
vValue := mDepth1.mDepth2.mDepth3.mValue;
writeln( 'vValue: ', vValue );
mDepth1.Free;
end;

I consider .mDepth2.mDepth3 nested classes ;)

Bye,
Skybuck.

IMHO, I think he talked about:
TFoo = object [vs] TFoo = class

Marcos Douglas

vValue := mDepth1.mDepth2.mDepth3.mValue;

You can implement such a funny hierarchy in any language. So what?

DoDi

-----Original Message-----

I said that. ;-)

TMyClass.Create: this is a call to the class constructor. MyObject.Create: this is a call to a method.

Object type is (very) older than Class type and I don't think the core team wanted some similarity between Object and Class types. Everybody prefer classes so, the Object type was forgotten.

I thinking if the Object type will be deprecated in the future... I hope not.

Marcos Douglas

Marcos Douglas wrote

Object type is (very) older than Class type and I don't think the core team wanted some similarity between Object and Class types. Everybody prefer classes so, the Object type was forgotten.

It wasn't the core team who introduced the differences between classes and objects, but Borland, who first created the "object system" in Turbo Pascal and later switched to the more advanced "class system".

I thinking if the Object type will be deprecated in the future... I hope not.

As Free Pascal still writes on its flag that it is compatible to Turbo Pascal I doubt that it will be deprecated (also there is quite some code in the compiler and also in some packages which use object).

Regards,
Sven

Hans-Peter Diettrich wrote

Better question: what common capabilitiers are implemented differently in Object and TObject?

The funny thing being that TObject is a class and not an Object :-)

-Michael

True, you're right.

Good to know ;)
And, as somebody asked, what the advantages (performance?) using Object instead Class?

I like to use Object to group routines instead of using procedure/functions... as a 'namespace' to not use the unit name as a prefix.
I would to know what do you, guys, think about it.

Marcos Douglas

They are basically similar to "records with methods" (which we now have as well...) if you use them directly (this means: not as pointer types): they are located on the stack and nested objects are part of the memory structure of the object. But if you use references to objects you work more like with classes as you have constructors, virtual methods and the objects are then located on the heap (thus you need to care for the memory management yourself).

I haven't implemented objects yet myself (besides testing whether some feature that was implemented for classes works for objects as well - which many features do!) and I also haven't used the new advanced records, so I'm the wrong person to ask this question ;)

Regards,
Sven

I don't see any reason why the Object type should be dropped. It's close to C++ objects, useful in porting code. It allows for static objects, e.g. in the stack, while TObject is bound to the heap (without tricks).

I used Object types to e.g. emulate C bitfields, with a simple typecast of a variable into the according object...

DoDi

That makes *what* difference?

DoDi

To clarify "nested": object types can inherit from other objects, like TObject can do - that's an advantage over records. They even can emulate multiple inheritance, because (as you pointed out) contained objects become part of the composed object, do not reside in a different (heap) area.

But if you use references to objects you work more like with classes as you have constructors, virtual methods and the objects are then located on the heap (thus you need to care for the memory management yourself).

Objects with virtual methods must not necessarily reside in the heap. A VMT reference is inserted into the object, as soon as the first virtual method is added. This leads to VMT pointers which do not reside at the begin of the instance memory, similar to interface references. OTOH the VMT (classtype!) reference at the begin of *every* TObject allows for "is" and "as" operators (RTTI).

DoDi

Ah, now I understand what you mean. Nonetheless I don't see sane reasons for creating such (deeply nested) structures in real life code - records would serve the same (demonstrated) purpose.

Also the slightly different syntax is kinda a shame... this would make it a little bit difficult to flip/flop between different "object models".

I don't see much of a difference here. Objects without constructors can be declared as simple variables. Objects on the heap have no advantage over TObjects, so that class types can be used for that purpose everywhere.

DoDi

So, Object types is indicated only for compatibility? In your opinion, for the atual code, we have some benefit using Object (stack) instead Class (heap)?

I used Object types to e.g. emulate C bitfields, with a simple typecast of a variable into the according object...

What is bitfields?

Marcos Douglas

If one really suffers from cache misses, then using prefetch(...) might be a good idea. And if data is heavily used, the CPU keeps it in the caches anyways and then CPU is very good in this. I doubt any serious perforance where data locked into L1 cache could improve program performance. Experience showed that any static predictions like this are much worse than that what the CPU can do at run time.

I once for some reason tried to compile TurboVision with Lazarus. In TurboVision TObject is an object, in Lazarus TObject is a class.

As this only was a test, after some lame efforts to solve the problem, I gave up.

So it does make a difference :)

And the funny thing is just the naming Borland chose when moving from TP to Delphi. There is a concept called "Object" that is similar but not identical to a concept called "class" and now they do a type "TObject = class".

-Michael

Delphi (now) provides Records with methods, but these lack inheritance. Why introduce such a crippled construct, when Objects can do the same and more (virtual methods...).

> I used Object types to e.g. emulate C bitfields, with a simple typecast of a > variable into the according object... What is bitfields?

C bitfields are parts of some integral type variable, with each field spanning one or more bits. They allow to e.g. subdivide DWORD parameters, which consist of several parts (combined with OR).

DoDi

one should consider a better layout of the data structures.

In your example a class hierarchy would be better suited, where no additional pointers are required to access base class members.

DoDi

In our previous episode, Michael Schnell said:

> Better question: what common capabilitiers are implemented differently > in Object and TObject? The funny thing being that TObject is a class and not an Object :-)

Which tobject do you mean? Objpas.tobject (Delphi) or objects.tobject (TP) ? :-)

In our previous episode, Sven Barth said:

Afaik records with methods is more advanced since they are initialized.

Afaik stack based TP Objects are not initialized and thus not safe for automated types. (I looked into upgrading TV with ansistring a few years back)

05.01.2012 15:45, Marco van de Voort пишет:

This is no longer correct, stack based objects are initialized and finalized if necessary. There was indeed an issue with inheritance (if both ancestor and descendant contain managed members, then members of ancestor were not handled), but I personally fixed that in r16335 a year ago.

Sergei

In our previous episode, Sergei Gorelkin said:

Ah, I thought Delphi didn't intialize them either, and therefore it was a won't fix.

But anyway, thanks, I updated the relevant wiki page.

In our previous episode, Sergei Gorelkin said:

r16335 is a commit by Michael?

r16335 | michael | 2010-11-13 16:51:43 +0100 (Sat, 13 Nov 2010) | 1 line

* Correction of PAFProtocols (Ivan Shikhalev, bug ID 17924 ------------------------------------------------------------------------

Mantis 16335 neither, that's about makefiles.

05.01.2012 16:12, Marco van de Voort пишет:

Oops... revision 16635 it is (more precisely, both 16632 and 16635). Sorry.

Sergei

Marco van de Voort wrote

Which tobject do you mean? Objpas.tobject (Delphi) or objects.tobject (TP) ? :-)

even more funny...

-Michael

AFAIK adding unit "objects" might have solved that (I have not tested that and thus I am simply guessing!). At least that unit contains a "TObject = object" declaration (see here at line 250: http://svn.freepascal.org/cgi-bin/viewvc.cgi/trunk/rtl/inc/objects.pp?view=markup).

Regards,
Sven

+1
But more about Object type, what do you think to use Object to group routines instead of using procedure/functions, as a 'namespace' to not use the unit name as a prefix?

Anyone else?

Thanks for clarification.

Marcos Douglas

Just this morning I had to move some methods out of a class, so that they could be used without an instance. IMO it's a bad idea to bind any general-purpose identifier to an artificial container (namespace...).

DoDi

Why?
Using an identifier (unit class object, or it) is better to reduce name conflicts, do not you think? The code also become more organized, IMHO.

Other way that people most do is using one or two letter to prefix (I use too) but you have to repeat the prefixes in all procedures/functions.

Marcos Douglas

When you have ambiguous names, you'll always have to disambiguate in code. If not, an identifier can be used as is.

DoDi

-----Original Message-----

Skybuck Flying wrote

Another more radical approach would be to insert the prefetch instructions into the computer program at runtime, but this would require self modifieing code and is probably way to futuristic/complex to program at this moment.

It doesn't require self-modifying code and it already exists, both for Just-in-Time and for native code environments. Here are a couple of links describing several variations of that idea (prefetching anything from memory to IO): http://scholar.google.com/scholar?q=prefetch+thread&hl=en&as_sdt=1%2C5&as_sdtp=on

Secondly, this list is about developing FPC, not about processor extensions.

Jonas

Skybuck Flying wrote

Finally if you do believe prefetching is a good alternative to a pointer cache or simply want to try out the effect of prefetching class pointers then I challenge you to implement it in a experimental branch of the free pascal compiler, so the prefetch idea can be tried out and tested !

Why don't you try yourself whether it has a positive effect? "prefetch" is already part of FPC's RTL since quite some time: http://www.freepascal.org/docs-html/rtl/system/prefetch.html

Regards,
Sven

... and the compiler itself uses it already for several years.

Out of interest: In what situations does the compiler use it?

Regards,
Sven

iirc somewhere in the hash lists and inside the assembler writer, just grep for "prefetch(" in the compiler sources ;)

Ah... inside the compiler's sources. I thought you meant "the compiler inserts calls to prefetch in specific situations". ^^

Regards,
Sven

Sven Barth wrote

Ah... inside the compiler's sources. I thought you meant "the compiler inserts calls to prefetch in specific situations". ^^

It can also do that, if you compile it with -dprefetchnext (at least if that still works, it's been a long time since I implemented and tried that). In that case, it will look for constructs like this:

while assigned(hp) do
  begin
    ...
    hp:=hp^.next;
  end;

and it will insert prefetch instructions like this:

while assigned(hp) do
  begin
    prefetch(hp^.next^);
    ...
    hp:=hp^.next;
  end;

I don't remember exactly, but I think it will also consider class fields as implicit pointers and insert the transformation there. At least for the compiler cycle this optimization does not change anything though.

Jonas