conversion between ordinals and pointers

[dbannon]

Why double casts? Declare it properly.....

To add an integer into my list, so that it goes into the space reserved for a pointer, I must do -

Code: Pascal  [Select][+][-]

1.  function TSortList.Add(ANumber: integer): integer;
2. begin
3.     result := inherited Add(pointer(PtrUInt(ANumber)));      // hint
4. end;  

Declare what properly ?

BrunoK, 440bx - for performance reasons, I want as little as possible going on in this sort method. I found, for example, by getting rid of intermediate, locally declared variables, I could speed up this bottleneck by 30%. It now looks like -

Code: Pascal  [Select][+][-]

1. function SortOnDate(Item1, Item2 : Pointer):Integer; inline;
2. begin
3.     if TheMainNoteLister.NoteList[PtrUInt(item1)]^.LastChange
4.                     = TheMainNoteLister.NoteList[PtrUInt(item2)]^.LastChange then
5.         Result := 0
6.     else if TheMainNoteLister.NoteList[PtrUInt(item1)]^.LastChange
7.                     > TheMainNoteLister.NoteList[PtrUInt(item2)]^.LastChange then  
8.         Result := 1
9.     else Result := -1;
10. end;

   

In this particular method, I am sorting on a datestring in another list, TheMainNoteList. The cast generates a hint, I can live with that. PtrUInt is certainly the right cast to use in this direction but is not enough, of itself, going from integer to pointer.

Mark - I can be quite sure that the integer I am storing is never negative, its the index into the main FPList and I check its valid.

Thanks folks !

Davo

               

[440bx]

by getting rid of intermediate, locally declared variables, I could speed up this bottleneck by 30%. It now looks like -

Just FYI, local variables that are "absolute"(d) on top of parameters have _no_ impact on performance one way or the other.

OTOH, inlining the sort function (whenever possible) will usually have an impact, which is much larger in 32bit than in 64bit due to the difference in how the sort function parameters are passed.


 

[dbannon]

Just FYI, local variables that are "absolute"(d) on top of parameters have _no_ impact on performance one way or the other.

OK, so I benched marked that and you are (as expected) quite right. It does make for more readable code too ! So, my LastChange sort method now looks like -

Code: Pascal  [Select][+][-]

1. function SortOnDate(Item1, Item2 : Pointer):Integer; inline;  
2. var
3.    LItem1: SizeInt absolute Item1;
4.    LItem2: SizeInt absolute Item2;
5. begin
6.     if TheMainNoteLister.NoteList[LItem1]^.LastChange
7.                     = TheMainNoteLister.NoteList[LItem2]^.LastChange then
8.         Result := 0
9.     else if TheMainNoteLister.NoteList[LItem1]^.LastChange
10.                     > TheMainNoteLister.NoteList[LItem2]^.LastChange then         // ?? This gives most recent at the top
11.         Result := 1
12.     else Result := -1;
13. end;      
14.  

OTOH, inlining the sort function (whenever possible) will usually have an impact, which is much larger in 32bit than in 64bit due to the difference in how the sort function parameters are passed.

Ah, that is interesting, I was disappointed that inline seemed to buy me nothing, but only tested on on my 64bit linux platform. I'm leaving it in anyway ....

Thanks again !

Davo

[PascalDragon]

The documentation of ptrInt says:

[…] Ptrint is considered harmful and should almost never be used in actual code, because pointers are normally unsigned. […]
The introduction of the ptrint type was a mistake. Please use ptruint instead.

The not portable complaint is (at its heart) over 22 years old (insertion into tccnv.pas). I think it’s a relic of architectures not having a linear address space.

It has nothing to do with non-linear address space, cause back then FPC did not support such platforms.
It was introduced when the first 64-bit targets were introduced, because it was rather common to do things like SomeComponent.Tag := Integer(SomePtr) (especially as back then Tag was Integer as well) which would potentially lead to an invalid pointer value on 64-bit systems.
And even if one uses an ordinal value of the correct size considering that ordinals are easily assignable to eachother there is still the hint just so that the user is aware that they take care there.

I have a data structure based on a FPList, all I need store is a single integer in each element. So, I thought, the pointer is, sort of, an integer, why not store it there ?  Works perfectly (64bit Linux) but, of course, generates the "conversion between ordinals and pointers is not portable" warning when I typecast. For example, the sort method looks like -

Why not simply use a FGL.specialize TFPGList<Integer> or Generics.Collections.TList<Integer>? You don't have to deal with typecasts then and if you need to add functionality you can still do that by descending from the specialization.

Why double casts? Declare it properly. And Pointers can not be negative, so make sure it is a ptrUint (or Uintptr) and catch any negative value.{$R+}

