Effect of using a constant parameter for string types (revisited)

Long eight years ago i wrote an post about using const for string parameters and effects in generated code. It showed benefits in using const for string types but was far from difference showed with similar test done with Delphi. I never bothered to replicate in Freepascal, i took it as granted.

As the discussion arose in forum, i decided to do a test equals to Delphi one, basically just using the parameter without modifying it, by the way, the most common usage.

I compared

procedure ByValueReadOnly(V: String);
begin
  DoIt(V);
end;

with

procedure ByReferenceReadOnly(const V: String);
begin
  DoIt(V);
end;    

The result talks by itself

Also compared

procedure ByValue(V: String);
begin
  V := V + 'x';
  DoIt(V);
end;

with

procedure ByReference(const V: String);
var
  S: String;
begin
  S := V + 'x';
  DoIt(S);
end;

The generated code is similar, size and performance wise.

For those that underestimate the impact of such differences, read this.

For the curious (or the wary), i uploaded the code.

The cost to supress a warning (and how not pay for it)

In the previous post, i pointed that passing a managed type (dynamic array) as a var parameter is more efficient than returning the value as a function result. However this technique have a known side effect: the compiler outputs a message  (Warning: Local variable "XXX" does not seem to be initialized) each time a call to the procedure is compiled.

The direct way to suppress the warning is change the parameter from var to out. Pretty simple but out does more than inhibit the compiler message. It implicitly initialize managed types parameters to nil or add a call FPC_INITIALIZE if the parameter is a record that has at least a field of a managed type. It does not add implicit code to simple types like Integer or class instances (TObject etc).

Although the performance impact is mostly negligible, is extra code anyway. In my case i initialize the parameter explicitly so out would add redundant code. There's an alternative to suppress the message: add the directive {%H-} in front of the variable that is being passed to the procedure. In the example of the previous post would be:

BuildRecArray({%H-}Result);

It can be annoying if the function is called often or the routine is part of a public API, otherwise is fine. At least for me.

Update: out does not generate initialization code for records that contains only fields which type is not automatically managed by the compiler, e.g., Integer.

Does it matter how dynamic arrays are passed/returned to/from a routine?

I was implementing a routine that should return a dynamic array and wondered if the produced code of a function and a procedure with a var parameter are different. So, i setup a simple test:

type
  TMyRec = record
    O: TObject;
    S: String;
  end;

  TMyRecArray = array of TMyRec;

function BuildRecArray: TMyRecArray;
begin
  SetLength(Result, 1);
  Result[0].O := nil;
  Result[0].S := 'x';
end;

procedure BuildRecArray(var Result: TMyRecArray);
begin
  SetLength(Result, 1);
  Result[0].O := nil;
  Result[0].S := 'x';
end;

var
  Result: TMyRecArray;

begin
  BuildRecArray(Result); //or Result := BuildRecArray
end.

Looking at the generated assembly revealed that the function version (returns the array in the result) leads to bigger code when compared with the procedure version (pass the array as a var parameter). More: the code difference is due to an implicit exception frame which is known to impact performance.

And what about the caller code? Again the function version generates more code (creates a temporary variable and calls FPC_DYNARRAY_DECR_REF).

In short: yes, it matters.

The cost of accessing object fields (part 2)

In the last post, we could see the benefits of using a temporary variable to access frequently used object fields. What if the object field is accessed only two times. The benefit would be maintained?
Let's see this example:
Before:

begin
  if FDataLink.Field <> nil then
    Caption := FDataLink.Field.DisplayText
  else
    Caption := '';
end; 

After:

var
  DataLinkField: TField;
begin
  DataLinkField := FDataLink.Field;
  if DataLinkField <> nil then
    Caption := DataLinkField.DisplayText
  else
    Caption := '';
end; 

It seems that yes, although very little (saves only two instructions). This is the kind of optimization to be done on only very sensitive areas.

Since the benefit was mainly due to the compiler saving the local variable in a register, a doubt that i had in mind was what would happen in a method with many parameters? The addition of the variable would still be beneficial?

So i tested the addition of a variable in a method with the following header

procedure DoIt(Sender, Sender2, Sender3: TObject);

As we can see, the version with the local variable is still smaller.

All in all, some like to say that less is more, but sometimes, as in this case, more is less!

The cost of accessing object fields (part 1)

The common sense make us believe that adding more code and/or more variables leads to bigger programs. Looking at the generated code of one example in the previous post, the addition of one variable made the executable smaller. This occurs because fpc is smart enough to reuse registers (in this case eax).

This week, while fixing one Lazarus bug i noticed the following pattern in the generated code of method TDBEdit.DataChange:

 movl 12(%ebx),%eax
 movl 24(%eax),%eax

Basically this is the code to access FDataLink.Field property (the first instruction get the FDataLink address and the second get the Field address). So what would happen if this field was "buffered" in a TField local variable?

Before:

procedure TDBEdit.DataChange(Sender: TObject);
begin
  if FDataLink.Field <> nil then begin
    Alignment := FDataLink.Field.Alignment; 
  [..]

After:

procedure TDBEdit.DataChange(Sender: TObject);
var
  DataLinkField: TField;
begin
  DataLinkField := FDataLink.Field;
  if DataLinkField <> nil then begin
    Alignment := DataLinkField.Alignment; 
  [..]

This simple change lead to these differences.

As expected the code became smaller but two things surprised me:

There's no increase in the temporary memory allocated

The variable assignment did cost nothing (not even one instruction)

The above test was done with a "clone" of TDBEdit.DataChange in a test project. To make sure there are no confounding factors i also tested with the original code to confirm the differences. Notice that in this case, although the code is also smaller, the addition of the variable increase the temporary memory allocated as well the variable assignment requires one extra instruction. Bad.

But there was one last hope: compile LCL with -O2 option (i assumed that LCL was already compiled with that optimization turned on). Seems that my assumption was wrong. The -O2 option did the trick: the same result as before.

In the next post i will play with a few more scenarios.

And remember: don't forget to put -O2 in LCL build options when doing a release, it makes difference.

Condition check versus a type map

Often, the programmer is faced with the need to translate from one type to another, e.g., given a boolean variable return a corresponding integer value. As a real world example see a piece of Lazarus code:

  if NewWordWrap then
    gtk_text_view_set_wrap_mode(AGtkTextView, GTK_WRAP_WORD)
  else
    gtk_text_view_set_wrap_mode(AGtkTextView, GTK_WRAP_NONE); 

NewWordWrap is a boolean variable, but the gtk function expects an integer. To translate from type to another a condition check is done.

Another way to handle this would be creating a map array with the type to be translated. Lazarus also has an example of this technique:

const
  WidgetDirection : array[boolean] of longint = (GTK_TEXT_DIR_LTR, GTK_TEXT_DIR_RTL);
[..]
  gtk_widget_set_direction(AGtkWidget, WidgetDirection[UseRightToLeftAlign]);

Here is the same pattern: UseRightToLeftAlign is a boolean variable and the gtk function expects a integer, but instead of checking for the variable value a boolean to integer map (WidgetDirection) is used.

While the map approach seems faster because avoids a check, it adds an additional constant. I decided to look at the generated code to see the actual benefits.

Check the condition code:

  if B then
    DoIt(CONST_1)
  else
    DoIt(CONST_2);

Map code:

const
  BoolMap: array[Boolean] of Integer = (CONST_2, CONST_1);

  DoIt(BoolMap[B])

Here is the generated code. This shows a clear advantage to the map approach. Notice that in this small example the size of executables were the same.

I also tested a more complex type than boolean: an enumerated.

Check the condition code:

  case E of
    EnumA: DoIt(CONST_1);
    EnumB: DoIt(CONST_2);
    EnumC: DoIt(CONST_3);
  end;

Map code:

const
  EnumMap: array[TMyEnum] of Integer = (CONST_1, CONST_2, CONST_3);

  DoIt(EnumMap[E])

The result.

Now with a slight optimized code for the condition check...

var
  I: Integer;

  case E of
    EnumA: I := CONST_1;
    EnumB: I := CONST_2;
    EnumC: I := CONST_3;
  end;
  DoIt(I);

... i got this.

Effect of using a constant parameter for string types

Is not rare to find implementations of procedures/functions/methods that uses a value parameter for read only string arguments. While i always use constant parameters for such cases, the real benefit of this code practice was not clear. Until today.

I made a small application that implements two versions of a procedure identical except by the type of parameter (Value vs Constant)...

program asmConstParameter;

{$Mode ObjFpc}
{$H+}

uses
  SysUtils, Types;

procedure DoIt(V: String);
begin
  Writeln(V);
end;

procedure ByValue(V: String);
var
  S: String;
begin
  S := V;
  DoIt(S);
end;

procedure ByReference(const V: String);
var
  S: String;
