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.

Review: Performance Anti-Patterns

Being a performance engineer, I always appreciate when others give solid guidance for how to write performant code.  One such work is Performance Anti-Patterns.  While you can read this article, there are a couple of things I'll reiterate here.

First, performance should be part of the entire development process.  Trying to optimize code at the end of the cycle limits the options that are available.  Conversely, adding micro-optimizations early is potentially wasteful as future development may negate the effect.

Second, benchmarks are key to proper measurement of performance. Establish what are the important scenarios for the application.  And the metrics of interest for the benchmark.  Is the goal to increase throughput?  Or perhaps cycles per request?  Power consumption at a given load?  Without a specific measurement of performance, a benchmark just serves as an application that is run regularly.

This also defines the common case.  Take a storage driver and three operations: read, write, and recovery.  In all likelihood, the read and write operations occur far more often than recovery.  If a disk fails, does it matter if the user is notified 10ms versus 20ms after the event?  Does it matter if a read takes 10ms versus 20ms?  Spend the effort on optimizations like-wise.

Third, think parallel.  This requirement is beginning to sink in; however, just being multi-threaded is not enough.  How many threads?  One per task, CPU?  Is the data properly partitioned?  A scientific application will operate very different from a web server.

Finally, there is a cost and trade-off to performance.  Reliability and security are obviously paramount.  But also the readability of the code and future extensions to the application.  Taking these elements into account can distinguish performant code from truly elegant implementations.

Object-Oriented C (part 3)

In this exciting conclusion to the object-oriented C programming series, I will discuss a couple of drawbacks to my prior solution, as well as compare my implementation to those provided by OO compilers.

Drawback #1: Branch Prediction
It is important to remember that a branch is any instruction that changes the instruction pointer, which includes function calls.  Most functional calls are straightforward; however, some branches use a register (i.e., runtime value) for their destination, most commonly with function pointers and switch statements.  Ray tracers may already use oct-trees to reduce the set of intersection objects.  Further sorting a set of objects into their different types would present an easier to predict sequence of indirect function calls.

Drawback #2: Inheritance is Explicit
All of the OO inheritance is up to the programmer.  There is no assistance from the compiler to ensure that classes inherit correctly, nor for "constructors" or protection of fields.  This forces the programmer(s) to be quite disciplined in their usage.  Under particular circumstances, I'd not worry about this, but in general I would want the compiler to keep an eye on the usage of this model.

To reprise, for someone who has limited experience with C++ and its notation (like I did at the time), using the limited OO capabilities provided by this solution proved ideal.

All of this work hinged on an important "law of programming": If a compiler / run-time can do something implicitly, the programmer can do so explicitly.  (See More Rules).  Because a compiler for C++ is generating machine code to support OO, there must be a way to write code to give an equivalent compilation in C.  So then what does the C++ compiler generate?  (As someone who has not written a compiler and is not disassembling C++ programs, the following will remain speculation, though clarifying comments are appreciated).

I can conceive of three ways for a compiler to store an object's functional information:
1) Type field.  The type of an instance is always clearly known, but types must be globally unique.  Any code wishing to perform operations needs multiple levels of indirection to get from a "type" to the appropriate function.  Bleh.
2) Direct inlined fields.  This is effectively the solution in C.
3) Indirect fields.  Keep a single table of function pointers for this type in memory.  While this saves the memory for a couple of function pointers, there is an additional layer of indirection that must be traversed on every function call.

My remaining question is: "how does a compiler / run-time address 'diamond' inheritance"?  That is, classes that inherit from multiple distinct classes.

Problem Solving via Programming Languages

As an interlude to the OO series, I want to clarify something about language preference.

BASIC, C, C++, C#, IA64, Java, Lisp, MIPS, ML / OCAML, Perl, Python, and X86 / X64 -- I've written executable code in them all (some far more than others).  While C dominates my coding experience, and is my general preference, I recognize that sometimes another language provides better support.  Usually, this support is primarily a reduction in development time, but I'd like to delve a little deeper into why I choose three particular languages: C, C#, and Perl.

C -- "Machine independent assembly"
When I chose to write C code, I'm often thinking of precisely how a computer will execute the high-level solution that I've sketched.  Usually, given a problem, I am decomposing it into executable bits, like looping through a list, building a tree just-so, etc.  I know what I want, and if I'm wrong then its my foot that I'm shooting.

C# -- "Rapid application development"
I'm only beginning to use C# regularly, but I'm finding it very useful for achieving simple tasks, particularly those that require a UI.  .NET is providing an extensive collection of support libraries, so that loading graphics, interacting with them, etc is mostly a matter of connecting the pieces together.  To me C# is called for when my problem is UI-centric: click the button and an image appears....

Perl -- "Text, files and strings"
My Perl use has been declining over the years, not for a dislike of the language, but rather a shortage of problems that call for its use.  Perl is my tool of choice when I need to work with lots of text and files.  I've used it to write everything from copy files between directions and rename to parse MBs of raw data and compute statistics for particular results of interest.  (The later eventually was rewritten in C for speed and portability).