If it's Integer values that are stored in the list then using UIntPtr would be wrong, cause you wouldn't be able to check negative values then (cause that's what's stored there: ordinary values, not pointers).

[440bx]

Thanks again !

You're welcome Davo.

[Josh]

Hi

Could this function be bench marked? needs math unit

Code: Pascal  [Select][+][-]

1. function SortOnDate(Item1, Item2 : Pointer):Integer; inline;
2. var
3.    LItem1: SizeInt absolute Item1;
4.    LItem2: SizeInt absolute Item2;
5. begin
6.    Result:=Sign(TheMainNoteLister.NoteList[LItem1]^.LastChange-TheMainNoteLister.NoteList[LItem2]^.LastChange);
7. end;

[dbannon]

Why not simply use a FGL.specialize TFPGList<Integer> or Generics.Collections.TList<Integer>? ....

Untyped parameters ? What would Nikolaus Wirth think of that ?

Seriously, I understand (sort of) that Generics are used when you don't know the type that might come in. I absolutely, completely and unequivocally know that the type and size of the data going in and out. Its an integer, it cannot possibly be negative and it cannot possibly be larger than an integer. Further, FPList is already widely used in my project and its well documented on the wiki. I have just now re-read the various Generics docs. Its not well documented.

If it's Integer values that are stored in the list then using UIntPtr would be wrong, cause you wouldn't be able to check negative values .....

Code: Pascal  [Select][+][-]

1. for i := 0 to AnotherList.Count -1 do
2.      SortList.Add(i);

If 'i' ever becomes negative I have a lot more trouble than I can imagine.

Josh - Are you asking how I benchmarked it ?  Easy, I have a FPList that each contains 2000 items, each only an integer (stored, to my shame, in a pointer's location). I sort that list by calling the List.sort() method passing the address of the sort method. A proportion of the time it takes to run is spent in the sort method. Right now, I have that total down to 4mS to 8mS. Here is a slightly simplified version -

 

Code: Pascal  [Select][+][-]

1.    // at this stage, the two indexes contain unordered data,
2.      T3 := GetTickCount64();
3.     TitleSearchIndex.sort(@SortOnTitle);                          // ToDo : running each sort in its own thread ?
4.     T4 := GetTickCount64();
5.     DateSearchIndex.sort(@SortOnDate);
6.     T5 := GetTickCount64();
7.     debugln('TNoteLister.NewSearch() ' + inttostr(T3-T2) + 'mS ' + ' TSort=' + inttostr(T4-T3) + ' mS DSort=' + inttostr(T5-T4) );

[PascalDragon]

Seriously, I understand (sort of) that Generics are used when you don't know the type that might come in.

This is not about not knowing what type comes in, but about using a container type that can be used with multiple different types without sacrificing type safety. If you want type safety with a TFPList you need to descend from it and add your own methods, properties and such. With a generic you simply specialize it and be done.

I absolutely, completely and unequivocally know that the type and size of the data going in and out. Its an integer, it cannot possibly be negative and it cannot possibly be larger than an integer.

And that's when I would “absolutely, completely and unequivocally” pick a TFPGList<> or TList<> cause I don't want to adjust TFPList so that it is as typesafe as what the compiler provides through generics and the RTL provides through its generic containers.

Further, FPList is already widely used in my project and its well documented on the wiki. I have just now re-read the various Generics docs. Its not well documented.

Patches are as always welcome. We are only so many people after all. Though at least for Generics.Collections you can also use the Delphi documentation, cause they're considered to be compatible.

If it's Integer values that are stored in the list then using UIntPtr would be wrong, cause you wouldn't be able to check negative values .....

Code: Pascal  [Select][+][-]

1. for i := 0 to AnotherList.Count -1 do
2.      SortList.Add(i);

If 'i' ever becomes negative I have a lot more trouble than I can imagine.

That was meant towards Thaddy, cause after all nothing in the code stops you from adding a negative value to the list and thus the code needs to be able to handle it correctly.

[jamie]

Amazing how a thread can get blown up.

 Getting back to the original request, wouldn't a TFPGLIST resolve a lot of headaches?

 I am not much of a Generics evocate but, in this case, I think it would reduce the congestion.

 Or did I get onto the wrong train?

 

[PascalDragon]

Getting back to the original request, wouldn't a TFPGLIST resolve a lot of headaches?

 I am not much of a Generics evocate but, in this case, I think it would reduce the congestion.

You did read that I already suggested that five posts or so above and dbannon rejected that? And yes, in my opinion that would be the easiest solution as well.

[MarkMLl]

Untyped parameters ? What would Nikolaus Wirth think of that ?

NIH, must be bad. AND SOMEBODY SPELT MY NAME WRONG!!!!! :-)

