Author: Frédéric Hannes

Optimization: Comparisons

Frédéric Hannes

The first code optimization technique I’d like to discuss is the use of comparisons. Every modern programming language uses short-circuit boolean evaluation, so there’s not much I can say about that. However when programming there’s a few things you should keep in mind about comparisons. The first and most important being > and < require a lot more work to validate than == or !=. This is important to remember when you are writing high performance routines that require a lot of looping, small details like this can really speed up loops and certainly nested loops. Of course the speed increase won’t be gigantic, but all optimizations that can be applied together should have a nice impact.

Example:
You want to loop though an array of numbers. The intuitive way to do this would be to get the length of the array and build a for-loop that will loop while the index is smaller than the length of the array.
for (int i = 0; i < l; i++)
Now lets think about this. We start at 0 so the index will always be smaller or equal the length of the array. We increment the index with 1 on every run, so no indexes are skipped. As i will never be larger than l, we can therefore conclude that we can replace < with !=.
for (int i = 0; i != l; i++)
The same is true for > when you decrementing the index from a certain bigger number.

Another thing to remember is that when writing an if statement, when you know a condition will for example validate as true most of the time, put this is the if-clause.

Example:
You have a number to compare, you know that 95% of the time this number will be 5. So you write this:
if (i = 5)
…
else if (i = 2)
…
else
…
You can check the i = 2 statement first, however as you know the number is usually 5, it will save time to check the i = 5 first as it will usually never have to go any further.

A note: These optimizations are very language specific, for some languages they may not be effective or may even have an adverse effect.

Read More

Java: SelectionSort

Frédéric Hannes

SelectionSort is another sorting algorithm that has a performance of O(n²) like BubbleSort. It sorts an array of numbers by finding the smallest element in the unsorted part of the array and switching it with the current item. This is repeated until the entire array is sorted.

public static void selectionSort(int[] ia) {
	int l = ia.length;
	if (l == 1)
		return;
	for (int i = 0; i != l; i++) {
		int s = i;
		for (int j = i; j != l; j++)
			if (ia[j] < ia[s])
				s = j;
		int t = ia[i];
		ia[i] = ia[s];
		ia[s] = t;
	}
}

Read More

Delphi: Basic Brainfuck Interpreter

Frédéric Hannes

This is a really basic commandline brainfuck interpreter, it’s not written for speed or performance, it just shows you how a brainfuck interpreter should work. Of course you can speed it up by converting the code to a form of bytecode, working with pointers or even convert it to machine code.

program Brainfuck;

{$APPTYPE CONSOLE}

uses
  Classes;

const
  ARRAY_SIZE = 30000;

type
  TBFEngine = class
  private
    FScript: TStrings;
    FCompiled: AnsiString;
    FArr: array of Byte;
    FIndex: Integer;
    procedure Compile;
    procedure ClearArray;
  public
    constructor Create;
    destructor Destroy; override;
    procedure Run;
    property Script: TStrings read FScript;
  end;

{ TBFEngine }

procedure TBFEngine.ClearArray;
var
  i, l: Integer;
begin
  l := Length(FArr);
  for i := 0 to l - 1 do
    FArr[i] := 0;
end;

procedure TBFEngine.Compile;
var
  i, l: Integer;
begin
  l := Length(FScript.Text);
  FCompiled := '';
  for i := 1 to l do
    if FScript.Text[i] in ['>', '<', '+', '-', '.', ',', '[', ']'] then
      FCompiled := FCompiled + FScript.Text[i];
end;

constructor TBFEngine.Create;
begin
  FScript := TStringList.Create;
  SetLength(FArr, ARRAY_SIZE);
end;

destructor TBFEngine.Destroy;
begin
  FScript.Free;
end;

procedure TBFEngine.Run;
var
  c: AnsiChar;
  i, j, l, t: Integer;
begin
  Compile;
  ClearArray;
  t := 0;
  FIndex := 0;
  l := Length(FCompiled);
  i := 1;
  while i <= l do
  begin
    case FCompiled[i] of
      '>':
        if FIndex <> (ARRAY_SIZE - 1) then
          Inc(FIndex);
      '<':
        if FIndex <> 0 then
          Dec(FIndex);
      '+': Inc(FArr[FIndex]);
      '-': Dec(FArr[FIndex]);
      '.': Write(Chr(FArr[FIndex]));
      ',': Read(FArr[FIndex]);
      '[':
        if not Boolean(FArr[FIndex]) then
          for j := i + 1 to l do
          begin
            c := FCompiled[j];
            if c = '[' then
              Inc(t)
            else if c = ']' then
              if t <> 0 then
                Dec(t)
              else begin
                i := j;
                Break;
              end;
          end;
      ']':
        if Boolean(FArr[FIndex]) then
          for j := i - 1 downto 1 do
          begin
            c := FCompiled[j];
            if c = ']' then
              Inc(t)
            else if c = '[' then
              if t <> 0 then
                Dec(t)
              else begin
                i := j;
                Break;
              end;
          end;
    end;
    Inc(i);
  end;
end;

var
  Engine: TBFEngine;
begin
  if ParamCount = 1 then
  begin
    Engine := TBFEngine.Create;
    Engine.Script.LoadFromFile(ParamStr(1));
    Engine.Run;
    Engine.Free;
  end;
end.

Hello world in brainfuck:
++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.——.——–.>+.>.

Read More

Delphi: Binary Data Storage

Frédéric Hannes

When developing software you’ll often have to store data for some purpose, whether this being int he form of files that your program outputs, settings or other things. One of the things you’ll certainly almost always have to store are boolean values, True or False. This can be done in various ways, the worst way to tackle the problem would be to create a delimited string with the boolean values as strings ‘True’ and ‘False’, which would result in a string like ‘True|True|False|True|False|False|False|True’. The reason this is the worst way to handle the problem is simply because it takes up so much space. A boolean is a single bit value, meaning it contains a value that can be stored in 1 bit. By storing it in the previous manner you will be using 4 bytes or 32 bits for “True’ and 5 bytes or 40 bits for False and an additional 1 byte or 8 bits for each delimiter.

Another way to store the booleans is simple by converting them to byte values. Bytes are the smallest primitive datatypes in the Delphi programming language, they are 1 byte or 8-bit unsigned values. So by converting the booleans to this datatype, you can store a boolean as a single byte. This can be done by casting it to Byte and preferably convert it to a Char and back to Byte so you get the characters 0 and 1 as result Byte(Chr(Byte(MyBoolean))). Because the length of True and False is now the same, you can append this into a single string without delimiters, so your result will be something like ‘11010001’.

If you’ve counted the number of booleans in my previous examples you probably see where this is going. The previous method is ok to use but if you really want to conserve file size you should take it even a step further. The previous method uses a byte value to store a boolean, a byte contains 8 bits and as I mentioned before a boolean can be stored in a single bit as it can only be 2 values. so in theory this would let us store 8 booleans in a single byte. to do this we will have to write a bit more complex code. We will use bitshiting to shift up to 8 boolean values into a single byte and then reverse the process.

Selecting the most right bit in a value can be done by applying the bitwise and operator to the value along with the value 1. When you do this to a bit you can cast it directly to Boolean. If you want the next bit, you use a right bitshift of a single position to shift the value and then you can select that first bit again, only this time it will be the bit that used to be next in line. The same is true the other way around, to shift bits into a single value, you just convert a boolean to an integer and apply it to the value with a bitwise or, then you shift the value 1 position to the left with a left bitshift and you can repeat the process.

Here’s an example:

program BoolsTest;

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
  TBooleanArray = array of Boolean;

function BoolToChar(const Bools: TBooleanArray): Char;
var
  Buffer: Byte;
  i, l: Integer;
begin
  Buffer := 0;
  i := 0;
  l := Length(Bools);
  while (i < l) and (i <> 8) do
  begin
    Buffer := (Buffer shl 1) or Integer(Bools[i]);
    Inc(i);
  end;
  Result := Chr(Buffer);
end;

procedure CharToBool(const c: Char; out Bools: TBooleanArray;
  const Len: Integer = 8);
var
  Buffer: Byte;
  i: Integer;
begin
  Buffer := Ord(c);
  SetLength(Bools, Len);
  for i := Len - 1 downto 0 do
  begin
    Bools[i] := Boolean(Buffer and 1);
    Buffer := Buffer shr 1;
  end;
end;

var
  Booleans: TBooleanArray;
  c: Char;
begin
  // Initialize boolean array
  SetLength(Booleans, 8);
  Booleans[0] := True;
  Booleans[1] := False;
  Booleans[2] := True;
  Booleans[3] := False;
  Booleans[4] := False;
  Booleans[5] := True;
  Booleans[6] := True;
  Booleans[7] := False;
  // Convert booleans to char
  c := BoolToChar(Booleans);
  WriteLn(c);
  // Set the boolean array to False
  FillChar(Booleans, 8, 0);
  // Convert char back to boolean array
  CharToBool(c, Booleans);
  // Convert back to char to show the output is the same
  c := BoolToChar(Booleans);
  WriteLn(c);
  ReadLn; // Prevent window from closing
end.

Read More

Delphi: Operator Overloading

Frédéric Hannes

Delphi has the ability to include operator overloading for structured types, this allows you to use any standard operator on your structured type. The Delphi documentation on the subject states that you can apply operator overloading to both structured types and classes, however this is wrong, it can only be applied to structured types. Here’s an example of it being used:

program OperatorsTest;

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
  TIntValue = record
  private
    FValue: Integer;
  public
    class operator Add(const a, b: TIntValue): TIntValue;
    class operator Implicit(const a: Integer): TIntValue;
    class operator Implicit(const a: TIntValue): Integer;
    property Value: Integer read FValue;
  end;

{ TIntValue }

class operator TIntValue.Add(const a, b: TIntValue): TIntValue;
begin
  Result.FValue := a.FValue + b.FValue;
end;

class operator TIntValue.Implicit(const a: Integer): TIntValue;
begin
  Result.FValue := a;
end;

class operator TIntValue.Implicit(const a: TIntValue): Integer;
begin
  Result := a.FValue;
end;

var
  Int: TIntValue;

begin
  Int := 5;
  Int := Int + 10;
  WriteLn(IntToStr(Int));
  Readln; // Prevent window from closing
end.

The documentation shows you all of the operators you can overload and has some extra examples as well.

Read More

Java: BubbleSort

Frédéric Hannes

The bubblesort algorithm is one of the slowest sorting algorithms around as it’s performance is O(n²). As a result of this the algorithm is barely ever used in any real life applications, however, even though the algorithm will always stay rather slow, it can be tweaked to improve the code’s performance.

The implementation of the algorithm you see below has been optimized in various ways and it also makes use of the property that all items in an array of numbers that come after the last index that was sorted in a run through the array by the algorithm are already sorted.

public static void bubbleSort(int[] ia) {
	int l = ia.length, i = l;
	if (l == 1)
		return;
	while (i != 0) {
		int last = 0;
		for (int j = 1; j != i; j++)
			if (ia[j - 1] > ia[j]) {
				int t = ia[j];
				ia[j] = ia[j - 1];
				ia[j - 1] = t;
				last = j;
			}
		i = last;
	}
}

Read More

Delphi: Singleton Patterns

Frédéric Hannes

I’m a big fan of singleton patterns, basically a singleton pattern lets a class maintain a single instance of itself which you can then reuse as often as you want without having to create a new instance. This is achieved by creating a private static field inside the class that can hold an instance of itself, when the user wants to retrieve the instance for the first time, a new one is created and stored in the field, if there’s already one present, the class will return that instance. The implementation I usually use also has automated cleaning of the instance once the application terminates by adding a shared constructor. It’s also possible to add a private constructor to the class to disable the coder to create any instances of it directly without using the singleton pattern or subclassing it.

Here’s an example of the singleton pattern with cleaning:

type
  TTestClass = class
  private
    class var FInstance: TTestClass;
  public                               
    class function GetInstance: TTestClass;
    class destructor DestroyClass;
  end;

{ TTestClass }

class destructor TTestClass.DestroyClass;
begin
  if Assigned(FInstance) then
    FInstance.Free;
end;

class function TTestClass.GetInstance: TTestClass;
begin
  if not Assigned(FInstance) then
    FInstance := TTestClass.Create;
  Result := FInstance;
end;

It’s also possible to add a property named Instance or something even shorter that will get the instance from the GetInstance method which you would then make private, this will shorten the amount of code you have to write when using it.

Read More

Delphi: Static Members

Frédéric Hannes

Delphi comes with support for both OOP and procedural code, something you come across less every day as more languages move over to an OOP-only structure. Because of this static code in Delphi is often added as procedural code, which makes sense of course. However, Delphi also has the ability to add static members to classes which can be quite useful at times.

Delphi features several different kinds of static members. The first are fields and properties. A Delphi class can contain any number of static fields and properties which work the exact same way as a regular member would, however they can only be accessed in a static context. Same as with regular properties a static property can retrieve values by calling methods, however all of these accessors and mutators have to be static members as well.

Aside from fields, properties and methods, Delphi classes can also hold shared constructors/destructors. A shared constructor is called when the application is started and allows you to initialize static fields or other stuff you might want to initialize from a static context in or possibly outside of the class. A shared destructor is called when your application is terminated, this allows you to clean up static resources and such. This is similar to the initialization and finalization clauses, but part of a class instead of the entire unit.

