To research the unknown

As part of my duties as a graduate student, I presented some of my research on Friday.  Beyond the presentation itself, which went well, an intriguing question arose: "If something is so difficult / expensive to implement that no one has written the code, then how do you know what it is?"  Indeed.  This is an honest criticism, how am I going to explore performance improvements to particular problems when the problems are so computationally expensive that they aren't implemented in existing applications.

Fortunately for my research, the scope of computationally expensive is still well within the feasible realm.  Furthermore, many of these expensive problems are already known, and are not so far removed from the current applications as to be independent.  So in the end, perhaps it isn't a horrible road block, but rather just one more piece to *research.*

For bonus points, the discussion portion of my presentation ran about the same length as my presentation itself.  And spawned further emails in the subsequent days.  So I'm delighted by how thought provoking (or perhaps contentious) my research is proving to be.

A Pointer on Pointers Part 1

People often express uncertainty about the working of pointers, structures, etc.  They may not be my readers, but hearing their plight moves me to write nonetheless.  Others have noticed this too, again looking at StackOverflow.  Everything in this post is written from a C-centric point of view, unless otherwise noted.

There are two separate items to understand about pointers.  First, where they come from.  And second, what they point to.  We will roughly be working off of the following picture of memory usage, but understand that this is so simplified that it is almost wrong.

Memory can be allocated from two places: stack and heap.  Both are generalizations of the actual mechanics.  Stack allocations are explicitly named variables in the source that are either made globally or local to a function.  Global variables use space delineated in the binary image, rather than the stack pages, but they should be considered identically by a programmer in that the allocations are only good within their scope.  This leads to my first example:

struct foo* newFoo()

{

    struct foo F;

    return &F;

}

Managed language programmers often attempt the above example.  newFoo() creates a foo and returns a reference; however, the referenced foo is on the stack.  In case there is uncertainty, let's see the assembly for function newFoo():

; Using 32bit x86 assembly, as 64bit has calling convention differences

  push    ebp

  mov     ebp, esp

  sub     esp, 0x10  ; Allocate 16 bytes for a "foo"

  mov     eax, esp   ; Put the address into the return value

  mov     esp, ebp   ; Cleanup

  pop     ebp

  ret

Esp points to the end of the stack, so the subtract instruction changes the location pointed to, thereby setting aside the required space for an object foo on the stack, but the space is only available while in the function.  When the cleanup section is reached, the space is "reclaimed" as esp is changed back.  (The funny thing is, an optimizing compiler may inline newFoo() and therefore change the scope of this stack allocation).  So to make an allocation persist beyond its allocation scope, we need the "heap".

Heap memory is memory that won't be reclaimed until the program explicitly requests (or termination).  While malloc() is the most common method for heap allocations, it is not the only one.  From these methods, a section of memory has been set aside for the program's usage.  To again simplify our picture of computing, a Java implementation of newFoo would disassemble to something like the following:

  push    ebp

  mov     ebp, esp
  sub     esp, 0x4     ; Space for arguments

  mov     [esp], 0x10  ; "Push argument"

  call    malloc

  mov     esp, ebp     ; Cleanup

  pop     ebp

  ret

A language like Java might prohibit making an allocation of an object foo on the stack and therefore force the allocation to made from the heap.  And it does so by not using "sub esp, 0x10" to make the allocation but instead calling out to malloc() to set aside the necessary space.  Now, out of this function, the address returned is not reclaimed.

An entire series of courses would be required to fully explain the trade-offs and reasoning, and since the length is growing long, I will conclude here and discuss the usage of this memory in a later post.

Accessing Structs with Side Effects

In my recent research, I've needed to take certain additional actions when the fields in a data structure are changed.  Since all code involved is my own, my initial approach was to annotate any access with explicit calls.  Obviously, this isn't sustainable in larger projects, but for quick prototyping, it is sufficient.  Let's see a simple example (with pseudo-C as usual):

typedef struct _tree {

    pTree left, right;

    int data;

} Tree, *pTree;

Tree t;

t.left = t.right = NULL;

// Now take action

Since we want to ensure that we take action after every update, get / set routines could be introduced for each field.  Yet, now I have the overhead of calling these routines on every access.  And I still have to trust that all accesses will use the routines (though using another language like C++, I could make the fields private and force access to the routines).

My research is currently using C#, so I have further tools available to me, specifically accessors.  Initially, they seemed to be yet another silly hoop to jump through while writing code.  However, they provide a great tool for my present problem, where modifications to fields need to incur side effects.  Now for a C# snippet:

private Node pLeft;  // Internal storage

public Node left     // Public accessor
{
    get { return pLeft;}
    set
    {
        if (pLeft == value) return;  // discard redundant stores
        pLeft = value;
        pStack.Push(this); // side effect on update

    }

}

So my data structure now has implicit side effects from updates (good for the research).  And so any future development doesn't need explicit annotations.  All in all, I was quite pleased with this change (except for spending the time debugging the differences between implicit and explicit detection).

Book Review: Beautiful Code

