Parnassus

Top Four

Thomas G Grubb – string comparison optimization

This project is a great example of badly written tokenizing, and an optimization that is much slower than the original code.

Thomas writes that the parsing code was based on FMX’s TPathData.SetPathString method (fixed in XE8) which had a loop getting a the next command in the path. Each time it compared to a string even if there was a match found earlier, in a set of if statements not joined by ‘else’ or not terminating early. Thomas’s version of this, “improved” with a Found flag, looks like:

procedure TForm1.StringCompareUnOpt(aString: String);
var
Found: Boolean;
begin
Found := False;
if aString = 'A' then
begin
Log('B');
Found := True;
end;
if (aString = 'One') and (not Found) then
begin
Log('Two');
Found := True;
end;
// … etcetera

if not Found then
Log('Unknown');
end;


Clearly checking against every possible string even when a match has already been found is not optimal, so this code needs some optimization. And everyone knows string comparisons are slow and a solution with a case statement on an integer would be faster, right?

The new code precalculates (as constants) hashes for the various strings that can be looked for. It then hashes the string and compares the hash in a case statement.

Here’s the optimized code:

const
StringA = 65;
StringFoo = 70063;
// etc

procedure TForm1.StringCompareOpt(aString: String);
begin
case aString.GetHashCode of
StringA: Log('B');
StringOne: Log('Two');
StringFoo: Log('Bar');
StringFour: Log('And Seven Years Ago');
StringHello: Log('World');
StringQuestion: Log('Answer');
else
Log('Unknown');
end;
end;


Much smaller code, clearer code, immediate action instead of falling through and comparing multiple times… right? No. First, it’s incorrect: the hash is case-sensitive (though the original code was too.) Second, what if the string constants change – you need to regenerate the constants – or what if GetHashCode’s implementation changes? It would suddenly not match anything. Third, it’s much, much slower. Calculating a hash is not necessarily fast. On my test machine, running the “unoptimized” code one million times took 81ms; running the new “optimized” version took 245ms. That’s three times slower.

I like this entry because it’s based on real code (from FMX), and because the optimization is plausible – someone could indeed write that code thinking they were speeding it up.

It reminds of a job interview I had a few months ago with a Big Company (who you would know, one of the top three.) We were discussing performance and algorithms, and they’d asked me to analyze some code and give the Big-O characteristics. Afterwards, I thought I’d mention how that kindof analysis is only a guide, and you need to know your data and algorithms and to profile when trying to solve a problem. The example I gave was where, many times, I’d seen a C++ std::map outperform a std::hash_map, especially on lookups. (A std::map is backed by a red-black tree, and uses multiple comparisons to navigate through the tree. A hash_map calculates a hash and then has a single lookup, assuming no collisions. The question is, at what point do multiple cheap comparisons cost more than a single potentially expensive hash calculation? In practice, depending on the data etc etc, and I’ve certainly seen this, there can be a point.) “No,” they replied in a very strong tone, “a std::map is O(n log n). A hashmap is O(1). It can’t be faster.” I didn’t hear back after the interview.

Yuta Tomino – EnumWindows

This is a very clever entry that probably only qualifies as ‘bad code’ because it’s tricky, written in assembler, and would be hard to maintain. The author writes, “Delphi has the enumerator idiom, known as outer-iterator, to implement an user-defined “for-in” loop. However, it’s hard to make an enumerator for EnumWindows API because call-back idiom, known as inner-iterator, is used to EnumWindows. Generally, converting from outer-iterator to inner-iterator is easy, but converting from inner-iterator to outer-iterator is hard… One of typical solution is using threads, but I think it’s extravagant heavy method only for a mere loop. Using fiber is a little lighter method than thread, but it also creates its own stack as thread… still heavy. So I have implemented the context-switch without new stack to this purpose, with inline-assember.”

Here are some of the methods:

function TEnumerator.MoveNext: Boolean;
asm
mov edx, TEnumerator[eax].FNext
mov TEnumerator[eax].FCurrent, edx {FCurrent := FNext}
{ jump to the current state }
xor edx, edx
mov dl, TEnumerator[eax].FState
mov edx, dword ptr[@JumpTable + edx * 4] jmp edx
@Start:
mov TEnumerator[eax].FState, esEnumerating
@Enumerating:
{ save the context }
pop ecx
mov TEnumerator[eax].save_esp, esp
mov TEnumerator[eax].save_eip, ecx
{ context switch }
mov TEnumerator[eax].caller_ebx, ebx
mov TEnumerator[eax].caller_esi, esi
mov TEnumerator[eax].caller_edi, edi
mov TEnumerator[eax].caller_ebp, ebp
mov TEnumerator[eax].caller_eip, offset @Next
mov ebx, TEnumerator[eax].enum_ebx
mov esi, TEnumerator[eax].enum_esi
mov edi, TEnumerator[eax].enum_edi
mov esp, TEnumerator[eax].enum_esp
mov edx, TEnumerator[eax].enum_eip
jmp edx
@Next:
{ restore the context}
mov esp, TEnumerator[eax].save_esp
mov ecx, TEnumerator[eax].save_eip
push ecx
mov dl, TEnumerator[eax].FState
cmp dl, esEnded
jne @Continue
{ unwind the stack }
mov eax, TEnumerator[eax].base_esp
lea edx, [eax - 16] { return address over the exception-frame (12-byte) }
mov eax, esp
mov ecx, 16
push edx
call System.Move
pop esp
@Continue:
mov al, 1
ret
@Terminated:
mov TEnumerator[eax].FState, esEnded
mov al, 1
ret
@Ended:
xor al, al
ret
@JumpTable:
dd @Start
dd @Enumerating
dd @Terminated
dd @Ended
end;

class function TEnumerator.Each(Item: Pointer; Self: TEnumerator): Boolean;
asm
mov edx, Item
mov eax, Self
push $12345678 //ecx {?... dummy, for escaping crash when some exception }
push ebp
mov TEnumerator[eax].FNext, edx
mov TEnumerator[eax].enum_ebx, ebx
mov TEnumerator[eax].enum_esi, esi
mov TEnumerator[eax].enum_edi, edi
mov TEnumerator[eax].enum_esp, esp
mov TEnumerator[eax].enum_eip, offset @Next
mov ebx, TEnumerator[eax].caller_ebx
mov esi, TEnumerator[eax].caller_esi
mov edi, TEnumerator[eax].caller_edi
mov edx, TEnumerator[eax].caller_eip
mov ebp, TEnumerator[eax].caller_ebp
jmp edx
@Next:
pop ebp
pop ecx {?... pop dummy}
mov eax, Self
mov al, TEnumerator[eax].FState
cmp al, esTerminated
setae al
end;


There are some subclasses of TEnumerator for windows and child windows, one being:

function TWindowCollection.GetEnumerator: TWindowEnumerator;
procedure Call;
begin
EnumerateWindows(CEachWindow(@TWindowEnumerator.Each), Result);
end;
begin
Result := TWindowEnumerator(TWindowEnumerator.GetEnumerator);
Call
end;


I have to straight-out admit that I do not understand the code here, and while I’m happy with reading basic assembler tracking I did not understand how this works. Even when tracing through execution in the debugger, trying to see how it achieved its results, I frequently got confused. There is one whole method that’s completely empty, yet is executed and achieves something (returning a list.) I think this entry errs far more towards the ‘impressive’ side than the ‘bad code’ side.

Alexander Benikowski – Mario

This is a very neat submission: Alexander implemented the basics of level Super Mario Bros level 1-1, where inside the game loop the entire game logic, for all entities, is implemented in a single statement. No, not a single line of code, eg where an ‘end else begin’ was just wrapped together – no, the entire game logic for all entities determining both if it needs to draw the entity and all logic for it, including input, movement, collision detection, etc is a single very, very long statement.

While coding this, Alexander found that the Delphi IDE does not handle lines of code longer than 1023 characters. The single statement is several times this length and is wrapped. He was quite disappointed by this because originally he had wanted to put the statement on a single line as well. Here it is, formatted:

for i := Low(GEntity) to High(GEntity) do
begin
//the following giant IF is executed per Entity. It evaluates if the Entity must be updated/painted
//and executes it's logik at the same run!

