Hi,

I am just trying to wrap (parts of) the OpenSSL¹ bignum library (large integer arithmetic) into something that makes using it look at least a little bit more elegant than using the naked procedural C API while at the same time trying to not overdo it and not create a heavy code monster instead of a lightweight wrapper.

The problem is: Each bignum needs to be allocated by OpenSSL and freed when no longer needed. If I make a Pascal Object or Class representing a bignum and overload the arithmetic operators and then have expressions like (a+b)*(c+d) I would need to find a way to create and destroy anonymous instances of bignums on the fly. I have tried making use of Interface and TInterfacedObject and this seems to do what I want: for example when witing A := A + B the + operator would return a new instance and the reference counting would then automatically call the destructor of A when it assigns the newly created number.

The question is: Isn't using interfaces only to get reference counting complete overkill in this situation, isn't there a more lightweight way of doing this (or something similar)? And also maybe does some clever and elegant pattern exist that would enable me to simply reuse the instance of A (if an initialized object exists already on the left side of the assignment) instead of destroying it and creating a new one? (OpenSSL would theoretically allow me to reuse the same allocated number handle for the result of an operation, I could do BN_add(a,a,a) without allocating more than one number handle)?

Bernd
_____
¹ I depend on OpenSSL already anyways, so I thought why not make use of its bignum too when I need it.

2011/7/28 Bernd :

And also maybe does some clever and elegant pattern exist that would enable me to simply reuse the instance of A (if an initialized object exists already on the left side of the assignment)

For example (pseudocode, not sure if this is allowed):

operator + (a,b: IBigNum):IBigNum;
begin
  if not assigned(Result) then
    Result := TBigNum.Create;
  BN_add(Result.BN, a.BN, b.BN);
end;

Am I allowed to access the Result in this way? I have done only a few experiments and at one time it seemed I could indeed access values of the fields of the object on the left side of the assignment through the Result variable but I'm not sure whether this was only coincidence or if this is actually allowed.

Bernd

2011/7/28 Bernd :

This was last night when I was experimenting with records and objects, I just tried it again with interfaces and there it is always nil.

2011/7/28 Bernd :

I have profiled it
http://imagebin.org/165317

procedure Loop(a,b: IFoo);
var
  I : Integer;
begin
  for i := 0 to 10000 do begin
    //BN_mul(b.Handle, a.Handle, a.Handle, b.Context);
    b := a * a;
  end;
end;

This creates and destroys an object of TFoo everytime and this in turn will also create and free resources inside OpenSSL, its only spending 37% of the time doing actually useful work (BN_mul).

I think I'm not going to continue this route. I can't see any possible way to make useful use of overloading these operators, other than making a few lines in other places of the code look a little bit nicer at the cost of degrading performance by a factor of 3 (for add instead of mul its even factor 6).

Occasionally I hear other people mentioning operator overloading as a must-have feature of any decent language but I wonder what real-world problems they are actually solving with it. Are other compilers better at dealing with these problems, is there room for improvement?

Bernd

Implement += and *= operator to avoid allocating new objects? You could also/instead override TObject.NewInstance and FreeInstance to implement a pool of objects.

-Flávio

I wonder if I could ask a silly question here, without displaying too much ignorance.