Seriously, I understand (sort of) that Generics are used when you don't know the type that might come in. I absolutely, completely and unequivocally know that the type and size of the data going in and out. Its an integer, it cannot possibly be negative and it cannot possibly be larger than an integer. Further, FPList is already widely used in my project and its well documented on the wiki. I have just now re-read the various Generics docs. Its not well documented.

Writing as somebody with no great love for "computer sciencey crap", I have some sympathy with that. However, provided that the implementation is efficient the idea does have some merit: it /is/ desirable to be able to generalise this over ordinals of various size, and the only place where the signedness of the ordinal (specifically, whether it is a signed or an unsigned integer) is relevant is at the single > operation.

However, going back to Wirth's position: he was a proponent of single-pass compilers, possibly generating an intermediate bytecode but resolving all high-level issues before doing so. By comparison, there was a Pascal derivative called Pastel which had "parameterised types", but which worked by holding a representation of the entire program in memory until all types etc. had been resolved: Stallman fell foul of this when he tried to use it as the foundation of what became GCC.

So Wirth's objection would or at least /should/ not be that it was a verbose alien syntax, but that it couldn't be compiled efficiently by a single-pass compiler on a limited batch-oriented machine (i.e. cards in, cards out). My understanding is that FPC fixes it by being a 1.x pass compiler, where 0<x<999r: if I were trendy I'm sure I'd find a way to work "fractal" into that description :-)

Allowing that FPC /can/ handle this fairly elegantly using a generic, and assuming that the implementation is efficient, I see no reason (other than portability) to not use the facility.

MarkMLl

[avk]

...
Getting back to the original request, wouldn't a TFPGLIST resolve a lot of headaches?
...

If sorting performance is important (and I realized that it is), then the bad news is that FpgList has noticeably worse performance than FpList.

[dbannon]

You did read that I already suggested that five posts or so above and dbannon rejected that? And yes, in my opinion that would be the easiest solution as well.

Oh, please don't take offense PD, I value this and all the other advice you have offered.  But think about it, for you, well versed in generics, it might seem the "easiest solution" but to me, its plainly not. But I did make a note to go and read up more about this topic when time permits. And I will ! And maybe I'll write up what I learn for the wiki as I have done for a number of other topics. But only when I understand generics.

NIH, must be bad. AND SOMEBODY SPELT MY NAME WRONG!!!!! :-)

Ah, Niklaus, sincere apologies !

Allowing that FPC /can/ handle this fairly elegantly using a generic, and assuming that the implementation is efficient, I see no reason (other than portability) to not use the facility.

Except, perhaps, that I don't know how to use generics and the FPList solution is already working ?

Amazing how a thread can get blown up.

Amazing, and brilliant !

If sorting performance is important (and I realized that it is), then the bad news is that FpgList has noticeably worse performance than FpList.

   well, it turns out I like doing benchmarks, we'll see.

Davo

EDIT: typo

[PascalDragon]

So Wirth's objection would or at least /should/ not be that it was a verbose alien syntax, but that it couldn't be compiled efficiently by a single-pass compiler on a limited batch-oriented machine (i.e. cards in, cards out). My understanding is that FPC fixes it by being a 1.x pass compiler, where 0<x<999r: if I were trendy I'm sure I'd find a way to work "fractal" into that description :-)

Parsing is still done as a single pass. This will only slightly change once more complex expressions with inline specializations in mode Delphi are supported, because then back tracking might be needed (in most situations it won't be however). However in non-Delphi modes (and Delphi modes as of right now) parsing is done in a single pass. The whole code generation is done in multiple passes however to allow for optimizations (where parsing is only a single pass).

You did read that I already suggested that five posts or so above and dbannon rejected that? And yes, in my opinion that would be the easiest solution as well.

Oh, please don't take offense PD, I value this and all the other advice you have offered.  But think about it, for you, well versed in generics, it might seem the "easiest solution" but to me, its plainly not. But I did make a note to go and read up more about this topic when time permits. And I will ! And maybe I'll write up what I learn for the wiki as I have done for a number of other topics. But only when I understand generics.

I didn't take offense with you rejecting the idea. You might have your reasons or might simply not see the light yet. But I definitely rolled my eyes when jamie suggested something that I already had suggested...

[MarkMLl]

Except, perhaps, that I don't know how to use generics and the FPList solution is already working ?

Frankly, I'm inclined to agree. But this /is/ a textbook case: older iterations of the language, intent on avoiding casts, would no doubt have had separate FPxList implementations for pointers, signeds and unsigneds, but now they can be unified into a generic.

Provided that efficiency is equivalent.

MarkMLl