begin
  S := V;
  DoIt(S);
end;

var
  X: String;

begin
  X := 'Test';
  ByValue(X);
  ByReference(X);
end.

...and examined the assembler output. See the difference yourself. Using optimizations through -O compiler options does not change the produced code.

So using a constant parameter has a practical effect, is not only a good code practice.

BTW: just for curiosity i put {$IMPLICITEXCEPTIONS OFF} in the program header. Not bad. Be aware that this info is here just for curiosity ;-) .

UPDATE: Using constant arguments also benefits ShortString types. See.

Reduce memory usage of LCL

To test the conclusions of the last post i modified the field order of some LCL classes to group together Boolean fields.

Here's the return value of the InstanceSize property:

TButton
before: 874 bytes
after: 829 bytes (saved 24, 16 and 5 bytes in TControl, TWinControl and TCustomButton respectively)

TMenuItem
before: 152 bytes
after: 136 bytes

In an application with 100 controls and 20 menu items you save 2400 (considering only TControl memory) and 320 bytes respectively.

Maybe be this is negligible in computers with 1GB or more of RAM, but for mobile platforms it makes a difference.

The patch is here. Have fun!

Memory layout (and size) of a object

After reading a article about memory layout of objects in Delphi i was curious about how fpc behaves. So i did some small tests:

Memory layout of objects (instances of a class)

At offset 0 resides the virtual method table. Starting from ofsset 4 comes the fields. Just like in Delphi.

Number of associated methods

The number of associated methods and if they are virtual does not influence the object size. Just like in Delphi.

Type of the fields

According to the cited article, Delphi reserves 4 bytes for each field even if the type has a size of 1 byte. Here comes the fun.

Take the following classes:

TOneFlagClass = class
Flag1: Boolean;
end;

TTwoFlagClass = class
Flag1: Boolean;
Flag2: Boolean;
end;

The size of TOneFlagClass and TTwoFlagClass are 5 and 6 bytes respectively (4 for the vmt and 1 for each field). The memory offsets of Flag1 and Flag2 are 4 and 5.

Delphi is a bit different here. The size of both classes are 8. The memory offsets of the fields are the same as fpc.

At this time i think: "In this case is better to place less than 4 bytes fields at the end of the class declaration to avoid subsequent fields to be accessed outside the dword boundary"

I was wrong. In fact half wrong:

Take the following classes:

TFlagFirstClass = class
Flag1: Boolean;
Int1: Integer;
end;

TFlagLastClass = class
Int1: Integer;
Flag1: Boolean;
end;

The size of TFlagFirstClass and TFlagLastClass are 12 and 9 respectively. The compiler allocates 4 bytes for the boolean field to maintain subsequent fields (that has a size of 4 bytes) aligned with the dword boundary.

If another boolean field (Flag2) is added just after Flag1, the instance size is not affected. In fact, grouping 4 boolean (or another 1 byte type) fields together will lead to the same instance size as only one boolean field if those are succeeded by Integer or Pointer like types.

In the end, my suggestion is still valid: put the "less than 4 bytes field types" at the end of the field declaration of the class (or group together in groups with 4 bytes in total). You will save some memory.

If you are not convinced compare size of a class with the following fields sequence:
Boolean, Integer, Boolean, Integer, Boolean, Integer, Boolean, Integer
Boolean, Boolean, Boolean, Boolean, Integer, Integer, Integer, Integer
Integer, Integer, Integer, Integer, Boolean, Boolean, Boolean, Boolean

Some notes:

• Object here is not referenced as the object type (that has the same memory layout of a record), but as the instance of a class
  
• There's no difference between mode delphi and objfpc
• It's valid only for i386 architeture. No idea how this works in ppc, amd64, arm
  

Effect of buffer size in deflate and md5

I tested the effect of buffer size in compressing a file using deflate procedure (paszlib unit) and calculating the md5 (using the functions of md5 unit).

I loaded a 30MB file in memory and did the compression/md5 calculation. The buffer size varied from 1024 to 512.000.

To my surprise no significantly difference was found, so no graph this time since is almost a plain line.

Effect of buffer size for reading files [Linux]

Reading a file entirely in memory is not a good idea as stated before, but how large should be the memory buffer?

I did a test under Linux (Ubuntu 7.04) reading the fpc2.2.0 installation file (29MB) using different buffer sizes.

Here's the result:


The time to read the file decreases as the buffer size increases until the buffer is 128kb then, as the buffer gets bigger, the trend inverts.

Some notes:

• The test was executed three times for each buffer size. The results are expressed as the Median;
  
• The Y axis is the time to read all the file in microseconds. The X axis is the buffer size in bytes;
• The first time the file is read is significantly slower than subsequent reads. Probably this is an effect of the OS file system buffering (I did not find a way to skip it). This limits further analysis. However, excluding the first run, all other results are consistent across the same buffer size. All results can be browsed here.
  

Update: Using Valgrind/massif with fpc

In a previous post i claimed that the option to hide memory allocation wrappers in massif was broken or not working with fpc.

The problem is that i was using only the pascal name of the function (CMEM_CGETMEM) instead of the mangled internal name (CMEM_CGETMEM$LONGINT$$POINTER).

Thanks to Michalis Kamburelis that gave the hint and also provided this script:

#!/bin/sh
set -eu

valgrind --tool=massif \
--alloc-fn='CMEM_CGETMEM$LONGINT$$POINTER' \
--alloc-fn='CMEM_CREALLOCMEM$POINTER$LONGINT$$POINTER' \
--alloc-fn='SYSTEM_GETMEM$LONGINT$$POINTER' \
--alloc-fn='SYSTEM_GETMEM$POINTER$LONGINT' \
--alloc-fn='SYSTEM_REALLOCMEM$POINTER$LONGINT$$POINTER' \
--format=html \
"$@"

I updated the previous charts so they show where in pascal code the memory is allocated.

PS: it's annoying that the function names are truncated in the charts.

Zlibar memory behavior compressing many small files

The previous analysis of zlibar memory behavior was done taking as example the compression of one big file. Let's with many small files (all *.pas files under lazarus/lcl dir).

Original (load the entire file in memory):
The heaptrc dump:
18573 memory blocks allocated : 496119560/496173048
18573 memory blocks freed : 496119560/496173048
0 unfreed memory blocks : 0
True heap size : 4423680
True free heap : 4423680


After memory optimization (load file in small buffer):
The heaptrc dump:
17446 memory blocks allocated : 439659064/439708048
17446 memory blocks freed : 439659064/439708048
0 unfreed memory blocks : 0
True heap size : 2326528
True free heap : 2326528



We can take some conclusions:

• The memory usage is almost equal over time (the graph scale does not help much here)
  UPDATE: the heaptrc dump shows that the original code really takes more memory.
  
• In the optimized build the memory is allocated in a continuous fashion, always growing. The original build the memory is allocated and freed all over time while still growing in the end. This can lead to more memory fragmentation.
  
• In the optimized build there's not the final peak. This is not really expected since the section of code responsible by the peak was not changed. Some options: 1) the peak exists but valgrind does not detect 2) a bug in the optimized code 3) an unexpected (and good) side effect

Reduce zlibar memory usage - step1

Previously we learned that zlibar uses 1.5MB of memory to compress a 1.1MB file. It compress each file in three passes: 1) loads all the file into memory 2) feed the deflate function with this data using a small buffer as a bridge 3) calculate the md5 signature transversing the file data again.

The option is to compress using only one pass: load the file data incrementally into a memory buffer and than feed deflate and md5 functions with it. It has two advantages: the memory usage (in this step) is constrained by the size of the buffer and you save the memory copy from the stream (that holds the file data) to the deflate buffer and to md5 buffer.

The modified InternalCompressStream function would be something like:

MD5Init(Context);
z.next_in := @input_buffer;
z.avail_in := FileRead(InStream, input_buffer, MAX_IN_BUF_SIZE);
MD5Update(Context, input_buffer, z.avail_in);
while z.avail_in > 0 do
begin
repeat
z.next_out := @output_buffer;
z.avail_out := MAX_OUT_BUF_SIZE;
err := deflate(z, Z_NO_FLUSH);
OutStream.Write(output_buffer, MAX_OUT_BUF_SIZE - z.avail_out);
until Z.avail_out > 0;
z.next_in := @input_buffer;
z.avail_in := FileRead(InStream, input_buffer, MAX_IN_BUF_SIZE);
MD5Update(Context, input_buffer, z.avail_in);
end;
MD5Final(Context, Result.Md5Sum);

Lets run valgrind/massif to see what we got:

Comparing with the previous graph we notice a great memory usage reduction: from 1.5MB to 0.5MB.