//execute only if active and has input or is near to the camera
if (GEntity[i].Active <> 0) and (GEntity[i].Input or (bfAlwaysUpdate in GEntity[i].BehaviorFlags) or (((GEntity[i].X - FCamera_X) >= -CActivityBorder) and ((GEntity[i].X - FCamera_X) < FScreenWidth + CActivityBorder))) and Boolean(Trunc( //reset some values TInterlocked.Exchange(LTargetEnt, CNoDynCollision) //get input + Integer(GEntity[i].Input and Boolean(Trunc(TInterlocked.Exchange(GEntity[i].Vel_X, 2*((GetAsyncKeyState(VK_RIGHT) shr 31 and 1) - (GetAsyncKeyState(VK_LEFT) shr 31 and 1)))))) + Integer(GEntity[i].Input and (GEntity[i].DownBlocked <> 0) and Boolean(Trunc(TInterlocked.Exchange(GEntity[i].Vel_Y, 6.5 * (GetAsyncKeyState(VK_SPACE) shr 31 and 1)))))
//apply velocity
+ Integer( (((GEntity[i].LeftBlocked = 0) and (GEntity[i].Vel_X < 0)) or ((GEntity[i].RightBlocked = 0) and (GEntity[i].Vel_X > 0))) and (TInterlocked.Exchange(GEntity[i].X, GEntity[i].X + GEntity[i].Vel_X) * 0 = 0))
//apply gravity
+ TInterlocked.Exchange(GEntity[i].Vel_Y, Max(-5, GEntity[i].Vel_Y - CGravity * GEntity[i].Gravity))
+ Integer((((GEntity[i].DownBlocked = 0) and (GEntity[i].Vel_Y < 0)) or ((GENtity[i].UpBlocked = 0) and (GEntity[i].Vel_Y > 0))) and
Boolean(Trunc(
TInterlocked.Exchange(GEntity[i].Y, GEntity[i].Y - GEntity[i].Vel_Y)
+ TInterlocked.Exchange(GEntity[i].InAirTimer, GEntity[i].InAirTimer + 1)
))
)

//////Collisiooncode...loooong!
//Trunc current position to pixels
+ TInterlocked.Exchange(LX, Trunc(GEntity[i].X))
+ TInterlocked.Exchange(LY, Trunc(GEntity[i].Y))
+ TInterlocked.Exchange(LBBLeft, LX - GEntity[i].bbWidth div 2)
+ TInterlocked.Exchange(LBBRight, LX + GEntity[i].bbWidth div 2 - 1)
+ TInterlocked.Exchange(LBBTop, LY - GEntity[i].bbHeight div 2)
+ TInterlocked.Exchange(LBBBottom, LY + GEntity[i].bbHeight div 2 - 1)
//do checks only if we are alive and do not ignore it!
+ Integer(not (bfIgnoreCollision in GEntity[i].BehaviorFlags) and (GEntity[i].Live > 0)
and Boolean(Trunc(
//collision checks
//static collision
//get collision values of edges of BoundingBox
//TopEdge
+ TInterlocked.Exchange(LTopEdgeLeft, FStaticCollision.Canvas.Pixels[LBBLeft + CEdgeIdent, LBBTop])
+ TInterlocked.Exchange(LTopEdgeRight, FStaticCollision.Canvas.Pixels[LBBRight - CEdgeIdent, LBBTop])
//LeftEdge
+ TInterlocked.Exchange(LLeftEdgeTop, FStaticCollision.Canvas.Pixels[LBBLeft, LBBTop + CEdgeIdent])
+ TInterlocked.Exchange(LLeftEdgeBottom, FStaticCollision.Canvas.Pixels[LBBLeft, LBBBottom - CEdgeIdent])
//RightEdge
+ TInterlocked.Exchange(LRightEdgeTop, FStaticCollision.Canvas.Pixels[LBBRight, LBBTop + CEdgeIdent])
+ TInterlocked.Exchange(LRightEdgeBottom, FStaticCollision.Canvas.Pixels[LBBRight, LBBBottom - CEdgeIdent])
//BottomEdge
+ TInterlocked.Exchange(LBottomEdgeLeft, FStaticCollision.Canvas.Pixels[LBBLeft + CEdgeIdent, LBBBottom])
+ TInterlocked.Exchange(LBottomEdgeRight, FStaticCollision.Canvas.Pixels[LBBRight - CEdgeIdent, LBBBottom])
//combine 2 corners each edge to determine if walking into the given direction is possible
+ TInterlocked.Exchange(GEntity[i].LeftBlocked, LLeftEdgeTop + LLeftEdgeBottom)
+ TInterlocked.Exchange(GEntity[i].RightBlocked, LRightEdgeTop + LRightEdgeBottom)
+ TInterlocked.Exchange(GEntity[i].UpBlocked, LTopEdgeLeft + LTopEdgeRight)
+ TInterlocked.Exchange(GEntity[i].DownBlocked, LBottomEdgeLeft + LBottomEdgeRight)
//Dynamic Collision
//get collision values of edges of BoundingBox
//TopEdge
+ TInterlocked.Exchange(LTopEdgeLeft, FDynamicCollision[FCurrentDC].Canvas.Pixels[LBBLeft + CEdgeIdent, LBBTop])
+ TInterlocked.Exchange(LTopEdgeRight, FDynamicCollision[FCurrentDC].Canvas.Pixels[LBBRight - CEdgeIdent, LBBTop])
//LeftEdge
+ TInterlocked.Exchange(LLeftEdgeTop, FDynamicCollision[FCurrentDC].Canvas.Pixels[LBBLeft, LBBTop + CEdgeIdent])
+ TInterlocked.Exchange(LLeftEdgeBottom, FDynamicCollision[FCurrentDC].Canvas.Pixels[LBBLeft, LBBBottom - CEdgeIdent])
//RightEdge
+ TInterlocked.Exchange(LRightEdgeTop, FDynamicCollision[FCurrentDC].Canvas.Pixels[LBBRight, LBBTop + CEdgeIdent])
+ TInterlocked.Exchange(LRightEdgeBottom, FDynamicCollision[FCurrentDC].Canvas.Pixels[LBBRight, LBBBottom - CEdgeIdent])
//BottomEdge
+ TInterlocked.Exchange(LBottomEdgeLeft, FDynamicCollision[FCurrentDC].Canvas.Pixels[LBBLeft + CEdgeIdent, LBBBottom])
+ TInterlocked.Exchange(LBottomEdgeRight, FDynamicCollision[FCurrentDC].Canvas.Pixels[LBBRight - CEdgeIdent, LBBBottom])
//combine 2 corners each edge to determine if walking into the given direction is possible
+ TInterlocked.Exchange(LDynLeft, IfThen((LLeftEdgeTop <> CNoDynCollision) and (LLeftEdgeTop <> i), LLeftEdgeTop, LLeftEdgeBottom))
+ TInterlocked.Exchange(LDynRight, IfThen((LRightEdgeTop <> CNoDynCollision) and (LRightEdgeTop <> i), LRightEdgeTop, LRightEdgeBottom))
+ TInterlocked.Exchange(LDynTop, IfThen((LTopEdgeLeft <> CNoDynCollision) and (LTopEdgeLeft <> i), LTopEdgeLeft, LTopEdgeRight))
+ TInterlocked.Exchange(LDynDown, IfThen((LBottomEdgeLeft <> CNoDynCollision) and (LBottomEdgeLeft <> i), LBottomEdgeLeft, LBottomEdgeRight))
// //if collided and not collided with self, add to entity collision state
+ TInterlocked.Exchange(GEntity[i].LeftBlocked, GEntity[i].LeftBlocked + IfThen((LDynLeft <> CNoDynCollision) and (LDynLeft <> i), LDynLeft, 0))
+ TInterlocked.Exchange(GEntity[i].RightBlocked, GEntity[i].RightBlocked + IfThen((LDynRight <> CNoDynCollision) and (LDynRight <> i), LDynRight, 0))
+ TInterlocked.Exchange(GEntity[i].UpBlocked, GEntity[i].UpBlocked + IfThen((LDynTop <> CNoDynCollision) and (LDynTop <> i), LDynTop, 0))
+ TInterlocked.Exchange(GEntity[i].DownBlocked, GEntity[i].DownBlocked + IfThen((LDynDown <> CNoDynCollision) and (LDynDown <> i), LDynDown, 0))
// //determine entity we collided with if exists
+ TInterlocked.Exchange(LTargetEnt, IfThen((LDynRight <> i) and (LDynRight <> CNoDynCollision), LDynRight, CNoDynCollision))
+ TInterlocked.Exchange(LTargetEnt, IfThen((LDynLeft <> i) and (LDynLeft <> CNoDynCollision), LDynLeft, LTargetEnt))
+ TInterlocked.Exchange(LTargetEnt, IfThen((LDynDown <> i) and (LDynDown <> CNoDynCollision), LDynDown, LTargetEnt))
+ TInterlocked.Exchange(LTargetEnt, IfThen((LDynTop <> i) and (LDynTop <> CNoDynCollision), LDynTop, LTargetEnt))
)))
//end of collisioncode!!!
//positional correction in case we are inside an obstacle
//do not correct Horizontal position if fallspeed was higher then walkspeed and we collided with floor to avoid being pushed of blocks we jumped on
//wen just a few pixels on the blocks
+ Integer(((Abs(GEntity[i].Vel_X) >= Abs(GEntity[i].Vel_Y)) or (GEntity[i].DownBlocked = 0)) and Boolean(
Integer( (GEntity[i].LeftBlocked <> 0) and Boolean(Trunc(TInterlocked.Exchange(GEntity[i].X, GEntity[i].X + 1))))
+ Integer( (GEntity[i].RightBlocked <> 0) and Boolean(Trunc(TInterlocked.Exchange(GEntity[i].X, GEntity[i].X - 1))))
))
+ Integer( (GEntity[i].UpBlocked <> 0) and Boolean(Trunc(TInterlocked.Exchange(GEntity[i].Y, GEntity[i].Y + 1))))
+ Integer( (GEntity[i].DownBlocked <> 0) and Boolean(Trunc(TInterlocked.Exchange(GEntity[i].Y, LY - 1))))
//bounce/reset velocity when colliding to reset falling momentum
+ Integer( (((GEntity[i].LeftBlocked <> 0) and (GEntity[i].Vel_X < 0)) or ((GEntity[i].RightBlocked <> 0) and (GEntity[i].Vel_X > 0)))
and Boolean(Trunc(
TInterlocked.Exchange(GEntity[i].Vel_X, GEntity[i].Vel_X * -GEntity[i].BounceX)
)))
+ Integer( (((GEntity[i].UpBlocked <> 0) and (GEntity[i].Vel_Y > 0)) or ((GEntity[i].DownBlocked <> 0) and (GEntity[i].Vel_Y < 0))) and Boolean(Trunc( TInterlocked.Exchange(GEntity[i].Vel_Y, GEntity[i].Vel_Y * -GEntity[i].BounceY)) + TInterlocked.Exchange(GEntity[i].InAirTimer, 0) ) ) + TInterlocked.Increment(GEntity[i].LastColliderTime) //if we collided with another entity(which we didn collide with in the last frame), which is alive and not in our team, attack and take damage! + Integer((LTargetEnt <> CNoDynCollision) and (GEntity[LTargetEnt].Active <> 0) and (GEntity[LTargetEnt].Team <> GEntity[i].Team)
and (((GEntity[i].LastCollider <> LTargetEnt) and (GEntity[LTargetEnt].LastCollider <> i))
or ((GEntity[i].LastColliderTime > 5) and (GEntity[LTargetEnt].LastColliderTime > 5))
)
and Boolean(Trunc(
+ Integer((LTargetEnt = LDynTop) and (GEntity[LTargetEnt].Live > 0) and Boolean(Trunc(
TInterlocked.Add(GEntity[LTargetEnt].Live, -GEntity[i].DamageTop*GEntity[LTargetEnt].VulnerableBottom)
+ TInterlocked.Add(GEntity[i].Live, -GEntity[LTargetEnt].DamageBottom*GEntity[i].VulnerableTop)
)))

+ Integer((LTargetEnt = LDynDown) and (GEntity[LTargetEnt].Live > 0) and Boolean(Trunc(
TInterlocked.Add(GEntity[LTargetEnt].Live, -GEntity[i].DamageBottom*GEntity[LTargetEnt].VulnerableTop)
+ TInterlocked.Add(GEntity[i].Live, -GEntity[LTargetEnt].DamageTop*GEntity[i].VulnerableBottom)
)))

+ Integer((LTargetEnt = LDynLeft) and (GEntity[LTargetEnt].Live > 0) and Boolean(Trunc(
TInterlocked.Add(GEntity[LTargetEnt].Live, -GEntity[i].DamageLeft*GEntity[LTargetEnt].VulnerableRight)
+ TInterlocked.Add(GEntity[i].Live, -GEntity[LTargetEnt].DamageRight*GEntity[i].VulnerableLeft)
)))

+ Integer((LTargetEnt = LDynRight) and (GEntity[LTargetEnt].Live > 0) and Boolean(Trunc(
TInterlocked.Add(GEntity[LTargetEnt].Live, -GEntity[i].DamageRight*GEntity[LTargetEnt].VulnerableLeft)
+ TInterlocked.Add(GEntity[i].Live, -GEntity[LTargetEnt].DamageLeft*GEntity[i].VulnerableRight)
)))
//store us as lastcollider in targetent so it does not interact with us on next frame
+ TInterlocked.Exchange(GEntity[LTargetEnt].LastCollider, i)
+ TInterlocked.Exchange(GEntity[LTargetEnt].LastColliderTime, 0)
+ TInterlocked.Exchange(GEntity[i].LastCollider, LTargetEnt)
+ TInterlocked.Exchange(GEntity[i].LastColliderTime, 0)
)))
//check DeadZone
+ Integer((GEntity[i].Y > CDeadZoneMin) and (GEntity[i].Y < CDeadZoneMax) and Boolean( + TInterlocked.Exchange(GEntity[i].Live, 0) )) //camera movement + Integer((bfCameraFollows in GENtity[i].BehaviorFlags) and Boolean( + TInterlocked.Exchange(FNextCameraY, Trunc(GEntity[i].Y) div CDeadZoneMax * FScreenHeight) + Integer((GEntity[i].X - FCamera_X > FScreenWidth-CCameraDeadZone) and Boolean(TInterlocked.Exchange(FNextCameraX, Min(FLevel.Width - FScreenWidth, Trunc(FCamera_X + (GEntity[i].X - FCamera_X - FScreenWidth + CCameraDeadZone))))))
+ Integer((GEntity[i].X - FCamera_X < CCameraDeadZone) and Boolean(TInterlocked.Exchange(FNextCameraX, Max(0, Trunc(FCamera_X + (GEntity[i].X - FCamera_X - CCameraDeadZone)))))) )) + Integer((bfCameraCenters in GEntity[i].BehaviorFlags) and Boolean( TInterlocked.Exchange(FNextCameraX, Trunc(GEntity[i].X - FScreenWidth div 2)) + TInterlocked.Exchange(FNextCameraY, Trunc(GEntity[i].Y - FScreenHeight div 2)) )) + TInterlocked.Add(GEntity[i].LiveTime, -1) //check if we died and take actions if this is true + Integer(((GEntity[i].Live < 1) or (GEntity[i].LiveTime = 0)) and Boolean(Trunc( Integer((GEntity[i].LiveTime = 0) and Boolean(TInterlocked.Exchange(LNextEntity, GEntity[i].ReplaceOnTimeOut))) + Integer((GEntity[i].Live < 1) and Boolean(TInterlocked.Exchange(LNextEntity, GEntity[i].ReplaceOnDead))) //deactivate us so we are removed next frame + TInterlocked.Exchange(GEntity[i].Active, 0) //replace with entity if specified + Integer((LNextEntity > 0) and Boolean(Trunc(
+ TInterlocked.Exchange(LNextEntity, i + LNextEntity)
+ TInterlocked.Exchange(GEntity[LNextEntity].Active, 1)
+ TInterlocked.Exchange(GEntity[LNextEntity].LastCollider, GEntity[i].LastCollider)
+ Integer((sfCopyPosition in GEntity[LNextEntity].SpawnFlags) and Boolean(Trunc(
+ TInterlocked.Exchange(GEntity[LNextEntity].X, GEntity[i].X)
+ TInterlocked.Exchange(GEntity[LNextEntity].Y, GEntity[i].Y)
)))
)))
)))
//check our current state(standing, walking, Jumping/InAir)
+ TInterlocked.Exchange(LSpriteState, CStand)
+ Integer((GEntity[i].Vel_X <> 0) and Boolean(Trunc(TInterlocked.Exchange(LSpriteState, CWalk))))
+ Integer(((GEntity[i].DownBlocked = 0) and (GEntity[i].InAirTimer > 1)) and Boolean(Trunc(TInterlocked.Exchange(LSpriteState, CJump))))
//check if we need to use a flipped version of our image or the normal one
+ Integer((not GEntity[i].NoDirection) and (GEntity[i].InAirTimer <= 1) and (GEntity[i].Vel_X <> 0)
and (Boolean((GEntity[i].Vel_X < 0) and Boolean(Trunc( + TInterlocked.Exchange(GEntity[i].Orientation, -1) * 0 - 1 ))) or Boolean( TInterlocked.Exchange(GEntity[i].Orientation, 1) )) ) + Integer(((GEntity[i].Orientation < 0) and Boolean(Trunc( Integer(TInterlocked.Exchange(LSprite, FFlippedSprites[GEntity[i].Sprite][LSpriteState])) * 0 - 1
))) or
Boolean(Trunc(
Integer(TInterlocked.Exchange(LSprite, FSprites[GEntity[i].Sprite][LSpriteState]))
))
)
//Calculate current Frame of sprite to display
+ Integer(((GEntity[i].Frames > 0) and Boolean(
TInterlocked.Exchange(LFrameCount, GEntity[i].Frames) * 0 - 1))
or
Boolean(TInterlocked.Exchange(LFrameCount, (LSprite.Width div CSpriteWidth)))
)
+ TInterlocked.Exchange(LFrameWidth, LSprite.Width div LFrameCount)
+ TInterlocked.Exchange(LSpriteFrame, FFrameCounter div (50 div 16) mod LFrameCount)
//Translate EntityPosition
+ TInterlocked.Exchange(LX, Trunc(GEntity[i].X - LFrameWidth div 2 - FCamera_X))
+ TInterlocked.Exchange(LY, Trunc(GEntity[i].Y - LSprite.Height div 2 - FCamera_Y))
//recalculate the BB area
+ TInterlocked.Exchange(LBBLeft, Trunc(GEntity[i].X) - GEntity[i].bbWidth div 2)
+ TInterlocked.Exchange(LBBRight, Trunc(GEntity[i].X) + GEntity[i].bbWidth div 2)
+ TInterlocked.Exchange(LBBTop, Trunc(GEntity[i].Y) - GEntity[i].bbHeight div 2 )
+ TInterlocked.Exchange(LBBBottom, Trunc(GEntity[i].Y) + GEntity[i].bbHeight div 2)
)*0-1)
then
begin
//Draw Entity