I came across the book, Beautiful Code: Leading Programmers Explain How They Think (Theory in Practice (O'Reilly)), several months ago and was immediately intrigued.  Could this be a book to do so much of what I want to achieve here?  In short, no.  The editors want us to read thirty or so examples and learn something about what makes code beautiful.  In principle, I can agree with this thesis, as I have learned a lot about writing better code from reading what others have programmed.

The book provides 33 chapters, the shortest is 6 pages and the longest is over 30.  And the quality is inversely proportional to the length.  The shorter contributions are far more likely to achieve their goal of demonstrating beauty in programs, as their programs are more self evidently beautiful.  Short contributions just need fewer pages for their beauty.  Thus in reading 550 pages, one will find long sections of slow development to reach an uncertain conclusion as to the quality of a contributor's code, punctuated by shorter gems of programming.

To compound the difficulties in reading, I have yet to discern the method to the organization of the chapters.  Programmers use a wide variety of languages and the book is no different.  For example, the chapters using Fortran were skipped due in part from my lack of knowledge of the language.  Yet the final chapter used Lisp and was rather interesting, even though I have virtually no experience with it either.  But that chapter succeeds because the point is not based in the language, and changing its examples to pseudo-code would be just as workable.

To conclude, the premise is still valid.  And so I will remain hopeful for a future rewrite that discards about 20 chapters and provides some degree of transition between each.  Perhaps even confining the languages down to a handful, but just deciding this might be intractable.

Is elegance pretty?

Through the course of my work and reading, I encountered a write-up about what makes code "pretty" with   reasonable suggestions for establishing and maintaining a code style.  The essential objective is to make the code readable by others.  As I work with undergrads, they are not always thrilled about the effort required for "pretty" code, yet they can accept that I have to read and understand their program.  Yet this barely compares to the effort required in a commercial context, where the code may have a multi-year lifetime and pass through many programmers.

Is pretty code elegant?  No, although the reverse is true (and thus the title).  Elegant code has an aesthetic aspect that can be termed pretty, yet it must also be more than aesthetic.  My continuing proposal of elegant is code that must also be efficient, extensible, reliable, etc.  Basically, to be elegant, code must leave the objectors behind.  Instead, you want to show others your elegant code.

So go and write pretty code.

Stack Overflow: String Replace

I've recently begun exploring Stack Overflow.  Helping to answer people's questions has a considerable appeal to one, such as I, who enjoys teaching.  Sometimes you can find a question that no one has answered, as few know the answer.  Other times, almost any professional programmer can answer the question, and often these are from CS students trying to solve their homework.  On occasion, I may repost interesting questions here.

For my first repost, we have a StringReplace function that needs optimizing.  Independent of the questioner's implementation, let's consider the core algorithm.

StringReplace(OldText, NewText, BaseString)

    for SubString of length OldText in BaseString

        if (OldText == SubString) {Replace text}

This is how we want to replace.  Find each instance of OldText in BaseString and replace.  Given the nature of the question, our implementation will be written in C and not use any libraries (like regex, CRT, etc).

Working backwards, we'll need to return a final string of some indeterminate size.  Then the BaseString, as it is modified, is stored in this final string, in the following form, where each base is a subset of the string:

When the problem is viewed this way, an implementation is suggested, recursive.  The following code expands upon this approach (though avoiding some casting requirements, necessities of sizeof(char), and possibility of unicode support).

#define StringReplace(x, y, z) StringReplaceHelper(x, y, z, 0)

char* StringReplaceHelper(char* OldText, 

                          char* NewText, 

                          char* BaseString,

                          unsigned long space)

{

    char* start = BaseString, ret = NULL;

    unsigned long offset = 0;

    while (*BaseString != '\0')

    {

        if (Match(OldText, BaseString))

        {

             offset = (BaseString - start);

             // The next search will begin after 

             // the replacement text

             ret = StringReplaceHelper(OldText, NewText,

                                 BaseString + strlen(OldText), 

                                 space + offset + strlen(NewText));

             break;

        }

        BaseString++;

    }

    // If the end of string, then this is the last piece

    // Else copy in subset and replacement piece

    if (*BaseString == '\0')

    {

        offset = (BaseString - start);

        ret = (char*) malloc((space + offset));

        memcpy(ret + space, start, offset));

    }

    else

    {

        memcpy(ret + space, start, offset);

        // Don't actually do the following, the processor

        // will have to walk NewText twice

        memcpy(ret + offset, NewText, strlen(NewText));

    }

    return ret;

}

First, the routine Match() is basically a string compare, which can have its own interesting optimizations including partial skip-ahead.  Second, a final version wouldn't use strlen, except perhaps at the start.  The lengths can be passed between iterations.  Finally, using memcpy and malloc aren't cheating as I've written my own implementations in the past, and therefore their omission in the present is just for the sake of brevity.

But this is just what I'd currently write for a string replace.  You can follow the link to Stack Overflow and see the original request (and my suggestion for improvement).  Or perhaps consider your own.

Elegance in Function

A friend shared today a post about an elegant worm, Stuxnet.  While I am not a security researcher and cannot comment on the claims of elegance, I can delight to hear that others are evaluating their fields with aesthetics in mind.  If the thought of an elegant virus bothers you, consider that I would also claim that there are beautiful swords and firearms.

The post begins: "Brilliance and elegance are powerful adjectives most often used to describe things of beauty -- people, places, and things.  Works of art whether they are literary or visual; aural or editable often bear these designations but it is rare indeed when we see them used to describe malicious code & content..."

Edit: Since this post, I've been seeing many other places Stuxnet has been mentioned, including the NYTimes.