Following on from yesterday’s post, Barry Kelly (CodeGear engineer) kindly clarified a few points, one of which was that Generics support in Delphi 2009 won’t extent to unit procedures, only class methods, so speculation about a possible generic implementation of a Swap()/Exchange() routine was rendered largely academic.
Not to be dissuaded I came up with this solution to meet my current and quite possibly future needs.
Untyped Is Not Enough
I decided that the untyped parameter approach – despite it’s risks – was the one for me, avoiding a library full of overloads. To recap, this is the original untyped parameter implementation:
procedure Exchange(var A, B);
var
aa: Integer absolute A;
bb: Integer absolute B;
i: Integer;
begin
i := aa;
aa := bb;
bb := i;
end;
The problem with this implementation is that it does not support parameters that are not 32-bits in size. This isn’t a problem for the vast majority of cases (my cases – ymmv). It means that it does handle Cardinal, Integer, String (yes, String), object references etc etc. It doesn’t handle Doubles or TDateTime though, for example.
So, I added a refinement so that this routine can safely accomodate parameters of any size, as long as we correctly identify that size when we make the call:
procedure Exchange(var A, B; aSize: Integer);
var
a8: Byte absolute A;
b8: Byte absolute B;
a16: Word absolute A;
b16: Word absolute B;
a32: LongWord absolute A;
b32: LongWord absolute B;
a64: Int64 absolute A;
b64: Int64 absolute B;
aE: Extended absolute A;
bE: Extended absolute B;
i8: Byte;
i16: Word;
i32: LongWord;
i64: Int64;
iE: Extended;
p: Pointer;
begin
case aSize of
sizeof(Byte) : begin
i8 := a8;
a8 := b8;
b8 := i8;
end;
sizeof(Word) : begin
i16 := a16;
a16 := b16;
b16 := i16;
end;
sizeof(LongWord) : begin
i32 := a32;
a32 := b32;
b32 := i32;
end;
sizeof(Int64) : begin
i64 := a64;
a64 := b64;
b64 := i64;
end;
sizeof(Extended) : begin
iE := aE;
aE := bE;
bE := iE;
end;
else
GetMem(p, aSize);
try
CopyMemory(p, Pointer(@A), aSize);
CopyMemory(Pointer(@A), Pointer(@B), aSize);
CopyMemory(Pointer(@B), p, aSize);
finally
FreeMem(p);
end;
end;
end;
This is something of a step up in apparent complexity compared to the original – the specific handling of certain parameter sizes is a performance optimisation – the all-purpose CopyMem() approach is some 20x slower than the local variable implementation for 4 byte values, for example.
If anyone out there has some inline ASM that could improve things further, that would be welcome. I can’t seem to figure out the XCHG opcode!
Speaking of 4-byte parameters, as I say, most parameters used with this routine are 4-bytes, so the interface declaration for the routine declares this as the default aSize:
procedure Exchange(var A, B; aSize: Integer = 4);
In use of course things are still very straightforward:
var
a, b: Integer;
topleft, bottomright: TPoint;
s1, s2: String;
begin
Exchange(a, b);
Exchange(s1, s2);
Exchange(topleft, bottomright, sizeof(topleft));
end;
Don’t get me wrong – this is far from perfect. The compiler isn’t going to pick you up if you don’t provide aSize when you should or if you provide the wrong size in the aSize parameter although using sizeof() on one of the params, rather than a type name will help avoid that mistake.
Still, the idea of untyped parameters might be off-putting to some people, but bear in mind that FreeAndNIL() accepts an untyped parameter.
But, as with anything I post, no-one’s going to come knocking on your door demanding to know why you aren’t using my code – it’s your choice.
🙂
Whether or not you choose to use this routine yourself, quite possibly the techniques used might trigger some insight into some other problem you are facing.
Options For The Future
For this particular problem, the lack of generic support for unit procedures and (as things stand at least) the lack of type inferencing mean that even an implementation based on these new language features are going to have unappealing (to me at least) downsides.
Fixing things to suit this one procedure would be going too far. But maybe it would be useful to have such a routine “built in” to the compiler, perhaps as an operator:
a :=: b;
Which looks kind-a neat, pretty obvious and still “Pascally” to my eye at least.
I doubt I’m the first one to suggest it, and it strikes me that it should be very straightforward to implement. The compiler need only enforce that a and b are simple variables (not properties or function calls, for example) of the same type and generate the necessary inline code
This is the sort of thing that is possibly regarded as so trivial as to not be worth bothering with, even though implementing it would itself also be trivial. But I wonder, would it be something that a lot of Delphi developers would find useful?
I think I prefer a =:= b; over a :=: b; as it is slightly more visually recognizable.
In my student days, I got the chance to mess around with a N.Wirth family style language named PLANC
5 =: a =: b; // Store 5 in a, store a in b
It had really nice loop constructs as well.
http://en.wikipedia.org/wiki/PLANC
Perhaps it’s just me but one of the best features of Delphi is its strongly enforced typing. I can’t count the number of times that this has allowed the compiler to locate bugs in my code and save me very considerable debugging time. I’m really not convinced that type inferencing would be a step forward. For the same reason these ‘type-blind’ procedures don’t seem appealing. However I can accept that multiple overloaded procedures or methods may be just as unappealing to others.
a :=: b;
I LOVED this one. Someone please make it happen 🙂
How about the following assembly procedure, which you would call like this:
Exchange (@a,@b,SizeOf(a));
procedure Exchange (pA,pB: pointer; aSize: longword);
//pA (pointer to a) passed in EAX, pB in EDX and aSize in ECX
asm
cmp ecx, 4
jne @Not32bit
mov ecx, [eax] //ECX:= A (pointed to by [EAX])
xchg ecx, [edx] //Exchange ECX (A) and B (pointed to by [EDX])
mov [eax], ecx //A (Pointed to by [EAX]:= ECX (contains B)
ret //exit procedure
@Not32bit:
cmp ecx,0
jne @NotZero
ret
@NotZero:
cmp ecx, 2
je @Is16bit
cmp ecx, 1
je @Is8bit
cmp ecx, 8
je @Is64bit
cmp ecx, 10
je @Is80bit
//All other cases:
push ebx //Need to preserve EBX across ASM procedures!
@OtherSizeLoop:
//NB: this exchanges single bytes. If we were to exchange large data structures,
//it would be worthwhile to copy larger chunks
mov bl, [eax+ecx]
xchg bl, [edx+ecx]
mov [eax+ecx], bl
loop @OtherSizeLoop
pop ebx
ret
@Is8bit:
mov cl, [eax]
xchg cl, [edx]
mov [eax], cl
ret
@Is16bit:
mov cx, [eax]
xchg cx, [edx]
mov [eax], cx
ret
@Is64bit:
mov ecx, [eax]
xchg ecx, [edx]
mov [eax], ecx
mov ecx, [eax+4]
xchg ecx, [edx+4]
mov [eax+4], ecx
ret
@Is80bit: //Extended 80bit floating point value
fld tbyte ptr [eax]
fld tbyte ptr [edx]
//Now, ST(0) = B and ST(1) = A
fstp tbyte ptr [eax] //A:= ST(0) and pop FPU stack
fstp tbyte ptr [edx] //B:= new ST(0) and pop FPU stack
end;
There may still be room for optimisation, but it’s a start.
@Lars:
Hmmm, I don’t think it would really matter one way or the other. Either way I think it would be a neat little addition.
🙂
@Angus:
I largely agree, although it should be noted that type inferencing still produces type-safe code. My problem with it is that I fear that it makes it harder to read code without the aid of tools to provide the information that the compiler has to hand at compile time.
Untyped parameters are a little “uncomfortable”, but only a little. As I mentioned, FreeAndNIL() is type-blind yet it’s use is widely recommended and seen as a “good thing”.
For such limited-use routines as these I think it’s acceptable that a little care be needed when calling the routine. Not everything can done in a way that removes the need for all care or attention on the part of the developer; creating a false impression that we can will simply lead to developers making more errors, not less, imho – myself included. 🙂
@PhiS
Thanks!! A couple of things though – leaving the A, B params as untyped var’s is essentially exactly the same as passing untyped pointers but makes the calls less cumbersome (no need for @ operators). The other strange this is that this asm routine seems a little slower (10-20%!!).
This is based on quickly plugging the routine into a testing framework I’ve developed which supports performance testing as well as unit testing. I shall take a closer look this evening to see if there aren’t other things interfering. But thanks again.
What about an abstract class with the generic class method Swap?
Something like
Helpers = class
. class procedure Exchange(var A, B: T); static;
end;
class procedure Helpers.Exchange(var A, B: T);
var
. Tmp: T;
begin
. Tmp := A;
. A := B;
. B := Tmp;
end;
Helpers.Exchange(a, b);
Hi Andreas,
Yes, that is possible but I rail against classes that exist solely to serve as containers for things that do not need a class for any other reason.
They may be a necessary evil in other languages, but they are (imho) an abomination in Delphi where units give us the qualified containing scope we need, we shouldn’t – and don’t – need to fabricate artificial containers as workarounds.
The need to qualify with a classname (named incorrectly incidentally – imho – to hide the fact that it is an artifice – it should be THelpers) makes it awkward to use, even more so without type inferencing. I’m guessing that the site stripped the necessary type parameters from your comment:
Helpers.Exchange<Integer>(a, b);
vs
Exchange(a, b);
and is more cumbersome even than the slightly safer:
Exchange(a, b, sizeof(a));
The additional type safety in the generic class is undeniable. Whether it is critically and practically important and worth the cumbersome and awkward invocation syntax in this specific case is a different question.
I think compiler support for an exchange operator is the ideal solution.
🙂
Personally, I don’t use Exchange often enough for it to be worth taking time away from more useful compiler features (like type inferencing and generic unit-level routines). To be honest, I don’t think I’ve used anything like Exchange() in the past year. Probably much longer.
Just out of curiosity, what kind of code are you writing that makes such extensive use of Exchange?
Hi Joe,
It’s a fair question, and it’s not actually an “extensive” use of Exchange() that’s involved. I just happened to find myself wanting to exchange two object references that happened not be declared as TObject types, so my TObject version wouldn’t work for me (without hardcasting the params).
Generics *look* like they should be able to help but bizarrely would struggle to do a decent (imho) job in even this trivial little case.
How many incredibly useful little features would never make it into a/the language if the criteria was how often it is being used?
(a self-defeating question, since if the feature doesn’t exist it can’t be used, so the real question should be how often *would* you use it if it were available, and that is almost impossible to answer)
Not having it is a minor irk, at most. Really, no big deal.
But having it would bring a little spark of joy at those times when otherwise we might curse Pascal under our breath for not having such useful little time savers.
I have to say I’ve been surprised at the level of interest and engagement that the subject has attracted – perhaps that says something about how useful it might be. I don’t know.
@Joe White
Sorting all the kinds?
@Jolyon
Another neat feature that would be implemented in compiler – iif.
@Joe:
I can figure out, there’s a lot of algorithms that use “exchange” functionality e.g. graphical processing, sorting… It’s up to us to invent even more 🙂
@Jolyon:
Defining new operators/syntax elements could make Delphi more comfortable, though, at least, this requires to conform with some guidelines:
– readability (recognition)
– match syntax appearance with functionality
The “a:=:b;” solution isn’t really readable.
The “a=:=b” and the “a:=:b;” do mistakenly suggest an equality trough the use of the “=” sign.
A simple “ab;” could make it, maybe?
*second try*
A simple “a<->b;” could make it, maybe?
Thanks for the comment Lois, glad you figured out the formatting! 🙂
fwiw I think (if such an operator were to be provided) variations on the assignment operator would make most sense since the operation involved is a form of assignment.
Involving < and > could be a bit confusing given that these are usually most recognisable as relational operators (although their use in connection with generics also makes them parentheses – two uses is bad enough, a third would be really messy)
Hi,
why do you need the case statement? Why can’t you just use the code in the else part?
Hi Geza. 🙂
I don’t /need/ the case statement, but the CopyMemory() approach is 20x slower than using local variables so I provide local variable cases for those type sizes (it’s also the case that most calls are likely to involve these specific sizes – the CopyMemory approach is there for the rare cases, not the common ones).
@Jolyon:
I agree with you in the point, using the “greater than…” relational operators could lead to unexpected issues due to the syntax of generics (which I forgot to take into account while I was looking for a new age syntax 😉 ).
But … wait: Delphi 2009 is out!
And it supports Unicode (even the IDE itself)!
We’ll have to buildup our Unicode skills anyhow.
Why not starting now i.o.w. why not use an existing Unicode sign?
What’s about this really simple (and not too tricky) proposal?
“a ↔ b”
the ↔ can be accessed through its Unicode point value: ↔ or U+2194 or even through the HTML shortcut ↔
Alternatively: ⇔ i.e. ( ⇔ or ⇔ )
Hi Lois, I think you know what I’m going to say……
Where’s that key on my keyboard…? 😉
I want rotateVar(a, b, c …n)
tmp := a; a := b; b := c; … n := tmp;
and …
assign invoke?
update and modified require?
thread free?
How about testing this in your framework Jolyon?
How does it compare with your specific handling of certain parameters?
procedure Exchange(var A, B; ASize : Integer);
implementation
var
MemStream : TMemoryStream;
procedure Exchange(var A, B; ASize : Integer);
begin
MemStream.Position := 0;
MemStream.Write(Pointer(@A)^,ASize);
MemStream.Write(Pointer(@B)^,ASize);
MemStream.Position := 0;
MemStream.Read(Pointer(@B)^,ASize);
MemStream.Read(Pointer(@A)^,ASize);
end;
initialization
MemStream := TMemoryStream.Create;
MemStream.SetSize(1024);
finalization
FreeAndNil(MemStream);
@Todd – I might get around to testing the performance of this out of curiosity at some point, but I’m not in any huge hurry. Even if it is significantly more efficient I would never consider using it in The Real World™ as the use of a global memory stream object makes it hazardous to the health of multi-threaded code!
The singleton memory stream is hidden inside the implementation of the unit, so it is only accessible inside the Exchange() method. It would be easy to employ a critical section inside the procedure for multi-threading.
Yes, easy enough to fix, but why introduce a problem that has to be fixed, and a potential bottleneck ?
Adding a critical section would make the technique “safe” for threading but reduce the parallelism of an entire application.