This works in several ways. It uses the TInterlocked.Exchange method (which returns a value so can be part of a longer expression) in order to achieve math and assignment of the result without having a ‘Result := …’ statement. The result is the left operand, and it’s given the value on the right. Multiple assignments are added together. In addition, he achieves a kind of ‘if-then-else’ by abusing Boolean short-circuit evaluation. For example,

((X > 0) and Boolean(Trunc(
TInterlocked.Exchange(A, B*C)
)))


is equivalent to

if X > 0 then
begin
A := B*C;
end;


An ‘else’ is added by using an ‘or’ and Alexander notes, “Something that is VERY important here is that we multiply the content of our “then”-Block with 0 and subtract 1. -1 represents the constant TRUE of delphi.” (I had thought that true was simply non-zero.) For example, this is an else statement added to the previous example:

(((X > 0) and Boolean(Trunc(
TInterlocked.Exchange(A, B*C) * 0 -1
))) or Boolean(Trunc(
TInterlocked.Exchange(E, X+Y)
)))


This is just under 14,000 characters in a single statement and, believe it or not, works. (Interestingly, when compiled with Seattle, it causes a number of range check errors and accession violations. However, it works fine with XE6. This actually adds points because it truly is bad code – can you imagine upgrading your IDE and trying to find an error in a single 14000-character long statement?)

Andrea Raimondi – Calculator

This entry’s readme has a nice backstory: it is a calculator project written by two developers, who also don’t use source control. Both developers are really bad.

The code is bad in many places – rather than being a solid block of code to look at, like most other entries, this reads far more like a real-life project. It crashes on startup. Once you continue, the calculator doesn’t work, and always returns a result for any expression of the first operand entered. (Ie, 2 + 3 = 2.) Even if this worked, a copy-paste error means any operations other than addition give the wrong result. It uses a TClientDataSet to store values, but is buggy because it addresses them both as ‘RESULT’ and as ‘_RESULT_’. The dataset is supposed to store previous answers, which you can access by pressing up or down in the number entry, but of course this is broken due to how it addresses them. Andrea suggested trying to debug by browsing the dataset; I didn’t try this but I can imagine it would not help at all. Even worse, the developers have defined a T0bject class (note the zero not capital O) and happily cast to and from it via ‘absolute’.

Here are some code snippets, with related methods nowhere near each other, of course:

procedure TForm1.AddResultToDB;
begin
CDSMaster.FieldByName( '_RESULT_' ).AsString := txtResult.Text;
end;

procedure TForm1.Button14Click(Sender: TObject);
begin
FOperation := Division;
AssignOperand;
end;

procedure TForm1.Button15Click(Sender: TObject);
var Result : Currency;
begin
case FOperation of
Addition: Result := FOperand1 + FOperand2;
Subtraction: Result := FOperand1 + FOperand2;
Multiplication: Result := FOperand1 + FOperand2;
Division: Result := FOperand1 + FOperand2;
end;
txtResult.Text := CurrToStr( Result );
end;