The heaptrc dump:
55 memory blocks allocated : 2811961/2812056
55 memory blocks freed : 2811961/2812056
0 unfreed memory blocks : 0
True heap size : 950272
True free heap : 950272

Let's do a deeper analysis:

• The memory used by deflate functions is close to the expected 256kb.
• The pink area is the memory used by the stream that holds the compressed data. It is allocated incrementally so the ascending angle.
• There's a peak after the deflate memory is freed and just before the program finishes. This represents the copy from the compressed stream to the output stream that doubles the data in memory. More on this later.

Someone may say that load a file using a small buffer is slower than reading all data directly in memory. This is true but it would be reasonable only with small files. In a general usage packer it would be a big limitation.

Using Valgrind to profile fpc applications

Before starting to optimize is necessary to know beforehand what and where to optimize. It's here that the profiler tools plays a role. Valgrind, and its brother KCachegrind, are know unix profiler tools that makes success in the C crowd. Let's see if is useful to fpc programmers.

Zlibar is a fpc component that encapsulates the paszlib functions in a programmer friendly way. I use it in the Becape application and for sometime i have a plan to optimize it.

The heart of the component is the TZlibWriteArchive.CreateArchive method that compress the files (InputFiles) into a stream (OutputStream):

TmpStream := TMemoryStream.Create;
TmpFile := TMemoryStream.Create;
[..]
for X := 0 to fInputFiles.Count-1 do begin
[..]
TmpFile.LoadFromFile(fInputFiles.FileName[X]);
[..]
FileInfo.CompressedSize := InternalCompressStream(X, TmpFile, TmpStream); //(1)
FileInfo.Md5Sum := StreamMD5(TmpFile);
[..]
end;
WriteHeader(AHeader);
OutStream.CopyFrom(TmpStream, TmpStream.Size);//(2)
[..]

It creates two temporary memory streams (TmpFile and TmpStream). TmpFile will hold the uncompressed data of the file being added. TmpStream will be filled with the compressed data in step (1). The process continues until all files are compressed in the TmpStream.
After that the header is written in the OutputStream and then the compressed data is written in the OutputStream.

The problems:

1. The file is stored entirely in memory before is processed. For small files is fine but for larger files it would be problems.
2. Even for small files the memory of TmpFile will be reallocated in most of the LoadFromFile calls
3. After step (2), you will have three streams in the heap: an uncompressed file, the compressed data of all files and a header + the compressed data of all files

To see this in action i created a small application that just compress only file (the VirtualTrees.pas with 1.1MB), and compiled with -gv (Generate code for Valgrind) and -gl. Run with valgrind(callgrind):

valgrind --tool=callgrind ./zlibar_opt

It was created a file with the pattern callgrind.out.[pid] that i loaded in KCacheGrind. In this tool is possible to see most of the function calls the application did, the times that each function were called, who called who, and the time each function spent.
To my surprise the memory allocation routines does not spent much time (in fact was zero). The most expensive was, of course, the compression related functions.

Now let's use the massif tool:

valgrind --tool=massif ./zlibar_opt

It creates two files: massif.[pid].ps and massif.[pid].txt. The txt file contains info about the callstack and how much memory each function allocated. The ps file contains a graphic showing the functions that were responsible for most memory allocation and the evolution in time. See below:


Now you say "what hell is this"?
To work with valgrind the -gv option forces the use of the cmem memory manager which is a wrapper around malloc, so massif understand the cmem* functions as the programmers allocation routines. I tried to use the fn-alloc option to force the display of the pascal functions without success.
Update: i was passing only the pascal name function (CMEM_GETMEM) to fn-alloc while is necessary also the parameter list names. I updated the charts to show where in pascal the memory is allocated.

Anyway in the graphic we can see that 1.5MB of heap memory is allocated (used?*) at its peak and that is the point where we can optimize.

Here's the heaptrc dump:
58 memory blocks allocated : 3926105/3926208
58 memory blocks freed : 3926105/3926208
0 unfreed memory blocks : 0
True heap size : 950272
True free heap : 950272

In the next articles, i will take a look in the possible optimizations.

Notes:

• * The fpc heap manager pre allocates space in the heap that sometimes is not all used but i dont know if this is still valid when using the cmem functions
  
• The -gv option is necessary to run the massif tool but is dispensable when using the callgrind
• The valgrind checkmem tool is of little utility to fpc since it provides the heaptrc unit with a lot of advantages
• One drawback of valgrind is that is exclusive to unix. No windows.
• For more info see the valgrind manual