Static fields have to be added by adding the keywords “class var” as prefix. For properties you just add “class”. Static methods need to have prefix “class” and they can also take a “static;” at the end, this isn’t required for regular methods, but it is for mutators and accessors. Shared constructors/destructors also only need to have “class” added in front of them. Note that static contructors/destructors can take any name, even Create/Destroy, but i personally prefer the names CreateClass/DestroyClass.

Here’s an example that will show you all of these features:

program StaticTest;

{$APPTYPE CONSOLE}

uses
  SysUtils, Classes;

type
  TTestClass = class
  private
    class var FStaticField: TStrings;
    class function GetStaticField: string; static;
    class procedure SetStaticField(const Value: string); static;
  public
    class property StaticField: string read GetStaticField write SetStaticField;
    class constructor CreateClass;
    class destructor DestroyClass;
  end;

{ TTestClass }

class constructor TTestClass.CreateClass;
begin
  FStaticField := TStringList.Create;
  FStaticField.Text := 'Hello world!';
end;

class destructor TTestClass.DestroyClass;
begin
  FStaticField.Free;
end;

class function TTestClass.GetStaticField: string;
begin
  Result := FStaticField.Text;
end;

class procedure TTestClass.SetStaticField(const Value: string);
begin
  FStaticField.Text := Value;
end;

begin
  WriteLn(TTestClass.StaticField);
  ReadLn; // Stop window from closing
end.

Read More

Cross-platform Delphi

Frédéric Hannes

After doing some further investigation it seems that the cross-platform support for Delphi has yet again been moved up to a next release. The fact that Embarcadero wants to wait for them to fully stabilize the product before releasing it is certainly an admirable thing to do, but it does bring up some questions…

So what does this mean for RAD Studio XE? We’ve seen 2 previews so far, it shows us some nice new features, a lot of integrations of 3rd party applications to make coding more convenient. However, a lot of these applications are limited because they have a paying version, yet there’s barely any or no details on how this is dealt with in RAD Studio. Another somewhat big concern is whether this release is actually worth purchasing when updating from RAD Studio 2010. So far we have seen no actual new Delphi language features being previewed, all that remains is a bunch of new tools in the IDE of which now part only seem to be added to somewhat bulk up the product and make it appear as more than just a bugfix release. Personally I’m waiting for some details on language features, however i must admit that the addition of RadPHP makes the product somewhat more appealing as it had to be purchased separately previously and since the initial release as Delphi for PHP, RadPHP seems to have matured quite a lot.

It seems Embarcadero has also released a new roadmap, though there’s very little communication from the company about why the cross-platform support was moved up or even that it was, it clearly shows on the new roadmap that was released just 6 days ago. The cross-platform support has been jumping around a lot on the roadmap since it was initially announced, but it seems they have now finally brought everything together in a release named project “Pulsar”, which I assume will be Delphi 2012. The release promises to include x64 support for windows applications and the inclusion of cross-platform compiling for 32-bit mac applications, only for Delphi however. The release has no mentioning of Linux support which previously vanished from the roadmap, however it has reappeared in the Wheelhouse release, however note that they carefully refer to the Linux support as support for Linux servers which might suggest it will not support GUI applications. This release will also bring the cross-platform and x64 support to the other RAD Studio products, mainly C++ Builder of course.

It seems to be clear Embarcadero wants to have the product catching up with competing products with the Commodore release, which will feature full 32- and 64-bit support for all platforms. However, when counting the number of projects it would suggest this being part of Delphi 2014. Even though they are certainly making an effort, it seems Embarcadero is once again dropping the ball here as they are already losing many (potential) customers because they do not support 64-bit and cross-platform at the present time, certainly 64-bit support will also become more pressing in the future as gradually more and more platforms are moving over to 64-bit. Will there be a market left for them when they finally catch up with the current day products of their competitors in 3 years from now?

An interesting item that I’m coming across a few times on the roadmap is the considered addition of a cross-platform VCL library. Originally this item was part of the roadmap as a somewhat standard item included with cross-platform support. However it seems that currently they are only considering to add this. How will this affect the cross-platform support? As I mentioned before they are saying that they will only include Linux server support into the Wheelhouse release, that would certainly require no GUI, so a cross-platform VCL library would not be required. However, for the Mac support you would want to be able to build visual applications. When they say they might not include a cross-platform VCL library, I’m guessing this means they intend to add a custom Mac-only library for compiling to Mac, personally i find the thought of this somewhat horrifying, the reason people are so eager to get cross-platform support is obviously to compile their applications to multiple platforms, having more than 1 visual component library needed to do so will obviously complicate things a lot. Because of this I am certainly expecting they will eventually move this feature over to the actual plans for one of the releases.

Read More