procedure TForm1.CDSMasterAfterScroll(DataSet: TDataSet);
begin
txtResult.Text := CDSMaster.FieldByName( 'RESULT' ).AsString;
end;

procedure TForm1.AssignTags;
var CompIndex: Integer;
ResultBtn : TButton;
begin
for CompIndex := 0 to ComponentCount -1 do
begin
if Components[ CompIndex ] is TButton then
begin
if Components[ CompIndex ] is TButton then
ResultBtn := Components[ CompIndex ] as TButton;
if Assigned( ResultBtn ) then
ResultBtn.Tag := StrToInt( ResultBtn.Caption[ Length( ResultBtn.Caption ) ] ) ;
end;
end;
end;

function TForm1.GetTag(AButton: TButton): Integer;
var Btn : T0bject absolute AButton;
begin
Result := TButton( Btn ).Tag;
end;

procedure TForm1.HandleButton(Sender: T0bject);
begin
txtResult.Text := ( GetTag( Sender as TButton ) ).ToString;
end;


Unlike the other entries, it’s hard to communicate how bad this entry is just with code snippets – it’s more of an overall effect.

What I like about this is the complete confusion that the two coders who write this must have about basic concepts. It’s realistic: I have seen code not too different from this.

Smaller code snippets

These are some interesting entries that were much smaller than the large projects listed above, but are good examples of bad code. Interestingly these are all to do with basic Delphi language methods or functionality – checking if a number is odd, and two to do with loop flow control.

