Disclaimer

The content of this blog is my personal opinion only. Although I am an employee - currently of Nvidia, in the past of other companies such as Iagination Technologies, MIPS, Intellectual Ventures, Intel, AMD, Motorola, and Gould - I reveal this only so that the reader may account for any possible bias I may have towards my employer's products. The statements I make here in no way represent my employer's position, nor am I authorized to speak on behalf of my employer. In fact, this posting may not even represent my personal opinion, since occasionally I play devil's advocate.

See http://docs.google.com/View?id=dcxddbtr_23cg5thdfj for photo credits.

Thursday, March 22, 2012

Expressing fetch-old-and-do-new in a High Level Language

Quite often I find myself wanting to test the old value of some variable, using that to go into an IF, while then or soon thereafter setting a new value.
For example:

  our $titles_already_printed;
  sub print_titles {
     if( ! $titles_already_printed ) {
         print "TITLES...";
     }
     $titles_already_printed = 1;
  }

This doesn't look so bad if it is a simple variable:

  our $f;
  sub print_titles {
     if( ! $f ) {
         print "TITLES...";
     }
     $f = 1;
  }

But it can be painful if the flag variable iws accessed via a long and complicated path:

  our %titles_already_printed;
  sub print_titles {
     my $titles = shift;
     if( ! $titles_already_printed{$titles} ) {
         print "TITLES...";
     }
     $$titles_already_printed{$titles} = 1;
  }

And there can be more than one way of expessuing it:

  our %titles_already_printed;
  sub print_titles {
     my $titles = shift;
     if( $titles_already_printed{$titles} ) {
         return;
     }
     print "TITLES...";
     $$titles_already_printed{$titles} = 1;
  }
The return form is convenient for functions - but only if it is correct to return. I have seen quite a few bugs caused by such returns, when there is later code (perhaps added later) that should not be skipped by the return. The first form is convenient for straight line code, not wrapped in a function. It is annoying that refactoring code from straight line to function may sometimes require changing its control flow structure. Here are some other forms: First, separating the flag manipulation from the action:
  our %titles_already_printed;
  sub print_titles {
     my $titles = shift;

     my $old_resukt = exists $titles_already_printed{$titles};
     $titles_already_printed{$titles} = 1;
 
    if( $old_result ) {
         return;
     }
     print "TITLES...";
  }
You can probably see where I am going. Would it not be nice to not have the repetition? Something like
  our %titles_already_printed;
  sub print_titles {
     my $titles = shift;

     my $old_result = 
        lambda_define_and_invoke_here( NAME = $titles_already_printed{$titles} ) {
            return_value = exists name;
            NAME = 1;
        }
 
    if( $old_result ) {
         return;
     }
     print "TITLES...";
  }
Purely syntactic sugar, but...
  • lambda_define_and_invoke_here defines a lambda function, a code block, in part to get parameterization so a shiort NAME can be used. It is defined and used immediatekly, so that we don't have to repeat ourselves by defining it associated with a name, and then immediately invoking that lambda name.
  • Something like Jensen's device, name substitution, is used for NAME. In this example because $titles_already_printed{$titles} doesn't exist at the time of invocation. If that weren't an issue, a non-Jensen's device lvalue could be used. Extend that to a special lvalue for $titles_already_printed{$titles}, that creates $titles_already_printed{$titles} if it doesn't already exist and is later assigned to. An "potential lvalue for an ordinary lvalue that may not exist yet".
  • return_value used so that we don't have to obscure things by creating a tmp for the old value.
This is purely syntactic sugar, but... I see this code a lot. But it is often slightly different. The purpose of an HLL is to make expresion easier and less error prone. Note: I am NOT talking about fetch-and-op or compare-and-swap for purposes of parallel programing synchronization - although obviously related. And, bonus if idioms expressed this way could be automatically translated to hardware atomic RMWs.

No comments: