Compiler memory barriers

I've written in the past about memory barriers. Basically a membar instruction ensures that other processors see memory operations in the order that they appear in the source code. The obvious example being a mutex lock where you want the memory operations that occurred while the lock was held to be visible to other processors before the memory operation that releases the lock.

There's actually another kind of memory ordering and that is the ordering used by the compiler. If you write:

  *a=1;
  *b=2;

If the compiler can determine that a and b do no alias, then there's no reason for it not to swap the stores to a and b if it thinks that will be a more optimal code pattern.

The most cross-platform way of enforcing this ordering is to put a function call between the two stores:

  *a=1;
  reorder_barrier();
  *b=2;

Memory needs to be the program defined state at the call, so the compiler cannot defer the store to a, and cannot hoist the store to b.

This is a great solution, but causes the overhead of a function call, and function calls can have significant costs. There are some compiler intrinsics that cause the compiler to enforce the desired memory ordering. Sun Studio 12 Update 1 supports the GCC flavour:

  *a=1;
  asm volatile ("":::"memory");
  *b=2;

You can test the performance overhead using the following code:

void barrier(){}

void main()
{
  for (int i=0; i<1000000000;i++)
  {
    barrier();
  }
} 

On the test system this code took about 5 seconds to run. The alternative code is:

void main()
{
  for (int i=0; i<1000000000;i++)
  {
    asm volatile ("":::"memory");
  }
}

This code took under a second.

I'm presenting at the Silicon Valley OpenSolaris Users Group on Thursday evening. I was only asked today, so I'm putting together some slides this evening on "Multicore Application Programming". The talk is going to be a relatively high level presentation on writing parallel applications, and how the advent of multicore or CMT processors changes the dynamics.

x86 performance tuning documents

Interesting set of x86 performance tuning documents.

Bitten by inlining (again)

So this relatively straight-forward looking code fails to compile without optimisation:

#include <stdio.h>

inline void f1()
{
  printf("In f1\n");
}

inline void f2()
{
  printf("In f2\n");
  f1();
}

void main()
{
  printf("In main\n");
  f2();
}

Here's the linker error when compiled without optimisation:

% cc inline.c
Undefined                       first referenced
 symbol                             in file
f2                                  inline.o
ld: fatal: Symbol referencing errors. No output written to a.out

At low optimisation levels the compiler does not inline these functions, but because they are declared as inline functions the compiler does not generate function bodies for them - hence the linker error. To make the compiler generate the function bodies it is necessary to also declare them to be extern (this places them in every compilation unit, but the linker drops the duplicates). This can either be done by declaring them to be extern inline or by adding a second prototype. Both approaches are shown below:

#include <stdio.h>

extern inline void f1()
{
  printf("In f1\n");
}

inline void f2()
{
  printf("In f2\n");
  f1();
}
extern void f2();

void main()
{
  printf("In main\n");
  f2();
}

It might be tempting to copy the entire function body into a support file:

#include <stdio.h>

void f1()
{
  printf("In duplicate f1\n");
}

void f2()
{
  printf("In duplicate f2\n");
  f1();
}

This is a bad idea, as you might gather from the deliberate difference I've made to the source code. Now you get different code depending on whether the compiler chooses to inline the functions or not. You can demonstrate this by compiling with and without optimisation, but this only forces the issue to appear. The compiler is free to choose whether to honour the inline directive or not, so the functions selected for inlining could vary from build to build. Here's a demonstration of the issue:

% cc -O inline.c inline2.c
inline.c:
inline2.c:
% ./a.out
In main
In f2
In f1

% cc inline.c inline2.c
inline.c:
inline2.c:
% ./a.out
In main
In duplicate f2
In duplicate f1

Douglas Walls goes into plenty of detail on the situation with inlining on his blog.

A very British computer

Couple more articles from the BBC, the Manchester Baby, and EDSAC at Cambridge.

I find it appropriate that one of the first commercial computers was used for ordering supplies for tea shops.

Little book of semaphores

Interesting read that demonstrates that there's much more to semaphores than might be expected.

BBC articles on British computer pioneers

The BBC are running a week-long series of articles on the history of British computing. The first is on GCHQ, the second is on Colossus at Bletchley.

Although the articles are interesting, I'm slightly dubious about some of the claims "It was not until the 1990s that general purpose machines could match Oedipus for searching through a database and finding a particular term, said Prof Lavington."

The article contains an interesting link map of the people involved. The link map includes the NPL Ace Pilot. The NPL is the National Physical Laboratory, and I was driven past on my way to school every day. Back then it looked like a science laboratory covered in odd shaped objects and brick buildings. Unfortunately the photos on the history page fail to capture this ramshackle nature.