Simon Müller – Odd or Even

Simon wrote, “This code was found by a coworker of mine in some legacy source code, probably written with Turbo Pascal. It returns a boolean value for a given Integer indicating if it’s even (true) or odd (false). Unfortunately the author apparently never heard of the Odd() function and decided to write his own implementation in an interesting (but horribly inefficient) way:

Divide by 2, subtract 0.1, convert this float value to a String with no decimals, convert the String to an Integer, multiply it by 2 and compare it with the initial value.

This code didn’t compile in Delphi 2010, so for this competition I decided to adapt it to working Delphi code.”

// Found in old source code, maybe Turbo Pascal?
function is_number_even(z:integer):boolean;
begin
if 2*value(realtostr(z / 2 - 0.1,10,0)) = z then is_number_even := true
else is_number_even := false;
end;

// Equivalent Delphi Code
function is_number_even(z:integer):boolean;
var lInt,lCode: Integer;
begin
Val(FloatToStrF(z / 2 - 0.1,ffFixed,10,0),lInt,lCode);
if 2*lInt = z then is_number_even := true
else is_number_even := false;
end;


Although a small snippet, an impressive example of horrific code.

Thaddy – For loop step

The ability to increment or decrement the loop variable in a for loop by a value other than 1 is occasionally requested. Here, a coder has implemented it themselves inside a for loop. Direct access to a for loop variable causes a compiler error so it’s altered via pointer access.

var
step:Integer;
begin
for step := 0 to 11 do
begin
writeln(step);
inc(PInteger(@step)^);// step 2
end;
readln;
end.


The code as written works, but changing the for loop to terminate at 10 shows the bug – the loop will never terminate.

Wouter van Nifterick – BreakStuff

Wouter pointed out that special functions like Break and Continue are not reserved words in Delphi, and in fact are pseudo-implemented in the System unit. That means they can be hidden if you define a Break procedure somewhere higher in scope.

For example, with a Break method in scope:

procedure Break;
begin
// Yeah, I'm pretty sure this will break something :)
end;


the following code no longer behaves as expected:

var i:integer;
begin
for I := 1 to 10 do
begin
WriteLn(I);

if I=5 then
Break;
end;
ReadLn;
end.

This makes it easy to introduce hard-to-find bugs.

Results

Results were judged on creativity, deviousness, and backstory. The prompt for the competition asked for “the worst believable code snippet or small app that you can [write], in the spirit of amusing, entertaining, or horrifying the reader.” Entries which clearly had a lot of effort put into them were rated more highly than small code snippets, as were entries which displayed creativity, abuse of the language, etc.

Of the top four, two were realistic code, code that could have been written by someone trying and failing: String comparison with the slow and buggy hash solution, and the Calculator with its absolute ineptness. The other two stretched limits: EnumWindows with complex assembler converting callbacks to a normal enumerable, Mario with its entire game logic in a single 14000-character-long statement.

Roman Yankovsky of FixInsight kindly donated a couple of licences for this competition. (I started it planning just to award a license of Navigator, when I realized the subject matter – bad code – was squarely in FixInsight’s purview. So, slightly disorganized, I asked Roman if he’d be interested in joining. He was.) Very kindly, Roman has also given input on the entries to assist with judging. We decided that rather than award one winner, we would have a winner and two runners-up, where the winner gets a license of both FixInsight and Navigator, and the runners-up each get a license of one of them.

For each winner, you should receive your prize(s) via email within 24 hours. If you don’t, please contact me!

The results are…

Honourable Mention: Thomas G Grubb, String Comparison

This was an excellent entry, and illustrated both some bad code, and some pitfalls when optimizing it. In a way, the code was almost too good: both the bad code and optimized code worked, and the logic behind the design of the optimized code makes sense. It very nicely illustrates a trap where a programmer can assume something is better based on basic CS knowledge, and without measuring. I struggled with not giving this entry a prize, because those are really good points to learn. Ultimately, despite the errors, other code was worse in a horrifying sense – which is a compliment to Thomas.

String Comparison wins a copy of Navigator.

Two runners-up: Yuta Tomino, EnumWindows, and Andrea Raimondi, Calculator

These were both excellent entries, showing a lot of time and effort. EnumWindows was one I do not understand, but was very impressive, and presumably absolutely unmaintainable (although I’m not sure; it’s very neat assembler.) It absolutely deserves a prize. Calculator was very realistic bad code, disorganized, confused and showing lack of understanding, and I appreciated the fact Andrea had even written a backstory explaining how the code got that way. It was the entry that I think most showed code decay, and the effects of several bad programmers with no source control working together.

EnumWindows wins a copy of FixInsight, and Calculator wins a copy of Navigator.

And the winner is…

First prize: Alexander Benikowski for Mario

Just imagine debugging a 14000-character-long logic statement. The idea by itself shows all the qualities of “amusing, entertaining, or horrifying the reader”. I think it entertains – I had lots of fun playing the level – and is a very creative example of terrible code. The single statement, and the tricks to squash a lot of logic into one statement, was very creative.

Mario wins a copy of both Navigator and FixInsight.

Congratulations to all, and thankyou to everyone who entered, including those who for space reasons I was unable to include here. Make sure you check out FixInsight, a static code analysis tool which will hopefully help prevent you writing code like you’ve seen here, and Navigator, which is code navigation done right; it lets you quickly jump around your unit (eg to and from the uses clause, a property, a method, anything important) right from the keyboard and adds a useful bonus minimap to the editor. If you like these tools, spread the word – Roman and I are both indie developers and every sale counts. Buy a copy yourself, get your boss to buy a bulk purchase for your company, or just link to them on twitter or forums. Thankyou.