Implementing a lookup table inside a procedure

[yogo1212]

Hello everybody,

I'm trying to do a lookup table inside a method and i found that the implemtation of nested procedures doesn't seem to be consistent.
+ Anonymous Methods are not implemented.
Both vital for writing optimized code.

Code: [Select]

procedure TInput.NotifyBinding(id: word; Value: smallint);
procedure Bound;
begin
  cb(bindings[id], Value)
end;

procedure Unbound;
begin
if dbg then
writeln('Callback undefined on ', dev.GetName, '''s input');
end;

type THonkProc = procedure is nested;
const run: array[Boolean] of THonkProc = (@Bound, @Unbound);
begin
  run[cb <> nil];
end;   
Error: Typed constants of the type 'procedure is nested' can only be initialized with NIL and global procedures/functions

I dont want to assign them in the method.
It is potentially called at 100 Hz and it would be a waste of cycles. And there's the possibility of pipeline flushing which would be dead cereal. It's not possible to optimize the out-of-order execution because the function itself is called via a lookup table.
(which means the processor has to do it at runtime, which i'm not sure he will)

I already posted a bug relating to this issue, but i mixed stuff up because i have been sitting on this for some days now and didn't get much sleep.

My assignment is to look over maaaaaaany lines of code and optimize the hell out of it for x86_64 architecture until monday.
Please forgive the nonsense i'm filing bugs for..

To make up for it, i would like to help implementing/fixing anonymous procedures and nested stuff issues.

[BigChimp]

Haven't looked at content of your post except to note that posting your operating system, compiler and Lazarus version would be *very* useful.

If you're running 2.6.2 you could try with trunk; there might be some fixes there; you could if necessary request backporting (e.g. via a bug report).

Edit: as you're willing to help improve the code, I'd suggest you post on the fpc mailing list. Better chance of getting to the right guy who can point you in the right direction.

[yogo1212]

Of course:

I'm using x86_64 Debian on amd64 with current Lazarus/fpc binaries from sourceforge.
Which would be Laz 1.0.8 and fpc 2.6.2.

I'll try getting the trunk version and report my findings.


Right now i'm dealing with

Code: [Select]

Error: Typed constants of the type 'procedure is nested' can only be initialized with NIL and global procedures/functionsWhich I think is horribly funny, because the const-section is also inside the function..

Have to go home and eat mooo

[Blaazen]

Try

Code: [Select]

{$mode Delphi}
....
type THonkProc = procedure;

[User137]

Why do such fancy tricks anyway? You would actually write more memory efficient and clearer code with:

Code: [Select]

begin
  if cb<>nil then Bound
  else Unbound;
end;

[yogo1212]

I thought delphi was the same as objfpc, but you taught me otherwise

after changing mode from objfpc to delphi and (@Bound, @Unbound) to (Bound, Unbound) i feel more like passing a procedure and not a pointer, but still i get this error:

Code: [Select]

Error: Typed constants of the type 'procedure is nested' can only be initialized with NIL and global procedures/functions
or just illegal Expression, when trying to use Pointers.

Right now im fideling with the use of const Pointers, but from what i get, a pointer to a nested function also needs the bsp (base stack ptr) of the parent method, which i wouldn't be needing, because i would call it only from the function itself.

After that i'll try to do it with assembly. I'll report back with the results :-)

But before that, i'll sleep for a while

@User137:
By doing so "effecient" would mean less memory but in my case this is critical code.
With Instruction-Prefetching, Pipelining and Branch-Prediction in mind, writing "if a <> b then" results in

Code: [Select]

cmp a,b
jz $bla // this is the "bad" instruction

Typically with at least intel-cpus:
1. This code cannot be torn apart, because other instructions might change flags. This prevents OOOE.(Google: OOO-Execution)
2. anytime there is a conditional jump, the cpu builds a table to try to predict which branch will be taken so that the instructions can be put in
3. The pipeline. When the cpus fetches operands that are going to be written back by a previous instruction, the Von Neumann-property is violated and the pipeline has to be flushed. This can take up to 20 cycles. Don't want that in a critical section
4. + as result of that another thread might be scheduled to run in the meantime, which will probably replace to page of instructions cached in the cpu, which is also bad, because there already are carefully chosen timers that should make sure that threads run as parallel as they can

AMD does some things differently and they don't stick to optimizations they introduce, that's why i'm not doing optimization for AMD.

[User137]

Well, to me it seems this thing isn't implemented yet. For what i can see, is that if i instantiate 3 class objects like this, all the nested procedures have same pointers. That says that objects have same shared space for the procedures, so they could be treated constants. At least i cannot think of a scenario where this nested procedure pointer would change during program.

Code: [Select]

{$mode objfpc}
{$modeswitch nestedprocvars}
...
type
  TSomeProc = procedure is nested;

  TSomeObject = class
    procedure Test;
  end;
...
procedure TForm1.FormCreate(Sender: TObject);
var i: integer;
begin
  for i:=1 to 3 do TSomeObject.Create.Test;
end;

procedure TSomeObject.Test;
  procedure SubProc;
  begin
    // Does nothing.
  end;
var proc: TSomeProc;
begin
  proc:=@SubProc;
  form1.memo1.Lines.Add(inttostr(ptruint(@proc)));
  Free; // Destroy here, so don't call Test again for same object
end;This prints 3 same numbers in memo, with or without Free called at the end of Test.

[irfanbagus]

@yogo1212
just curious, how much increasing performance you can get using your method ? you safe from jump instruction but you need call instruction right ? in other hand using "if", you can make Bound and Unbound static. my knowledge about modern cpu is very poor so cmiiw.

[yogo1212]

@User137:
Interesting, what you did there.
i always tell myself i don't have time for such nice tests

It is logical, that the number is always the same (if you print it that way):

Code: [Select]

inttostr(ptruint(@proc))
TSomeProc is two pointers wide. The first is the address, the second a base stack pointer address.
Just as procedure of object; is.
But as i'm calling only from within the parent procedure and the nested procs not returning or having any parameters, i wouldn't be needing the bsp-part. I would be happy without a stack-frame but that's only possible via inlining (or nor? Calling convention hacks?) and i cant be inling, because in a look up table.

Try casting @SubProc to something like this:

Code: [Select]

//Really bad style
TNestedMethodPtr = record
method, bsp: Pointer;
end;   
Or:

inttostr(ptruint(@proc))

@irfanbagus: The only downside of the "call"-call is that it will create a stack frame for methods which either return or use registers (bas because of memory access). At least on 32 bit. To avoid that you should be using the register calling convention. But even without that it is usually faster.
64 bit uses registers for calling by default.

Just make sure not to optimize code that isn't critical. As a start, try using callgrind and you''ll have a rough idea.
In this case, it's user input with up to, let's say 10 burst calls per second.

When i got it running with the nested procedure type i noticed that suddenly i could no longer access the fields of the class the parent member was a method of...
There is nothing like: procedure of object is nested;
It would be three pointers and disassembling the record i would have to create takes too much time.
Though, as i dont want to leave the context of object/method i'm already in, i dont see why i should need more than one pointer.

So I've decided to give up for now and go try harder next week.

I just stored the Bound/Unbound-methods as members  of the class. Not nice, but works without more complicated stuff.