I generally understand the significance of an interface in the Windows context, where COM (or whatever today's name for it) is integrated fairly deeply into the OS.

But what of other OSes like Linux? Does the use of interfaces as a way of getting refcounted storage assume the presence of CORBA etc., and how much overhead is there at program startup- does it demand that an ORB be loaded into memory?

Occasionally I hear other people mentioning operator overloading as a must-have feature of any decent language but I wonder what real-world problems they are actually solving with it.

I think operator overloading is a pain. As you said: What is the advantage? For me operators should be defined by the language only (Pascal) so that everybody who reads the code imediately knows what happens. Instead you now need additional information (that can be far away from the code lines you review). That makes code obscure and less clear. But now there is no way back. It's implemented. Pascal moves in C direction...

While COM-interfaces in Delphi/FPC are designed to be Delphi compatible, they do not rely on COM. Basically a IInterface or IUnknown is simply an interface that contains calls for increasing/releasing a reference count. You as the implementor of the interface need to provide the implementation. So e.g. TInterfacedObject which implements IInterface implements a reference counting mechanism where the object is freed when the reference count reaches zero. In FPC/Delphi this reference count is normally controlled by the compiler by calling the methods of IUnknown, but in C/C++ these calls need to be done manually (AFAIK).

CORBA-interfaces as implemented by FPC are just plain interfaces without any methods defined. Also the compiler does not generate code to influence the reference count as it does with COM-interfaces.

Basically an interface in FPC/Delphi is something that allows you to use certain methods (those provided by the interface) without knowing what the implementing class does. The COM-interface just contain a bit more compiler magic, but that's it.

So no, you don't need an ORB or something like that.

Regards,
Sven

PS: There is also a third kind of interfaces called dispinterface that contain again more compiler magic and are indeed used with COM automation (or XPCOM on non-Windows).

I have run across another even more severe problem: Although using reference counted interfaces makes everything work without memory leaks there is one problem that gives all the nice syntactic sugar a really bad taste:

A := B

I am not allowed to overload the assignment of equal types. This means in the above I would have created a reference to B instead of a copy. If I now do an operation on A that does *not* create a new instance of it I will also change the value that B is pointing to, so I am *forced* to make new instances even if I could in some cases easily avoid them. Otherwise the user of that unit would have many WTF-moments when debugging the unexpected strange behavior in his code and all the efforts of making it look and behave natural would effectively be nullified by such a problem.

Bernd

So if I understand you correctly, use of interfaces does not imply use of OS or ORB facilities, but can permit it if required.

It improves readability, making it more logical. Say for instance you are working on Galois fields and you have to do arithmetic on the elements like this:

g1 + g2 / g3

If you don't have operator overloading, you have to do it with functions, like this:

gf_add(g1, gf_div(g2, g3))

This is not very readable, I'm sure you will agree. They have to be used carefully, however.

clear. But now there is no way back. It's implemented. Pascal moves in C direction...

Troll. C has no operator overloading.

Henry

2011/7/29 Jürgen Hestermann :

I'm not condemning it per se. It has its uses. I can still overload at least the comparison operators for example, I didn't want to rant against operator overloading in general. I only think it is overrated and often more complicated than useful.

If I have a type that can be created and deleted/overwritten on the stack on the fly (record, object) without needing a destructor to free additional resources then everything can be made to work as if it were a natural part of the language and there would be no performance penalty and everything would be fine.

My question was only if there are really many different real-world examples that go beyond the complex numbers example and maybe some simple linear algebra types, that can fit their entire data into a record on the stack without needing any allocation/deallocation of heap or external resources. Making a nice looking lightweight wrapper around an external library would surely be very desirable but I can't see any way to overcome the problems and these seem fundamental problems to me. This seems to need some non-trivial optimizations that might even need help from the compiler itself to make it really effective.

With interfaces and their reference counting it can be made to work but the cost of doing this seems so immense that I don't believe it is justifiable in many real world applications (at least not in my application).

Maybe if there were a way to make the compiler generate code to hook into whenever a record is created/deleted/overwritten on the stack this would allow some creative hacks around some of these problems but with classes and interfaces alone I can't justify the immense overhead that is associated with it.

Simply spoken: yes (although I don't know of a CORBA ORB usage myself(!))

Regards,
Sven

No. Just check the ref. count if you plan to do an operation on A: if it's >1, create a copy for A and operate on the copy.

Bernd wrote

With interfaces and their reference counting it can be made to work but the cost of doing this seems so immense that I don't believe it is justifiable in many real world applications (at least not in my application).

The performance penalty was the same reason
why I abandoned the use of interfaces in the
qt4 binding, just look at the way I used it in the qt2 binding: Though it was pretty nifty, people may not be aware of the performance cost of such albeit nice abstractions.

http://qtforfpc.cvs.sourceforge.net/viewvc/qtforfpc/qte/demo/qteobjects.pas?revision=1.2&view=markup

That's the problem, you always have to be very careful. They are easy to overlook in the code.
You can circumvent type-checking.
One more thing for the IDE to support (if it doesn't, you're royally screwed). At least in *Pascal strings are native types, so one less problem (and a big one in C++) to worry.

Of course he meant C++.

-Flávio

> I think operator overloading is a pain. As you said: What is the > advantage? For me operators should be defined by the language only It improves readability, making it more logical.

Just the opposite! It hides important imformation for the reading person.

Say for instance you are working on Galois fields and you have to do

arithmetic on the elements like this:

g1 + g2 / g3 If you don't have operator overloading, you have to do it with

functions, like this:

gf_add(g1, gf_div(g2, g3)) This is not very readable, I'm sure you will agree.

No, I don't procedure call clearly shows me that a complex calculation is done instead of an (atomic) add and division command on numbers.

For me the basic operators should be just that: Basic operators. Otherwise you have problems to interpret code.

For example, IMO the assignment := should just copy bytes, nothing more. There can be additional range checks but it should not lead to side effects you are not aware of. I had a hard time to find out that a simple "A:=nil" on a dynamic array does more than just copying bytes to the memory adress of A. As a side effect it uses the current pointer in A and frees memory. But I had just read this data from a file so that the pointer was garbage. I just wanted to init A. But what a surprise that this atomic assignment command does more on dynamic arrays! If I create pointers to types on my own, this does not happen.

Operator overloading weakens the meaning of the operators. It can be just everything but you do not see it anymore.

> clear. But now there is no way back. It's implemented. Pascal moves

in C direction...

Troll. C has no operator overloading.

I meant it in a more general spirit: Pascal was created to be clear and unambiguous while C was an improved assembler which ignored any kind of readability. Now all these obscure things creep into Pascal too so that in this respect there is not much difference between current C(++) and current Pascal compilers anymore.

> Say for instance you are working on Galois fields and you have to

do arithmetic on the elements like this:

> g1 + g2 / g3 > If you don't have operator overloading, you have to do it with

functions, like this:

> gf_add(g1, gf_div(g2, g3)) > This is not very readable, I'm sure you will agree. No, I don't procedure call clearly shows me that a

complex calculation

is done instead of an (atomic) add and division command on numbers.

And there is another advantage of using procedures/functions instead of overloading operators:
You can search for the procedure to look what it actualy does. How do you find the code that overloaded an operator?

Not if you use function/procedure overloading. Then the situation is exactly the same as for operators.

How do you find the code that overloaded an operator?

The automatic constructor/destructor concept of C++ causes the same overhead. And the overhead for a function or operator overloading based approach is the same imo. Or do you have any example where a function based approach performs better? Overloaded operators are converted into function calls, there is no real difference.

Repeating myself, if there isn't something like CodeTools (i.e. only with text search) is way more difficult to search for operator declarations.

> How do you find the code that overloaded an operator?

-Flávio

2011/7/30 Florian Klaempfl :

I didn't intend to mean it is better solved in C++ (or any other language), I didn't want to specifically criticize the Operator overloading how it is implemented in Object Pascal, I just spent some time experimenting with trying to wrap this bignum library in some clever way to make it look and behave nicely. I posted this thread only because at some point I realized that whatever I do to make it behave like a built in type it becomes slow and ineffective and the wrapper becomes big and complicated.

The reason is because it IS a function call.

A := B + C;
A := add(B, C);

This will create a new A and free the old one. I have no idea how to prevent this.

add(A, B, C);

with var or out arguments would enable me to re-use the existing A.

If I cannot find a way to let me look to the left *trough* the := operator from inside the + operator I have no Idea how to implement something like this, so I always have to create a new instance of A and let the old one be freed.

The solution that I have chosen now will force me to explicitly create and free them manually and all my methods take all variables as arguments, have side effects and don't return anything. The only operators that I have overridden are the comparison operators.

Here is the unit I am talking about in its current form (this is at least the fifth different variation/rewrite of it already and likely to change yet again once I have a new idea):
http://code.google.com/p/fpbitcoin/source/browse/trunk/openssl_bignum.pas

and here is an example where it is used (currently the only place because it is all still far from complete):
http://code.google.com/p/fpbitcoin/source/browse/trunk/bitcoin_base58.pas

And since I believe this is a very deep and fundamental problem and not only related or limited to FPC and not easily solved without massive changes to the compiler and the entire operator overloading syntax (if it is possible at all) I did not intend to make this a Pascal bashing thread. I LOVE this language and this compiler and the related projects around it.

if i understand correctly, your problem is not operator overloading or whatever in the language.

You have references.

Now you want to write counted references to references and deal with this in the overloaded operators

your problem is right into the counted reference to reference.

A := B makes A point to the same reference as B, and this is perfectly correct semantic, but this will not work correctly by itself if the referenced object is itself a reference (without counting) to another thing.

a pointer to a pointer...

you have to refcount the original pointer instead.

So the solution is to have a singleton that holds all references to all bignums and then work from that on.

2011/7/30 Bernd :

Imagine the following :

A -> C -> E
B -> D -> E

A is ref counted, and says that theres 10 references to the object C B is ref counted, and says that theres 5 references to the object D

But both C and D points to the same object !

So now you have actually 15 references to the same object.

Lets say objects gone out of scope and C is now counted at 0 on A, what to do ?

Deallocate C causes E to be deallocated, but, what happens at B -> D ?

So what you need ?

A -> Singleton -> E
B -> Singleton -> E

In other words, make an object that stores all bignums and decides when to allocate or deallocate then and work from that on.

Why? Searching for operator+ is no more difficult than for function add ?

This is exactly what ref. counting solves? Did you read my other mail regarding your problem with ref. counting?

Blanks and linebreaks... Of course if one always use the same editor, that supports searching for linebreaks, and often use Regex in it, maybe they'll remember whether its Regex flavor uses \b or \s or \w for blanks :-/ Of course this is not major, just annoying, since you'll rarely need it.
But maybe if FPC forced the symbol to follow the keyword immediately... ;-)

Best regards,
Flávio

2011/7/30 Florian Klämpfl :

This is exactly what ref. counting solves? Did you read my other mail regarding your problem with ref. counting?

Yes, of course Ref counting "solves" it (in the sense that it can all be made to work as expected and not leak memory) and your suggestion of checking the reference counter also solves the problem of detecting when a copy would be needed and when it is safe to recycle the existing object.

But this does not solve the initial problem that in most cases with operator overloading I simply do not have any access to the result and *must* create a new instance and in my bignum example this is 3 times slower than intelligently reusing existing objects.

A := B + C

The code in the plus operator cannot access A to change it even if it were safe to recycle the existing instance. It does not even know about the A, it has no way of looking "through" the function result to see what is on the other side and check its ref count, and so it *always* must create a new A and let the ref counting dispose the old one.

procedure Add(var A, B, C: TBigNum);

could check the ref count of A and optimize this greatly and simply recycle the existing instance if it detects that it is the only one. But a function

function Add(A, B: TBigNum): TBigNum;

does not have any other chance than *always* creating a new instance. Result is always nil, I cannot look "through" it, its a one-way street, I cannot make any assumptions what the result is used for and cannot check the operator overloading functions
could be defined like this (pseudo code):

operator + (var Result: TBigNum;  A, B: TBigNum);

then maybe but I'm not sure whether it would even be possible to make the compiler arrange things in such a way that such a thing could be done.

But the same applies to functions as well?

nobody provents you to code like
function

add(...)  : ...;
?

Searching for add might not be feasible because the symbol could be used a lot (I know about this because I'am a heavy "jump to symbol by grep"-user :)

But maybe if FPC forced the symbol to follow the keyword immediately... ;-)

I would argue that the operator is in practice a little more annoying and, well, unnecessary, but you're right that they can be equally "mismanaged".

Best regards,
Flávio

Why? Searching for operator+ is no more difficult than for function add ?

I don't what I have to search for when looking for the overload function of the operator +. Can I search for the text "operator+"? Never heard of this...

Also, when I use a function instead of operator overloading I can use a more speaking function name which can be found much easier. If I understand it correctly, then dozens of equal named functions exist when
+ is overloaded for dozens of types. That makes it harder to find.

Nevertheless, the fundamental problem with overloading is, that it hides information from the user. I never would have expected that := does more than just filling bytes for dynamic arrays. It obscures what realy happens.

Why not? This is not rocket science.

Well, the important word "know" was missing. It should read:

I don't *know* what I have to search for when looking for the overload function of the operator +. Can I search for the text "operator+"?

2011/7/28 Bernd :

¹ I depend on OpenSSL already anyways, so I thought why not make use of its bignum too when I need it.

I hope you're aware of the FPC GMP bindings:

http://wiki.freepascal.org/gmp

The section

http://wiki.freepascal.org/gmp#Extensions_bindings_.26_types

discuses extended bindings which use the automated memory handling and overloaded operators. See also the sources:

http://svn.freepascal.org/cgi-bin/viewvc.cgi/trunk/packages/gmp/src/gmp.pas?view=markup

starting at line 1684.

2011/7/31 Honza :

It seems the author fought with the same kind of problems and now there exist two ways of using these bindings, a thin one and a fat one with reference counting. I have considered this too.

But at the moment for my project the pragmatism has won: I need them only for very simple operations in only a few parts of the application and in tight loops where speed matters more than elegance or being able to write A:=B instead of A.Assign(B).

This means I am now representing them as Objects (not classes) and only a handful of inlined methods calling the external API and doing nothing else, no reference counting, no additional overhead, its just not worth all the effort for these 10 simple function calls (I'm not even using the complete API, only the bare minimum).

Unfortunately Using the GMP library for *this* project is not an option, it took me already a week to convince myself (and stop evaluating alternatives) that there is no way around depending on OpenSSL anyways (because I need ECDSA) and since this will also give me some other things for free (SHA and RIPEMD which I also need) and also the bignum that I need for Base58 I don't have to add yet another dependency for any of these things (at the moment).

*Maybe* I will later (when it all works) find the time and replace it with an existing native Pascal bignum implementation (I found one already) and then try to use this to implement ECDSA in Pascal myself and then get rid of OpenSSL altogether. But this has *very* low priority and can be done at any later time.

Bernd