I'm always thinking that one of these days I'll try learning more about a functional language.  However, I quickly fall into the trap of thinking procedurally.  "I know you're on an x86, so just let me write my assembly and we can be done."

Object-Oriented C (part 2)

In part 1, I outlined the problem with writing a ray tracer in C, particularly how to opaque the presence of different objects.  Since my roommate was a TA, he and I discussed some of the crude ways he feared that he would have to grade.  For example, the intersect calls might be based on switch ... case or an if ... else chain, as follows:

switch (object->type)

{

    case TRIANGLE: ...

    case SPHERE: ...

...

}

While it clearly handles the different object types, it sets up regular patterns of duplicated code.  Once for intersection, then for finding a color, etc.  Each pattern also has to be modified if a new scene object is introduced.  But I wanted something better, particularly I wanted to show that carrying a type field is unnecessary for my design.  I concluded that I could have my scene objects carry their function pointers.  (Note, the following code is still pseudo in nature and is provided for illustration and not compilation purposes).

typedef struct _SCENE_OBJECT {

    float (*Intersect) (pSCENE_OBJECT, Vec3);

    void (*Color) (pSCENE_OBJECT, Vec3 ...);

    pSCENE_OBJECT next;

} SCENE_OBJECT, *pSCENE_OBJECT;

Then I declare my sphere scene object (and similarly for other scene objects), as follows:

typedef struct _SCENE_OBJECT_SPHERE {

    SCENE_OBJECT generic;

    ....

} SCENE_OBJECT_SPHERE, *pSCENE_OBJECT_SPHERE;

Now, my scene object types have inherited from the base object.  Therefore, the intersection loop from part one now has a single line intersection call:

dist = object->Intersect(object, ray);

This approach still has drawbacks, but it achieves a simple inheritance between structs in C, thereby providing a rudimentary OO capability to a language known for not having one.  In part 3, I look forward to exploring some of the drawbacks, as well as the elusive discussion of how OO intrinsically works in C++ or other languages.

Object-Oriented C (part 1)

For most programmers, the very idea of writing object-oriented (OO) C code seems wrong on several levels.  First, there are several, quite usable, programming languages that already support OO designs, so why mess with adding something to C that is as core to a language as OO?  Second, how would someone do this anyway?

Disclaimer: I am not recommending that OO programming be generally accomplished in C, but rather am writing to argue how some OO constructs can be integrated into a program to improve its design / readability (i.e., elegance).

Many years ago when I was an undergraduate in Computer Science, one assigned project was to write a ray tracer.  The provided framework was in C++, but having not studied the details of inheritance, overloading, etc, I elected to rewrite the framework in C.  Since the framework was very simple, the few classes were merely renamed to struct and member functions provided a prefix.  Yet, this is not the interesting part, merely the starting point.

In brief, ray tracers cast (i.e., test for intersection) a ray (i.e., vector) against the scene (i.e., a list of objects).  The object that is first intersected provides the color for that part of the image.  Different objects will have different intersection tests / other properties.  In pseudo-C, the code for intersection might read:

object = objectList->head;

minDist = INF;  minObject = NULL;

while (object != NULL) {

    dist = Intersect(object, ray);

    if (dist < minDist) {... }

    object = object->next;

}

The fundamental design problem is therefore how to properly set up the objects so that the ray tracer's operations upon its scene objects are still elegant.  How to accomplish this will be discussed in part 2, along with how OO intrinsically works.

Elegance in Coding

To start this blog, I thought I'd quote the first paragraph from my statement of purpose, which I wrote as part of applying for grad school.

Elegance is when an object achieves its telos, designed end, well and simply. For software to achieve elegance, it must be performant as well as satisfying other fundamental requirements like security and reliability. This refined software does not waste its resources: CPU cycles, memory, and device accesses. Instead it makes efficient use of what it requires. Reaching software elegance is often limited by the experiences of developers; important developments require looking beyond the standard realms for which applications are designed, whether the realms consist of workloads or hardware configurations or even the problems being solved.  Academic research provides one setting for the long term investigations required for exploring potential solutions of the next realms of software.

Writing software is not just a logical act of solving a given problem.  Often though it is viewed this way, even by me.  Yet there are days when I see my code as a creative art.  One that isn't about solving the problem, but rather doing so well.  Because in being written well, the source code can be called beautiful.  You may wish to share the code with others, to take it before the class, before the team and let us all admire the work.  Admire its elegance and simplicity.

Yet this art of computer science is not a matter of font selection, or pleasing quantities of white space.  Rather, we see that the problem is solved with efficiency at run time and without defect.  Still, this code has style too.  That it is consistent in using spacing.  The variables are named meaningfully.  Comments are useful.

So I'll be writing sometimes about elegance in programming, more commonly from the negative direction.  But most posts will be about ordinary problems in writing software or brainstorming designs or so many of the other tasks that a computer scientist faces.